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.
We describe a new randomized parallel algorithm for computing the planar convex hull of n points on a p processor-memory pair machine communicating through a network for which O(log p) routing is possible. We show tha...
详细信息
We describe a new randomized parallel algorithm for computing the planar convex hull of n points on a p processor-memory pair machine communicating through a network for which O(log p) routing is possible. We show that the algorithm has optimal O(n log n/p) performance provided that p = o(n/log3n). We report extensive computational experience with the algorithm which supports its theoretical claims.
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.
In this paper, we present a dynamic load-balancing algorithm for parallel digital logic simulation making use of reinforcement learning We first introduce two dynamic load-balancing algorithms oriented towards balanci...
详细信息
ISBN:
(纸本)9781450300797
In this paper, we present a dynamic load-balancing algorithm for parallel digital logic simulation making use of reinforcement learning We first introduce two dynamic load-balancing algorithms oriented towards balancing the computational and communication load respectively and then utilize reinforcement learning to create an algorithm which is a combination of the first two algorithms In addition, the algorithm determines the value of two important parameters the number of processors which participate in the algorithm and the load which is exchanged during its execution. We investigate the algorithms on gate level simulations of several open source VLSI circuits
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...
详细信息
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'...
详细信息
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...
详细信息
暂无评论