CS 560 Spring 2011: (tentative) Detailed Schedule

Combined on-campus on-line sections

In general, the schedule below is tentative and will be tweaked as we go along in the semester. There are four main components: Lectures which are taped and available in the "Video" column), Discussions, Assignments and Readings. Students are expected to actively participate in all four, especially the on-line discussions where a number of problems and examples will be worked out.

Month	Day		Week	Lecture	Video	Discussion	Homework		Readings
							Posted	Due
Jan	18	Tue	1	Introduction: Fine Grain Parallelism (slides)	Jan 18	Setting up AlphaZ (wiki)	HW1	HW1	Foundations1 Alphabets [WiRa95]
	20	Thu			Jan 20	Mat.Mult & TMM
	25	Tue	2	Equations as programs: Alpha/Alphabets & AlphaZ Compiling and executing Equations (scribes' notes, slides)	Jan 25
	27	Thu			chat	TMI
Feb	1	Tue	3	Complexity Reduction through equational reasoning: distributivity and factorization (Gautam's slides)	Feb 1				[GR06]
	3	Thu			Feb 3	LoS & Scans	Disc2
	8	Tue	4	Complexity Reduction in AlphaZ AlphaZ wiki (reductions)	Feb 8		HW2	Disc2
	10	Thu		Alpha/Alphabets Foundations Polyhedra, Affine Functions, Operations)	Feb10	Using ISL in AlphaZ		HW2	Notes 2
	15	Tue	5		Feb15
	17	Thu					Disc3
	22	Tue	6	Semantics, Domains, Equivalence (slides 1 and slides 2) Context Domains (slides)	Feb22				Calculator
	24	Thu			Feb24
Mar	1	Tue	7	Change of Basis: The Key Transformation	Mar 1		HW3	HW3
	3	Thu			Mar 3
	8	Tue	8	Midterm Review: equations, factorization, distibutivity, simplification, polyhedral operations, AlphaZ manipulation of programs, Alpha semantics) lecture video			MT 1
	10	Thu		Take-home Midterm (posted Tuesday, due in class on Thurdsday)
	15	Tue	9	Spring Break (no classes)
	17	Thu
	22	Tue	10	Exact Data flow Analysis (slides)	Mar22	Finding Schedules & parallelism			[Fea91]
	24	Thu			Mar24
	29	Tue	11	Code Generation from Polyhedra: Fourier Motzkin Elimination (slides)	Mar29	Systolic Sorter	HW4	HW4
	31	Thu		AlphaZ Code Generator	Mar29
Apr	5	Tue	12	AlphaZ Verifier & Code Generator demo		Finding the CoB
	7	Thu		No class, Sanjay traveling
	12	Tue	13	Scheduling: some classic results: Lamport 74	Apr12	Complete Target Mapping			[Lam74]
	14	Thu			Apr14		HW5	HW5
	19	Tue	14	More Scheduling: Karp, Miller & Winograd 67 Rajopadhye Purushothaman & Fujimoto 86	Apr 19.1 Apr 19.2 Apr 19.3 Apr 19.4				[KMW67] [RPF86]
	21	Thu			Apr 21.1 Apr 21.2
	26	Tue	15	Finding Schedules: Lamport & Beyond	Apr 26.1 Apr 26.2
	28	Thu			Apr 28.1 Apr 28.2
May	3	Tue	16	Code Generation Foundations & Tiling	May 3
	5	Thu
	10	Tue	17
	12	Thu		Project Poster Presentations

References

[BBK+08] M. Baskaran, U. Bondhugula, S. Krishnamoorthy, J. Ramanujam, A. Rountev, and P. Sadayappan, A Compiler Framework for Optimization of Affine Loop Nests for General Purpose Computations on GPUs, in Proc. 22nd ACM International Conference on Supercomputing, Island of Kos, Greece, June 2008.
[Bon08] U. Bondhugula: Effective Automatic Parallelization and Locality Optimization Using the Polyhedral Model. Ph.D. Dissertation, Computer Science, The Ohio University, 2008.
[CGP+05] A Cohen, S. Girbal, D. Parello, M. Sigler, O. Temam, and N. Vasilache Facilitating the search for compositions of program transformations, in ICS 2005: International Conference on Supercomputing, June 2005.
[Fea91] P. Feautrier: Dataflow Analysis of Array and Scalar References. IJPP 1991: International Journal of Parallel Programming, Vol 20.
[Fea92a] P. Feautrier: Some efficient solutions to the affine scheduling problem. I. One-dimensional time. IJPP 1992: International Journal of Parallel Programming, Vol 21, Number 5 (Note: Received: 15 May 1992 Revised: 15 April 1993).
[Fea92b] P. Feautrier: Some efficient solutions to the affine scheduling problem. Part II. Multidimensional time. IJPP 1992: International Journal of Parallel Programming, Vol 21, Number 6 (Note: Received: October 1992 Revised: June 1993).
[GR06] Gautam and S. Rajopadhye: Simplifying reductions. POPL 2006: ACM Symposium on Principles of Programming Languages, January 2006, pages 30-41.
[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.
[KMW67] R. M. Karp, R. E. Miller and S. Winograd: The Organization of Computations for Uniform Recurrence Equations Journal of the ACM (JACM), July 1967, Volume 14 Issue 3
[Kun74] H. T. Kung: "Why Systolic Architectures?" IEEE Computer. Jan 1982, pp. 37-46.
[Lam74] L. Lamport: The Parallel Execution of DO Loops. CACM 1974: Communications of the ACM, February 1974, Vol 17, No 2, pages 83-93.
[RPF86] S. Rajopadhye, S. Purushothaman, and R. Fujimoto: Synthesizing Systolic Arrays from Recurrence Equations with Linear Dependencies Foundations of Software Technology and Theoretical Computer Science, December 1986.
[Raj02] S. Rajopadhye: Dependence Analysis and Parallelizing Transformations. In "The Compiler Design Handbook" CRC Press, Editors Priti Shankar and Y. Srikant, 2002, pages 329-372.
[Vas07] N. Vasilache Scalable Program Optimization Techniques in the Polyhedral Model. Ph.D. Dissertation, University of Paris, Sud. September 2007.