ENEE759K/CMSC751: Parallel Algorithmics, Spring 2004

Time and Location

• MW 11:00-12:15. CSI 3118.

Instructor: Dr. U. Vishkin

• E-mail: vishkin@umd.edu
• Office hours: MW 9:30-10:30 (by appointment) at AVW 2365.

Written Homework

• Homework 1: Exercises 1-5. Due: February 23, 2004.
• Homework 2: Exercises 6-8. Due: March 1, 2004.
• Homework 3: Exercises 9-14. Due: March 10, 2004.
• Homework 4: Exercises 15,17-19. Due: March 18, 2004.
• Homework 5: Exercises 20-24. Due: April 5, 2004.
• Homework 6: Exercises 25-32. Due: April 12, 2004.
• Homework 7: Exercises 33-38. Due: April 21, 2004.
• Homework 8: Exercises 39-44. Due: April 28, 2004.
• Homework submission: Homework must be submitted by 5pm on the due date. You have two options for submission: (i) in the last class before the submission deadline, or (ii) to Mr. Aydin Balkan's mail box. His mail box is in AVW 2464 in the second column of mail boxes on your right as your enter the room.

Programming Assignments

• Assignment 0. Due: March 31. Please issue a Jasmine account (at the ECE Computer Help Desk, AVW 1449A) if you don't have one asap.
• Information on how to access the simulator
• File xmtData8.txt
• File xmtData512.txt
• File xmtasm.exe
• File xmtass.exe
• File xmtsim.bat
• File xmtsim.exe
• Assignment 1. Due: April 23. (Note: Another example code for the compaction problem, as per the pdf file under 2002 talks.)

Links to the Programmability Study Project

• Background survey (fill out once): http://care.cs.umd.edu:3555/CMSC751/Background_Questionnaire.html
• Effort form (fill out multiple times): http://care.cs.umd.edu:3555/CMSC751/Effort_Log.html
• For questions on the programmability study project please write to Dr. Jeff Carver carver@cs.umd.edu.

Course Goals

• Introduction to the theory of parallel algorithms. The course will highlight parallel algorithmic thinking for obtaining good speed-ups with respect to serial algorithms.
• Close examination of one of the most exciting applied research questions facing computer science and engineering: Will the upcoming ``Billion-transistor-per-chip'' era provide a way for building a truly parallel computer system on-chip? The examination has 3 parts: (i) operational (i.e., how will the system work?), (ii) functional (i.e, for what application it will be useful?), and (iii) facilitating science and technology (e.g., algorithms, deep-submicron VLSI).

Of Special Interest This Year

• 2-3 parallel programming assignments will be given.
• Professor Vic Basili's software engineering team will include this class in their important DARPA funded study on parallel programming productivity. 4 other Spring 2004 classes are included in the study (at MIT, UCSB, UCSD and USC).

Prerequisite Topics

• Basic knowledge and understanding of algorithms and data structures and computing systems.

Course readings:

• Class notes and research papers will be provided by the instructor. Please download and print out the first item (104 pages) under http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/papers.html
  
  Reference books:
• J. JaJa, An Introduction to Parallel Algorithms, Addison Wesley, 1992.
• D.E. Culler and J.P. Singh, Parallel Computer Architecture, Morgan Kaufmann, 1999. The following quote appears under the title Potential Breakthroughs: ..."breakthrough may come from architecture" ... "that is, to truly design a machine that can look to the programmer like a PRAM".
• J.L. Hennessy and D.A. Patterson. Computer Architecture a Quantitative Approach, 3rd Edition. Morgan-Kaufmann, San Francisco, 2002.

Some Core Topics:

• Introduction to Parallel Algorithms: Performance of Parallel Algorithms, Optimality Notions
• Basic Techniques: Balanced Trees, Pointer Jumping, Divide-and-Conquer, Partitioning, Pipelining, Accelerated Cascading, Breaking Symmetry
• Trees and Lists: List Ranking, The Euler Tour Techniques, Tree Connection, Evaluation of Arithmetic Expressions
• Searching, Merging and Sorting
• Graphs: Connected Components, Transitive Closure, Paths Problems
• Strings: Some string matching algorithms
• Introduction to Parallel Processing: Principles of available multi-processors and instruction-level parallel (ILP) systems, and Parallel Models
• Studies on limits of ILP extractable from serial code
• Introduction to published expectations from the upcoming "Billion-transistor-per-chip" era: (i) Over 4 orders-of-magnitute of potential improvement over the CPU of the first PC. (ii) Large on-chip memories will enable high bandwidth and low latency. (iii) Low overhead hardware/software mechanisms
• Suggestions and possibilities for putting it all together. Can fine-grained large scale on-chip parallel computing be harnessed towards faster completion time of a single general-purpose computing task?

Grading

• 10% - Written homework.
• 20% - Programming projects. You must submit all programming projects to get a grade.
• 70% - Mid-term exam. Exam date: April 28, in class.
• There will not be a final exam.