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.< >
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.
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 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.< >
In this paper, we study the problem of implementing standard data structures on a hypercube multiprocessor. We present a technique for efficiently executing multiple independent search processes on a class of graphs c...
详细信息
In this paper, we study the problem of implementing standard data structures on a hypercube multiprocessor. We present a technique for efficiently executing multiple independent search processes on a class of graphs called ordered h -level graphs. We show how this technique can be utilized to implement a segment tree on a hypercube, thereby obtaining O (long 2 n ) time algorithms for solving the next element search problem, the trapezoidal composition problem, and the triangulation problem.
Given a rectangle R (with its edges parallel to the coordinate axes) containing a set S = { s 1 ,…, s n } of n points in the Euclidean plane, consider the problem of finding the largest area subrectangle r in R with ...
详细信息
Given a rectangle R (with its edges parallel to the coordinate axes) containing a set S = { s 1 ,…, s n } of n points in the Euclidean plane, consider the problem of finding the largest area subrectangle r in R with sides parallel to the coordinate axes that contains no point of S . We present optimal parallel algorithms for solving this problem on one- and two-dimensional arrays of processors.
In this paper, we study the problem of implementing standard data structures on a hypercube multiprocessor. We present a technique for efficiently executing multiple independant search processes on a class of graphs c...
详细信息
The main problem for the design of dictionary machines on coarse grained hypercube multiprocessors, in comparison to the widely studied dictionary problem for fine grained hypercube multiprocessors, is that due to une...
详细信息
暂无评论