CS 670 DV, Spring 2003

[top]

Course Overview:

This class (co-listed 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 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 :-) [top]

Textbooks and 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).
• Loop 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.
  • 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 0-8176-4149-1.
• Theory of Integer and Linear Programming, Alexander Schrijver, Wiley Interscience, ISBN 0-471-90854-1.

Tentative Schedule:

• 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
  • Space-Time 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 hardware-software co-design

Grading Policy:

[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]