AI Search, especially Branch-and-Bound type searches:

Combinatorial search in parallel naturally involves the simultaneous expansion of different portions of a search space. Much of the work within PPL on this problem has made use of prioritization of messages to control how portions of a search space are selected for expansion. Since many search problems involve heuristics on the likelihood of a solution being reached in a particular branch, Charm++/Converse's prioritization of messages provide a natural, low-level way of specifying these algorithmic ideas, and handling the prioritized scheduling of such subtasks implicitly. Have a look at Prioritization in Parallel Symbolic Computing for the details.

 

• 11-05    Yanhua Sun, Gengbin Zheng, Pritish Jetley and Laxmikant V. Kale,  An Adaptive Framework for Large-scale State Space Search,  Proceedings of Workshop on Large-Scale Parallel Processing (LSPP) in IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2011
• 03-09    Jonathan A. Booth,  Balancing Priorities and Load for State Space Search On Large Parallel Machines,  M.S. Thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, August 2003.
• 95-05    L. V. Kale and B. H. Richards and T. D. Allen,  Efficient Parallel Graph Coloring with Prioritization,   Lecture Notes in Computer Science, vol 1068, August 1995, pp 190-208. Springer-Verlag.
• 93-16    L.V. Kale,  Prioritization in Parallel Computing (extended abstract),  US/Japan Workshop on Parallel Symbolic Computing, October 1992, Boston, MA. [Internal Report #93-16]
• 93-13    Amitabh B. Sinha and Laxmikant V. Kale,  A Load Balancing Strategy For Prioritized Execution of Tasks,  International Symposium on Parallel Processing, Newport Beach, CA, April 1993.
• 93-06    L.V. Kale, B. Ramkumar, V. Saletore, and A.B. Sinha,  Prioritization in Parallel Symbolic Computing,  Lecture Notes in Computer Science, Vol. 748, pp. 12-41, 1993. [Internal Report #93-6]
• 93-05    Thorr Tjorvi Einarsson,  Bidirectional Search in Parallel,  June 1993, MS thesis. [Internal Report #93-5]
• 92-05    Amitabh B. Sinha and Laxmikant V. Kale,  A Load Balancing Strategy For Prioritized Execution of Tasks,  Workshop on Dynamic Object Placement and Load Balancing, in co-operation with ECOOP's 92, April 1992. Utrecht, The Netherlands.
• 90-02    V. Saletore and L.V. Kale,  Consistent Linear Speedups for a First Solution in Parallel State-Space Search,  Proceedings of the AAAI, August 1990.
• 90-10    Vikram Saletore,  Machine Independent Parallel Execution of Speculative Computations,  Doctoral Thesis. Dept. of Computer Science, University of Illinois. 1990.