We prove that in any N-node communication network with maximum degree d, any deterministic oblivious algorithm for routing an arbitrary permutation requires Ω(√N/d) parallel communication steps. This is an improveme...
详细信息
ISBN:
(纸本)0897913701
We prove that in any N-node communication network with maximum degree d, any deterministic oblivious algorithm for routing an arbitrary permutation requires Ω(√N/d) parallel communication steps. This is an improvement of the Ω(√N/d3/2) bound obtained by Borodin and Hopcroft. For the N-node hypercube, in particular, we show a matching upper bound by exhibiting a deterministic oblivious algorithm that routes any permutation in O(√N/log N) time. The best previously known upper bound was O(√N). Our algorithm could be practical for small N (up to about 214 nodes).
We present a parallel randomized algorithm for finding if two planar graphs are isomorphic. Assuming that we have a tree of separators for each planar graph, our algorithm takes O(log(n)) time with P = (n1.5&middo...
详细信息
ISBN:
(纸本)0897913701
We present a parallel randomized algorithm for finding if two planar graphs are isomorphic. Assuming that we have a tree of separators for each planar graph, our algorithm takes O(log(n)) time with P = (n1.5·√log(n)) processors with probability to fail of 1/n or less, where n is the number of vertices. The algorithms needs 2·log(m)·log(n) + O(log(n)) random bits. The number of random bits can be decreased to O(log(n)) by increasing the processors number to n3/2+Ε. This algorithm significantly improves the previous results of n4 processors.
The authors address the apparently difficult problem of doing parallel transitive closure when the (directed) graph is sparse and/or, only single-source information is desired. O(e) work is their target for the single...
详细信息
ISBN:
(纸本)0897913701
The authors address the apparently difficult problem of doing parallel transitive closure when the (directed) graph is sparse and/or, only single-source information is desired. O(e) work is their target for the single-source problem. When the graph is sparse, then the all-pairs transitive closure problem can be solved by performing a depth-first search from each node, taking O(ne) time;that is their target for the all-pairs problem. The authors do not reach either target, except for the all-pairs case when e is fairly large. However, they make significant progress, in the sense that they have the first algorithms that simultaneously use time much less than linear and use work that is less than M(n).
The authors investigate practical routing on the CAAPP, a content addressable SIMD mesh that has the power of broadcast over reconfigurable buses. Greedy algorithms are developed which avoid the need for queues by usi...
详细信息
ISBN:
(纸本)0897913701
The authors investigate practical routing on the CAAPP, a content addressable SIMD mesh that has the power of broadcast over reconfigurable buses. Greedy algorithms are developed which avoid the need for queues by using the coterie network. Through simulation, these algorithms are found to be close to optimal when operating on random permutations, and to perform similarly on many particular permutations. The worst case for one of these algorithms is found to be θ(N), it is doubted that this type of permutation will occur in practice.
There are now a number of fundamental problems in computational geometry that have optimal algorithms on PRAM models. We present randomized parallel algorithms which execute on an n-processor butterfly inter-connectio...
详细信息
ISBN:
(纸本)0897913701
There are now a number of fundamental problems in computational geometry that have optimal algorithms on PRAM models. We present randomized parallel algorithms which execute on an n-processor butterfly inter-connection network in O(log n) time for the following problems of input size n: trapezoidal decomposition, visibility, triangulation and 2-D convex hull. These are based on some previous work of the authors on PRAM algorithms and a new algorithm for doing binary search on fixed connection network. Apart from a 2-D convex hull algorithm, these are the first non-trivial geometric algorithms which attain this performance on fixed connection networks. The techniques developed in this paper rely on random sampling methods to do load-balancing on fixed-connection networks;it seems likely that they will have wider applications.
We present parallel algorithms to construct, for given sets of leaf weights, binary trees with almost optimal weighted path length (i.e. approximate Huffman trees). Specifically, assuming that weights are normalized (...
详细信息
ISBN:
(纸本)0897913701
We present parallel algorithms to construct, for given sets of leaf weights, binary trees with almost optimal weighted path length (i.e. approximate Huffman trees). Specifically, assuming that weights are normalized (to sum up to one) and error refers to the (absolute) difference between the weighted path length of a given tree and the optimal tree with the same weights, we present: (i) O(logn) time and n loglogn/logn EREW processor algorithm which constructs a tree with error less than 0.172;(ii) O(klogn log*n) time and n CREW processor algorithm which produces a tree with error at most 1/nk, and (iii) an O(k2logn) time and n2 CREW processor algorithm which produces a tree with error at most 1/nk. Our approach also leads to two sequential algorithms: an O(kn) time algorithm which produces a tree with error at most 1/n2(k) and O(kn) time algorithm which produces a tree with error at most 1/2n2(k). The last two algorithms use different computation models. (A detailed description of sequential algorithms is left to an expanded version of the paper [KP89].)
In this paper, we describe an O(log N) bit-step randomized algorithm for bit-serial message routing on a hypercube. The result is asymptotically optimal, and improves upon the best previously known algorithms by a log...
详细信息
ISBN:
(纸本)0897913701
In this paper, we describe an O(log N) bit-step randomized algorithm for bit-serial message routing on a hypercube. The result is asymptotically optimal, and improves upon the best previously known algorithms by a logarithmic factor. The result also solves the problem of on-line circuit switching in an O(1)-dilated hypercube (i.e., partitioning the edges of a dilated hypercube so as to realize an arbitrary permutation of point-to-point connections between the nodes). Our algorithm is adaptive and we show that this is necessary to achieve the logarithmic speedup. We generalize the Borodin-Hopcroft lower bound on oblivious routing by proving that any oblivious randomized algorithm on a polylogarithmic degree network requires Ω(log2 N/log log N) bit steps with high probability for almost all permutations.
The author develops two algorithms for a massively parallel system, an SIMD (single instruction, multiple data) computer with a general and fast communication network. Each of the two operations (unification and inher...
详细信息
The author develops two algorithms for a massively parallel system, an SIMD (single instruction, multiple data) computer with a general and fast communication network. Each of the two operations (unification and inheritance) is basic for one knowledge representation scheme. Both take data represented by directed graphs. For ease of integration in real systems and naturalness of specification, the operations are implemented incrementally, in the spirit of M. R. Quillian's 'spreading activation,' and not as atomic operations. The running time of both algorithms is almost linear in the number of vertices on the longest path in the graph representation. The association of the two operations is not accidental;the author intends to integrate them in a hybrid reasoning system.
The authors compare three parallel Astar search algorithms: the shared-list algorithm, where a search space is shared among processors;the static-distribution algorithm, where a search space is distributed once to all...
详细信息
ISBN:
(纸本)0818620080
The authors compare three parallel Astar search algorithms: the shared-list algorithm, where a search space is shared among processors;the static-distribution algorithm, where a search space is distributed once to all processors;and the continuous-diffusion algorithm, where a search space is continuously redistributed. The continuous-diffusion algorithms outperform the other two algorithms on message-passing architectures. The grid-flow technique developed for continuous diffusion is of general importance for nearest-neighbor algorithms that need to share some global information.
In this paper, we analyze the average case behavior of greedy routing algorithms on arrays under a variety of assumptions. Overall, we find that certain greedy algorithms perform surprisingly well on average, For exam...
详细信息
ISBN:
(纸本)0897913701
In this paper, we analyze the average case behavior of greedy routing algorithms on arrays under a variety of assumptions. Overall, we find that certain greedy algorithms perform surprisingly well on average, For example, given an N × N array or torus where every node starts with one packet headed for a random destination, we show that some (but not all) greedy store-and-forward algorithms route every packet to its destination with only O(log N) delay per packet and maximum queuesize 4 with probability near 1. Moreover, the expected delay per packet is only a small constant, independent of N. We also extend the analysis to a steady state model of routing in which packets enter the network at random times. Provided that the overall arrival rate of packets to the network is less than 100% of the network capacity, we show that any packet encounters at most O(log N) delay with high probability. In addition, we show that the maximum size of a queue over a time span of T steps is O(log T/log N) with high probability. The results can also be extended to analyze the average case behavior of cut-through (or, flit-serial) routing under lighter loading.
暂无评论