ECE 459 VLSI Algorithmics

Time & place (New!)

MW 300-420pm         Tech L170 (changed from LG76)

Instructor and office hours

Prof. Hai Zhou
haizhou@ece.nwu.edu
L461 Tech Institute
(847) 491-4155
Office Hours: MW 1100-1200 or by appointment

Overview

Beginning with an inspection on modern hardware design methodology and tools, and a comparison between hardware design and software design (i.e. programming), this course will study synthesis problems in hardware design. It considers how to specify the functionality and requirements of a system, how to synthesis a RTL (Register Transfer Level) design from such a specification (also known as higher level synthesis), and how to synthesis a gate level design from a RTL design and optimize it in terms of performance, area, and power consumption. Balance will be given between design methodology and efficient synthesis algorithms.

Prerequisites

CS 336 or any algorithms course.
VLSI design background is not required.

Required text

• G. De Micheli, Synthesis and Optimization of Digital Circuits. McGraw-Hill, 1994.

Policies

Grading: 20% Homework     40% Exam      40% Project
Late policy: -40% per day

Reading materials

0. EWD340: The humble programmer Pondering about programming--the central task of computing science--Dijkstra urges us "to approach the task with a full appreciation of its tremendous difficulty, ..., stick to modest and elegant programming languages, ..., respect the intrinsic limitations of the human mind and approach the task as Very Humble Programmers." Since here we approach not only programming but also hardware design, we should prepare us with doubly humble minds.

1.  Graph-Based Algorithms for Boolean Function Manipulation by Randal E. Bryant. IEEE Transactions on Computers, C-35-8, pp. 677-691, August, 1986.

Lecture schedule (with slides from De Micheli--they are here for reference, my lectures use blackboard)

Week 1  Modern hardware design methodology and tools: critical review and comparison with programming.
lec1.ps       lec2.ps

Week 2  Hardware specification and architectural synthesis.
lec3.ps

Week 3  Task scheduling algorithms.
lec4.ps       lec5.ps

Week 4  Hardware resource sharing and binding.
lec6.ps

Week 5-6  Two-level combinational logic optimization; BDDs
lec7.ps       lec8.ps       lec9.ps

Week 7-8  Multiple-level combinational logic optimization.
lec10.ps      lec11.ps      lec12.ps

Week 9  Sequential logic optimization: retiming.
lec13.ps

Week 10  Technology mapping (a.k.a. cell-library binding).
lec14.ps

Week 11  Project presentations.

Homework (Some are just exercises and need not to be turned in)

1. To appreciate the difficulty of hardware design and timing issues, design a buffer between two systems with different clocks.

2. Due on 1/21: Chapter 3: 6, Chapter 4: 4.

3. Homework 2: due on 2/6

4. Homework 3: due on 2/20

5. Homework 4: as exercises