The paper studies the problem of restructuring two dimensional wafers in the presence of faults. It constructs arrays of size as much as the size of the original faulty wafer. Obviously this is done at the cost of inc...
详细信息
A prototype of an object-oriented system implemented in C_Prolog is described. Its main objective is to demonstrate system features that would support efficient management of objects and object-oriented databases in a...
详细信息
ISBN:
(纸本)0818620528
A prototype of an object-oriented system implemented in C_Prolog is described. Its main objective is to demonstrate system features that would support efficient management of objects and object-oriented databases in a persistent anddistributed environment. Mechanisms at the low level of the system were considered to support object distribution, mobility control, and configuration management in a simple and uniform way. Objects exist in clusters, which are transparent to the applications. The prototype is a framework for a self-organizing object-oriented distributed system.
Semijoin has traditionally been relied upon for reducing the communication cost required for distributed query processing. However, judiciously applying join operations as reducers can lead to further reduction in the...
详细信息
ISBN:
(纸本)0818620528
Semijoin has traditionally been relied upon for reducing the communication cost required for distributed query processing. However, judiciously applying join operations as reducers can lead to further reduction in the communication cost. In view of this fact, we explore in this paper the approach of using join operations, in addition to semijoins, as reducers in distributed query processing. We first show that the problem of determining a sequence of join operations for a query graph can be transformed to that of finding a set of cuts to that graph, where a cut to a graph is a partition of the nodes in that graph. In light of the mapping we develop an efficient heuristic algorithm to determine an effective sequence of join reducers for a query. The algorithm using the concept of divide-and-conquer is shown to have polynomial time complexity. Examples are also given to illustrate our results.
In [16] a pipelined strategy is presented for processing recursive queries in deductive database systems. As a follow-up, this paper studies the run-time performance of the proposed strategy. The algorithm, introduced...
详细信息
ISBN:
(纸本)0818620528
In [16] a pipelined strategy is presented for processing recursive queries in deductive database systems. As a follow-up, this paper studies the run-time performance of the proposed strategy. The algorithm, introduced informally by examples in this paper, is coded in occam2 and runs on a network of transputers. A wide range of recursive queries and database structures are used as benchmarks in this study. Both the speedup factors achieved and the elapsed time spent by the strategy in answering recursive queries are analysed. Experimental results show that it is possible to achieve significant performance improvement when queries are evaluated in parallel, and provide insights into the success of this strategy in meeting the primary objective of focusing on relevant data.
The authors present two EREW PRAM algorithms and one CREW PRAM algorithm for solving set recurrence equations of the type commonly used in dynamic programming solutions to many problems in pattern matching, sequence c...
详细信息
Algorithms for processingdistributed queries require a priori estimates of the size of intermediate relations. Most such algorithms take a “static” approach in which the algorithm is completely determined before pr...
详细信息
ISBN:
(纸本)0818620528
Algorithms for processingdistributed queries require a priori estimates of the size of intermediate relations. Most such algorithms take a “static” approach in which the algorithm is completely determined before processing begins. If size estimates are found to be inaccurate at some intermediate stage, there is no opportunity to re-schedule, and the result may be far from optimal. Adaptive query execution may be used to alleviate the problem. Care is necessary, though, to ensure that the delay associated with re-scheduling does not exceed the time saved through the use of a more efficient strategy. This paper presents a low overhead delay method to decide when to correct a strategy. Sampling is used to estimate the size of relations, and alternative heuristic strategies prepared in a background mode are used to decide when to correct. Correction is made only if lower overall delay is achieved, including correction time. Evaluation using a model of a distributed data base indicates that the heuristic strategies are near optimal. Moreover, it also suggests that it is usually correct to abort creation of an intermediate relation which is much larger than predicted.
The design of a functional embedding kernel (E-kernel) to support automatic mapping of parallel programs having higher dimensional mesh or torus task graphs onto the 2D mesh network of Victor is described. E-kernel su...
详细信息
The design of a functional embedding kernel (E-kernel) to support automatic mapping of parallel programs having higher dimensional mesh or torus task graphs onto the 2D mesh network of Victor is described. E-kernel supports two levels of embeddings: in the first level, the mapping of a parallel program onto the system network; and in the second level, the mapping of a network topology onto the 2D mesh. The first level of embeddings corresponds to the support of automatic program mapping, and the second level the support of network reconfiguration.< >
The authors present two EREW PRAM algorithms and one CREW PRAM algorithm for solving set recurrence equations of the type commonly used in dynamic programming solutions to many problems in pattern matching, sequence c...
详细信息
The authors present two EREW PRAM algorithms and one CREW PRAM algorithm for solving set recurrence equations of the type commonly used in dynamic programming solutions to many problems in pattern matching, sequence comparison, and language recognition. All three algorithms run in O(log/sup 2/n) time. The first EREW PRAM algorithm uses O(M(n/log n)log/sup 2/n) processors, where M(n) is the number of processors needed to multiply two n*n Boolean matrices in O(log n) time on an EREW PRAM. The second algorithm uses O(M'(n/(log n square root loglog n))log/sup 2/n) processors, where M'(n) is the number of processors needed to multiply two n*n matrices over an arbitrary ring in O(log n) time on an EREW PRAM. The CREW PRAM algorithm uses O(M"(n/log/sup 1.5/n)log/sup 2/n) processors, where M"(n) is the number of processors needed to multiply two n*n matrices over an arbitrary ring in O(log n) time on a CREW PRAM. The authors show that linear context-free languages can be recognized in O(log/sup 2/n) time using o(M(n)) processors on an EREW PRAM. They give applications to other problems such as string shuffling, recognition of languages accepted by two-head nondeterministic finite automata, and transductions defined by two-tape nondeterministic finite transducers.< >
An approach is suggested to map the solution of the least-square (LS) problem, using Gram-Schmidt (GS) orthogonalization, on a distributed memory parallelprocessing (DMPP) architecture. Using algorithmic partitioning...
详细信息
An approach is suggested to map the solution of the least-square (LS) problem, using Gram-Schmidt (GS) orthogonalization, on a distributed memory parallelprocessing (DMPP) architecture. Using algorithmic partitioning, the resulting lower-order problems are mapped concurrently on the architecture concerned so that the computational loads are more evenly balanced than when the conventional method is applied. This results in much higher multiprocessor efficiencies. Specific implementation advantages are seen to exist for the partitioning factors which are a power of 2. DMPP architectures are very useful for future implementation of high speed digital processing (DSP) applications because of the excellent potential they offer for being able to be implemented in the form of VLSIs. The solution of the problem concerned on the ring and torus topologies is discussed.< >
The iWarp communication system supports two widely used interprocessor communication styles: memory communication and systolic communication. A description is given of the rationale, architecture, and implementation f...
详细信息
The iWarp communication system supports two widely used interprocessor communication styles: memory communication and systolic communication. A description is given of the rationale, architecture, and implementation for the iWarp communication system. Memory communication is flexible and well suited for general computing, whereas systolic communication is efficient and well suited for speed-critical applications. The iWarp design is made possible by two important innovations in communication: (1) program access to communication and (2) logical channels. The former allows programs to access data as they are transmitted and to redirect portions of messages to different destinations efficiently. The latter increases the connectivity between the processors and guarantees communication bandwidth for classes of messages. These innovations have provided a focus for the iWarp architecture. The result is a communication system that provides a total bandwidth of 320 MBytes/sec and that is integrated on a single VLSI component with a 20 MFLOPS plus 20 MIPS long instruction work computation engine.< >
暂无评论