Name
Abstract | ||
|---|---|---|
Backtracking algorithms are used to methodically and exhaustively search a solution space for an optimal solution to a given problem. A classic example of a backtracking algorithm is illustrated by finding all solutions to the problem of placing N-queens on an N × N chess board such that no two queens attack each other. This paper demonstrates a methodology for rewriting this backtracking algorithm to take advantage of multi-core computing resources. We accelerated a sequential version of the N-queens problem on ×86 and PPC64 architectures. Using problem sizes between 13 and 17, we observed an average speedup of 3.24 for ×86 and 9.24 for the PPC64. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/SACI.2011.5873061 | SACI |
Keywords | Field | DocType |
application program interfaces,tree searching,multi-core computing resources,multiprocessing systems,openmp,backtracking algorithms,n-queens problem,n queens problem,acceleration,force | Computer science,Parallel computing,Dancing Links,Beam stack search,Rewriting,Eight queens puzzle,Acceleration,Backtracking,Speedup | Conference |
ISBN | Citations | PageRank |
978-1-4244-9108-7 | 0 | 0.34 |
References | Authors | |
7 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| A. Ayala | 1 | 0 | 0.34 |
| H. Osman | 2 | 0 | 0.34 |
| Daniel Shapiro | 3 | 8 | 1.95 |
| John-Marc Desmarais | 4 | 2 | 0.75 |
| Jonathan Parri | 5 | 22 | 3.00 |
| Miodrag Bolic | 6 | 503 | 58.17 |
| Voicu Groza | 7 | 127 | 27.41 |