Electronic Design Automation

Course: CS137ab

Next Offered: Fall 2005+Winter 2006
Instructor: André DeHon
Prerequisite: basic algorithms and computational theory, some exposure to VLSI (e.g. CS138 and CS181 are more than adequate; CS138 as a co-req is sufficient)
When: MWF10:30am-12:00pm
Where: 287 JRG
URL: <http://www.cs.caltech.edu/courses/cs137/>

Catalog Level Description: Formulation, automation, and analysis of design mapping problems with emphasis on VLSI and computational realizations. Major themes include: formulating and abstracting problems, figures of merit (e.g. Energy, Delay, Throughput, Area, Mapping Time), representation, traditional decomposition of flow (logic optimization, covering, scheduling, retiming, assignment, partitioning, placement, routing), and techniques for solving problems (e.g. greedy, dynamic programming, search, (integer) linear programming, graph algorithms, randomization).

Motivation

Our ability to design interesting and powerful systems is limited by size and complexity---often not from substrate costs, but from human design and management costs. A powerful technique to tackle this limitation is to abstract away details and use higher level building blocks to describe computations and systems. However, when we increase the abstraction it is ultimately necessary to fill in those details---preferably, automatically, without further human intervention. This is a key role of automation and mapping tools: they produce the low-level details, sparing the human designer's time and attention to solve bigger problems.

While this ideal is attractive, the state-of-the-art falls short of giving us the ideal solution for at least two key reasons:

  1. Hard problems---Most of the problems associated with elaborating the details are NP-complete (or worse) and the problem size is increasing over time. Consequently, solving the problems ``optimally'' is seldom tenable. We have a tension of exploiting automation at some cost or expanding precious human time to, perhaps, find a better solution. My observation is that as problems get larger and algorithms refined, we find less and less cases where it is viable to have the human involved in solving the problem even if he/she can find a better solution.
  2. New problems---As our underlying costs, needs, and problems change, it takes time and effort to develop automated solutions to the problems. To date, our problems have evolved more rapidly than they can be solved. Globally, this leaves many problems open or poorly handled. Locally, it means any particular problem you may encounter or create may well be new and unsupported.
As a consequence, novel system designers and researchers exploiting novel media must be prepared to tackle their own automation problems---that is, build their own tools---to advance rapidly into new areas.

Contents

This course is intended to expose students to the key themes, ideas, and techniques in producing correct/efficient/(optimal) mappings of some semantic computation onto a physical computational substrate; in practice, many of the fundamental problems are more widely applicable in engineering than simply mapping computations, but that will be our intellectual focus for this course. The course will not cover the area exhaustively, it but will convey key ideas so the student will know where to look for further details and is aware of the major intellectual tools and analysis developed in this area.

Major themes include:

Terms

The first term will cover the major intellectual ground and present students a series of contained projects as a chance to exercise their understanding of the material. In the second term students will work through all phases of formulation, design, automation, and analysis of some particular automation problem, preferably one which arises in the student's own research.

Preliminary Schedule

Past Offerings

André DeHon