In this paper we present a new parallel algorithm for finding the connected components of an undirected graph. On a graph with n vertices and m edges, the algorithm runs in O(log n loglog n) time using n+m processors ...
详细信息
In this paper we present a new parallel algorithm for finding the connected components of an undirected graph. On a graph with n vertices and m edges, the algorithm runs in O(log n loglog n) time using n+m processors on an EREW (exclusive-read and exclusive-write) PRAM. Prior to our work, the best known exclusive-write algorithm for this problem requires O(log1.5 n) time using n+m processors [JM91, KNP92].
In this paper we study the practical viability of the BSP model of parallel computation as proposed by Valiant. This model is intended for simulating the often considered PRAM model on more realistic parallel computer...
详细信息
ISBN:
(纸本)0897916131
In this paper we study the practical viability of the BSP model of parallel computation as proposed by Valiant. This model is intended for simulating the often considered PRAM model on more realistic parallel computers with a fixed interconnection network. One of the main attributes of the BSP model is randomized routing. From experimentation on an existing parallel architecture, analytic models are derived which characterize the efficiency of this routing scheme. This characterization leads to the identification of the bottlenecks involved in building a parallel architecture in which the BSP model can efficiently be embedded.
The symposium materials contain 54 papers. The topics covered include fast deterministic processor allocation, min-cut algorithms, random weighted Laplacians, combinatorial algorithms, dynamic point location, ray shoo...
详细信息
The symposium materials contain 54 papers. The topics covered include fast deterministic processor allocation, min-cut algorithms, random weighted Laplacians, combinatorial algorithms, dynamic point location, ray shooting, iterated nearest neighbors, repeated median line estimator, biconnected subgraphs approximation, vertex colored graphs triangulation, scapegoat trees, shortest path problem, submodular flow problems, geometric graph problems, greedy matching algorithm, physical mapping of chromosomes, non-clairvoyant scheduling, dynamic closest-pair problem, cow-path problem, parallel programs implementation, traveling salesman problem, optimistic sorting and information-theoretic complexity, unconditionally secure secret key, polynomial algorithms, and minimum-cost paths in periodic graphs.
Interval allocation has been suggested as a possible formalization for the PRAM of the (vaguely defined) processor allocation problem, which is of fundamental importance in parallel computing. The interval allocation ...
详细信息
ISBN:
(纸本)0898713137
Interval allocation has been suggested as a possible formalization for the PRAM of the (vaguely defined) processor allocation problem, which is of fundamental importance in parallel computing. The interval allocation problem is, given n nonnegative integers x1,...,xn, to allocate n nonoverlapping subarrays of sizes x1,...,xn from within a base array of O(∑j = 1nxj) cells. We show that interval allocation problems of size n can be solved in O((log log n)3) time with optimal speedup on a deterministic CRCW PRAM. In addition to a general solution to the processor allocation problem, this implies an improved deterministic algorithm for the problem of approximate summation. For both interval allocation and approximate summation, the fastest previous deterministic algorithms have running times of Θ(log n/log log n). We also describe an application to the problem of computing the connected components of an undirected graph.
We introduce a fast parallel approximation algorithm for the positive linear programming optimization problem, i.e. the special case of the linear programming optimization problem where the input constraint matrix and...
详细信息
The efficient or optimal scalable algorithms for a number of geometric problems for a machine model reflecting real parallel machines are presented. As stated, relevant parallelalgorithms must be applicable and effic...
详细信息
ISBN:
(纸本)9780897915823
The efficient or optimal scalable algorithms for a number of geometric problems for a machine model reflecting real parallel machines are presented. As stated, relevant parallelalgorithms must be applicable and efficient for a wide range of ratios n/p, for some given geometric problem of size n on a parallel computer with p processors. The designing techniques presented are independent of the communication network. One particular strength of the approach taken is that all inter processor communication is restricted to a constant number of two types of global routing operations: global sort and segmented broadcast. It remains open if it is possible to make the algorithms fully scalable, i.e. to develop algorithms for any n ≥ p and not only for n ≥ p2 or n ≥ p3. Meanwhile, similar technique can be used to decompose data structures such as the segment tree.
The proceedings contain 33 papers. The topics discussed include: a comparison of sorting algorithms for the connection machine CM-2;randomized sorting and selection on mesh-connected processor arrays;large-scale sorti...
ISBN:
(纸本)0897914384
The proceedings contain 33 papers. The topics discussed include: a comparison of sorting algorithms for the connection machine CM-2;randomized sorting and selection on mesh-connected processor arrays;large-scale sorting in parallel memories;optimal speedup for backtrack search on a butterfly network;fast and reliable parallel hashing;tight bounds for the chaining problem;parallel construction of trees with optimal weighted path length;more time-work tradeoffs for parallel graph algorithms;an overview of supertoroidal networks;and architectural primitives for a scalable shared memory multiprocessor.
The symposium materials contain 24 papers. The topics covered include local area networks as distributed systems;operating systems research;scalable parallel computing;atomic snapshots;radio networks;fast deflection r...
详细信息
ISBN:
(纸本)0897916131
The symposium materials contain 24 papers. The topics covered include local area networks as distributed systems;operating systems research;scalable parallel computing;atomic snapshots;radio networks;fast deflection routing for packets and worms;parallel computing models;wait-free clock synchronization;optimal clock synchronization;partially synchronized clocks;resource bounds and combinations of consensus objects;scalable synchronization with minimal hardware support;adaptive solutions to the mutual exclusion problem;distributed fingerprints and secure information dispersal;replicated files;space complexity of randomized synchronization;lower bound on wait-free counting;and knowledge-oriented programming.
Data-parallel languages like Fortran 90 express parallelism in the form of operations on data aggregates such as arrays. Misalignment of the operands of an array operation can reduce program performance on a distribut...
详细信息
ISBN:
(纸本)0897915607
Data-parallel languages like Fortran 90 express parallelism in the form of operations on data aggregates such as arrays. Misalignment of the operands of an array operation can reduce program performance on a distributed-memory parallel machine by requiring nonlocal data accesses. Determining array alignments that reduce communication is therefore a key issue in compiling such languages. We present a framework for the automatic determination of array alignments in data-parallel languages such as Fortran 90. Our language model handles array sectioning, reductions, spreads, transpositions, and masked operations. We decompose alignment functions into three constituents: axis, stride, and offset. For each of these subproblems, we show how to solve the alignment problem for a basic block of code, possibly containing common subexpressions. Alignments are generated for all array objects in the code, both named program variables and intermediate results. The alignments obtained by our algorithms are more general than those provided by the `owner-computes' rule. Finally, we present some ideas for dealing with control flow, replication, and dynamic alignments that depend on loop induction variables.
We apply the methodology of competitive analysis of algorithms in problems related to the implementation of programs on parallel machines. Previous work on the problem of implementing parallel programs in the face of ...
详细信息
ISBN:
(纸本)0898713137
We apply the methodology of competitive analysis of algorithms in problems related to the implementation of programs on parallel machines. Previous work on the problem of implementing parallel programs in the face of communication delays between the processors [6], [7] had assumed that the DAG of the computation is known beforehand. But in reality only the program text is known at compile time, while the precise program DAG depends critically on the data and parameters of the runtime environment. We discuss two natural and interesting situations in which the number of processors is fixed and the DAG is not completely known at compile time: When the nature of the DAG is known (a binary tree coming from divide-and-conquer, as in [9]);and when the DAG is known qualitatively, but each node has unknown execution time, to be determined online. In the first case, a binary tree coming from divide-and-conquer, we show a competitive ratio 3/2 (upper and lower bound) in the case of two processors;for more processors, the competitive ratio is Ω(τ/log τ) and O(τ), where τ is the communication delay ratio of the system (roughly, the average interprocessor communication measured in instruction cycles). For general DAGs the lower bound becomes Ω(τ), matching the upper bound within a constant multiplicative factor. For the second case, DAGs with unknown node execution times, the approximation algorithm in [7] can be made online with competitive ratio two when the number of processors is at least equal to the number of nodes. When the number of processors is fixed, we present a competitive online algorithm for merging trees, and for DAGs with bounded Dilworth number;the latter result leads to improved results for diamonds and the FFT.
暂无评论