We describe a randomized CRCW PRAM algorithm that finds a minimum spanning forest of an n-vertex graph in O(log n) time and linear work. This shaves a factor of 2log* n off the best previous running time for a linear-...
详细信息
ISBN:
(纸本)9780897918091
We describe a randomized CRCW PRAM algorithm that finds a minimum spanning forest of an n-vertex graph in O(log n) time and linear work. This shaves a factor of 2log* n off the best previous running time for a linear-work algorithm. The novelty in our approach is to divide the computation into two phases, the first of which finds only a partial solution. This idea has been used previously in parallel connected components algorithms.
An upper bound for the trade-off between space and routing time and space needed to store routing information in the processors and the packets is proven. This result is a consequence of a new strategy for the simulat...
详细信息
An upper bound for the trade-off between space and routing time and space needed to store routing information in the processors and the packets is proven. This result is a consequence of a new strategy for the simulation between arbitrary networks. Finally, several techniques are applied for the simulation of networks to demonstrate space-efficiently routing strategies for vertex-symmetric networks.
In this paper we describe a technique for finding efficient parallelalgorithms for problems on directed graphs that involve checking the ezistence of certain kinds of paths in the graph. This technique provides effic...
详细信息
This paper presents a method for mapping binary hypercube-algorithms onto lower dimensional meshes and analyzes this method in a model derived from the architecture of modern mesh machines. We outline the criteria use...
详细信息
ISBN:
(纸本)089791483X
This paper presents a method for mapping binary hypercube-algorithms onto lower dimensional meshes and analyzes this method in a model derived from the architecture of modern mesh machines. We outline the criteria used to evaluate graph embeddings for mapping supercomputer communication networks. The measured sorting rate of more than 2x106 keys per second on an iWarp torus with just 64 processors shows the excellent absolute performance of our approach.
This paper introduces the Asynchronous PRAM model of computation, a variant of the PRAM in which the processors run asynchronously and there is an explicit charge for synchronization. A family of asynchronous PRAM'...
详细信息
This paper presents an engineering design for a low latency high bandwidth interconnection network which will form the switching substrate for a multi-model parallel processing system. The performance is enhanced with...
详细信息
A new approach to parallel sorting called parallel Sorting by OverPartitioning (PSOP) is presented. The approach limits the communication cost by moving each element between processors at most once, and leads to good ...
详细信息
暂无评论