Keywords: Systolic Arrays, FPGAs, Loop Parallelization, Silicon
Compilation, Systems-on-a-Chip, Codesign.
This class (co-listed as ECE670) is a special topics advanced graduate class,
offered in Fall 2001). It deals with the foundations of high performance,
parallel embedded and reconfigurable systems. Specifically, we will study how
to design highly parallel, special purpose architectures (called systolic
arrays) for compute/data intensive loop programs. We will
implement them on FPGA based reconfigurable co-processors. We will
also study how these arrays may be designed automatically: the issues involved
in compiling programs directly to silicon.
Prerequisites: You should have taken at least two of CS-570/EE-554
(Computer Architecture), EE-571 (VLSI System Design), CS-553 (Compilers) and
CS-575 (Parallel Processing). You should have very high mathematical maturity
(especially in linear algebra, and optimization): 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 have questions.
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 4 credit-hrs (you may register for
less but you will have to do the same work :-)
Textbooks and References:
There is no required text. We will usually work off papers in the literature
and lecture notes. In addition, the following is a set of useful references
- Systolic Algorithms and Architectures, Patrice Quinton & Yves
Robert, Prentice Hall International / Mason, 1991. ISBN 0-13-880790-6
(translation of the French original). This excellent book is out of print.
However, we have permission from the authors to make photocopies. I will try
to make this available (there may be a nominal charge).
Tiling for Parallelism, Jingling Xue, Kluwer Academic
Publishers, Boston ISBN 0-7923-7933-0.
- References for VHDL There are a number of texts and references
(text as well as on-line) for VHDL, the hardware description language that we
will use to describe, simulate and implement our architectures.
- VHDL, third Edition Douglas Perry, McGraw-Hill, ISBN 0071400702.
- VHDL for Logic Synthesis Andrew Rushton, Wiley, 1998.
- The Student's Guide to VHDL, Peter J. Ashenden, Morgan Kaufmann
Publishers, 1998, ISBN 1-55860-520-7.
link at U Hamburg
Usage of VHDL: The Synthesis Point of View, an article (tech memo) by Roy
and Vemury, U of Cincinnati. This is fairly old (1992), but prety useful.
- xtrj.org has a
collection of VHDL related links
- 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.
There will be five modules of about 3-weeks each, covering the following
- Getting Started (a panorama)
- Introduction: Context and Motivation
- Review of VHDL by Kolin
Paul, Postdoc Researcher, CS Department, CSU (there's a wealth of resource material that he's compiled for this
class, and more is available off his homepage).
- FPGA's and Reconfigurable Computing
- Intro to Systolic Arrays
- Complete Design/Implementation Trajectory
- Systolic Arrays
- Examples of Systolic Architectures and Algorithms
- Using equations to describe systolic arrays.
- Systolic Array Synthesis (from equations)
- Space-Time Transformations
- Advanced Synthesis Techniques
- Tools for Systolic Synthesis
- Equations as programs: Alpha and MMAlpha.
- Towards Silicon Compilation
- Challenges and Limitations
- Partitioning & Tiling
- Multidimensional schedules
- Code Generation and hardware-software co-design
You grade will be determined by a combination of homeworks (30%), a take-home
midterm (30%) and a final project (40%). You will need to plan the project
early, submit intermediate and final reports and make a final in-class
- Homework 0: due Jan 28 in class, sent by email. Prove that the
product of two band matrices is also banded, and modified sorting algorithm
with bidirectional flow.
- Homework 1: due in
two parts: Feb 4 and Feb 16.