Abstract | ||
---|---|---|
Maze solving has been used as an example parallel-programming problem for some years. Suggested solutions are often based on a sequential program, using work queues to allow multiple threads to explore different portions of the maze concurrently. This paper analyzes such an implementation, but also explores an alternative implementation based on strategies long used by human maze solvers. This alternative implementation outperforms the conventional approach on average, and furthermore exhibits large superlinear speedups. The paper uses insights into the cause of these superlinear speedups to derive a faster sequential algorithm, and finally considers further implications and future work. |
Year | Venue | Keywords |
---|---|---|
2012 | HotPar | future work,work queue,alternative implementation,superlinear speedup,maze concurrently,retrofitted parallelism,large superlinear speedup,suggested solution,human maze solvers,sequential algorithm,sequential program |
Field | DocType | Citations |
Computer science,Parallel computing,Queue,Thread (computing),Sequential algorithm | Conference | 0 |
PageRank | References | Authors |
0.34 | 2 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Paul E. McKenney | 1 | 279 | 30.11 |