Abstract
Distributed and parallel computation is, on the one hand, the cheapest way to increaseraw computing power. Turning parallelism into a useful tool for solving new problems, onthe other hand, presents formidable challenges to computer science. We believe that parallelcomputation will spread among general users mostly through the ready availability of convenientand powerful program libraries. In contrast to general‐purpose languages, a programlibrary is specialized towards a well‐defined class of problems and algorithms. This narrowfocus permits developers to optimize algorithms, once and for all, for parallel computers ofa variety of common architectures. This paper presents ZRAM, a portable parallel library ofexhaustive search algorithms, as a case study that proves the feasibility of achieving simultaneouslythe goals of portability, efficiency, and convenience of use. Examples of massivecomputations successfully performed with the help of ZRAM illustrate its capabilities anduse.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
K. Appell and W. Haken, The solution of the four-color-map problem, Sci. American (Oct. 1977)108-121.
D. Avis and K. Fukuda, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discrete Computational Geometry 8(1992)295-313.
D. Avis and K. Fukuda, Reverse search for enumeration, Discrete Applied Mathematics 65(1996)21-46.
M. Benaïchouche, V. Cung, S. Dowaji, B. Le Cun, T. Mautor and C. Roucairol, Building a parallel branch and bound library, in: Solving Combinatorial Optimization Problems in Parallel, LNCS 1054, eds. A. Ferreira and P. Pardalos, Springer, Berlin, 1996, pp. 201-231.
A. Brüngger, A parallel best-first branch and bound algorithm for the traveling salesperson problem, in: Proceedings of the 9th International Parallel Processing Symposium, Workshop on Solving Irregular Problems on Distributed Memory Machines, ed. S. Ranka, 1995, pp. 98-106.
A. Brüngger, Solving hard combinatorial optimization problems in parallel: Two case studies, Ph.D. Thesis, ETH Zürich, 1997.
G. Ceder, G.D. Garbulsky, D. Avis and K. Fukuda, Ground states of a ternary fcc lattice model with nearest-and next-nearest-neighbor interactions, Physical Review B49(1994)1-7.
R. Corrêa and A. Ferreira, Parallel best-first branch-and-bound in discrete optimization: A framework, in: Solving Combinatorial Optimization Problems in Parallel, LNCS 1054, eds. A. Ferreira and P. Pardalos, Springer, Berlin, 1996, pp. 171-200.
H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer, 1987.
R. Finkel and U. Manber, DIB — a distributed implementation of backtracking, ACM Transactions on Programming Languages and Systems 9(1987)235-256.
K. Fukuda and A. Prodon, Double description method revisited, to appear in: Lecture Notes in Computer Science, Springer. PS file available from ifor13.ethz.ch (129.132.154.13), directory/pub/fukuda/reports.
R. Gasser, Harnessing computational resources for efficient exhaustive search, Ph.D. Thesis, ETH Zürich, 1995.
A. Geist, A. Beguelin, J. Dongarra, W. Jiang, B. Manchek and V. Sunderam, PVM: Parallel Virtual Machine — A User's Guide and Tutorial for Networked Parallel Computing, MIT Press, 1994.
B. Gendron and T.G. Crainic, Parallel branch-and-bound algorithms. Survey and synthesis, Operations Research 42(1994)1042-1066.
W. Gropp, E. Lusk and A. Skjellum, Using MPI: Portable Parallel Programming with the Message-Passing Interface, MIT Press, 1994.
D.E. Knuth, Estimating the efficiency of backtrack programs, Math. Comp. 29(1975)121-136.
C.H. Koelbel, D.B. Loveman, R.S. Schreiber, G.L. Stelle, Jr. and M.E. Zosel, The High Performance Fortran Handbook, MIT Press, 1994.
R.E. Korf, Depth-first iterative deepening: An optimal admissible tree search, Artificial Intelligence 62(1993)97-109.
N. Kuck, M. Middendorf and H. Schmeck, Generic branch-and-bound on a network of transputers, in: Transputer Applications and Systems '93, eds. R. Grebe et al., IOS Press, Amsterdam, 1993, pp. 521-535.
A. Marzetta, ZRAM: A library of parallel search algorithms and its use in enumeration and combinatorial optimization, Ph.D. Thesis, ETH Zürich, 1998. http://www.inf.ethz.ch/publications/diss.html.
F. Mattern, Experience with a new distributed termination detection algorithm, in: Distributed Algorithms 1987, LNCS 312, Springer, 1987, pp. 127-143.
G.P. McKeown, V.J. Rayward-Smith and H.J. Turpin, Branch-and-bound as a higher-order function, Annals of Operations Research 33(1991)379-402.
J. Nievergelt, R. Gasser, F. Mäser and C. Wirth, All the needles in a haystack: Can exhaustive search overcome combinatorial chaos?, Invited paper in Lecture Notes in Computer Science 1000, Computer Science Today, ed. J. van Leeuwen, Springer, 1995, pp. 254-274.
D. Ratner and M. Warmuth, Finding a shortest solution for the (N × N)-extension of the 15-puzzle is intractable, Journal of Symbolic Computation 10(1990)111-137.
A. Reinefeld and T.A. Marsland, Enhanced iterative-deepening search, Reihe Informatik 120, Paderborn Center for Parallel Computing, 1993.
L.B. Stiller, Exploiting symmetry on parallel architectures, Ph.D. Thesis, The Johns Hopkins University, 1995.
K. Thompson, Chess endgames, vol. 1, ICCA Journal 14(1991)22.
K. Thompson, Chess endgames, vol. 2, ICCA Journal 15(1992)149.
S. Tschöke and T. Polzer, Portable parallel branch-and-bound library: User manual, Technical Report, University of Paderborn, 1995.
Rights and permissions
About this article
Cite this article
Brüngger, A., Marzetta, A., Fukuda, K. et al. The parallel search bench ZRAM and its applications. Annals of Operations Research 90, 45–63 (1999). https://doi.org/10.1023/A:1018972901171
Issue Date:
DOI: https://doi.org/10.1023/A:1018972901171