|
As a pedagogical exercise in parallel programming and scientific computing, we looked at the problem of state space searching. We focused on the standard example problem, the 15-puzzle, and developed original C++ code which quickly and efficiently finds solutions to the puzzle on a parallel machine, using two different algorithms. In this paper, we summarize the theory behind our two parallel implementations, and analyze our results using the Jumpshot profiling package. Furthermore, we discuss the problems with our scalability and performance data, and offer some conclusions on the success of this project, as well as some ideas about directions for future research. Please see the links below to view our project summary, download our source code, view our lecture slides, etc. You may also wish to visit Professor Keyes's class website here. |
|
|
V. Cung and B. Cun. An efficient implementation of parallel a*, 1994. A. Grama, V. Kumar, and P. Pardalos. Parallel processing of discrete optimization problems. In Encyclopaedia of Microcomputers. Marcel Dekker Inc., New York, 1992. A. Y. Grama and V. Kumar. A survey of parallel search algorithms for discrete optimization problems, 1993. William Gropp, Ewing Lusk, and Anthony Skjellum. Using MPI: Portable Parallel Programming with the Message Passing Interface, 2nd edition. MIT Press, Cambridge, MA, 1999. V. Kumar, A. Grama, A. Gupta, and G. Karypis. Introduction to Parallel Computing: Design and Analysis of Algorithms, 2nd edition. Addison-Wesley, 2003. |