Research On The Partitioning Algorithm Of VHDL Parallel Simulation

Logic simulation is an important component of design automatic of digital circuits. To reduce the simulation time of large circuits, parallel logic simulation has attracted considerable interest in recent years. A better partition algorithm is a key to parallel simulation.In this thesis, several popular algorithms are described and their advantages and disadvantages are listed. Then, a linear-time partitioning algorithm based on a linear ordering of nodes in a circuit for parallel logic simulation is presented. The algorithm is composed of two sections. In the first section the nodes in a circuit are arranged in linear time order to preserve simulation validity. In the second section, the nodes in order are divided into several sets whose root is primary input node and nodes in which can be reached by path; then these sets are united by connectivity among sets into some larger sets, the number of which is equal to that of processors; at last the sets are assigned to each processor by connectivity among sets. The second section consists of three phases to solve three competing goals: to maximize concurrency, to balance processor workload, and to minimize inter-processor communication. Three conflicting goals can be separately considered in each phase so to reduce computational complexity.Most previous algorithms balance the accumulated amount of workload over the whole simulation period instead of the workload at real time. Unlike most other partitioning algorithms, the proposed algorithm preserves circuit concurrency by balancing the workload on processors at real time.