Our main result in this paper is a parallel algorithm for suffiz-prefix matching that has optimal speedup on a CRCW PRAM. It runs in time O(logn) using n/log n processors. This algorithm is important because we utihze...
详细信息
The authors have simulated several numerical and nonnumerical algorithms on five distributed-memory parallel processors (DMPPs). All five DMPPs have the same topology (a torus) and the same number of nodes. The archit...
详细信息
ISBN:
(纸本)9780897913195
The authors have simulated several numerical and nonnumerical algorithms on five distributed-memory parallel processors (DMPPs). All five DMPPs have the same topology (a torus) and the same number of nodes. The architectures differ only in the speed of communication between neighboring nodes, with the computation unit unchanged. The authors quantify the effect that interprocessor communication speed and synchronization overhead have on the performance of the DMPPs. After introducing their rationale and reviewing related work, the authors present and discuss the results of the simulations.
This paper shows how n-node, e-edge graphs can be contracted in a manner similar to the parallel tree contraction algorithm due to Miller and Reif. We give an O((n + e)/lgn)-processor deterministic algorithm that cont...
详细信息
作者：
AnonACM
Special Interest Group for Automata and Computability Theory New York NY USA ACM Special Interest Group for Automata and Computability Theory New York NY USA
This conference proceedings contains 50 papers. The topics covered include: algorithms;graph theory;parallel processing;automata;boolean circuits;computational geometry;cryptography;complexity;distributed computing.
This conference proceedings contains 50 papers. The topics covered include: algorithms;graph theory;parallel processing;automata;boolean circuits;computational geometry;cryptography;complexity;distributed computing.
We present an NC algorithm for recognizing chordal graphs, and we present NC algorithms for finding the following objects on chordal graphs: all maximal cliques, an intersection graph representation, an optimal colori...
详细信息
ISBN:
(纸本)9780897912211
We present an NC algorithm for recognizing chordal graphs, and we present NC algorithms for finding the following objects on chordal graphs: all maximal cliques, an intersection graph representation, an optimal coloring, a perfect elimination scheme, a maximum independent set, a minimum clique cover, and the chromatic polynomial. The well known polynomial algorithms for these problems seem highly sequential, and therefore a different approach is needed to find parallelalgorithms.
We describe efficient deterministic techniques for breaking symmetry in parallel. The techniques work well on rooted trees and graphs of constant degree or genus. Our primary technique allows us to 3-color a rooted tr...
详细信息
ISBN:
(纸本)9780897912211
We describe efficient deterministic techniques for breaking symmetry in parallel. The techniques work well on rooted trees and graphs of constant degree or genus. Our primary technique allows us to 3-color a rooted tree in O(lg n) time on an EREW PRAM using a linear number of processors. We apply these techniques to construct fast linear processor algorithms for several problems, including ( DELTA plus 1)-coloring constant-degree graphs, 5-coloring planar graphs, and finding depth-first-search trees in planar graphs. We also prove lower bounds for 2-coloring directed lists and for finding maximal independent sets in arbitrary graphs.
The dynamic parallel complexity of general computational circuits is discussed. We exhibit some relationships between parallel circuit evaluation and some uniform closure properties of a certain class of unary functio...
详细信息
ISBN:
(纸本)9780897912211
The dynamic parallel complexity of general computational circuits is discussed. We exhibit some relationships between parallel circuit evaluation and some uniform closure properties of a certain class of unary functions and present a systematic method for the design of processor efficient parallelalgorithms for circuit evaluation. Using this method: (1) we improve the algorithm for parallel Boolean circuit evaluation;(2) we give a nontrivial upper bound for parallel min-max-plus circuit evaluation;(3) we partially answer an open question raised by G. L. Miller et al. by showing that all circuits over a finite noncommutative semiring and circuits over an infinte noncommutative semiring which has finite dimension over a commutative semiring can be evaluated in polylogarithmic time in its size and degree using M(n) processors. Moreover, we develop a theory for determining closure properties of certain classes of unary functions.
Rule-based systems appear to be capable of exploiting large amounts of parallelism, because it is possible to match each rule to the data memory in parallel. It is pointed out that in practice the speedup from paralle...
详细信息
ISBN:
(纸本)081860719X
Rule-based systems appear to be capable of exploiting large amounts of parallelism, because it is possible to match each rule to the data memory in parallel. It is pointed out that in practice the speedup from parallelism is quite limited, less than 10-fold. The reasons for the small speedup are: (1) the small number of rules relevant to each change to data memory;(2) the large variation in the processing required by the relevant rules;and (3) the small number of changes made to data memory between synchronization steps. To obtain this limited factor of 10-fold speedup, it is necessary to exploit parallelism at a very fine granularity. It is suggested that a suitable architecture to exploit such fine-grain parallelism is a bus-based shared-memory multiprocessor with 32-64 processors. Using such a multiprocessor (with individual processors working at 2 MIPS), it is possible to obtain execution speeds of about 3800 rule-firings/s. This speed is significantly higher than that obtained by other proposed parallel implementations of rule-based systems.
An approach is proposed for modeling off-the-shelf hardware and for modeling parallelalgorithms, along with a design methodology to use the information provided by these models, to design a class of macro-pipelined s...
详细信息
ISBN:
(纸本)0818606347
An approach is proposed for modeling off-the-shelf hardware and for modeling parallelalgorithms, along with a design methodology to use the information provided by these models, to design a class of macro-pipelined special-purpose architectures. Nine parameters to form a model of the characteristics of parallel/distributed algorithms and the environment in which they must execute are presented. In addition, a set of tuples to model the characteristics of computer architectures is presented. By combining the tuples with the parameters, the execution time of the algorithm modeled by the parameters on the hardware modeled by the tuples can be approximated. The combination of these models could be used as a basis for computer-aided tools used in the design of macro-pipelined parallel/distributed processors.
暂无评论