Unstructured tree search on SIMD parallel computers
IEEE Transactions on Parallel and Distributed SystemsPublished 1 January 1994
George Karypis, Vipin Kumar
Citations42
SJR quartileQ1
SJR score2.10
SNIP2.28
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
The analysis and experiments show that the new load balancing methods presented are highly scalable on SIMD architectures, and their scalability is shown to be no worse than that of the best load balancing schemes on MIMD architectures.
Abstract
We present new methods for load balancing of unstructured tree computations on large-scale SIMD machines, and analyze the scalability of these and other existing schemes. An efficient formulation of tree search on an SIMD machine consists of two major components: a triggering mechanism, which determines when the search space redistribution must occur to balance the search space over processors, and a scheme to redistribute the search space. We have devised a new redistribution mechanism and a new triggering mechanism. Either of these can be used in conjunction with triggering and redistribution mechanisms developed by other researchers. We analyze the scalability of these mechanisms and verify the results experimentally. The analysis and experiments show that our new load-balancing methods are highly scalable on SIMD architectures. Their scalability is shown to he no worse than that of the best load-balancing schemes on MIMD architectures. We verify our theoretical results by implementing the 15-puzzle problem on a CM-2 SIMD parallel computer.>
Keywords
Computer Science
American Mathematical MonthlyCombinatorial Optimization: Algorithms and Complexity.
6,028 Citations1984David Johnson, Christos H. Papadimitriou +1 more
Principles of Artificial Intelligence
3,336 Citations1982Nils J. Nilsson
This classic introduction to artificial intelligence describes fundamental AI ideas that underlie applications such as natural language processing, automatic programming, robotics, machine vision, automatic theorem proving, and intelligent data retrieval.
Scientific AmericanThe Connection Machine
1,614 Citations1987W. Daniel Hillis
The Connection Machine describes a fundamentally different kind of computer that Daniel Hillis and others are now developing to perform tasks that no conventional, sequential machine can solve in a reasonable time.
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.
Information Processing & ManagementHeuristics: Intelligent search strategies for computer problem solving.
1,431 Citations1985
This book presents, characterizes and analyzes problem solving strategies that are guided by heuristic information and provides examples of how these strategies have changed over time.
Communications of the ACMReevaluating Amdahl's law
1,399 Citations1988John L. Gustafson
Dans cet article, il est question de l'importance, pour la communaute scientifique informatique, de venir a bout du «blocage mental» contre le parallelisme massif impose par une mauvaise utilisation de la formule de Amdahl.
Fundamentals of Computer Algorithms
1,391 Citations1983Ellis Horowitz, Sartaj Sahni
Benjamin-Cummings Publishing Co., Inc. eBooksIntroduction to parallel computing: design and analysis of algorithms
1,221 Citations1994Vipin Kumar, Ananth Grama +2 more
European Journal of Operational ResearchHeuristics: Intelligent search strategies for computer problem solving
812 Citations1985Heiner Müller-Merbach
SIAM Journal on Scientific and Statistical ComputingDevelopment of Parallel Methods for a $1024$-Processor Hypercube
422 Citations1988John L. Gustafson, G.R. Montry +1 more
The scaled-problem paradigm better reveals the capabilities of large ensembles, and permits detection of subtle hardware-induced load imbalances that may become increasingly important as parallel processors increase in node count.
Journal of Parallel and Distributed ComputingScalable Load Balancing Techniques for Parallel Computers
211 Citations1994Vipin Kumar, Ananth Grama +1 more
This paper analyses the scalability of a number of load balancing algorithms which can be applied to problems that have the following characteristics: the work done by a processor can be partitioned into independent work pieces; the work pieces are of highly variable sizes; and it is not possible to estimate the size of total work at a given processor.
Journal of Parallel and Distributed ComputingAnalyzing Scalability of Parallel Algorithms and Architectures
207 Citations1994V. Kumar, Aman Gupta
The objectives of this paper are to critically assess the state of the art in the theory of scalability analysis, and to motivate further research on the development of new and more comprehensive analytical tools to study the scalability of parallel algorithms and architectures.
ACM SIGART BulletinReview of "Principles of Artificial Intelligence by Nils J. Nilsson", Tioga Publishing Company, Palo Alto, CA, ISBN 0-935382-01-1.
202 Citations1980Keith Price
Nils Nilsson's new book on AI is now available from Tioga Publishing Company, P.O. Box 98, Palo Alto, CA 94302; (415) 854--2445.
International Journal of Parallel ProgrammingParallel depth first search. Part II. Analysis
172 Citations1987Vipin Kumar, V. Nageshwara Rao
A work-distribution algorithm is presented that guarantees close to optimal performance on a shared-memory/ω-network-with-message-combining architecture (e.g. RP3) and is applicable to other parallel algorithms in which work is dynamically shared between different processors.
International Journal of Parallel ProgrammingParallel depth first search. Part I. Implementation
168 Citations1987V. Nageshwara Rao, Vipin Kumar
A parallel formulation of depth-first search which retains the storage efficiency of sequential depth- first search and can be mapped on to anyMIMD architecture is presented and results show that hypercube and sharedmemory architectures are significantly better.
Search in Artificial Intelligence
140 Citations1988Leveen Kanal, Vipin Kumar
This book brings together some new insights and recent developments on the topics of search procedures in Artificial Intelligence and the relationships among search methods in Artificial intelligence, Operations Research, and Engineering in a manner accessible to students and professionals in Computer Science, Engineering, Operations research, and Applied Mathematics.
IEEE Transactions on Parallel and Distributed SystemsThe scalability of FFT on parallel computers
134 Citations1993Anshul Gupta, Vipin Kumar
The authors present the scalability analysis of a parallel fast Fourier transform (FFT) algorithm on mesh and hypercube connected multicomputers using the isoefficiency metric and show that it is more cost-effective to implement the FFT algorithm on a hypercube rather than a mesh.
IEEE Transactions on Parallel and Distributed SystemsOn the efficiency of parallel backtracking
96 Citations1993V. Nageshwara Rao, Vipin Kumar
Experimental results for many synthetic and practical problems run on various parallel machines that validate the theoretical analysis are presented, and it is shown that the average speedup obtained is linear when the distribution of solutions is uniform and superlinear when the distributed distribution is nonuniform.
ComputerMultiprocessing of Combinatorial Search Problems
92 Citations1985Wah, Guojie Li +1 more
This chapter presents three paradigms of representations for combinatorial search problems, and develops theoretical bounds, efficient algorithms, and functional requirements of multiprocessing architectures for supporting efficient evaluation of combinatorially search problems.
CERN Document Server (European Organization for Nuclear Research)Hypercube Algorithms: with Applications to Image Processing and Pattern Recognition
90 Citations1990Sanjay Ranka, Sartaj Sahni
Most of the algorithms in this book are for hypercubes with the number of processors being a function of problems size, however, for image processing problems, the book also includes algorithms for and MIMD hypercube with a small number of processes.
IEEE Transactions on ComputersMANIP—A Multicomputer Architecture for Solving Combinatonal Extremum-Search Problems
85 Citations1984Wah, Ma
This paper proposes and analyze the design of MANIP, a parallel machine for processing nondeterministic polynomial (NP)-hard problems, and proposes a system with distributed intelligence so that sorting can be carried out efticiently.
Optimal speedup for backtrack search on a butterfly network
76 Citations1991Abhiram Ranade
IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsA parallel branch and bound algorithm for test generation
76 Citations1990S. Patil, P. Banerjee
Journal of Parallel and Distributed ComputingScalability of parallel algorithms for the all-pairs shortest-path problem
71 Citations1991Vipin Kumar, Vineet Singh
This paper uses the isoefficiency metric to analyze the scalability of several parallel algorithms for finding shortest paths between all pairs of nodes in a densely connected graph and demonstrates that isoe efficiency functions are a compact and useful predictor of performance.
A dynamic scheduling strategy for the Chare-Kernel system
55 Citations1989Wei Shu, Laxmikant V. Kalé
The experimental results show that ACWN algorithm achieves better performance in most cases than randomized allocation, and its agility in spreading the work helps it outperform the gradient model in performance and scalability.
A multi-level load balancing scheme for OR-parallel exhaustive search programs on the multi-PSI
50 Citations1990Masakazu Furuichi, K. Taki +1 more
This work has developed a dynamic load balancing scheme which is applicable to OR-parallel programs in general and scalable to any number of processors because of this multi-level hierarchical structure.
National Conference on Artificial IntelligenceDistributed tree search and its application to alpha-beta pruning
44 Citations1988Chris Ferguson, Richard E. Korf
Implementing the managed protocol had an impact on the improvement of sepsis treatment quality indicators and reduced the hospitalization period and decreased mortality.
On the scalability of FFT on parallel computers
37 Citations2002Aman Gupta, Vipin Kumar
The scalability analysis shows that the FFT algorithm cannot make efficient use of large-scale mesh architectures and the addition of such features as cut-through routing and multicasting does not improve the overall scalability on this architecture.
Artificial IntelligenceA SIMD approach to parallel heuristic search
36 Citations1993Ambuj Mahanti, Charles J. Daniels
It is shown (as shown previously only for MIMD machines) that for admissible search, high average speedup can be obtained for problems of significant size and will enhance AI problem solving using parallel heuristic search algorithms.
Reevaluating Amdahl's law
31 Citations1995John L. Gustafson
PRA*: a memory-limited heuristic search procedure for the Connection Machine
30 Citations2002Matthew P. Evett, James Hendler +2 more
A variant of A* search designed to run on the massively parallel SIMD (single-instruction-stream, multiple-data-steam) Connection Machine is described, which takes maximum advantage of the SIMD design of the Connection Machine and is guaranteed to return an optimal path when an admissible heuristic is used.
Scalability of parallel sorting on mesh multicomputers
27 Citations2002Vineet Singh, Vipin Kumar +2 more
The paper presents two new parallel algorithms QSP1 and QSP2 based on sequential quicksort for sorting data on a mesh multicomputer, and analyzes their scalability using the isoefficiency metric and presents a different variant of Lang's sort which is asymptotically as scalable as QSP 2 (for the multiple-element-per-processor case).
A General Branch-and-Bound Formulation for AND/OR Graph and Game Tree Search
26 Citations1988Vipin Kumar, Dana Nau +1 more
The procedure searches an AND/OR graph in a top-down manner and can be viewed as a general branch-and-bound procedure, applicable to a very large class of problems, and thus provides a way of synthesizing algorithms for new applications.
National Conference on Artificial IntelligenceConsistent linear speedups to a first solution in parallel state-space search
20 Citations1990Vikram A. Saletore, Laxmikant V. Kalé
This work presents prioritizing strategies which yield consistent linear speedups and requires substantially smaller memory over other methods and the performance of these strategies is demonstrated on a multiprocessor.
Efficient parallel algorithms for search problems: applications in VLSI CAD
19 Citations2002Sunil Arvindam, Vipin Kumar +1 more
Experimental results are presented to demonstrate that it is possible to speed up search-based algorithms by several orders of magnitude.
Proceedings of the International Conference on Parallel ProcessingScalability of Parallel Algorithms for the All-Pairs Shortest Path Problem: A Summary of Results.
19 Citations1990Vipin Kumar, Vineet Kumar Singh
The reduced need for preparation and the strengthening effect on the remaining tooth were the principal reasons for the shift from dental amalgam to adhesive dentistry with resin composite at Nijmegen dental school.
The Journal of SupercomputingHypercube computing: Connected components
18 Citations1989Jinwoon Woo, Sartaj Sahni
Several approaches to finding the connected components of a graph on a hypercube multicomputer on an NCUBE hypercube are proposed and analyzed and experimental results support the analysis.
Parallel ComputingAutomatic test pattern generation on parallel processors
16 Citations1991Sunil Arvindam, Vipin Kumar +2 more
Experimental validation of most of the theoretical results builds confidence in the following theoretical prediction: the parallel formulation of PODEM is highly scalable on a variety of commercially-available, large MIMD parallel processors (in additions to the ones with which the authors experimented).
Lecture notes in computer scienceParallel processing of combinatorial search trees
15 Citations1987Burkhard Monien, Oliver Vornberger
The design and analysis of multiprocessor systems used to solve combinatorial optimization problems from the area of operations research and artificial intelligence are reported on.
Conference on High Performance Computing (Supercomputing)Unstructured tree search on SIMD parallel computers: a summary of results
15 Citations1992George Karypis, Vipin Kumar
The Journal of SupercomputingComputing biconnected components on a hypercube
11 Citations1991Jinwoon Woo, Sartaj Sahni
Two hypercube algorithms to find the biconnected components of a dense connected undirected graph are described, one is a modified version of the Tarjan-Vishkin algorithm and the other is an adaptation of Read's sequential algorithm.
Unstructured tree search on SIMD parallel computers: a summary of results
10 Citations2003George Karypis, Vipin Kumar
The analysis and experiments show that the novel load balancing methods are highly scalable on SIMD architectures and their scalability is shown to be no worse than that of the best load balancing schemes on MIMD (multiple-instruction multiple-data) architectures.