Performance Characterization of Shared- and
Distributed-Memory Multiprocessors on a Tree Search Problem
Makoto Ando, Yoshio Tanaka, Kazuto Kubota, Motohiko Matsuda,
Yutaka Akiyama, Mitsuhisa Sato
In this paper, we measure and compare the performance of shared- and
distributed-memory multiprocessors using a parallel tree search
problem to characterize these types of multiprocessors. We take the
knapsack problem using the branch-and-bound algorithm as our workload.
It is difficult to compare the performance using irregular parallel
problems such as tree search problems because the parallelism and the
shape of the search space depend on input data set. The performance is
affected by the input data set as well as programming and cost for
managing shared data in the parallel programs. We define some types
of input data set with different characteristics in search space to
evaluate the performance. Shared-memory multiprocessors achieve good
performance when unnecessary branches can be pruned effectively and
the shape of the search tree is narrow, because data used in pruning
branches are easily shared among all the processors in the
shared-memory space. For exhaustive search problems where branches
can not be pruned easily, distributed-memory multiprocessors achieve
good performance because they do not have to communicate frequently.
Our experimental results may give a hint for selecting suitable
configurations of multiprocessors and designing an appropriate
algorithm for irregular search problems.