ENEE459P/ENEE699*: Parallel Algorithms, Fall 2010
* 1. New in Fall 2010: This course is offered as a joint inter university course on parallel computing with the University of
Illinois.
2. To take the course as ENEE699 (Section 3201)
please contact the instructor at vishkin@umd.edu.
Why is it a good idea to take this course?
Click for a brief flyer addressing this question
Maryland Information
Time and Location MW 9:3010:45. ITV 1100.
Instructor Dr. U. Vishkin.
Instructor's Email and Office Hours
vishkin@umd.edu, M 2:003:00 (by appointment) at AVW 2365.
Grader Umer Ikram. Email umer.ikram@gmail.com
Illinois Information
Time and Location MW 8:309:45. 1109 Siebel Center.
Instructor Dr. D. Padua.
The Illinois course website
Slides
Slides for classes starting on September 20
Dry Homework
Homework 1: Exercises 15. Due: October 6.
Homework 2: Exercises 69. Due: October 13.
Homework 3: Exercises 1012. Due: October 25.
Homework 4: Exercises 14,15,2123. Due: November 3.
Homework 5: Exercises 24,2931. Due: November 17.
Homework 6: Exercises 32,3537. Due: November 29.
XMT Programming Assignments
Programming Assignments, Tutorial, Manual, Software Tools and Other
Information
OpenMP Programming Assignments
OpenMP Homework 1:
Do the 3credit version of MP3 on the University of Illinois web site. Due: October 18, 2010.
OpenMP Homework 2:
Do the OpenMP part of MP5 on the University of Illinois web site. Note that much of this homework statement is based on references to XMT HW2 (which is due Nov 2).
Due: November 8, 2010.
Teaching Motivation
Parallel algorithmic thinking and programming is in increasing demand as multicores, and other
chipmultiprocessing approaches are being deployed. These approaches are in line with the roadmap charted by the major industry vendors.
In fall 2010, Professors Padua and Vishkin coteach part of their respective
parallel algorithms and programming
undergraduate courses, each one teaching one part of the course to both classes.
The increasing need merits this broader coverage.
Research Motivation
Much of the core of the computing field needs to be reinvented for manycore parallelism.
The productivity of parallel programming has long been recognized as a limiting factor for parallel computing.
However, the computing research community is yet to develop agreed ways ('benchmarks') for assessing such productivity.
While major vendors urge rising mainstream programmers (e.g., every Computer Science and Computer Engineering major) to embrace generalpurpose parallelism,
the history of parallel computing has taught us that parallel programming of many parallel machines tend to be quite challenging.
We believe that developing ways for evaluating (and benchmarking) productivity of parallel programming and building some consensus around them can be a first step towards
changing that. This is not without challenges.
Core computer science and engineering research tends to put an emphasis on things we can "truly measure" analytically
(e.g., complexity analysis, or power analysis), or empirically using wallclock timing such as the computer system quantitative approach. But, the type of socialscience
evaluations that involve a human factor, as needed here, are yet to gain traction in core CS areas such as algorithms, computer systems and
performanceminded programming.
Idea: A necessary condition for improved productivity is easeofprogramming.
A necessary condition for easeofprogramming is easeofteaching, and, of course, easeoflearning.
Our idea is to make progress toward better understanding of the relative productivity of parallel programming
approaches by experimentally comparing their easeofteaching/learning.
Course Teaching Goals
 Introduction to the theory of parallel algorithms.
The course will highlight parallel algorithmic thinking for obtaining
good speedups with respect to serial algorithms.
 Introduction to parallel programming. The course will cover several parallel programming paradigms as well as strategies for performance tuning for shared, SIMD, and distributed memory target machines.
Course Research Goals
This joint class is part of a research project whose objective is experimentally evaluating different parallel programming paradigms
from the point of view of easeofteaching/learning ('teachability') and easeofuse ('usability') and comparing them. One specific goal is identifying the
characteristics of the most important parallel algorithms and programming models, when these models are seen as tools to learn
parallel programming concepts. A secondary goal is studying the feasibility, advantages and disadvantages of coteaching a course
involving faculty from different institutions.
Plan: A group of software engineering expert(s), and learning (as understood in) education expert(s) is being assembled to provide guidance
on the procedure to carry out the experimental evaluation.
All students will be asked to (make a small effort and) contribute to the research side of the course, but will be given the option not to without affecting
their grade.
Prerequisite Topics
 Basic knowledge and understanding of algorithms and data structures
and computing systems.
Course readings:
 Class notes will be available for all the material covered during the semester.
Some of the material will be drawn from these
class notes (104 pages)
Reference books:
 V. Kumar , A. Grama, A. Gupta, and G. Karypis, Introduction to Parallel Computing: Design and Analysis of Algorithms. BenjaminCummings Publishing Co. 1994

J. JaJa, An Introduction to Parallel Algorithms, Addison Wesley, 1992

D.E. Culler and J.P. Singh, Parallel Computer Architecture, Morgan Kaufmann,
1999
 J.L. Hennessy and D.A. Patterson. Computer Architecture a Quantitative
Approach, 4th Edition. MorganKaufmann, San Francisco, 2007
 W. Gropp, E. Lusk, and A. Skjellum Using MPI (2nd Ed.): Portable Parallel Programming with the MessagePassing Interface, MIT Press, 1999
Some Core Topics:
 Introduction to Parallel Algorithms:
Performance of Parallel Algorithms, Optimality Notions, Key Abstractions
 Basic Techniques: Balanced Trees, Pointer Jumping, DivideandConquer,
Partitioning, Pipelining, Accelerated Cascading,
Breaking Symmetry
 Numerical algorithms: MatrixMatrix multiplication, Reduction, Scan, Recurrence Solvers, Linear System Solvers, Iterative Synchronous and Asynchronous Algorithms
 Trees and Lists: List Ranking, The Euler Tour Techniques,
Tree Contraction, Evaluation of Arithmetic Expressions
 Searching, Merging and Sorting
 Graphs: Connected Components, Transitive Closure, Paths Problems
Grading
 10%  Written homework
 40%  Programming projects
 20%  Midterm exam, October 25, in class
 30%  Final exam (comprehensive), 8:0010:00 Saturday, December 18 (based on Testudo).