Electronic Design Automation

Course: ESE535

Units: 1.0 CU
Terms: Spring 2013
When: MW 12--1:30pm
Where: Moore 212
Instructor: DeHon (office hours T4: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).


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


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:


Grading

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.


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 Blackboard (below). Use CAD or drawing tools where appropriate. Handwritten assignments and hand-drawn figures are not acceptable.

All labs will be turned in electronically through the Penn Blackboard website. Once logged in, select ESE535 under My Courses, go to Assignments and click on the assignment you want 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). All file names should have your SEAS login followed by the assignment (e.g. bfranklin-hw1.pdf).

Note that some browsers (notable Google's Chrome) are not currently working with Blackboard. One symptom is that Blackboard will tell you the file format is invalid when you try to upload. If this happens to you, please try a different browser. As far as we know Firefox works.

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.

A written note from the academic dean or medical doctor will be required to gain consideration for extenuating circumstances.

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 blackboard. 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 = 	 {Alagorithms 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