A data-driven multiprocessor for switch-level simulation of vlsi circuits
Edward H. Frank · 1985
In this dissertation I describe the algorithms, architecture, and performance of a computer called the FAST-1--a special-purpose machine for switch-level simulation of VLSI circuits. The FAST-1 does not implement a previously existing simulation algorithm. Rather its simulation algorithm and its architecture were developed together. The FAST-1 is data-driven, which means that the flow of data determines which instructions to execute next. Data-driven execution has several important attributes: it implements event-driven simulation in a natural way, and it makes parallelism easier to exploit. Although the architecture described in this dissertation has yet to be implemented in hardware, it has itself been simulated using a 'software implementation' that allows performance to be measured in terms of read-modify-write memory cycles. The software-implemented FAST-1 runs at speeds comparable to other software-implemented switch-level simulators. Thus it was possible to collect an extensive set of experimental performance results of the FAST-1 simulating actual circuits, including some with over twenty thousand transistors. These measurements indicate that a hardware-implemented, uniprocessor FAST-1 offers several orders of magnitude speedup over software-implemented simulators running on conventional computers built using similar technology. Additional speedup over a uniprocessor can be obtained using a FAST-1 multiprocessor, that is constructed using multiple FAST-1 uniprocessors that are interconnected by one or more broadcast busses. In order for a FAST-1 multiprocessor to exploit the parallelism available in simulations, the FAST-1 representation of circuits must be carefully partitioned onto the processors. Although, even simple versions of the partitioning problem are NP-complete, I show that an additional order of magnitude speedup can be obtained by using a multiprocessor FAST-1 and fast heuristic partitioning algorithms.