The paper describes a preliminary evaluation of some multi-join strategies and their performances on parallel hardware. The hardware used was a Sequent (under UNIX) with 11 usable processors, each with shared and priv...
详细信息
ISBN:
(纸本)0818620528
The paper describes a preliminary evaluation of some multi-join strategies and their performances on parallel hardware. The hardware used was a Sequent (under UNIX) with 11 usable processors, each with shared and private primary memory. A multi-join was broken down into a series of single joins which were then allocated to clusters, each cluster being a collection of parallel processors. The results of single joins, which were studied by both binary search and hash-merge techniques, were then further processed as *** evaluation was conducted varying a number of parameters, such as cluster size, tuple size and cardinality. The comparative results were plotted. The study highlights the importance of a number of factors that influence the performance of a multi-join operation.
In this paper, we present a mixed MIMD / SIMD execution model for a reconfigurable computer. This model is adapted to the use of a specialized associative coprocessor, embedded in this host machine. A main characteris...
详细信息
ISBN:
(纸本)0818620528
In this paper, we present a mixed MIMD / SIMD execution model for a reconfigurable computer. This model is adapted to the use of a specialized associative coprocessor, embedded in this host machine. A main characteristic of the model is that it uses four types of processes (decoding, calculus, coprocessor communication and transaction manager), and that in principle one process of each type is allowed on each processor. Time intervals are allocated to operations into partitions of the set of processors. Transfers are usually limited to identifiers, logical addresses and locks. Simulations display a high level of processors occupation. Therefore the machine yield may be very high, and the operations should be very fast.
In this paper we introduce and discuss a model of distributed data processing. For this purpose, a typical application system is analyzed and divided into sub-applications. To fulfill the task of the global applicatio...
详细信息
ISBN:
(纸本)0818620528
In this paper we introduce and discuss a model of distributed data processing. For this purpose, a typical application system is analyzed and divided into sub-applications. To fulfill the task of the global application, the sub-applications have to communicate in an appropriate manner by exchanging data resp. information. In our model the communication between sub-applications is split up into two steps: the offering of information by sending sub-applications, and its acceptance by receiving sub-applications. For both communication steps synchronous and asynchronous processing modes are defined. Supporting those different communication modes the cooperation between sub-applications can be defined very closely to the specific demands of the application system. This optimizes distributed data processing. At last we demonstrate the prototype implementation of a distributed data management system, which is based on the flexible communication mechanism described in the paper.
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.
The models and languages most widely used for distributedsystems programming (such as ADA, CSP, and OCCAM) do not explicitly consider the process execution site, they assume a synchronous communication scheme of “re...
详细信息
ISBN:
(纸本)0818620528
The models and languages most widely used for distributedsystems programming (such as ADA, CSP, and OCCAM) do not explicitly consider the process execution site, they assume a synchronous communication scheme of “rendezvous” style, and require that each process recognize the names of their interlocutors. JOYCE+ is a modification of the JOYCE language defined by Brinch Hansen [Brinch 87, Brinch 89]. In the JOYCE+ model each process is executed in a specific site, it is assumed that the communication between processes at the same site is much more faster than between processes at different sites, and it is also assumed that the communication between processes is not always reliable. For this multi-site environment an asynchronous communication scheme is considered, eliminating waiting states for a process that sends a message to another process. Furthermore, modelling communication between processes through “channel” objects, the spaces for process names become *** this paper the JOYCE+ model for multi-site distributedsystems is presented and the operational semantic of the asynchronous communication between processes is illustrated with Petri Nets. The syntax of the JOYCE+ language is presented in terms of the Guarded Commands language [Dijkstra 75]. The expressive power of the JOYCE+ language in distributed synchronization problems with timeout handling is illustrated through examples. Finally, we discuss about software development environments (based on JOYCE+) for distributedsystems over multi- and mono-process computer *** Terms - Languages for distributedsystems, Tools and methodologies for distributedsystems.
Given a set of functional dependencies Σ and a single dependency σ, we show that the algorithm to test whether Σ implies σ is log-space complete in P. The functional dependencies Σ are represented as a directed h...
详细信息
ISBN:
(纸本)0818620528
Given a set of functional dependencies Σ and a single dependency σ, we show that the algorithm to test whether Σ implies σ is log-space complete in P. The functional dependencies Σ are represented as a directed hypergraph HΣ [1]. We first present a parallel algorithm which solves the above implication problem using P processors on a EREW-PRAM in Ο(e/P + ***) time and on a CRCW-PRAM in Ο(e/P + n) time, where e and n are the number of arcs and nodes of the graph HΣ. For graphs HΣ with fixed degree and diameter, we show that the closure HΣ+ can be computed in NC. We present NC algorithms to obtain a non-redundant and a LR-Minimum cover for the set of functional dependencies Σ. All our algorithms on a n-node directed hypergraph with fixed degree and diameter can be implemented to run in Ο(log2n) time with M(n) processors on a CREW-PRAM model, where M(n) is the cost of multiplying two binary matrices. The algorithms are efficient based on the transitive closure bottleneck phenomenon [7] that is, any improvement in the time and processor complexity of the transitive closure algorithm will result in an improvement by the same amount for the algorithms presented here.
Algorithms for processing distributed 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 processing distributed 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.
This conference proceedings contains 70 paperes. The following topics are dealt with: software engineering;neural nets;databases;parallel processing;expert systems;logic and symbolic programming;graphs and networks;in...
详细信息
ISBN:
(纸本)0818620315
This conference proceedings contains 70 paperes. The following topics are dealt with: software engineering;neural nets;databases;parallel processing;expert systems;logic and symbolic programming;graphs and networks;information retrieval and office automation;computational linguistics and natural language processing;parallel and distributedsystems;database and operating systems;networking;object-oriented systems;simulation;graphics;algorithms and file management;and queues and architecture.
The proceedings contains 121 papers. The following topics are dealt with: query processing;database algorithms;parallel architectures;distributed database reliability;concurrency control;heterogeneous and object-orien...
详细信息
The proceedings contains 121 papers. The following topics are dealt with: query processing;database algorithms;parallel architectures;distributed database reliability;concurrency control;heterogeneous and object-oriented database management systems;and the logical level/languages and design of databases.
K2 is a distributed-memory parallel processor designed to support a multiuser, multitasking, time-sharing operating system and an automatically parallelizing Fortran compiler. The architecture and the hardware impleme...
详细信息
ISBN:
(纸本)0818620471
K2 is a distributed-memory parallel processor designed to support a multiuser, multitasking, time-sharing operating system and an automatically parallelizing Fortran compiler. The architecture and the hardware implementation of K2 are presented. The authors focus on the architectural features required by the operating system and the compiler. A prototype machine with 24 processors is currently being developed.
暂无评论