Design and Analysis of Parallel N-Queens on Reconfigurable 课件.ppt

Design and Analysis of Parallel N-Queens on Reconfigurable Hardware with Handel-C and MPI Vikas Aggarwal, Ian Troxel, and Alan D. George High-performance Computing and Simulation (HCS) Research Lab Department of Electrical and Computer Engineering University of Florida Gainesville, FL Outline Introduction N-Queens Solutions Backtracking Approach N-Queens Parallelization Experimental Setup Handel-C and Lessons Learned Results and Analysis Conclusions Future Work and Acknowledgements References Introduction N-Queens dates back to the 19th century (studied by Gauss) Classical combinatorial problem, widely used as a benchmark because of its simple and regular structure Problem involves placing N queens on an N ? N chessboard such that no queen can attack any other Benchmark code versions include finding the first solution and finding all solutions Introduction Mathematically stated: Find a permutation of the BOARD() vector containing numbers 1:N, such that for any i != j Board( i ) - i != Board( j ) - j  Board( i ) + i != Board( j ) + j  4 2 5 3 1 BOARD [ ] i = 1 2 3 4 5 Q Q Q Q Q N-Queens Solutions Various approaches to the problem Brute force[2] Local search algorithms[4] Backtracking[2], [7] , [11], [12], [13] Divide and conquer approach[1] Permutation generation[2] Mathematical solutions[6] Graph theory concepts[2] Heuristics and AI[4], [14] Backtracking Approach One of the only approaches that guarantees a solution, though it can be slow Can be seen as a form of intelligent depth-first search Complexity of backtracking typically rises exponentially with problem size Good test case for performance analysis of RC systems, as the problem is complex even for small data size* Traditional processors provide a suboptimal platform for this iterative application due to serial nature of their processing pipelines Tremendous speedups achieved by adding parallelism at the logic level via RC * For an 8x8 board, 981 moves (876 tests