Parallel Computing I (CS412/CS512)

Call Numbers 01520/ 01529

Spring 2010/2011

MTRF 3:10-4:00 PM, 221 Academic and Research Center

Instructor:      Frank Drews

Office:             Stocker 321

Phone:            593-1248

email:             drews@ohio.edu

Office Hours: Monday, Tuesday, Thursday, and Friday 1:00-2:00pm and by appointment

News

The finals set of "Shared Memory" Slides (Sieve of Erathosthenes + Lock-free algorithms) are available here.

The handout for project 2 is available here.

The Amdahl stuff is available here.

The second set of "Shared Memory" slides are available here.

The first set of "Shared Memory" slides are available here.

The handout for project 1 is available here.

The second set of  "Parallel Algorithms Design" slides are available here.

The first set of the "Parallel Algorithms Design" slides are available here.

The second set of "Introduction" slides are available here.

The first set of "Introduction" slides are available here.

The syllabus is available here.

Course Objectives

This course is a practical-oriented introduction to Parallel Computing. It aims to teach students an understanding of the complex interactions between software and hardware in parallel systems. Upon completion of this course, the student should be familiar with fundamental aspects of parallel systems, taxonomies, performance measures, and theoretical limitations of parallel systems. Students will understand parallel programming languages and middleware, and will be able to design and implement efficient parallel applications on a variety of parallel architectures. The course will be accompanied by a number of programming projects and exercises including, but not limited to, bioinformatics applications and case studies.

Course Contents

1. Introduction:

    Motivation for Parallelism:

       Concurrency and Parallelism, Speedup, Moore’s Law,  

       Grand Challenge Problems

    Parallel Systems:

        Parallel Computing Taxonomies, Instruction Level Parallelism, Shared

        Memory Multiprocessors Systems, Distributed Memory Multiprocessor

        Systems, Cluster and Grid Computing

    Performance Measures:

        Granularity, Speed-Up, Efficiency, Cost, Amdahl’s Law, Gustafson’s Law

2. Parallel Programming Techniques:

    Fundamentals of Shared Memory Programming:

         Parallel Programming Decompositions, Parallel Programming Patterns,

         Synchronization Primitives and Critical Sections, Deadlocks,

    Shared Memory Programming API’s and Environments:

         Threading API’s (POSIX Threads), OpenMP

    Shared Memory Programming Issues:

         Data Races, Live Locks, and Deadlocks, Heavily Contended Locks, Priority

         Inversion, Non-blocking Algorithms, Memory and Cache-related Issues, Debugging

         Techniques

    Distributed Memory Programming:

         Message Passing Computing, Message Passing Programming Patterns, MPI and

         PVM, Remote Procedure Calls (RPC)

    SIMD/GPGPU Computing

         Associative Computing and SIMD, ClearSpeed Programming, Cn language, Nvidia

         CUDA

Text

Introduction to Parallel Computing, Ananth Grama, George Karypis, Vipin Kumar, Anshul Gupta, Addison Wesley, 2^nd edition, 2003

Additional Reading

Multi-Core Programming: Increasing Performance through Software Multithreading, Shameem Akhter, Jason Roberts, 1st edition, 2006, Intel Press

Class Website

http://www.frankdrews.com/cs412_512_SQ09/classwebsite.htm

Grading

Projects: There will be a sequence of in depth programming projects for this course.  Projects in this class will be written primarily in C or C++.

Quizzes: There will be sequence of quizzes. Quizzes are closed book and closed notes. Quizzes cannot be made up without prior notification of the medical (or other) reason for the absence (via email or phone). In addition, I preserve the right to give unannounced pop-up quizzes any time.

Tests: There will be a midterm and a ¯nal test in addition to the quizzes. The tests are cumulative by nature, but strongly emphasize more recent material. Tests are closed book. Students enrolled in CS 512 will complete additional, more challenging work in this course. In particular, students in CS 512 will complete at least one additional programming project.

Final grades: Determined as follows:

Programming assignments: 40%

Homework, class participation, and Quizzes 15%

Test 1 20% mid-term

Test 2 25% final

Letter grades

Numeric Grade             Letter Grade

90 and above                 A

88-90                            A-

85-88                            B+

82-85                            B

80-82                            B-

77-80                            C+

73-77                            C

70-73                            C-

67-70                            D+

63-67                            D

60-63                            D-

below 60                       F

Grades are not changed unless a grading error has been made. Academic Dishonesty: All work must be strictly the work of each individual student and any cases of academic dishonesty will be treated in accordance with the published departmental policy.

Other Policies

Late assignments, missed quizzes, and tests, cannot be made up unless the student has obtained prior approval or there are extenuating circumstances, such as medical problems accompanied by an written explanation from a doctor.