Edward H. Frank

A Data-driven Multiprocessor for Switch-level Simulation of VLSI Circuits Degree Type: Ph.D. in Computer Science
Advisor(s): Robert Sproull
Graduated: May 1985

Abstract:

In this dissertation I describe the algorithms, architecture, and performance of a computer called the F AST -1 a special-purpose machine for switch-level simulation of VLSI circuits. The F AST -1 does not implement a previously existing simulation algorithm. Rather its simulation algorithm and its architecture were developed together. The F AST -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 F AST -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 F AST -1 simulating actual circuits, including some with over twenty thousand transistors. These measurements indicate that a hardware-implemented, uniprocessor F AST -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 F AST -1 multiprocessor, that is constructed using multiple F AST -1 uniprocessors that are interconnected by one or more broadcast busses. In order for a F AST -1 multiprocessor to exploit the parallelism available in simulations, the F AST -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 F AST -1 and fast heuristic partitioning algorithms.