Undergraduate Program
Software Analysis and Improvement
Course: CSC
255
Term: Spring 2012-2013
CSC 255/455 Software Analysis and Improvement (Spring 2012, formally Advanced Programming Systems)
- Course description
- Course schedule (as of January 16, for later changes see [repos]/schedule.pdf)
- Instructor and grading
- Class repository
- Textbooks and other reading material
Lecture slides, demostration programs, and some of the reading material will be distributed through the class repository. Assignments and projects will be submitted through the repository as well.
Updates:
- Apr. 23, homework 2 is released, see [repos]/assignments/homework2.pdf, due April 30th.
- Apr. 11, lambda calculus assignment is released, due Monday April 23rd.
- Mar. 26, point-to project has been announced, see http://www.cs.rochester.edu/node/4994 for details, due Wen. April 4th, 11:59pm.
- Mar. 7, midterm is announced, see [repos]/midterm.pdf, due Friday Mar. 9 midnight.
- Feb. 28, data flow project is announced, see http://www.cs.rochester.edu/node/4950 for details, due Sunday Mar. 11 midnight.
- Feb. 27, homework 1 is assigned, see [repos]/assignments/homework1.pdf, due March 2nd.
- Feb. 9, control flow and value numbering assigned, see http://www.cs.rochester.edu/node/4937 for instructions. Control flow part due Wen. Feb. 15 midnight, value numbering part due Feb. 20 midnight.
- Jan. 23, tree iterator assigned, see [repos]/assignments/1_iterator/description.txt, due Sunday midnight
- Jan. 19, repository moved to csug. instructions updated.
Course description
Programming is the automation of information processing. Program analysis and transformation is the automation of programming itself---how much a program can understand and improve other programs. Because of the diversity and complexity of computer hardware, programmers increasingly depend on automation in compilers and other tools to deliver efficient and reliable software. This course combines fundamental principles and (hands-on) pracitical applications. Specific topics include data flow and dependence theories; static and dynamic program transformation including parallelization; memory and cache management; type checking and program verification; and performance analysis and modeling. The knowledge and practice will help students to become experts in software performance and correctness.
Course projects include the design and implementation of program analysis and improvement tools. Meets jointly with CSC 255, an undergraduate-level course whose requirement includes a subset of topics and a simpler version of the project.
List of topics:
- highly composable software design
- function closures
- iterators
- mix-ins
- meta-classes
- program analysis
- basic models
- code: basic block, extended basic blocks, control flow graph, call graph, iteration space
- data: value, name, location, type, point-to graph, data space
- invariances: value numbering, dataflow, dependence, and type theory, abstract interpretation
- hardware: pipelining, concurrency, memory hierarchy
- straight-line code: value numbering
- basic block, extended BB, dominator based
- procedure scope: dataflow analysis
- avail and live analysis, MOP sets, convergence
- properties: existence and uniqueness of fixed points, speed of convergence (455 only)
- dominance, def-use
- unified control and data flow: static single assignment (SSA)
- dominance frontier, phi-insertion, renaming
- beyond a single procedure: types are sets
- fundamental theorem
- type state
- programs as proofs: temporal logic and program verification
- basic models
- program transformation
- the fundation: dependence
- 3 types, reordering transformation, fundamental theorem
- Landin's equivalence condition
- the compiler: loop optimization
- loop carried and loop independent dependences
- dependence checking, Banerjee equations, omega testing
- do-all and do-across loops
- Allen-Kennedy vectorization algorithm
- improving parallelism (by eliminating dependences)
- loop interchange, renmaing, node splitting
- improving locality (by improving data reuse)
- Carr-McKinley-Tseng loop ordering
- unroll-and-jam, loop tiling, loop fusion
- loop carried and loop independent dependences
- language support:
- iterator, array language, lazy evaluation, memoization
- auto-tuning
- the fundation: dependence
- program behavior
- modeling
- frequency, "hot" functions and data
- locality, reuse distance, miss rate
- measurement
- profiling, sampling, call-context tree
- analysis
- hotness, affinity, phase
- effect of program input and resource sharing
- adaptation
- specialization and speculation
- modeling
- program semantics
- lambda calculus
- lazy evaluation
- memoization
- continuation passing
- call with continuation
- advanced type systems
- lambda calculus
Instructor and grading
Instructor: Chen Ding, Prof., CSB Rm 710, x51373
Lectures: Mondays and Wednesdays, 2pm-3:15pm, CSB 632
Office hours:
- Ding, 11am to 12pm, Fridays, and by appointment (use IM or email).
- Lingxiang Xiang, CSB Rm 615, 3:30pm to 5:30pm, Fridays, lxiang at cs.rochester.edu
You may contact us using instant messaging through any Jabber IM client such as a gmail address. Connect address TBA.
Grading (total 100%)
- midterm and final exams are 15% each
- the projects total to 60%
- written assignments are 10%
Class repository
The class repository is managed by the distributed version control system called Mercurial. If you haven't used Mercurial before, it is easy to follow one of the many on-line tutorials. The basic commands you need are as follows. Note that unlike subversion (svn), you have a copy of the repository on your local machine, and you check out from and check into the local repository.
Before you start, make sure that you have an account on cycle1.csug.rochester.edu
Create your local repository in a directory, which we use cs255repos as an example. The sequence of commands needed are
mkdir cs255repos
cd cs255repos
hg init
Create the file cs255repos/.hg/hgrc and add the following (if your repository is not on the same network as cycle1, e.g. on your laptop). Otherwise use file://u/cding/cs255hg instead of ssh addresses. If ssh is used, you will need to type in your password each time you synchronize with server repository (your local commits never require a password).
[paths]
default = ssh://[uid]@cycle1.csug.rochester.edu//u/cding/cs255hg
default-push = ssh://[uid]@cycle1.csug.rochester.edu//u/cding/cs255hg
Set up your user name by creating the file in your home directory ~/.hgrc and add the following
[ui]
username = First, Last <email>
Textbooks and other resources
Optimizing Compilers for Modern Architectures (UR access through books24x7), Randy Allen and Ken Kennedy, Morgan Kaufmann Publishers, 2001. Chapters 1, 2, 3, 7, 8, 9, 10, 11. lecture notes from Ken Kennedy. On-line Errata
Engineering a Compiler, Keith D. Cooper and Linda Torczon, Morgan Kaufmann Publishers. Chapters 1, 8, 9, 10 and 13. lecture notes and additional reading from Keith Cooper. On-line Errata
The Little Schemer, Daniel Friedman and Matthias Felleisen, MIT Press. Auxiliary reading. To play with lambda calculus, use the DrScheme environment.
Attachment | Size |
---|---|
schedule12.pdf | 29.06 KB |