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.
Some parallelalgorithms have the property that, as they are allowed to take more time, the total work that they do is reduced. This paper describes three such algorithms that find the strongly connected components of...
详细信息
This paper deals with the problem of parallel construction of trees with optimal weighted path length. We study both the unordered case, known as the Huffman coding problem and the ordered case known as the optimal al...
详细信息
Non-blocking networks have many applications in communications. Typical examples are telephone switching networks and communication networks among processors or between processors and memory devices. We construct non-...
详细信息
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...
详细信息
We give two optimal parallelalgorithms for constructing the arrangement of n lines in the plane. The first method is quite simple and runs in O(log2n) time using O(n2) work, and the second method, which is more sophi...
详细信息
A perfect hash function for a (multi)set X of n integers is an infective function h : X → {1,., s}, where s = O(n), that can be stored in O(n) space and evaluated in constant time by a single processor. We show that ...
详细信息
暂无评论