A New Framework for Scalable Parallel Tree
Ted Ralphs and Yan Xu
Industrial and Systems Engineering
IBM T.J. Watson Research Center
International Symposium on Mathematical Programming, TU Denmark, Monday, August 18, 2003
Outline of Talk
– Parallel computing concepts
– Tree search
– Knowledge sharing
• New framework
– Abstract Library for Parallel Search (ALPS)
– Branch, Constrain, and Price Software (BiCePS)
Motivation and Objectives
• Tree search algorithms are widely used in the areas such as Mathematical
Programming, Artificial Intelligence, Theorem Proving, etc.
• These areas are rich with difficult, but important problems.
• Numerous specialized frameworks and solvers already exist.
• Why another one?
• Our goal is a framework that
– operates effectively in both sequential and parallel environments;
– is general enough for a wide range of settings, but has the tools needed
for specific applications;
– provides scalability for applications with highly dynamic and irregular
search trees; and
– provides the functionality needed for management of large amounts of
dynamically generated data.
Parallel Systems and Scalability
• Parallel System: Parallel algorithm + parallel architecture.
• Scalability: How well a parallel system takes advantage of increased
Sequential runtime Ts
To = NTp − Ts
S = Ts/Tp
E = S/N
• The key to scalability is reducing parallel overhead.
• Contributors to parallel overhead
– Communication Overhead
– Idle Time due to
∗ Task Starvation
∗ Ramp Up/Down
– Performance of Redundant Work
• Redundant work is work that would not have been performed in the
Tree Search Algorithms
• The search space consists of a global set of states.
• The solut