A Framework for Scalable Parallel Tree Search
IBM T.J. Watson Research Center
CORS/INFORMS Joint Int’l Meeting, Banff, Alberta, Canada, Sunday, May 16, 2004
• Overview of parallel tree search
– Tree search
– Knowledge sharing
• The Abstract Library for Parallel Search (ALPS)
– Design overview
– Class hierarchy
– Knapsack solver
– Generic MIP solver
• Future work
• Tree search algorithms systematically search the nodes of a directed,
acyclic graph for one or more goal nodes.
• Generally, the graph is not known a priori, but is constructed as the
• A generic tree search algorithm consists of the following elements:
– Processing method: Is goal achieved?
– Search strategy: What is node priority?
– Fathoming rule: Can node can be fathomed?
– Branching method: What are the successors?
• Each node has an associated description and a status.
– candidate: Ready to be processed.
– active: Currently being processed.
– processed: Successors generated (not a leaf node).
– fathomed: No successors generated (a leaf node).
• The algorithm consists of choosing a candidate node, processing it, and
either fathoming or branching.
Parallelizing Tree Search
• Tree search is a “divide and conquer” approach, so it is conceptually
easy to parallelize.
• As the number of processors is increased, it becomes increasingly difficult
to manage the solution process.
• Scalability measures how well a parallel system takes advantage of
increased computing resources.
Sequential runtime Ts
Tp when using p processes
To = pTp − Ts
S = Ts/Tp
E = S/p
• Good scalability is the goal of any parallel algorithm.
• Achieving it involves a number of tradeoffs.
Knowledge Generation and Sharing
• Knowledge is information generated during the course of the search that