Electronic Design Automation
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)
Where: 287 JRG
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).
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:
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
- 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.
- 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.
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:
- Mapping problem for computation to substrate
- Formulating and abstracting mapping problems
- Figures of Merit (Energy, Delay, Throughput, Area, Mapping Time, ...)
- Canonical Representations
- Traditional decomposition pieces (e.g.
logic optimization, covering, scheduling, retiming,
assignment, partitioning, placement, routing)
- Techniques for attacking problems
Dynamic Programming, Search, LP/ILP formulation,
Graph algorithms (network flow, shortest path, ...),
Randomized (incl. SA, Genetic Prog., ),
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.