Due to their unique path property, banyan multistage interconnection networks (MINs) can be self-routed using control tags. The paper introduces a number of routing control classes of MINs and studies their structure....
详细信息
Due to their unique path property, banyan multistage interconnection networks (MINs) can be self-routed using control tags. The paper introduces a number of routing control classes of MINs and studies their structure. These include the D-controllable networks where the control tags are the destination labels, the FD-controllable networks, where the control tags are function of the destination labels and the doubly D- or FD-controllable networks which are D- or FD-controllable forward and backward. The paper shows that all D- and FD-controllable networks have a recursive structure, and that all doubly D-controllable (resp., FD-controllable) networks are strictly (resp., widely) functionally equivalent to the baseline network. The subclass of MINs where the interconnections are digit permute is also studied and shown to be doubly FD-controllable and hence equivalent to the baseline. Finally, the paper presents an efficient parallel algorithm that relabels the terminals of any one network to simulate any other network in that subclass.< >
Two issues are introduced into the scheduling problem: each of the sub-tasks can be performed using one of a number of parallel algorithms running on different configurations; and there is an overhead time to move dat...
详细信息
Two issues are introduced into the scheduling problem: each of the sub-tasks can be performed using one of a number of parallel algorithms running on different configurations; and there is an overhead time to move data (reconfiguration time) from the configuration required by one algorithm to the configuration required by the algorithm of the successor sub-task. The execution time for each algorithm and the reconfiguration times between all pairs of algorithms are provided along with the precedence graph. The problem is to find for each sub-task the algorithm to be executed such that the total system time, which is the sum of the execution times and the data movement times of all the selected algorithms, is minimized. The authors show that the problem is NP-hard even when the total degree, of each node of the precedence graph is at most three. They show that it can be solved in polynomial time if the total degree of each node is at most two, thus completely closing the gap between the polynomially solvable cases and the NP-hard cases in terms of the maximum degree of the precedence graph.< >
The overall architecture of the European Declarative System (EDS), ESPRIT II Project 2025 is briefly described. The aim of the project is to design and implement both the hardware and software for a parallel informati...
详细信息
The overall architecture of the European Declarative System (EDS), ESPRIT II Project 2025 is briefly described. The aim of the project is to design and implement both the hardware and software for a parallel information server. The final system will be used to develop advanced business information systems. The EDS machine is designed to be a high speed backend accelerator, primarily for data/knowledge base applications, serving a range of host computers. It is a message passing multiprocessor with a distributed store, commonly referred to as a shared nothing architecture. Whilst shared nothing architectures are not novel, their application to declarative/symbolic languages is relatively new. The authors describe the EDS software activities at ECRC. A conclusion reporting the current status of the project is given.< >
Conference proceedings front matter may contain various advertisements, welcome messages, committee or program information, and other miscellaneous conference information. This may in some cases also include the cover...
Conference proceedings front matter may contain various advertisements, welcome messages, committee or program information, and other miscellaneous conference information. This may in some cases also include the cover art, table of contents, copyright statements, title-page or half title-pages, blank pages, venue maps or other general information relating to the conference that was part of the original conference proceedings.
The authors explore the notion of node autonomy in distributed computer systems. Some motivations for autonomy are presented. Different facets of autonomy as well as relationships among them are discussed. Finally, th...
详细信息
ISBN:
(纸本)0818608935
The authors explore the notion of node autonomy in distributed computer systems. Some motivations for autonomy are presented. Different facets of autonomy as well as relationships among them are discussed. Finally, they examine how autonomy affects other aspects of distributed computing, including timeliness, correctness, load sharing, data sharing, and data replication.
The author describes the state of the art in models of concurrency. The models are analyzed along two dimensions: communication and computation. Some problems which make it difficult to realize large-scale concurrent ...
详细信息
ISBN:
(纸本)0818608935
The author describes the state of the art in models of concurrency. The models are analyzed along two dimensions: communication and computation. Some problems which make it difficult to realize large-scale concurrent systems are examined. Such problems include compositionality, heterogeneity, debugging, resource management, and concurrency control. Some useful comparisons are drawn to problems in distributeddatabases, and it is argued that solutions to these problems cross disciplinary boundaries. Finally, the author discusses trends in building concurrent computers and provides some expectations for the future.
Skew in the distribution of values taken by an attribute is identified as a major factor that can affect the performance of parallel architectures for relational joins. The effect of skew on the performance of two par...
详细信息
ISBN:
(纸本)0818608935
Skew in the distribution of values taken by an attribute is identified as a major factor that can affect the performance of parallel architectures for relational joins. The effect of skew on the performance of two parallel architectures is evaluated using analytic models. In one architecture, called database machine (DBMC), data as well as processing power are distributed;while in the other architecture, called single processor parallel input/output (SPPI), data is distributed but the processing power is concentrated in one processor. The two architectures are compared in terms of the ratio of MIPS (millions of instructions per second) used by DBMC and SPPI to deliver the same throughput and response time. In addition, the horizontal growth potential of DBMC is evaluated in terms of maximum speedup achievable by DBMC relative to SPPI response time. The MIPS ratio as well as speedup are found to be very sensitive to the amount of skew. These suggest that careful thought should be given in parallelizing database applications and in the design of algorithms and query optimizer for parallel architectures.
Using simulation and probabilistic analysis, the authors study the performance of an algorithm to read entire databases with locking concurrency control allowing multiple readers or an exclusive writer. The algorithm ...
详细信息
ISBN:
(纸本)0818608935
Using simulation and probabilistic analysis, the authors study the performance of an algorithm to read entire databases with locking concurrency control allowing multiple readers or an exclusive writer. The algorithm runs concurrently with the normal transaction processing (on-the-fly) and locks the entities in the database one by one (incremental). The analysis compares different strategies to resolve the conflicts between the global read algorithm and update. Since the algorithm is parallel in nature, its interference with normal transactions is minimized in parallel and distributeddatabases. A simulation study shows that one variant of the algorithm can read the entire database with very little overhead and interference with the updates.
A simulation model has been designed to evaluate the performance of distributed object-oriented database systems. By adjusting parameters, a variety of different hardware configurations and workloads can be represente...
详细信息
ISBN:
(纸本)0818608935
A simulation model has been designed to evaluate the performance of distributed object-oriented database systems. By adjusting parameters, a variety of different hardware configurations and workloads can be represented. The model has been used to study a number of performance issues relating to ORION-2, a distributed object-oriented database system currently being developed. Experiments show that the central server or the local area network can be a performance bottleneck.
暂无评论