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: Helpful background: 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).


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 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:


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:


Rough outline of grading:

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.



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.


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:

  author = 	 {Sabih H. Gerez},
  title = 	 {Algorithms for VLSI Design Automation},
  publisher = 	 {John Wiley \& Son Ltd},
  year = 	 {1999},
  note = {general reference}
amazon.com link
  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
  author={Thomas Cormen and Charles Leiserson and Ronald Rivest and
  Clifford Stein},
  title={Introduction to Algorithms},
  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