The state of the art of concurrency control is reviewed, and the pros and cons of various approaches are compared. The time-stamp interval approach is emphasized due to its promising features. Critical issues and cont...
详细信息
ISBN:
(纸本)0818608978
The state of the art of concurrency control is reviewed, and the pros and cons of various approaches are compared. The time-stamp interval approach is emphasized due to its promising features. Critical issues and control strategy are suggested for future studies in the 1990s. A time-stamp interval approach with parallel validation is presented under the proposed guidelines. simulation results are analyzed to compare the related methods.
The proceedings contain 46 papers. The special focus in this conference is on Computing: VLSI Algorithms and Architectures. The topics include: Optimal parallel evaluation of tree-structured computations by raking (ex...
ISBN:
(纸本)9780387968186
The proceedings contain 46 papers. The special focus in this conference is on Computing: VLSI Algorithms and Architectures. The topics include: Optimal parallel evaluation of tree-structured computations by raking (extended abstract);on finding lowest common ancestors: Simplification and parallelization: Extended summary;A scheduling problem arising from loop parallelization on MIMD machines;scheduling dags to minimize time and communication;computing a perfect matching in a line graph;separation pair detection;graph embeddings 1988: Recent breakthroughs, new directions;simulating binary trees on hypercubes;embedding rectangular grids into square grids;fast parallel and sequential algorithms for edge-coloring planar graphs: extended abstract;Efficient reconfiguration of VLSI arrays: Extended abstract;embedding grids into hypercubes;compaction on the torus: Extended abstract;channel routing with short wires;simple three-layer channel routing algorithms;applying the classification theorem for finite simple groups to minimize pin count in uniform permutation architectures: Extended abstract;a new algorithm for wiring layouts;Input sensitive VLSI layouts for graphs of arbitrary degree;Fast self-reduction algorithms for combinatorial problems of VLSI design;Regular structures and testing: RCC-adders: Extended abstract;optimal parallel algorithms on planar graphs;parallelsimulation and test of VLSI array logic;Universal hashing in VLSI;converting affine recurrence equations to quasi-uniform recurrence equations;better computing on the anonymous ring: Extended Abstract;Network complexity of sorting and graph problems and simulating CRCW PRAMS by interconnection networks: Preliminary version;analysis of a distributed scheduler for communication networks;weighted distributed match-making: Preliminary version;a tradeoff between information and communication in broadcast protocols;families of consensus algorithms.
The state of the art of concurrency control is reviewed, and the pros and cons of various approaches are compared. The time-stamp interval approach is emphasized due to its promising features. Critical issues and cont...
详细信息
The state of the art of concurrency control is reviewed, and the pros and cons of various approaches are compared. The time-stamp interval approach is emphasized due to its promising features. Critical issues and control strategy are suggested for future studies in the 1990s. A time-stamp interval approach with parallel validation is presented under the proposed guidelines. simulation results are analyzed to compare the related methods.< >
Existing hypercube multiprocessors only support one-to-one interprocessor communication. However, multicast (one-to-many) communication is needed for executing many data-parallel algorithms. An optimal multicast algor...
详细信息
Existing hypercube multiprocessors only support one-to-one interprocessor communication. However, multicast (one-to-many) communication is needed for executing many data-parallel algorithms. An optimal multicast algorithm should be able to minimize both the traffic generated and the time required to delivery a message. By modeling this problem as a graph-theoretical problem, the authors conjecture that the finding of an optimal solution is NP-hard. A heuristic greedy multicast algorithm which guarantees a minimized message delivery time is proposed. Routing of multicast messages is done in a distributed manner. simulation results show that the greedy algorithm is very close to an optimal solution.< >
We present a low cost efficient multimicroprocessor designed to study parallel algorithms like fixed point parallel algorithms or parallel algorithms for distributed systems control. This multiprocessor is a collectio...
详细信息
ISBN:
(纸本)0306424096
We present a low cost efficient multimicroprocessor designed to study parallel algorithms like fixed point parallel algorithms or parallel algorithms for distributed systems control. This multiprocessor is a collection of 8 processors sharing a common memory. Its architecture presents some original features that guarantee data consistency and good efficiency. Experimental results are given for synchronous and asynchronous algorithms applied to the Dirichlet problem.
The practical implementation of an integrated system optimization and parameter estimation technique for hierarchical control of steady state systems has been investigated using a distributed hierarchical computer sys...
详细信息
ISBN:
(纸本)0306424096
The practical implementation of an integrated system optimization and parameter estimation technique for hierarchical control of steady state systems has been investigated using a distributed hierarchical computer system. Problems associated with the on-line implementation of the technique have been discussed and methods for dealing with these problems are suggested and have been tested in the real-time situation. It is demonstrated that a double iterative version of the technique has important advantages under real time operation.
The systolic architecture concept has become widely popular in the design of VLSI special purpose architectures for applications like signal processing, image processing, etc. To make this architecture design simple a...
详细信息
ISBN:
(纸本)0444701044
The systolic architecture concept has become widely popular in the design of VLSI special purpose architectures for applications like signal processing, image processing, etc. To make this architecture design simple and attractive, inexpensive computer aided design tools have to be developed. Towards this step, two computer aided design systems namely DIASTOL and MISS are developed at IRISA, Rennes, France. This paper describes the system MISS Machine for Systolic simulation, which is a distributedsimulation system implemented on a dedicated multi-microprocessor architecture.
simulations are among the most expensive of computational tasks. Consequently, different authors [PEAC79], [CHAN81], [JEFF82] have investigated methods for performing fast concurrent simulations on a netwprk of proces...
详细信息
ISBN:
(纸本)9781450373357
simulations are among the most expensive of computational tasks. Consequently, different authors [PEAC79], [CHAN81], [JEFF82] have investigated methods for performing fast concurrent simulations on a netwprk of processors. Basic issues are synchronization (events must be simulated in the order in which, they are executed in the real system), flow control and memory management. There are two basic groups of synchronization algorithms, the blocking algorithms [PEAC79], [CHAN79], [CHAN81] and the Time Warp mechanism [JEFF82]. In blocking algorithms, the simulated system Is represented as a network of logical processes (LP's) or objects and directed links representing communication channels between the objects. Each LP simulates a physical process (PP) in the real system. LP's communicate by exchanging timestamped event messages. An LP is allowed to execute an event with the timestamp t if it is sure it will not receive an event with the timestamp smaller than t in the future. Thus, events are always executed in monotonically Increasing time order. This implies that the output times-tamps are in an increasing time order as well. Assuming that the communication medium preserves the order of messages, they arrive on a particular input link in an Increasing time order. An input buffer is assigned to each input link. This mechanism implies that an LP can always execute the input event with the smallest times-' tamp if each of the input buffers contains at least one event message. In the event that one or more input quaues are empty, the LP is blocked because an event with a timestamp smaller than the timestamps of the waiting events, might yet arrive via an empty input link. Therefore all LP's in the system can be divided at any time into two groups- blocked and unblocked. Only unblocked LP's can execute in parallel (Fig. 1). If all LP's were blocked the simulation would deadlock. This type of the deadlock may occur even when we assume unlimited buffering at the LP's. With
暂无评论