CADApps: Animations of VLSI CAD Algorithms

This site presents animations of several well-known algorithms for Computer-Aided Design (CAD) of Very Large Scale Integration (VLSI) circuits. VLSI chips are extremely complex and can contain hundreds of millions of transistors. CAD tools are essential because they allow designers to manage this complexity and complete designs in a timely fashion.

The animations presented here depict algorithms for the design tasks of placement, which involves the assignment of chip modules to physical locations on a chip surface, and routing, which involves the creation of connections between different modules.

These visualizations were originally developed as Java Applets that were intended to be run within a web browsers.  Now that applets are no longer supported, they have been ported to run as free-standing Java applications that can be downloaded, complied and run on a user system. The complete CADApps code repository is available on GitHub at https://github.com/jnestor/CADApps.   Visit the pages below to learn about the individual apps and how to use them.

Routing Algorithm Visualizations

Routing is the process of creating wires that connect together terminals attached to different components in an integrated circuit.  Early maze routing algorithms model the routing surface as a grid and search for a connection from a source terminal to a destination terminal.  Channel routing algorithms constrain the routing to connecting wires in a channel with terminals at the top and bottom of the using a limited number of wiring layers.  Minimum spanning trees and Steiner trees are used to find a way to connect multiple terminals together.

• Channel Routing – Left Edge Algorithm
• Maze Routing
  • Lee Algorithm
  • A* Algorithm
  • Hadlock’s Algorithm
• Spanning and Steiner Trees
  • Rectilinear Minimum Steiner Tree (Prim’s Algorithm)
  • Steiner Tree Demo
  • Borah-Owens-Irwin Steiner Tree Heuristic
• PathFinder Algorithm
• Cache Simulator

Placement Algorithm Visualizations

Placement is the process of assigning physical locations on a wiring surface to a set of modules.  It is usually done before routing but has a strong influence on the effectiveness of the routing.  This visualizations show algorithms for iteratively improving the placement of a set of connected modules of different sizes – a process known as floorplanning.

• • Floorplanning / Placement Display
  • Floorplanning / Iterative Improvement
  • Floorplanning / Simulated Annealing

This site is hosted by Lafayette College and maintained by Prof. John A. Nestor of Lafayette’s Electrical and Computer Engineering Department.