Parallel and Distributed Systems

CSC 258/458 Parallel and Distributed Systems (Spring 2012)

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/Changes:

  • Jan 18: setting up the course repository
  • weekly project/homework each week before the spring break, to be listed
  • term project in the second half of the course, to be assigned

 

Reading:


 Topics

  • parallel and concurrent programming
    • common steps: task partitioning, data sharing, and task distribution/scheduling
      • static, dynamic, and speculative tasks
      • shared memory, message passing, check-in/check-out
        • collaborative real-time editing
        • version control systems
      • synchronization and communication fundamentals
        • synchronous, asynchronous
      • scheduling (see parallel machine part)
    • semantics
      • data sharing: race, dependence, the Bernstein condition
      • progress: lock and wait freedom
        • reading: problems of fine-grain locks (Scherer), Lee article
      • distributed sharing: coherence/consistency in memory/cache
    • synchronization in shared memory
      • threads and locks (and why you should not use them)
      • non-blocking synchronization: transactions and dual data structures
      • scalable synchronization: MS queues and MCS locks
    • communication in distributed memory
      • Lamport clocks, vector timestamps
      • fault tolerance and distributed consensus
      • distributed shared memory: Treadmarks and Interweave
      • message passing: put/get, send/recv, collectives
    • programming languages and frameworks
      • OpenMP, Java, Cilk, Fortress
      • MPI, CUDA, DCOM, Jade, HPF, X10
      • APL, SaC, Multilisp
      • Synchronous I/O
    • programming tools
      • dependence and loop parallelization
      • parallelism profiling
      • performance analysis/debugging
      • verification
  • parallel machines
    • types of parallelism: superscalar, VLIW, SPMD, GPU
    • memory hierarchy
    • cache coherence
    • task static assignment and dynamic scheduling
      • OpenMP, Intel TBB schedulers
  • contemporary applications
    • browser architecture and Web 2.0
    • distributed version control: Mercurial and Git
    • Jabber instant messaging
    • Google's map-reduce
    • Ruby event machine and Javascript nodejs
    • adapter/proxy patterns and Ruby drb
    • Websphere, Ruby on rails
    • Apple's grand-central dispatch
    • servers and databases
    • Unix/Linux, iOS, Android
  • on-going research
    • safe/deterministic/race-free programming/execution
      • BOP, Pingali's Galois
    • multicore resource management
  • possible course projects
    • verification of a mobile protocol

Course projects include the design and implementation of program analysis and improvement tools.  Meets jointly with CSC 258, an undergraduate-level course whose requirement includes a subset of topics and a simpler version of the project.


 Instructor and grading

Instructor: Chen Ding, Prof., CSB Rm 710, x51373
Lectures: Mondays and Wednesdays, 3:25pm-4:40pm, CSB 632
Office hours:

You may contact me using instant messaging through any Jabber IM client such as a gmail address.  Email the instructor for the Jabber IM contact address.

Grading (total 100%)

  • midterm and final exams (15% each)
  • projects (30% weekly projects, 30% term project)
  • written assignments, mostly preparation for the exam (5% each)


 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 cs258repos as an example.  The sequence of commands needed are

mkdir cs258repos 
cd cs258repos
hg init

Create the file cs258repos/.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/cs258hg 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/cs258hg
default-push = ssh://[uid]@cycle1.csug.rochester.edu//u/cding/cs258hg

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