CSC255 Spring 2011

CSC 255/455 Advanced Programming Systems (Spring 2011)

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. 


Assignments:

  • Apr. 13.  Project 4.  Parallel programming, due Apr. 28.
    • You are asked to parallelize a non-trivial algorithm and measure and report the performance on the 8-core machine node2x4x2a.cs.rochester.edu.  A trivial problem is a single completely parallel loop. A non-trivial problem involves either multiple loops and functions, dependences between tasks, the use of dynamic data, or a combination of these.  Other project ideas are possible with my permission.
    • You are encouraged to work in a group if the group parallelizes the same aglorithm, and each member produces a different solution---either a different parallelization tool/language or method.  Collaborative work leads to comparative studies which reveal relative strength and weakness of the used techniques.
    • Project steps
      • By Friday Apr. 15.   Create a project directory in [repos]/projects/4_para, named by the user id (or the user_ids if a group project).  Form a project plan and describe it in a project page in html format.  Make a user page in the department Drupal system.  Store the link in file project.html in the project directory.  If you cannot create a Drupal page, store the page in project.html.
      • Monday Apr. 18.  Oral project announcement in class, 1 minute per person.  Please speak on the problem, the possible parallelization methods, the expected difficulty and findings/results.
      • Wednesday Apr. 20.  In class project updates for half of the projects, 2 minutes per person.
      • Friday Apr. 22.  Project implementation due in the repository.
      • Monday Apr. 25.  In class project updates for the other half of the projects, 2 minutes per person.
      • Wednesday Apr. 27.  Project presentation (video recorded for class records), 6 minutes per individual and 10 minutes per group project.  You will be provided a laptop computer that can access your slides (in pdf format) stored in the project directory in the repository (make sure to check in the slides before class).
      • Wednesday Apr. 28.  Finalized project report, code, and presentation files due in the repository.
    • Feel free to ask questions when you encounter problems in this project.  You can usually connect to me through IM whenever I am on-line.  My jabber id is in [repos]/ding_jabber_id.txt.
    • You are not required but encouraged to use the bop system in [repos]/bop, especially to explore and demonstrate safe or speculative parallelization.  If you use the system, you can count on me as a group member.
  • Apr. 4.  Homework 2 ([repos]/homework2.pdf) is assigned and due Apr. 11 in class.
  • Feb. 22. Homework 1 is assigned and due Mar. 2 in class.
  • Feb. 17. Project 3.  Data flow, due Mar. 4. 30% of the project grade.  Mostly an individual project in 2-3 student groups. The 5 steps and their requirements are as follows.
    • by Friday Feb. 18.  Form a group
      • email the instructor if the group prefers other techniques that require data flow analysis, e.g. SSA, constant propagation, copy propagation, avail/live, partial redundancy elimination. 
    • by Tuesday Feb. 22.  Discuss and define a common interface for the def-use graph
      • submit the initial interface specification (can be revised later) into the course repos
    • by Friday Feb. 25.  Each student implements def-use analysis (individually, no code sharing)
    • by Wednesday Mar. 2.  Each student uses another person's def-use graph module to implement dead code elimination
    • by Friday Mar. 4.  Individually submit code and a report with instruction count before and after your analysis and transformation for the tests in [repos]/test_cases

      • required: compare the results with group members and explain if there is a difference
  • Jan. 24. Project 2.  Value numbering in URCC, CFG due Feb. 7, local VN due Feb. 14.
  • Jan. 17. Project 1.  GCC pass for counting dynamic instructions, due Jan. 26.

 Course description

With the increasing diversity and complexity of computers and their applications, the development of efficient, reliable software has become increasingly dependent on automatic support from compilers & other program analysis and translation tools. This course covers principal topics in understanding and transforming programs by the compiler and at run time. Specific techniques include data flow and dependence theories and analyses; type checking and program correctness, security, and verification; memory and cache management; static and dynamic program transformation; and performance analysis and modeling.

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.

This year there will be new modules on dynamic program optimization and parallel programming for multicore and GPU.
 


 Instructor and grading

Instructor: Chen Ding, Prof., CSB Rm 710, x51373
Lectures: Mondays and Wednesdays, 2pm-3:15pm, CSB 632
Office hours: Ding, by appointment (use IM or email). 
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.cs.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.cs.rochester.edu//u/cding/cs255hg
default-push = ssh://[uid]@cycle1.cs.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.