Live Webcast 15th Annual Charm++ Workshop

Many problems in Artificial Intelligence involve traversing large search-spaces. Such problems typically have irregular structures that can be readily exploited for parallel execution. A class of such problems has multiple solutions where any one solution is acceptable. Parallel execution of such computations leads to speculative computations. We investigate schemes for parallel execution of such speculative computations to obtain consistent and good linear speedups to a first solution that increase monotonically with the addition of processors. The memory usage of these search techniques does not increase proportionately with the increase in the number of processors. A parallel execution scheme for speculative computations in pure state-space search that associates bit-vector priorities with computations is described. The bit- vector priorities ensure that the resources are focused towards the first solution. A technique called delayed-release is developed which ensures that the memory usage of parallel execution schemes is reduced and does not increase with the addition of processors.

A technique employing bit-vector priorities to reduce the time to the first solution in parallel execution of AND/OR speculative computations is presented. The scheme is further developed to obtain consistent and linear speedups to the first solution in these computations. We also investigate the problem of queue contention in large shared-memory machines. A technique to address this has been developed using dense graphs for processor-memory interconnection that has better scalability and performance. Priority balancing strategies in conjunction with load balancing strategies are also developed for large shared-memory and nonshared-memory multiprocessors to ensure that the processing effort is focused towards the first solution.

A machine independent parallel software package called SearchPack has been developed which embodies these ideas. SearchPack can be used with the Chare-Kernel II, the run time support system for machine independent parallel programming to run search algorithms across multiprocessors without change. Performance studies have been conducted on several shared- memory and nonshared-memory machines such as the Sequent Symmetry, Alliant FX/8, Encore Multimax, and Intel iPSC/2 Hypercube.