Selection of Applications

Current research in design automation of VLSI systems visualizes system design as a multi-stage process. First the system is described at a behavioral level. In the successive design steps, the description is refined to impose more structure into the design with the filling in of the implementation details. At each step of the refinement process, the behavior of the refined design is verified against the preceding one.

A typical top down design methodology would start with the design description in a hardware description language. This description is compiled into a gate level implementation by a hardware compiler. The gate level design is optimized using combinational and sequential optimization tools. The functionality of the implementation is checked by some verification or simulation tools. The gate level design is mapped into transistors using technology mapping. The transistor level design is further simulated for critical path analysis. And finally transistors are mapped into rectilinear blocks using place and route tools.

  
Table 1: Characteristics of the computation in the applications

Keeping in mind the state of the art in electronic design methodology, we chose the following six tools.

1. Hardware Compiler: VL2MV [6] compiles a Verilog description into a gate level netlist of finite state machines (FSMs) which preserves the system behavior defined in terms of simulated results. After creating the parse tree representing the control and data flow, semantic checking is performed and the hardware gates are generated. The underlying computation is largely symbolic with local memory accesses.
2. Formal Verification Tool: VIS [7] is a unified environment for formal verification, synthesis, and simulation of finite state systems. We chose the problem of combinational verification by building the BDD [8] representation of two circuits and comparing them. The major underlying computation is memory intensive. We have benchmarked machines for equivalence checking with two kinds of underlying BDD computations - random memory access [9] and localized memory access [10].
3. Logic Synthesis Tool: SIS [11] is a logic synthesis system for combinational and sequential circuits. It takes as input a representation of a set of Boolean functions in the form of a finite state machine or a netlist of gates and latches and provides a set of commands that can be used to optimize the circuit for either area, performance or power. We use a script that tries to optimize for area. The underlying computation was mainly symbolic with largely local memory accesses.
4. Switch Level Circuit Simulator: IRSIM [12] models the transistor as a bi-directional switch with a finite ON resistance and capacitances and simulates the resulting RC network using an event driven simulator. The main computation is dynamic partitioning of circuits involving integer operations, and computation of delay times and node voltages using floating point operations. Since all the computation is performed in isolated stages of the circuit, the memory accesses are mostly local in nature.
5. Transistor Level Circuit Simulator: SPICE [13] is a transistor level simulator. The input is a netlist that describes the various circuit elements and their interconnections, a set of models for the circuit elements and a specification of the type of analysis to be performed. A lot of floating point computations are needed involving equation formulation, solution of non-linear equations, and numerical integration.
6. Layout Generator: TimberWolfMC [14] uses simulated annealing to solve the floor-planning and placement problem for macro-cells . The underlying algorithm proceeds in two stages. In the first stage, simulated annealing is used to place the cells approximately. This involves a lot of floating point computations. In the second stage, channel definition, global routing and channel routing are done and the placement obtained from the first stage is refined if it does not meet the constraint. This stage mostly involves symbolic computation.