jvb@cs.duke.edu (Jack V. Briner, Jr.) (09/19/90)
My dissertation titled "Parallel Mixed-Level Simulation of Digital Circuits Using Virtual Time" is now available to researchers. The abstract appears at the end of this article. We will also be distributing the sequential version of the sequential simulator (LDVSIM) via ftp in the near future. The simulator provides mixed-level simulation of digital circuits at the gate (or higher) and switch-timing levels. The switch-timing levels are based upon Chris Terman's work (MIT) as updated by Mark Horowitz and C. Y. Chu (Stanford). Please send me US MAIL (not email) if you would like a copy either the program or the dissertation. Depending on the volume of request for the dissertation, a charge may have to be imposed. Copies are also available from UMI. My current address is: Jack Briner Department of Mathematics University of North Carolina at Greensboro Greensboro, NC 27412 Abstract ======== This dissertation studies the simulation of mixed-level, digital circuits on parallel computers using the virtual time paradigm introduced by David Jefferson. Virtual time is an appropriate mechanism for parallel simulation of digital circuits because its asynchronous nature allows varying levels of event intensity to be handled with minimal overhead. Other models, such as the conservative models of Chandy and Misra, may require extensive resources to handle idle portions of the circuit. A model of parallelism, using a greedy deterministic processor scheduling algorithm, demonstrates that circuits have significantly more parallelism than previously thought, provided asynchronous simulation is used. Previous implementations of virtual time simulation have used periodic breakpointing, periodic calculation of global virtual time, and fossil collection on demand. Such maintenance computations are performed better if done regularly, reducing overhead and balancing the simulation. State, if saved incrementally on each event, keeps the natural, demand-driven computation of discrete event simulation. Global virtual time can be calculated frequently, using a new tree-based algorithm. With a close bound on the global virtual time, fossils can be collected regularly, reducing memory usage and relieving the need for complicated state management operations. By keeping all processors within a specified bounding window of the global virtual time, processors are not allowed to get far out of synchronization, reducing rollback costs. Existing models of partitioning are inadequate for virtual time simulation. For transistor level model evaluations, random partitioning performs satisfactorily because the ratio of computation to communication is high. For gate level modelling, where event handling is more frequent, partitioning must reduce communication costs and also must promote concurrent model evaluations. However, such partitioning algorithms may be expensive. An implementation of virtual time simulation, known as PLDVSIM, is measured on BBN's GP1000 parallel processing system. PLDVSIM is functionally equivalent to LDVSIM, allowing existing mixed-level simulations to be used without modification. Circuits from 600 to 32,000 gates are simulated in parallel and compared against the tuned, sequential algorithm. Speedups in the range of 10 to 25 are achieved with 32 processors. <Please use US MAIL for requests! I will deny requests by email!>