CAD for Integrated Circuits

The course takes place in the summer semester.

Dates: always Mondays from 13:45 in room 1332

Course design: 6 CP, 2V+1Ü, 3 SWS

This CAD Algorithm course is aimed at graduate students and serious seniors who want broad exposure to the physical design automation, optimization techniques and data structures inside modern VLSI design tools. Because of the increasingly high complexity of modern chip design, CAD tools become vital for delivering high VLSI system performance. Many of the leading edge CAD algorithms are built upon optimization techniques which will be introduced in this course. The applications of these techniques will be described through realistic VLSI CAD problems, especially VLSI physical design automation algorithms. Physical design automation related issues for the current state of the art will familiarize students with existing techniques in VLSI design. Students will understand the relationships between optimization techniques and various constraints posed by VLSI fabrication and design technology. Critical performance related parameters and their importance in CAD tools will be introduced. The key goals of this course are to prepare students for design and development of CAD tools and for research in physical design automation of VLSI systems.Moreover, the algorithms discussed can be applied to many other contemporary digital design problems with o ly little adaptation.

It's not a circuits class--although we will mention circuits a few times. It's not a digital design class or VLSI design class, in the sense that we'd design a system or a chip. Visit our VHDL course instead for this. Instead, we analyze and design algorithms (aka software) as used in CAD tools.

Our research group explores design optimization algorithms for the next-level design tools.

The topic of the lecture is the automated design of integrated circuits with an emphasis on the methods and algorithms used ("How do the design tools tick?"). The contents keywords: optimization methods; algorithms in physical design: partitioning, placement, wiring; simulation algorithms... 

When designing integrated circuits, the layout is generated as a manufacturing template based on a structural description (gate-level netlist). This process is divided into several steps, for the automation of which corresponding algorithms are used in the CAD system, which work on an internal representation of all design relevant data.

Based on the theoretical basics, the methods and algorithms that form the basis for current industrial CAD systems for chip design are discussed following the design process. This will help to gain a deeper understanding of their functionality as well as any limitations and problems that may occur, and will enable the targeted use of these tools. The understanding of the algorithms is supported by examples and exercises (in the exercises and for self-study).

The lecture covers the following topics:

• design styles,
• levels of abstraction,
• physical design,
• graph theory and data structures,
• partitioning,
• floor planning and placement,
• wiring,
• simulation on different abstraction levels,
• error modeling and simulation.

The learner can

• outline the process and objectives of physical design,
• explain existing or known algorithms,
• combine partial algorithms to form an overall process,
• compare implementations of given algorithms,
• develop implementations of algorithms,
• evaluate placement and wiring results qualitatively,
• explain and classify simulation procedures.

The methods in the synthesis of gate netlists, the so-called high-level synthesis, are covered in detail in the lecture"Synthesis and Optimization...". You can learn more about the target technology FPGA (field-programmable gate array) in the lecture"Reconfigurable Structures" !

The lecture is aimed at Master students of computer science, electrical engineering, mechatronics and FUSE with an interest in technical computer science or with an interest in modern hardware design processes (2V+1Ü, 6 CP).

Learning Objectives: The learner will be able to.

• Outline the process and goals of physical design,
• explain given or known algorithms,
• combine partial algorithms into an overall sequence,
• compare implementations of given algorithms,
• Develop implementations of algorithms,
• Qualitatively evaluate placement and wiring results,
• explain and classify simulation methods.

The lecture also uses pseudocode formulations of algorithms. You should understand pseudocode and also learn to understand it step by step. The re-implementation of algorithms in a programming language will also be practiced.

All course materials and a forum can be found in Moodle. Please register with Moodle in any case, as current information will be disseminated via Moodle.

Books accompanying the lecture:

• Sabih H. Gerez: Algorithms for VLSI Design Automation, John Wiley & Sons; Auflage: 1. Auflage (9. November 1998), ISBN: 0471984892 

• Naveed A. Sherwani:Algorithms for VLSI Physical Design Automation, Springer, Berlin; Auflage: 3. Auflage. (1. Januar 1999), ISBN: 0792383931 

• Michael J. S. Smith: Application-Specific Integrated Circuits, Addison-Wesley Longman, Amsterdam (6. August 1997), ISBN: 0201500221 

• Jens Lienig: Layoutsynthese elektronischer Schaltungen - Grundlegende Algorithmen für die Entwurfsautomatisierung, Springer, Berlin; Auflage: 1 (März 2006), ISBN: 3540296271

• Thomas Lengauer: Combinatorial Algorithms for Integrated Circuit Layout, Teubner Verlag; Auflage: 1 (1990), ISBN: 3519021102 
  

Concerning Graph Theory and Algorithms:

• Robert Sedgewick, Kevin Wayne:Algorithms, Addison Wesley Pub Co Inc; Auflage: 0004 (23. Juli 2010), ISBN: 032157351X 

• Reinhard Diestel: Graphentheorie, Springer, Berlin; Auflage: 3., neu bearb. und erw. A. (2. März 2006), ISBN: 3540213910 

• Volker Turau:Algorithmische Graphentheorie, Oldenbourg; Auflage: 3., überarbeitete Auflage. (21. Oktober 2009), ISBN: 348659057X 

• George T. Heineman, Gary Pollice, Stanley Selkow (Autoren), Mary Treseler (Herausgeber): Algorithms in a Nutshell: A Dektop Quick Reference, O'Reilly Media; Auflage: 1 (21. Oktober 2008), ISBN: 059651624X 

 Also of interest are:

• Rainer Brück: Entwurfswerkzeuge für VLSI-Layout, Hanser Fachbuchverlag (1993), ISBN: 3446174893 

• Bing Lu, S. Sapatnekar, Ding-Zhu Du (Herausgeber): Layout Optimization in VLSI Design, Springer, Berlin; Auflage: 1 (1. Januar 2001), ISBN: 1402000898

On the subject of graph theory and algorithms:

• Robert Sedgewick, Kevin Wayne:Algorithms, Addison Wesley Pub Co Inc; edition: 0004 (July 23, 2010), ISBN: 032157351X. 

• Reinhard Diestel: Graph Theory, Springer, Berlin; edition: 3rd, newly edited and updated (March 2, 2006), ISBN: 3540213910 

• Volker Turau:Algorithmic Graph Theory, Oldenbourg; edition: 3rd, revised ed. (October 21, 2009), ISBN: 348659057X. 

• George T. Heineman, Gary Pollice, Stanley Selkow (authors), Mary Treseler (editors): Algorithms in a Nutshell: A Dektop Quick Reference, O'Reilly Media; Edition: 1 (October 21, 2008), ISBN: 059651624X. 

 Further interesting are:

• Rainer Brück: Design Tools for VLSI Layout, Hanser Fachbuchverlag (1993), ISBN: 3446174893 

• Bing Lu, S. Sapatnekar, Ding-Zhu Du (editors): Layout Optimization in VLSI Design, Springer, Berlin; Edition: 1 (January 1, 2001), ISBN: 1402000898.

The examination can be taken in the form of an oral examination. The exact modalities will be announced in the event. The oral examination can be complemented by a programming homework.