We design efficient parallel algorithms for solving several problems on interval graphs. The problems include finding a BFS-tree and DFS-tree, articulation points and bridges, and minimum coloring. Each of our algorit...
详细信息
Dehne, F., A. Ferreira and A. Rau-Chaplin, parallel fractional cascading on hypercube multiprocessors, Computational Geometry: Theory and Applications 2 (1992) 141–167. In this paper we present a new data-structuring...
Dehne, F., A. Ferreira and A. Rau-Chaplin, parallel fractional cascading on hypercube multiprocessors, Computational Geometry: Theory and Applications 2 (1992) 141–167. In this paper we present a new data-structuring technique for parallel computational geometry on a hypercube multiprocessor. This technique, called hypercube cascading, is an efficient parallel implementation of fractional cascading for the hypercube multiprocessor. That is, it allows complex data structures with catalogs to be traversed efficiently in parallel by a large number of simultaneous queries. We show that for monotone graphs with n nodes, m multiple look-up queries with path length at most p (including catalog look-ups) can be executed independently, in parallel, in time O( p log N + t s ( N )) on a hypercube multiprocessor of size N = max n, itm . The term t s ( N ) denotes the time for sorting N elements on a hypercube of size N ; currently t s ( N ) = O(log N log log N ). Note that, the best known sequential time complexity for one multiple look-up query, as presented by Chazelle and Guibas, is O( p + log N ). Our solution allows an arbitrary number of search queries to access the same node and its catalog at the same time. We present two parallel computational geometry applications of this technique: multiple stabbing of a simple polygonal path and multiple slanted range search.
Patterns of faults that are catastrophic for regular architectures, particularly the systolic arrays, have been studied. For a given link configuration, there are many fault patterns which are catastrophic. Among thos...
详细信息
Fault tolerance through the incorporation of redundancy and reconfiguration is quite common. Regular systems are being designed with massive redundancy built into them [5,6,12], These systems also make use of the redu...
详细信息
Patterns of faults that are catastrophic for regular architectures, particularly the systolic arrays, have been studied. For a given link configuration, there are many fault patterns which are catastrophic. Among thos...
详细信息
Patterns of faults that are catastrophic for regular architectures, particularly the systolic arrays, have been studied. For a given link configuration, there are many fault patterns which are catastrophic. Among those, there is a particular fault pattern, called the reference fault pattern, which is crucial for the development of testing techniques; furthermore, the efficiency of any testing algorithm can be further improved in the presence of efficient algorithms for constructing the reference fault pattern. The authors develop a new algorithm for the construction of the reference fault pattern for VLSI reconfigurable arrays in which the links are bidirectional. The complexity of the new algorithm is O(kN) which is a significant improvement over the existing O(N/sup 2/) algorithm, where k is the number of bypass links, and N is the length of the largest bypass link.< >
For a given design, it is not difficult to identify a set of elements whose failure will have catastrophic consequence. There exist many patterns (random distribution) of faults, not in a block, which can be fatal for...
详细信息
For a given design, it is not difficult to identify a set of elements whose failure will have catastrophic consequence. There exist many patterns (random distribution) of faults, not in a block, which can be fatal for the system. Therefore, the characterization of such fault patterns is crucial for the identification, testing and detection of such catastrophic events. This paper, is concerned with the development of efficient recognition schemes; that is, efficient mechanisms which automatically determine whether or not an observed/detected pattern of faults will have catastrophic consequences. The problem of recognizing whether a fault pattern is catastrophic has been addressed.< >
This paper discusses the effect of processor failures on computation performed on two-dimensional VLSI processor arrays. Previously established properties of catastrophic fault patterns are used to study inherent limi...
详细信息
We design a cost-optimal algorithm for managing a parallel heap on an exclusive-read and exclusive-write (EREW), parallel random access machine (PRAM) model. This is an improvement in space and time over the one recen...
详细信息
This paper discusses the effect of processor failures on computation performed on two-dimensional VLSI processor arrays. Previously established properties of catastrophic fault patterns are used to study inherent limi...
详细信息
This paper discusses the effect of processor failures on computation performed on two-dimensional VLSI processor arrays. Previously established properties of catastrophic fault patterns are used to study inherent limits to reconfigurability of these regular architectures. Bounds on number of faults the system can tolerate to provide guaranteed performance are derived. These results are the generalization of the results obtained in the case of one-dimensional processor arrays.< >
暂无评论