The problem of packet routing on an r-dimensional mesh-connected array or grid of processors with side-length n is studied. Each processor is able to store rf(n) packets, f(n) 1-1/r. The new class of balanced routing ...
详细信息
This conference proceeding contains 45 papers. The topics covered include: routing algorithms;array processing;message passing;fault tolerance;hypercubes;scheduling;parallelalgorithms;memory sharing;computational com...
详细信息
ISBN:
(纸本)0897913701
This conference proceeding contains 45 papers. The topics covered include: routing algorithms;array processing;message passing;fault tolerance;hypercubes;scheduling;parallelalgorithms;memory sharing;computational complexity;PRAMs;graph theory and data structures.
We introduce a new preconditioner for solving a symmetric Toeplitz system of equations by the conjugate gradient method. This choice leads to an algorithm which is particularly suitable for parallel computations and, ...
详细信息
ISBN:
(纸本)0897913701
We introduce a new preconditioner for solving a symmetric Toeplitz system of equations by the conjugate gradient method. This choice leads to an algorithm which is particularly suitable for parallel computations and, compared to the circulant preconditioner of [C3], has a better asymptotic convergence rate and a lower arithmetic cost per iteration.
In this paper we give efficient parallelalgorithms for a number of problems from computational geometry by using generalized versions of parallel plane sweeping. We illustrate our approach with a number of applicatio...
详细信息
ISBN:
(纸本)0897913701
In this paper we give efficient parallelalgorithms for a number of problems from computational geometry by using generalized versions of parallel plane sweeping. We illustrate our approach with a number of applications, which include general hidden-surface elimination (even if the overlap relation contains cycles), CSG boundary evaluation, computing the contour of a collection of rectangles, and hidden-surface elimination for rectangles. Our algorithms are for the CREW PRAM.
The time required to compute any function of a collection of circular doubly linked lists on a CROW PRAM is shown to be at most a constant factor more than on a CREW PRAM, but this is not true for singly linked lists....
详细信息
ISBN:
(纸本)0897913701
The time required to compute any function of a collection of circular doubly linked lists on a CROW PRAM is shown to be at most a constant factor more than on a CREW PRAM, but this is not true for singly linked lists. A tight lower bound of Ω(log log n) for colouring an n node doubly linked list on a CROW PRAM using a constant number of colours is also obtained.
A unified framework for finding efficient permutation routes on parallel networks in an off-line setting is presented. If the underlying graph of a parallel network contains an appropriate 'approximate' produc...
详细信息
ISBN:
(纸本)0897913701
A unified framework for finding efficient permutation routes on parallel networks in an off-line setting is presented. If the underlying graph of a parallel network contains an appropriate 'approximate' product structure then our method guarantees the existence of non-blocking near-optimal permutation routes. The routes in question can be determined in polynomial time. Furthermore, our results are extended to finding permutation routes among the remaining 'live' nodes in a faulty network.
The Program Dependence Graph (PDG), which represents the data and the control dependences of a program is considered. Attention is limited to the subgraph of the PDG which contains only the control dependence edges. T...
详细信息
ISBN:
(纸本)0897913701
The Program Dependence Graph (PDG), which represents the data and the control dependences of a program is considered. Attention is limited to the subgraph of the PDG which contains only the control dependence edges. This subgraph is called the Control Dependence Graph (CDG). The authors formalize what it means for a CDG to have a corresponding sequential version and characterize the conditions under which there is such a corresponding sequentialization not requiring duplication.
We introduce a task scheduling model which is useful in the design and analysis of algorithms for small parallel machines. We prove that under our model, the overhead experienced in scheduling an n × n grid graph...
详细信息
ISBN:
(纸本)0897913701
We introduce a task scheduling model which is useful in the design and analysis of algorithms for small parallel machines. We prove that under our model, the overhead experienced in scheduling an n × n grid graph is O(log log n) for p processors, p ≥ 2. We also prove a matching lower bound of Ω(log log n) for p processors, p ≥ 2. We give an extension of the model to cover the case where the processors can have varying speed or are subject to delay.
This paper investigates the parallel time and processor complexities of several searching problems involving Monge and Monge-composite arrays. We present array-searching algorithms for concurrent-read-concurrent-write...
详细信息
ISBN:
(纸本)0897913701
This paper investigates the parallel time and processor complexities of several searching problems involving Monge and Monge-composite arrays. We present array-searching algorithms for concurrent-read-concurrent-write (CRCW) PRAMs, concurrent-read-exclusive-write (CREW) PRAMs, hypercubes, cube-connected-cycles, and shuffle-exchange networks. All these algorithms run in optimal time, and their processor-time products are all within an O(lg n) factor of the worst-case sequential bounds. Several applications of these algorithms are also given. Two applications improve previous results substantially, and the others provide novel parallelalgorithms for problems not previously considered.
The problem of representing a set U = {u1, ..., um} of read-write variables on an n-node distributed memory parallel computer is considered. It is shown that U can be represented among the n nodes of a variant of the ...
详细信息
ISBN:
(纸本)0897913701
The problem of representing a set U = {u1, ..., um} of read-write variables on an n-node distributed memory parallel computer is considered. It is shown that U can be represented among the n nodes of a variant of the mesh-of-trees using O((m/n)polylog(m/n)) storage per node such that any n-tuple of variables may be accessed in O(log n(log log n)2) time in the worst case for m polynomial in n.
暂无评论