Optimization Techniques for Distributed Logic Simulation

Gate level simulation is a necessary step to verify the correctness of a circuit design before fabrication. It is a very time-consuming application, especially in light of current circuit sizes. Since circuits are continually growing in size and complexity, there is a need for more efficient simulation techniques to keep the circuit verification time acceptably small. The use of parallel or distributed simulation is such a technique. When executed on a network of workstations, distributed simulation is also a very cost-effective technique. This research focuses on optimization techniques for Time Warp based gate-level logic simulations. The techniques which are described in this thesis are oriented towards distributed platforms. The first major contribution of this thesis was the creation of an object oriented distributed simulator, XTW. It uses an optimistic synchronization algorithm and incorporates a number of known optimization techniques targeting different aspects of distributed logic simulation. XEQ, an O(1) event scheduling algorithm for this simulator was developed for use in XTW. XEQ enabled us to execute gate level simulations up to 9.4 times faster than the same simulator using a skip-list (O(lg n)) event queue. rb-message -- a mechanism which reduces the cost of rollback in Time Warp was also developed for use in XTW. Our experiments revealed that the rb-message mechanism reduced the number of anti-messages sent in a Time Warp based logic simulation by 76%on average. Moreover, based on the observations that (1)not all circuits should be simulated in parallel and (2) different circuits achieve their best parallel simulation performance with a different number of compute nodes, an algorithm that uses the K-NN machine learning algorithm was devised to determine the most effective software and hardware combination for a logic simulation. After an extensive training regime, it was shown to make a correct prediction 99% of the time on whether to use a parallel or sequential simulator. The predicted number of nodes to use on a parallel platform was shown to produce an average execution time which was not more than 12% of the smallest execution time. The configuration which resulted in the minimal execution time was picked 61% of the time. A final contribution of this thesis is an effort to link together commercial single processor simulators making use of Verilog PLI.