Based on a linear ordering of vertices in a directed graph, a linear-time partitioning algorithm for parallel logic simulation is presented. Unlike most other partitioning algorithms, the proposed algorithm preserves ...
详细信息
ISBN:
(纸本)9780818675393
Based on a linear ordering of vertices in a directed graph, a linear-time partitioning algorithm for parallel logic simulation is presented. Unlike most other partitioning algorithms, the proposed algorithm preserves circuit concurrency by assigning to processors circuit gates that can be evaluated at about the same time. As a result, the concurrency preserving partitioning (CPP) algorithm can provide better load balancing throughout the period of a parallelsimulation. This is especially important when the algorithm is used together with a Time Warp simulation where a high degree of concurrency can lead to fewer rollbacks and better performance. The algorithm consists of three phases, and three conflicting goals can be separately considered in each phase so to reduce computational complexity. A parallel gate-level circuit simulator is implemented on an Intel Paragon machine to evaluate the performance of the CPP algorithm. The results are compared with two other partitioning algorithms to show that reasonable speedup may be achieved with the algorithm.
parallel processing offers a viable way to improve the enormous execution time of the simulation of large VLSI designs. Various parallel logic simulation approaches have been proposed in recent years resulting in some...
详细信息
parallel processing offers a viable way to improve the enormous execution time of the simulation of large VLSI designs. Various parallel logic simulation approaches have been proposed in recent years resulting in some ambiguity as to the best parallelism and address these issues, the authors provide a detailed comparison of all four major types of event-driven logicsimulation algorithms (synchronous, conservative asynchronous with deadlock avoidance, conservative asynchronous with deadlock detection and resolution, and optimistic asynchronous). The comparisons are carried out on an ideal parallel machine capable of extracting all available parallelism in a given algorithm. The simulation execution time, average parallelism and total messages required for a particular simulation algorithm are measured on the ISCAS combinational and sequential benchmark circuits. The use of an ideal parallel machine exposes characteristics of the simulation algorithms independent of the effects caused by particular parallel architectures or implementations. It is shown that a recently developed conservative asynchronous algorithm of the deadlock avoidance type and the optimistic asynchronous algorithm achieve the best parallel execution time results. However, the new conservative algorithm requires much less implementation overhead than the optimistic algorithm.
We discuss a processor scheduling problem for parallel logic simulation of combinational circuits. In the processor scheduling problem, to be discussed in this paper, for logicsimulation using time-first method, the ...
详细信息
We discuss a processor scheduling problem for parallel logic simulation of combinational circuits. In the processor scheduling problem, to be discussed in this paper, for logicsimulation using time-first method, the time needed for each gate evaluation is not given beforehand, and is not constant. This feature distinguishes the processor scheduling problem from typical task scheduling problems. First, we devise newly Algorithm MET to solve the processor scheduling problem. The key idea of Algorithm MET is to determine processor scheduling incrementally and dynamically. Then, experimental evaluations using well-known twelve benchmark combinational circuits show the usefulness of Algorithm MET, compared with conventional static algorithms. We believe that this is a first step to implement parallel logic simulation of combinational circuits.
A recent paper by Bailey [1] contains a theorem stating that the idealized execution times of unit-delay, synchronous and conservative asynchronous simulations are equal under the conditions that unlimited number of p...
详细信息
A recent paper by Bailey [1] contains a theorem stating that the idealized execution times of unit-delay, synchronous and conservative asynchronous simulations are equal under the conditions that unlimited number of processors are available and the evaluation time of each logic element is equal. Further it is shown that the above conditions result in a lower bound on the execution times of both synchronous and conservative asynchronous simulations. Bailey's above important conclusions are derived under a strict assumption that the inputs to a circuit remain fixed during the entire simulation. We remove this limitation and, by extending the analyses to multi-input, multi-output circuits with an arbitrary number of input events, show that the conservative asynchronous simulation extracts more parallelism and executes faster than synchronous simulation in general. Our conclusions are supported by a comparison of the idealized execution times of synchronous and conservative asynchronous algorithms on ISCAS combinational and sequential benchmark circuits.
暂无评论