Logic, RTL and behavioral simulation are tasks which need to be performed repeatedly throughout the design cycle of modern digital systems. It is crucial, therefore to speed up these tasks as much as possible, while retaining the ability to handle ever larger designs. Suitably designed parallel algorithms can achieve these goals. In this paper, we investigate approaches to parallelization of compiled event driven simulation of models written in VHDL. The serial algorithm is a compiled algorithm, but has the advantage of supplying some delay information. We show that traditional methods of extracting task parallelism from arbitrary graphs, such as list scheduling are rendered ineffective by the extremely small computational grainsizes, even on shared memory multicomputers. Hence we are forced to rely on partitioning based methods which prefer replication of computation to frequent communication. This opens up interesting problems in reducing the amount of redundant computation while maintaining load balance. As part of solving this problem, we propose and solve an important theoretical problem called Workload Minimization of Overlapping Tasks (WMOT). We have implemented our parallel algorithms in a parallel VHDL simulator called PTHREAD-VHDL using the POSIX pthreads library on a variety of platforms. We demonstrate speedups of 3.5 to 4 on 8 processors on a Sun SparcServer 1000E symmetric shared memory multiprocessor (SMP), when compared to our efficient serial algorithm running on a single node.

Gzipped Postscript version of the paper