T-algorithm-based logic simulation on distributed systems

Increase in the complexity of VLSI digital circuit design demands faster logic simulation techniques than those currently available. One of the ways of speeding up existing logic simulation algorithms is by exploiting the inherent parallelism in the sequential version. The authors explore the possibility of mapping a T-algorithm based logic simulation algorithm onto a cluster of workstations interconnected by an Ethernet. The set of gates at a particular level is partitioned by the master task (running on the host processor) among the slave tasks (running on the other processors). Each slave task evaluates the set of gates assigned to it, for the complete simulation period independent of other slave tasks and communicates the evaluated outputs to the master task. After receiving the evaluated output from all the slaves, the master task partitions the gates at the next level and communicates this new set of gates to the slave tasks. The above process is repeated for all the levels in the circuit. The details of the partitioning scheme and its performance are also discussed