Concurrency preserving partitioning algorithm for parallel logic simulation

A partitioning algorithm for parallel discrete event gate-level logic simul ations is proposed in this paper. Unlike most other partitioning algorithms , the proposed algorithm preserves computation concurrency by assigning to processors circuit gates that can be evaluated at about the same time. As a result, the improved concurrency preserving partitioning (iCPP) algorithm can provide better load balancing throughout the period of a parallel simul ation. This is especially important when the algorithm is used together wit h a Time Warp simulation where a high degree of concurrency can lead to few er rollbacks and better performance. The algorithm consists of three phases and three conflicting goals can be separately considered so to reduce comp utational complexity. To evaluate the quality of partitioning algorithms in terms of preserving c oncurrency, a concurrency metric that requires neither sequential nor paral lel simulation is proposed. A levelization technique is used in computing t he metric so to determine gates which can be evaluated at about the same ti me. A parallel gate-level logic simulator is implemented on an INTEL Parago n and an IBM SP2 to evaluate the performance of the iCPP algorithm. The res ults are compared with several other partitioning algorithms to show that t he iCPP algorithm does preserve concurrency pretty well and reasonable spee dup may be achieved with the algorithm.