Email: Sanjay.Rajopadhye@colostate.edu
[top]
Course Overview:
Keywords: Systolic Arrays, FPGAs, Loop Parallelization, Silicon
Compilation, SystemsonaChip, Codesign.
This class (colisted as ECE670) is a special topics advanced graduate class,
(previously
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 coprocessors. 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 CS570/EE554
(Computer Architecture), EE571 (VLSI System Design), CS553 (Compilers) and
CS575 (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 CSECE crosslisted 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 credithrs (you may register for
less but you will have to do the same work :)
[top]
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 0138807906
(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).

Loop
Tiling for Parallelism, Jingling Xue, Kluwer Academic
Publishers, Boston ISBN 0792379330.
 References for VHDL There are a number of texts and references
(text as well as online) for VHDL, the hardware description language that we
will use to describe, simulate and implement our architectures.
 VHDL, third Edition Douglas Perry, McGrawHill, ISBN 0071400702.
 VHDL for Logic Synthesis Andrew Rushton, Wiley, 1998.
 The Student's Guide to VHDL, Peter J. Ashenden, Morgan Kaufmann
Publishers, 1998, ISBN 1558605207.
 The
VHDL Cookbook
 Bruno's
link at U Hamburg
 Appropriate
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 0817641491.
 Theory of Integer and Linear Programming, Alexander Schrijver,
Wiley Interscience, ISBN 0471908541.
[top]
Tentative Schedule:
There will be five modules of about 3weeks each, covering the following
topics.
 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)
 Scheduling
 Allocation
 SpaceTime Transformations
 Advanced Synthesis Techniques
 Serialization
 Localization
 Tools for Systolic Synthesis
 Equations as programs: Alpha and MMAlpha.
 Towards Silicon Compilation
 Challenges and Limitations
 Partitioning & Tiling
 Multidimensional schedules
 Code Generation and hardwaresoftware codesign
[top]
Grading Policy:
You grade will be determined by a combination of homeworks (30%), a takehome
midterm (30%) and a final project (40%). You will need to plan the project
early, submit intermediate and final reports and make a final inclass
presentation.
[top]
Homeworks:
 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.
[top]