Algorithms for VLSI Design Automation
Information
The design of integrated circuits is nowadays unthinkable without the aid of design automation tools. This course is about the internals of such tools. What is the reason that some tools need long times to execute? How can problems in design automation be defined in graph-theoretical terms? Which type of algorithms and data structures have been developed to solve these problems?
The course consists of two parts. The first part is the shorter one and introduces concepts such as graph theory, computational complexity and general-purpose methods for combinatorial optimization. The second part reviews selected topics in design automation including placement and routing, simulation, logic and high-level synthesis.
Audience
This course is suitable for the user of design automation tools for ASIC or FPGA who is curious to understand the world behind the tools. Such a user is typically a digital or analog design engineer.
A second category of audience for this course consists of CAD engineers. Following this course will not only provide a better understanding of the tools, but also the skills to perform non-trivial scripting in customizing tools and tool flow.
A third category consists of computer scientists intending to specialize in building design automation tools.
No specific preparation except for elementary knowledge of computer programming is required to follow this course.
Contents
Introduction. Design methodologies. Survey of design tools.
Algorithmic graph theory and computational complexity. Data structures for graph representations. Graph algorithms: depth-first and breadth-first search, Dijkstra's shortest path algorithm, Prim's minimum spanning-tree algorithm.
Tractable and intractable problems. P and NP, NP-completeness. Approximation algorithms and heuristics.
General-purpose optimization methods. Backtracking and branch-and-bound, dynamic programming, integer-linear programming. Local search, simulated-annealing, tabu search, genetic algorithms.
Layout compaction. Constraint graphs. Longest-path algorithms for acyclic and cyclic graphs including the Bellman-Ford algorithm.
Placement and Partitioning. Circuit representation. Constructive and iterative algorithms. Kernighan-Lin algorithm for partitioning.
Floorplanning. Floorplan representations, shape functions, floorplan sizing.
Local routing. Area routing. Channel routing: vertical and horizontal constraints, left-edge algorithm, heuristics for channel routing.
Global routing. Channel ordering. Efficient rectilinear Steiner-tree construction.
Simulation. Gate-level modeling: signals, delays, connectivity. Event-driven simulation. Switch-level modeling.
Logic synthesis and verification. Reduced-ordered binary decision diagrams, applications to verification and synthesis.
High-level synthesis. Hardware models. Data flow. Concepts of allocation, assignment and scheduling. Scheduling algorithms: ASAP, mobility-based, force-directed and list scheduling. Assignment problem and solutions.
Course Organization and Material
The course will consist of about 24 hours of teaching sessions (lectures, as well as some paper-and-pencil problems). So, the course could e.g. be organized as a three-day course or a sequence of 8 weekly sessions of 3 hours each.
The course will be based on the following book:
Gerez, S.H., Algorithms for VLSI Design Automation, John Wiley and Sons, Chichester, (1999).
