Electronic Design Automation
Course: ESE535
Units: 1.0 CU
Terms: Spring 2015
When: MW 12--1:30pm
Where: David Rittenhouse Laboratory (DRLB) 3N6
Instructor: DeHon (office hours T4:15pm--5:30pm)
Required Prerequisite:
- digital logic (e.g. at least CIS240 or ESE170);
- programming (at least CIS121); will need to
be comfortable writing ~1-3K lines of code and working with a large,
existing code base
Helpful background:
- algorithms and computational theory (e.g. CIS320)
- experience with modest software projects (e.g. CIS350)
- further experience with digital logic designs (e.g. CIS371)
- exposure to VLSI (e.g. ESE370 or ESE570)
Offered: roughly in alternate years with ESE534
URL: <http://www.seas.upenn.edu/~ese535/>
Quick Links: [Motivation]
[Grading]
[Syllabus]
[Policies]
[Reading]
[Previous Offerings]
[Piazza]
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,
satisfiability).
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:
- 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.
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 and Objectives
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, but it 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.
Students will learn:
- Freedom that exists in design mappings and how that freedom can be
exploited to reduce design costs
- How to formulating and abstract optimization problems associated
with design mapping
- How to decompose large mapping problem into pieces, including the
traditional decomposition for EDA (e.g.
logic optimization, covering, scheduling, retiming,
assignment, partitioning, placement, routing)
- Standard techniques for attacking these problems including
the ones that are naturally combinatorial
(e.g.
Dynamic Programming, Search, LP/ILP formulation,
Graph algorithms (network flow, shortest path, ...),
Randomized (incl. SA, Genetic Prog., ),
Greedy, Satisfiability)
- Traditional design objectives (e.g. Energy, Delay, Throughput, Area, Mapping
Time, ...) and how to abstract cost functions from physical phenomena
- Canonical representations for problems
- How to evaluate the quality of a design mapping and mapping approach
- How to implement design automation algorithms
Projects
Course includes a series of programming assignments following a project theme.
These are usual new challenges motivated by emerging optimization metrics
(e.g. power, fault tolerance) or advancing technologies. Past project
themes have included:
- defect-aware logic mapping
- performance-constrained mappings to minimize Energy for gate-level designs mapped to multicontext
programmable gate arrays (e.g. DPGA, Tabula).
- power optimization
- spatial/parallel implementation of optimizations
- concurrent error detection (in logic, in FSMs)
- simultaneously placement and clustering
- schedule, common sub-expression elimination, 1D placement for computing floating-point equations
Grading
Rough outline of grading:
- Participation (reading, class discussion) [10%]
- Assignments [30%]
- Final Project [40%]
- Final Exam [20%]
Writeups must be done in electronic form. Use CAD or drawing
tools where appropriate. Electronic submission required (see homework
turnin instructions below).
Handwritten assignments and hand-drawn figures are not
acceptable.
Policies
Collaboration
Each student is expected to do his/her own work -- including developing the details and writing the solutions.
For the algorithm and programming assignments, you are free to discuss basic strategies and
approaches with your fellow classmates or others, but all detail design, coding,
implementations, analysis, and writeups should always be the work of
the individual. (you may not share code.)
If you get advice or insights from others that
significantly influenced your work, please acknowledge this in your
writeups. More specific policy for projects will be included with the
project assignments.
You may help each other understand how to use the CETS computers, compilers
and debuggers, and course provided code.
In general, you are expected to abide by Penn's
Code of Academic Integrity. If there is any uncertainty, please ask.
Homework Turnin
Writeups must be done in electronic form and submitted through Canvas
(below). Use CAD or drawing tools where appropriate.
Handwritten assignments and hand-drawn figures are not acceptable.
All assignments will be turned in electronically through the Penn Canvas
website. Log in to canvas with your PennKey and password, then select ESE 535 from the Courses and Groups dropdown menu.
Select Assignments from the links on the left and select the assignment for
which you wish to submit. Attach all files and click
submit (See specific instructions in assignments. We will typically want a
single PDF with the description and a tar file for
the programming solutions).
Late Assignments
Assignments must be turned in by the published due date to receive full
credit. We deduct 10% of the assignment grade for each day late.
If assignments or exams fall due on a religious holiday, please make arrangements
with the instructor to accommodate before the posted due date.
Absentees
Use the Penn Course Absence Report (CAR) in Penn-in-Touch to report
absences.
Credit Adjustment
Make sure you call any problems with grading immediately and not later than
the next class meeting after they are returned or posted on canvas. To
submit a request for a review of a credit assignment on an assignment send
an email stating the nature of the problem and the remedy you desire. We
will not consider any requests for grade adjustments that are submitted
later than the one week grace period after the grades are posted on
blackboard. You are responsible for checking your posted grades in a timely
manner.
Reading, Text, and Lectures
Roughly one paper per lecture is expected reading. Most of the papers
will be electronically available through links from the syllabus page.
You will
be reponsible for acquiring those copies for yourself.
Citations for additional reading material will be
posted on the web along with the detailed syllabus (most of those also come
with links to the papers themsleves). There is no
required text as I will be pulling together material form many places.
Since this course is not based upon any particular text, following
lecture will be essential to keep up with the course material.
For those that want integrated references to backup the reading, consider
the following:
@Book{gerez_vlsida99,
author = {Sabih H. Gerez},
title = {Algorithms for VLSI Design Automation},
publisher = {John Wiley \& Son Ltd},
year = {1999},
note = {general reference}
amazon.com link
@Book{reconfigurable_computing_mk2008,
editor = {Scott Hauck and Andr\'e DeHon},
title = {Reconfigurable Computing: The Theory and Practice of FPGA-Based Computation},
publisher = {Elsevier},
year = 2008,
series = {Systems-on-Silicon}
note = {has a section on major components of tool flow for FPGA-like devices}
amazon.com linnk
@book{clrs_algorithms_mitpress2001,
author={Thomas Cormen and Charles Leiserson and Ronald Rivest and
Clifford Stein},
title={Introduction to Algorithms},
year=2001,
edition={2nd},
publisher={MIT Press},
note = {general algorithms reference}
}
amazon.com link
Previous Offering
Past Offerings
At Caltech, Prof. DeHon taught this as a two quarter sequence, with the bulk of the
instructional material in the first term.
The second term was focused on a large, student-selected project, but did
include additional topics.
André DeHon