c# - Parallel BFS rush hour solver -

so, uni have assignment have make serial implementation of rush hour solver parallel. solver uses bfs implementation.

here part of default bfs implementation:

// initialize empty queue         queue<tuple<byte[], solution>> q = new queue<tuple<byte[], solution>>();          // default, solution "no solution"         foundsolution = new nosolution();          // place starting position in queue         q.enqueue(tuple.create(vehiclestartpos, (solution)new emptysolution()));         addnode(vehiclestartpos);          // bfs         while (q.count > 0)         {             tuple<byte[], solution> currentstate = q.dequeue();              // generate sucessors, , push them on queue if haven't been seen before             foreach (tuple<byte[], solution> next in sucessors(currentstate))             {                 // did reach goal?                 if (next.item1[targetvehicle] == goal)                 {                     q.clear();                     foundsolution = next.item2;                     break;                 }                  // if haven't seen node before, add trie , queue expanded                 if(!addnode(next.item1))                     q.enqueue(next);             }         }          console.writeline(foundsolution);         console.readline(); 

i managed turn parallel this:

concurrentqueue<tuple<byte[], solution>> q = new concurrentqueue<tuple<byte[], solution>>();      foundsolution = new nosolution();      q.enqueue(tuple.create(vehiclestartpos, (solution)new emptysolution()));     addnode(vehiclestartpos);      while (q.count > 0 && !solutionfound)     {         tuple<byte[], solution> currentstate;         q.trydequeue(out currentstate);          parallel.foreach(sucessors(currentstate), (next) =>         {             // did reach goal?             if (next.item1[targetvehicle] == goal)             {                 solutionfound = true;                 foundsolution = next.item2;                 return;             }              // if haven't seen node before, add trie , queue expanded             if (!addnode(next.item1))                 q.enqueue(next);         });     } 

as can see, tried implement parallel foreach loop concurrentqueue. feeling concurrentqueue works well, locks automatically , costs time, making parallel implementation way slower serial one.

i thinking having wait-free or @ least lock-free queue, can save bit of time, not sure how implement such thing. guys give insight whether feasable , whether faster using regular queue ? or maybe use different concurrent data structure better suit situation. not sure how concurrentbag , fit in. shed light on ?

also, after having searched parallel bfs implementations, couldn't find any. general tips , hints people me wanting implement bfs in parallel ? alternatives queue, make thread-safe ?

edit1: managed implement tasks this:

int tasknumbers = environment.processorcount;     task[] tasks = new task[tasknumbers];      // set cancellation token     ctsource = new cancellationtokensource();      (int = 0; < tasknumbers; i++)         tasks[i] = new task(() =>         {             try{    traverse(); }             catch{ }         },          ctsource.token);      (int = 0; < tasknumbers; i++)         tasks[i].start();      task.waitall(tasks);      ctsource.dispose(); 

they call traverse method, looks this:

 private static void traverse() {     ctsource.token.throwifcancellationrequested();      while (q.count > 0)     {         tuple<byte[], solution> currentstate;          if (q.trydequeue(out currentstate))         {             foreach (tuple<byte[], solution> next in sucessors(currentstate))             {                 // did reach goal?                 if (next.item1[targetvehicle] == goal)                 {                     ctsource.cancel();                     foundsolution = next.item2;                     return;                 }                  // if haven't seen node before, add trie , queue expanded                 if (!addnode(next.item1))                     q.enqueue(next);             }         }          if (ctsource.iscancellationrequested)             ctsource.token.throwifcancellationrequested();     } } 

yet, having trouble figuring out condition while loop in traverse method. current condition allows tasks exit loop early. far know, dont have complete list of nodes available, cant compare visited tree list of nodes. besides that, don't have other ideas of how can keep tasks looping through while loop until have found answer or until there no more new nodes. guys me out ?

thnx @brian malehorn far, managed performance of parallel bfs version equal performance of serial version. need make tasks stay in while loop think.

the problem isn't queue, problem you're parallelizing wrong thing. you're parallelizing adding successors queue, when should parallelizing sucessors() call.

that is, sucessors() should called worker thread, never in "main" thread.

for example, suppose sucessors() takes 1 second run, , you're searching tree:

                           o                           / \                          /   \                         o     o                        / \   / \                       o   o o   o 

the fastest can search tree 3 seconds. how long code take?