World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

PARSSSE: AN ADAPTIVE PARALLEL STATE SPACE SEARCH ENGINE

    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. Blumofeet al., 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
    • Robert D. Blumofeet al., Journal of Parallel and Distributed Computing 37(1), 55 (1996). Crossref, ISIGoogle Scholar
    • Rina Dechter and Judea Pearl, Journal of the ACM 32(3), 505 (1985). Crossref, ISIGoogle Scholar
    • James Dinanet al., 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 Scholar
    • Rainer 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 Scholar
    • M. 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
    • Ananth Grama and Vipin Kumar, IEEE Transactions on Knowledge and Data Engineering 11(1), 28 (1999). Crossref, ISIGoogle Scholar
    • Gopal Guptaet al., ACM Transactions on Programming Languages and Systems 23(4), 472 (2001). Crossref, ISIGoogle 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
    • Laxmikant V. Kale and Gengbin Zheng, Advanced Computational Infrastructures for Parallel and Distributed Applications, ed. M. Parashar (Wiley-Interscience, 2009) pp. 265–282. CrossrefGoogle Scholar
    • L. V. Kalé, Journal of Logic Programming 11(1), 55 (1991). CrossrefGoogle 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
    • L. V. Kaleet al., Lecture Notes in Computer Science 748, eds. T. Ito and R. Halstead (Springer-Verlag, 1993) pp. 12–41. Google Scholar
    • L. V. Kalé and V. Saletore, Internaltional Journal of Parallel Programming 19(4), 251 (1990). Crossref, ISIGoogle Scholar
    • Richard M. Karp and Yanjun Zhang, J. ACM 40(3), 765 (1993). Crossref, ISIGoogle Scholar
    • Ten-Hwang Lai and Sartaj Sahni, Commun. ACM 27, 594 (1984). Crossref, ISIGoogle Scholar
    • Guo-Jie Li and Benjamin W. Wah, IEEE Transactions on Computing 35(6), 568 (1986). ISIGoogle Scholar
    • Yow-Jian Lin and Vipin Kumar, J. Log. Program 10(1/2/3&4), 155 (1991). Crossref, ISIGoogle Scholar
    • John D. C. Littleet al., Operations Research 11(6), 972 (1963). Crossref, ISIGoogle 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
    • Peter C. Nelson and Anestis A. Toptsis, IEEE Software 9, 77 (1992). Crossref, ISIGoogle Scholar
    • Stephen Olivieret al., Lecture Notes in Computer Sciences 4382 (Springer-Verlag, 2007) pp. 235–250. Google Scholar
    • V. 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 Scholar
    • V. Nageshwara Rao, Vipin Kumar and K. Ramesh, A parallel implementation of Iterative-Deepening-A*, AAAI (1987) pp. 178–182. Google Scholar
    • V. 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 Scholar
    • W. 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 Scholar
    • A. 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