CS 425: Parallel Computing, Fall 2015

Links: [Course Home] [Schedule] [Moodle]


Instructor Dr. Suzanne Rivoire
Meeting times MoWe 10:45 AM – 12:00 PM
LocationIves 35
Textbook [required] Gerassimos Barlas, Multicore and GPU Programming: An Integrated Approach, 1st edition, ISBN 9780124171374
Prerequisites CS 315 and CS 252, or consent of instructor.

Catalog Description

Lecture, 3 hours. Overview of parallel patterns, programming models, and hardware. Topics include parallel performance analysis; types of parallelism; parallel decomposition of tasks; shared vs. distributed memory; synchronization; hands-on experience with multiple parallel programming models; and architectural support for parallelism.


Course Goals

The most important goals of this course are for you to

  1. Understand parallelism at a conceptual level:
    • Explain the reasons for the trend towards multicore systems.
    • Distinguish parallelism from concurrency.
    • Distinguish shared from distributed memory.
    • Compare and contrast parallel programming paradigms, recognizing the strengths and weaknesses of each.
    • Explain and quantify speedup, bandwidth, latency, and scalability.
    • Describe the types of parallelism including task, data, and event parallelism. Identify computations and architectures that are well suited to each type.
    • Use parallel execution diagrams to compute work and span and determine the critical path.
    • Calculate the implications of Amdahl's Law for a particular parallel algorithm.
    • Explain why synchronization is necessary in a specific parallel program.
  2. Write correct parallel programs using common patterns:
    • Identify opportunities to partition a serial program into independent parallel modules.
    • Design, code, test, and debug programs for a parallel computation.
    • Write a correct and scalable parallel algorithm using multiple programming models.
    • Parallelize algorithms using task-based decomposition.
    • Parallelize algorithms using data-parallel decomposition.
    • Write test programs that can reveal concurrent programming errors.
    • Implement parallel divide-and-conquer algorithms.
    • Implement parallel producer-consumer algorithms.
    • Write parallel programs for graphics processors.
  3. Assess and tune the performance of parallel programs:
    • Evaluate performance of simple sequential and parallel versions of a program with different problem sizes, and be able to describe the speedups achieved.
    • Design and conduct performance-oriented experiments, e.g., benchmarking a parallel program with different data sets in order to iteratively improve its performance.
    • Correct load imbalances and false sharing.
    • Assess the performance impacts of data locality.

Note: this course's goals and objectives are based on the Association for Computing Machinery (ACM)'s Computing Curricula 2013. This course addresses the areas of Parallel and Distributed Systems, Systems Fundamentals, Programming Languages, Architecture and Organization, Operating Systems, Algorithms and Complexity, and Computational Science.


Coursework and Grading

Course Activities

Lecture and Reading

The tentative course schedule shows the topics to be covered. You are expected to attend all lectures and to get the notes from another student if absent. You are also expected to skim the assigned reading material before each lecture and read more fully after the lecture.

In-class Activities

In-class individual and group activities will be given regularly. Your lowest 2 scores on these activities will be dropped from the grade calculation. These activities cannot be made up.

Homework assignments

Approximately 6 homework sets will be assigned. These assignments may be problem sets, programming projects, or a mix of the two. You may work in groups of up to three students and submit a single solution set for the group.

No late problem sets will be accepted. This policy allows us to discuss their solutions in preparation for the quizzes.

Quizzes

There will be approximately 5 brief (30- to 45-minute) quizzes, each covering 2-3 weeks of course material. Your lowest quiz score will be dropped.

Final exam

The final exam is cumulative. It will emphasize on (a) concepts from the last two weeks of class and (b) cross-cutting concepts that bring together multiple course topics.

Grading Policies

Grade breakdown

Final exam 15%
Quizzes 35%
Homework problem sets 40%
Class activities10%

Grading scale

93-100%90-92%87-89%83-86%80-82%77-79%73-76%70-72%67-69%63-66%60-62%Below 60%
AA-B+BB-C+CC-D+DD-F

Up to 3% may be added to your final grade at the instructor's discretion for constructive participation in the class. Constructive participation includes in-class participation; asking good questions via email or during office hours; and doing outstanding or extra work on assignments. No other adjustments of borderline grades will be considered.

Collaboration Policies

Homework problem set collaboration policy

Problem sets must be the sole work of your group members, and academic misconduct is taken very seriously. You may discuss ideas and approaches with other students and the instructor, but you should work out all details and write up all solutions on your own. The following actions will be penalized as academic dishonesty:

Exam and quiz collaboration policy

Exams and quizzes must be your own work. You are allowed to consult only your own brain, your 8.5x11" handwritten cheat sheet, and other materials specifically permitted by the instructor. Quiz policies will vary and will be announced when the quiz is given. On both exams and quizzes, giving or receiving unpermitted aid will be penalized as academic dishonesty.

Penalties for Academic Dishonesty

Academic dishonesty will be severely penalized; at a minimum, you will receive a grade of 0 on the assignment. For more information, see SSU's cheating and plagiarism policy (http://www.sonoma.edu/UAffairs/policies/cheating_plagiarism.htm) and the Dispute Resolution Board website (http://www.sonoma.edu/senate/committees/drb/drb.html).


University Resources

Disability Accommodations

If you are a student with a disability and you think you may require accommodations, please register with the campus office of Disability Services for Students (DSS), located in Salazar Hall - Room 1049, Phone: (707) 664-2677, TTY/TDD: (707) 664-2958. DSS will provide you with written confirmation of your verified disability and authorize recommended accommodations. This authorization must be presented to the instructor before any accommodations can be made. Visit http://www.sonoma.edu/dss for more information.

University Policies

There are important University policies that you should be aware of, such as the add/drop policy, cheating and plagiarism policy, grade appeal procedures, accommodations for students with disabilities, and the diversity vision statement. Go to this URL to find them: http://www.sonoma.edu/uaffairs/policies/studentinfo.shtml.