A collection of local workpiles (task queues) and a simple load balancing scheme is well suited for scheduling tasks in shared memory parallel machines. Task scheduling on such machines has usually been done through a...
详细信息
We present a number of efficient parallelalgorithms for constructing 2- and 3-dimensional convex hulls on a randomized CRCW PRAM. Specifically, we show how to build the convex hull of n pre-sorted points in the plane...
详细信息
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.
暂无评论