CS670 Fall 2001: Architectures of Advanced Systems
High Performance Embedded Systems-on-a-Chip
Class meets: Tu-Th 16:30 - 17:45, USC 310B (601 S Howes St)
This class (co-listed as ECE670) could also have been listed as an advanced
topics class in programming languages (CS653) or in parallel computing
(CS675). It will cover the foundations of high performance parallel embedded
systems. Being a CS-ECE cross-listed course, I hope that we can
synergistically build on the the strengths and backgrounds of all students.
Although CS670 is a variable credit course, this one is for 4hrs (you may
register for less but you will have to do the same work :-)
We will essentially study the development of the polyhedral model;
for reasoning about massively parallel computations. This course will
involve a fair bit of theory: linear and integer programming, discrete
optimization, some notions of semantics and functional languages. It will
also involve some pragmatic machine-oriented work (FPGA's, VLSI circuits,
etc.) The prerequisites are essentially advanced graduate standing and
mathematical maturity: you don't have to know all the math beforehand, but you
should not be afraid to pick it up if needed. Please come and see me if you
Keywords: systems-on-a-chip, loop parallelization, polyhedral model,
silicon compilation, systolic arrays, FPGAs, power/energy optimization, cyclic
scheduling, functional/equational programming, data-parallel languages,
iteration space tiling, data partitioning.
Grading: Your final grade will largely be based on a research report
that you will write (intermediate steps towards this final report will also be
considered in determining the grade). You may also be required to do a small
independent study on a specific topic (common to all students), namely
"iteration space tiling", which will require reading and reviewing some of the
key early papers on this topic. Other forms of assessments (mid-terms,
assignments, etc.) are also possible, but will not count that heavily.
Textbook and References
There is no required text. We will work off current
papers in the literature. The following reference texts would be
Tiling for Parallelism, Jingling Xue, Kluwer Academic
Publishers, Boston ISBN 0-7923-7933-0.
Hardware/Software Co-Design: Principles and Practice,
J. Staunstrup and W. Wolf (Eds.), Kluwer, 1997.
Custom Memory Management Methodology, F. Catthoor et al.,
Systolic Algorithms and Architectures, Patrice Quinton
& Yves Robert, Prentice Hall International / Mason, 1991. ISBN
0-13-880790-6 (translation of the French original)
Scheduling and Automatic Parallelization, Darte, Robert
and Vivien, Birkhauser, ISBN 0-8176-4149-1
Theory of Integer and Linear Programming, Alexander
Schrijver, Wiley Interscience, ISBN 0-471-90854-1
Course Outline and (tentative) Schedule The lectures will proceed in
"concentric circles", starting with a short and superficial overview of the
whole semester, followed by a more detailed view of some of the same concepts,
and finally, in-depth study of some specific techniques, eg. scheduling,
tiling, I/O, etc. As the course proceeds, this page will evolve to contain
copies of the lecture transparencies, exercises (and possibly solutions),
Week 1: Introduction, Motivation and General Overview.
Week 2: Systolic Arrays and Systolic Synthesis. The material
will be based on Section 8.3 of Mead and Conways' classic VLSI textbook (a
guest article by Kung and Leiserson, which I will arrange to have photocopied
for you), the chapter from Quinton-Robert that you already have, and this
book chapter (only Sections 1 and 2 are relevant).
Week 3: Systolic Synthesis Overview (contd.) & The GKT Optimal
Week 4: VHDL, Cameron, Sassy and Review
Week 5: Systolic Synthesis Overview (concl); Alpha
- Tuesday Sept 18: Monica Chawathe's talk on the
Sassy compiler. My lecture notes on: (i) I/O &
Control in Systolic Synthesis, and (ii) some motivations for why you should
program with equations. Finally, for another very cute family of algorithms
that can be easily described by mathematical equations, take a look at the algebraic path problem
- Thursday Sept 20: lecture notes on the Alpha
language. See also this (fairly
terse) document that describes the Alpha language. Just a test.
Week 6: Alpha (contd)
- Tuesday Sept 25: We continue with a discussion of Alpha (here are my lecture notes. You may also find more information
aout the language from Doran Wilde's report The Alpha Language,
which is extracted from Mauras' PhD thesis. I'd say that this report is the
closest there is to an English translation (plus Doran's interpretation, so
don't take everything it says as the gospel) of the thesis. In some aspects
the report is more pragmatic, than my (fairly theoretical) view. A wealth of
information about Alpha and MMAlpha can be obtained from the Alpha home page.
- Thursday Sept 27: Executing Alpha programs. Here are my lecture notes. This is based on a simple (fairly
obvious) operational semantics of Alpha (as explained in Doran's report).
Details of the strategy may be found in [Wilde,
Rajopadhye, ASAP 1995]
Week 7: Review Week
- Tuesday Oct 02: Stacy and Howard presented an overview of VLSI design
starting right from rectangles, masks, stick diagrams, transistor sizing, all
the way through the tool chain. Here are their lecture
- Thursday Oct 04: Review of Alpha and (first) intro to MMAlpha. Many
documents are available form the Alpha
The demo files containing (i) the script of Mathematica/MMAlpha commands, (ii)
the trace of the execution of MMAlpha, and (iii) the Alpha and VHDL programs
produced may be found in this directory. In particular you
may look at the mathematica
script and the trace files
for the Getting-Started notebook, and the script and trace files for the Intro notebook.
Week 8: MMAlpha (contd.) and Dependence analysis, single assignment
Week 9: Scheduling
- Tuesday Oct 16: Scheduling URE's and SURE's with (1-D) affine schedules.
Here are my lecture notes, including the exercise
to find the longest path in the extended dependence graph
- Thursday Oct 18: Multidimensional schedules, and scheduing ARE's
and SARE's just a test.
Week 10: More Scheduling
- Tuesday Oct 23: Gautam's lectures on scheduling ARE's with reductions.
Here are his
- Thursday Oct 25: Gautam's lecture (contd.) just a test.
Week 11: Localization & Tiling
- Tuesday Oct 30:
- Thursday Nov 01:
Week 12: Localization & Tiling
- Tuesday Nov 06:
- Thursday Nov 08:
Week 13: More Tiling
- Tuesday Nov 13:
- Thursday Nov 15:
Week 14: Compilation & Code Generation
- Tuesday Nov 27:
- Thursday Nov 29:
Week 13 & 14: (Silicon) compilation of
Since this an advanced course, a large part of your grade is based on the work
you do for a research project and the report you turn in. Essentially, you
may think of this as a paper that you submit to a conference. What will be
evaluated is your work/research, but the specific object evaluated is the
report that you write (supplemented if necessary, by discussions,
demonstrations in class and with me). It is therefore very important that you
master the art of technical writing. The usinversity has resources available explicitly for
this, and you are more than welcome to use them.
There is considerable freedom in choosing your specific project. Here are
a few suggestions.
Final Report Format
The final report should be written using standard word-processing software
LaTeX (preferred) or MS word like a regular research paper (about a dozen
pages), and contain the following standard sections:
- Abstract: a summary of the work and a few lines about
- Introduction: problem definition, it's importance and impact,
and paper organization
- Main section(s): detailed description of your work, illustrative
examples showing your solution, and theoretical justification, experimental
validation (make sure that you describe this in enough detail that an
interested reader can duplicate the experiments) etc.
- Related Work
- Future Work and Open Problems
Three intermediate reports are intended to help you build your way towards the
For your final report you will directly use the first two (Intro and Related
Work). But remember, the related work evolves: as you work, you will
encounter new papers/literature on the topic, some new directions will force
you to look elsewhere, etc. Rule of thumb: if your final Related Work section
is identical to the report you submitted, then the project was
probably too predictable.
The plan of Action and the Status Report will help you do the actual work, but
parts can be incorporated into the final report and also help you develop its
- Proposal: This two-page report is intended to get you on your
way. I want you to identify the problem, discuss why it's important, and
touch upon the related work: identify the papers that you intend to read.
- Related Work and Plan of Action: This one/two page report should
critically discuss the state of the art: what has been done
previously, its limitations, etc. Develop a plan of attack to address the
limitations and propose a schedule for the work (discuss it with me
- Status Report: This (4-5 page) report should describe your
progress, the pitfalls that you encountered, the modifications that you
propose, and hence the updated plan of attack. Also describe the parts of the
plan that went smoothly and confirmed your original hypotheses.
- Pick a project: September 4
- Proposal: September 11
- Related Work: September 27
- Status Report: November 1
- Final Report: December 7