The parallel search bench ZRAM and its applications
Annals of Operations ResearchPublished 1 January 1999
Adrian Brüngger, Ambros Marzetta, Komei Fukuda, J. Nievergelt
Citations64
SJR quartileQ1
SJR score1.09
SNIP1.62
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper presents ZRAM, a portable parallel library of exhaustive search algorithms, as a case study that proves the feasibility of achieving simultaneously the goals of portability, efficiency, and convenience of use.
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. Copyright Kluwer Academic Publishers 1999
Keywords
Computer Science
Computers & Mathematics with ApplicationsUsing MPI: Portable parallel programming with the message-passing interface
2,897 Citations1995
Thank you very much for downloading using mpi portable parallel programming with the message passing interface for reading a good book with a cup of coffee in the afternoon, instead they are facing with some malicious bugs inside their laptop.
American Mathematical MonthlyAlgorithms in Combinatorial Geometry.
1,801 Citations1989Jacob E. Goodman, Herbert Edelsbrunner
Computers in PhysicsPVM-Parallel Virtual Machine: AUsers' Guide and Tutorial for Networked Parallel Computing
1,590 Citations1995Al Geist, Adam Beguelin +7 more
The PVM system, a heterogeneous network computing trends in distributed computing PVM overview other packages, and troubleshooting: geting PVM installed getting PVM running compiling applications running applications debugging and tracing debugging the system.
Artificial IntelligenceDepth-first iterative-deepening
1,549 Citations1985Richard E. Korf
A depth·first iterative·deepening algorithm is shown to be asymptotically optimal along all three dimmsions for exponential tree searches and is the only known algorithm that is capable of finding optimal solUtions to randomly generated instances of the Fif/un Puzzle within practical resource.
Algorithms in Combinatorial Geometry
1,516 Citations1987Herbert Edelsbrunner
This book offers a modern approach to computational geo- metry, an area thatstudies the computational complexity of geometric problems with an important role in this study.
Discrete Applied MathematicsReverse search for enumeration
760 Citations1996David Avis, Komei Fukuda
This paper develops the reverse search technique in a general framework and shows its broader applications to various problems in operations research, combinatorics, and geometry, and proposes new algorithms for listing.
Computers in PhysicsThe High Performance Fortran Handbook
577 Citations1994Charles Koelbel, David B. Loveman +6 more
High Performance Fortran is a set of extensions to Fortran expressing parallel execution at a relatively high level that brings the convenience of sequential Fortran a step closer to today's complex parallel machines.
A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
477 Citations1991David Avis, Komei Fukuda
A new pivot-based algorithm which can be used with minor modification for the enumeration of the facets of the convex hull of a set of points, or for the listing of the vertices of an arrangement or of a convex polyhedron, in arbitrary dimension is presented.
Lecture notes in computer scienceDouble description method revisited
423 Citations1996Komei Fukuda, A. Prodon
This paper reinvestigate this method for enumerating all extreme rays of a general polyhedral cone in ℝd, introduces some new ideas for efficient implementations, and shows some empirical results indicating its practicality in solving highly degenerate problems.
Discrete & Computational GeometryA pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
403 Citations1992David Avis, Komei Fukuda
OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information)A User''s Guide to PVM Parallel Virtual Machine
378 Citations1991Adam Beguelin, Jack Dongarra +3 more
This report is the PVM version 2.3 users'' guide, which contains an overview of PVM and how it is installed and used.
Operations ResearchParallel Branch-and-Branch Algorithms: Survey and Synthesis
324 Citations1994Bernard Gendron, Teodor Gabriel Crainic
A new characterization of branch-and-bound algorithms is given, which consists of isolating the performed operations without specifying any particular order for their execution.
Mathematics of ComputationEstimating the efficiency of backtrack programs
255 Citations1975Donald E. Knuth
This paper presents a simple method which produces reasonable estimates for most applications, requiring only a modest amount of hand calculation, and should prove to be of considerable utility in connection with D. H. Lehmer''s branch-and-bound approach to combinatorial optimization.
Journal of Symbolic ComputationThe (n2−1)-puzzle and related relocation problems
188 Citations1990Daniel Ratner, Manfred K. Warmuth
This paper extends the 8-puzzle and the 15-p Puzzle to an nxn board and shows that finding a shortest solution for the extended puzzle is NP-hard and is thus believed to be computationally infeasible.
National Conference on Artificial IntelligenceFinding a shortest solution for the N x N extension of the 15- Puzzle is intractable
182 Citations1986Daniel Ratner, Manfred K. Warmuth
The MIT Press eBooksHigh Performance Fortran Handbook
181 Citations1993Charles Koelbel, David B. Loveman +3 more
IEEE Transactions on Pattern Analysis and Machine IntelligenceEnhanced iterative-deepening search
130 Citations1994A. Reinefeld, T.A. Marsland
The authors show that iterative-deepening searches can be greatly improved by exploiting previously gained node information, and their methods are faster and easier to implement than previous proposals.
Physical review. B, Condensed matterGround states of a ternary fcc lattice model with nearest- and next-nearest-neighbor interactions
64 Citations1994Gerbrand Ceder, G. D. Garbulsky +2 more
ICGA JournalExploiting Symmetry on Parallel Architectures
32 Citations1995Lewis Stiller
This thesis describes techniques for the design and implementation of parallel programs that solve well-structured problems with inherent symmetry, and demonstrates the reduction of such problems to generalized matrix multiplication by a group-equivariant matrix.
Lecture notes in computer scienceAll the needles in a haystack: Can exhaustive search overcome combinatorial chaos?
20 Citations1995Jürg Nievergelt, Ralph Gasser +2 more
Lecture notes in computer scienceExperience with a new distributed termination detection algorithm
17 Citations1988Friedemann Mattern
The constraint based puzzle-solving method is explained, several test cases are reported, and preliminary experimental results show that far less control messages than indicated by the worst case behavior are usually generated.
Annals of Operations ResearchBranch-and-bound as a higher-order function
15 Citations1991G. P. McKeown, V. J. Rayward‐Smith +1 more
The branch-and-bound paradigm is presented as a higher-order function and illustrated by instantiations, providing two well-known branch- and-bound algorithms for the Steiner tree problem in graphs and one for the travelling salesman problem.