CS 560 Spring 2008: (tentative) Detailed Schedule

Month	Day		Week	Lecture	Assignments			Readings
					Posted	Due
					Posted	HW	Project
Jan	22	Tue	1	Intro: Fine Grain Parallel Architectures (bubble/insertion sort)				Notes 1
	24	Thu	1	Equations as programs	HW 1
	29	Tue	2	Equations as programs
	31	Thu	2	Reductions		HW 1
Feb	5	Tue	3	Executing Equations and Compiling Equations (scribes' notes)	HW 2		PCP1
	7	Thu	3		Rd 1
	12	Tue	4	[Kung 1982] discussion: Systolic Filters		Rd 1		[Kung82]
	14	Thu	4	Systolic Sorter revisited (+ CoB brief intro)			PCP2	Sorter
	19	Tue	5	(more CoB) + Systolic Synthesis (Slides, Slides2)
	21	Thu	5	Foundations (Affine Functions, Polyhedra, Reresentation)		HW 2	PCP3	[LQR99]
	26	Tue	6	Classic Systolic Arrays (band matrix computations)	HW 3		PCP4	[KL80]
	28	Thu	6	More Classic Arrays (band matric computations)				[KL80]
Mar	4	Tue	7	Change of Basis details		HW 3	PCP5	[GKT79]
	6	Thu	7	Sorter Derivation (geometric view); OSP (CRCW PRAM)				[CLRS01]
	11	Tue	8	GKT architecture and proof			PCP6	Cheat Sheet
	13	Thu	8	HW Solutions; Review; Midterm (due March 12, 11:59 pm)				Cheat Sheet
	18	Tue	9	Spring Break (no classes)
	20	Thu	9	Spring Break (no classes)
	25	Tue	10	Alpha Introduction				Alpha
	27	Thu	10	Alpha Introduction			PCP7	Alpha
Apr	1	Tue	11	MMAlpha
	3	Thu	11
	8	Tue	12		HW 4			NN Example
	10	Thu	12					NN Example
	15	Tue	13	Advanced Alpha (foundations)				Alpha (2)
	17	Thu	13	Advanced Alpha (foundations)		HW 4	PCP11	Alpha (2)
	22	Tue	14	Localization, Serialization, Scheduling and Allocation				[LQR99]
	24	Thu	14	Localization, Serialization, Scheduling and Allocation				[LQR99]
	29	Tue	15	Kahn Process Networks				[Kahn 74]
May	1	Thu	15	Kahn Process Networks				[Kahn 74]
	6	Tue	16	Return to GKT (derivation)				[GKT99]
	8	Thu	16	Project Poster Presentations			PCP12
	13	Thu	17	Final Exam Week			PCP13
	15	Thu	17	Final Exam Week			PCP13

References:

[CLRS 01] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, "Introduction to Algorithms". MIT Press; 2nd edition (September 1, 2001).
[Kahn 74] G. Kahn, "The Semantics of a Simple Language for Parallel Programming", Proceedings of International Federation for Information Processing Congress 74, pp. 471-475, North Holland Publishing Co., Aug 1974.
[Kung 82] H.T. Kung, "Why Systolic Architectures?" IEEE Computer. Jan 1982, pp. 37-46.
[KL80] H.T. Kung, C. Leiserson, "Algorithms for VLSI Processor Arrays". Introduction to VLSI Systems, C. Mead and L. Conway, Eds., Addison-Wesley 1980.
[GKT79] L. T. Guibas, H. T. Kung, and C. D. Thompson, "Direct VLSI implementation of combinatorial algorithms," in Proc. Cal. Tech. Conf. VLSI, Jan. 1979, pp. 509-525.
[LQR99] D. Lavenier, P. Quinton, and S. Rajopadhye, "Advanced systolic design". In K. K. Parhi and T. Nishitani, editors, Digital Signal Processing Multimedia Systems, Signal Processing Series, chapter 23, pages 657-692. Marcel Dekker, 1999.