PARSSSE: AN ADAPTIVE PARALLEL STATE SPACE SEARCH ENGINE
Abstract
State space search problems abound in the artificial intelligence, planning and optimization literature. Solving such problems is generally NP-hard, so that a brute-force approach to state space search must be employed. Given the exponential amount of work that state space search problems entail, it is desirable to solve them on large parallel machines with significant computational power. In this paper, we analyze the parallel performance of several classes of state space search applications. In particular, we focus on the issues of grain size, the prioritized execution of tasks and the balancing of load among processors in the system. We demonstrate the corresponding techniques that are used to scale such applications to large scale. Moreover, we tackle the problem of programmer productivity by incorporating these techniques into a general search engine framework designed to solve a broad class of state space search problems. We demonstrate the efficiency and scalability of our design using three example applications, and present scaling results up to 32,768 processors.
References
Robert D. Blumofe , Cilk: An Efficient Multithreaded Runtime System, Proc. 5th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP'95 (MIT, Santa Barbara, California, 1995) pp. 207–216. Google Scholar- Journal of Parallel and Distributed Computing 37(1), 55 (1996). Crossref, ISI, Google Scholar
- Journal of the ACM 32(3), 505 (1985). Crossref, ISI, Google Scholar
James Dinan , Scalable work stealing, SC '09: Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis (ACM, New York, NY, USA, 2009) pp. 1–11. Google ScholarRainer Feldmann , Peter Mysliwiete and Burkhard Monien , Studying overheads in massively parallel min/max-tree evaluation, SPAA '94: Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures (ACM, New York, NY, USA, 1994) pp. 94–103. Google ScholarM. Furuichi , K. Taki and N. Ichiyoshi , A multi-level load balancing scheme for or-parallel exhaustive search programs on the multi-psi, Second ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (1990) pp. 50–59. Google Scholar- IEEE Transactions on Knowledge and Data Engineering 11(1), 28 (1999). Crossref, ISI, Google Scholar
- ACM Transactions on Programming Languages and Systems 23(4), 472 (2001). Crossref, ISI, Google Scholar
L. V. Kalé , Comparing the performance of two dynamic load distribution methods, Proceedings of the 1988 International Conference on Parallel Processing (St. Charles, IL, 1988) pp. 8–11. Google Scholar- , Advanced Computational Infrastructures for Parallel and Distributed Applications, ed.
M. Parashar (Wiley-Interscience, 2009) pp. 265–282. Crossref, Google Scholar - Journal of Logic Programming 11(1), 55 (1991). Crossref, Google Scholar
L. V. Kalé and S. Krishnan , CHARM++: A Portable Concurrent Object Oriented System Based on C++, Proceedings of OOPSLA'93, ed.A. Paepcke (ACM Press, 1993) pp. 91–108. Google Scholar- , Lecture Notes in Computer Science 748, eds.
T. Ito and R. Halstead (Springer-Verlag, 1993) pp. 12–41. Google Scholar - Internaltional Journal of Parallel Programming 19(4), 251 (1990). Crossref, ISI, Google Scholar
- J. ACM 40(3), 765 (1993). Crossref, ISI, Google Scholar
- Commun. ACM 27, 594 (1984). Crossref, ISI, Google Scholar
- IEEE Transactions on Computing 35(6), 568 (1986). ISI, Google Scholar
- J. Log. Program 10(1/2/3&4), 155 (1991). Crossref, ISI, Google Scholar
- Operations Research 11(6), 972 (1963). Crossref, ISI, Google Scholar
-
Hans-Wolfgang Loidl and Kevin Hammond , On the granularity of divide-and-conquer parallelism , Proceedings of the Glasgow Workshop on Functional Programming . Google Scholar - IEEE Software 9, 77 (1992). Crossref, ISI, Google Scholar
Stephen Olivier , Lecture Notes in Computer Sciences 4382 (Springer-Verlag, 2007) pp. 235–250. Google ScholarV. Nageshwara Rao and Vipin Kumar , Superlinear speedup in parallel state-space search, Proceedings of the Eighth Conference on Foundations of Software Technology and Theoretical Computer Science (Springer-Verlag, London, UK, 1988) pp. 161–174. Google ScholarV. Nageshwara Rao , Vipin Kumar and K. Ramesh , A parallel implementation of Iterative-Deepening-A*, AAAI (1987) pp. 178–182. Google ScholarV. Saletore and L. V. Kale , Consistent linear speedups for a first solution in parallel state-space search, Proceedings of the AAAI (1990) pp. 227–233. Google ScholarW. W. Shu and L. V. Kalé , A dynamic load balancing strategy for the Chare Kernel system, Proceedings of Supercomputing '89 (1989) pp. 389–398. Google ScholarA. Sinha and L. V. Kalé , A load balancing strategy for prioritized execution of tasks, Seventh International Parallel Processing Symposium (Newport Beach, CA, 1993) pp. 230–237. Google Scholar


