CSIS 599 Parallel Programming and Algorithms                                                        Spring 2015 Syllabus

Updated Friday, Jan. 9, 2015

Classroom: CH3600

Time: 9:35am-10:50am

A textbook is not required for this course. Instead, the following resources will be used as references for lectures, slides, assignments, and worksheets. Additional resources may be added as the course progresses.

References:

Introduction to Parallel Programming 2nd Ed. (2008)
Authors: A. Grama, G. Karypis, V. Kumar, and A. Gupta
ISBN: 0201648652 (ISBN-10), 978-0201648652 (ISBN-13)
MPI: The Complete Reference
Authors: M. Snir, S. Otto, S. Huss-Lederman, D. Walker, and J. Dongarra
Link: http://www.netlib.org/utk/papers/mpi-book/mpi-book.html 

Hadoop: The Definitive Guide 3rd Ed. (2012)
Authors: Tom White
ISBN: 1449311520 (ISBN-10), 978-1449311520 (ISBN-13)

Using OpenMP: Portable Shared Memory Programming (2007)
Authors: B. Chapman, G. Jost, R. van der Pas
ISBN: 0262533022 (ISBN-10), 978-0262533027 (ISBN-13)

Programming Massively Parallel Processors: A Hands-on Approach (2010)
Authors: D. Kirk and W. Hwu
ISBN: 0123814723 (ISBN-10), 978-0123814722 (ISBN-13)

MPI: A Message Passing Interface Standard Version 3.0 (2012)
Authors: MPI Forum
Link: http://www.mpi-forum.org/docs/mpi-3.0/mpi30-report.pdf

Supplemental Material Link: OpenMP Resources, http://openmp.org/wp/resources/

Supplemental Material Link: Supercomputing in Plain English:
A High Performance Computing Workshop Series, http://www.oscer.ou.edu/education.php

Supplemental Material Link: CUDA Parallel Computing Platform, http://www.nvidia.com/object/cuda_home_new.html

Supplemental Material Link: Big Data University, http://bigdatauniversity.com

Supplemental Material Link: HPC University, http://hpcuniversity.com

Supplemental Material Link: LLNL Tutorials, https://computing.llnl.gov/?set=training&page=index

Instructor: David Monismith
                    2210 Colden Hall
                    monismi_at_nwmissouri_dot_edu

Office Hours: M 1:00pm - 3:00pm, W 1:00pm - 3:00pm, R 1:00pm - 3:00pm, F 10:00am - 11:00am

Course Website: http://monismith.info/cs599/

Teaching Assistants: Syed Mazhar Hussani and Murali Krishna Talluri

Help Session Hours: Tuesdays and Thursdays in CH3200 from 6:30pm to 7:30pm (until 8:00pm if necessary)

Prerequisite: Permission of instructor or CSIS 550 or equivalent, with a grade of "C" or better.

Course Description: Course covers concepts in parallel programming, concepts and tools including parallel architectures, shared and distributed memory programming, parallel algorithms, load balancing, manipulation of large data sets, and accelerator programming.

Course Outline:

Parallel Architectures
Shared Memory Programming (pThreads and OpenMP)
Message Passing and MPI
Parallel Sorting
Parallel Search
N-Body Problem
Floyd's Algorithm, Dynamic Programming, and Fast Fourier Transform as time permits
Map-Reduce Paradigm and Hadoop
Matrix Multiplication using CUDA

Course Schedule:

Week 1: Parallel Architectures - Multicore Processors, Pipelining and Superscalar Execution, Cache, Memory Bandwidth, Ideal Parallel Computers, Network Topologies, and Cache Coherence.

Week 2: Shared Memory Programming (pThreads and OpenMP): Thread Basics, Read Write Locks, Barriers, OpenMP Programming Model, Synchronization, Data Handling, Library Functions, and Environment Variables

Week 3: Process Communication Operations: One to All Broadcast, All to One Reduction, All to all broadcast and reduction, Scatter and Gather

Week 4: Message Passing and MPI: Blocking and Non-Blocking Communications, Communicators, Environment Information, Review of sending and receiving information. Review of batch scripts.

Week 5: Message Passing and MPI: Barrier, Broadcast, Reduction, Scatter, Gather, All-to-all and examples.  Review of batch scripts.

Week 6: Parallel Sorting: Bubble Sort, Bucket Sort, Sample Sort, and Quicksort

Week 7: Parallel Search: Shortest Path and Depth First Search

Week 8: N-Body Problem: Message passing and Graphical implementation

Weeks 9-10: Floyd's Algorithm, Dynamic Programming, and Fast Fourier Transform as time permits

Weeks 11 - 12: Map-Reduce Paradigm and Hadoop programming using Large data sets

Weeks 13 - 14: Introduction to CUDA and Matrix Multiplication using CUDA

Assignments:

Homework/Lab Assignments* (up to 15 @ 5 points) up to 75
Programming Projects**    up to 140
(up to 7 at 10 to 20 points each)
Exams (2 @ 100 points, 1 final @ 100 points)300
Lab Exams (2 @ 100 points) 200

Total Points    up to 715

*The instructor reserves the right to give a quiz in lieu of collecting homework.
**Graduate students will be required to complete an additional project (20 points).

Attendance Policy: Class attendance is important and roll will be taken. It is highly recommended that students attend class every day.

Work Policy: Homework* will be collected on the due date at the beginning of class and will not be accepted late. Projects must be submitted electronically by 11:59:59pm on the due date. Projects will be accepted up to 48 hours late at a penalty of 20%. Failure to make use of an XSEDE resource as denoted in an assignment, homework, or lab will result in a 25% penalty. The instructor and teaching assistant are able to track student use of XSEDE resources through the allocation tool on the xsede.org website. Projects that do not compile will be subject to a 50% penalty. You are expected to complete assignments in advance for known school events (e.g. athletic or club events). The instructor reserves the right to modify the late policy for students with extenuating circumstances. The instructor also reserves the right to waive the resource penalty above in the event of system failure.

Exams: As previously noted, there will be two examinations and one final. Unless announced otherwise in class, these examinations will take place on the following dates:

Exam 1:Thursday, Feb. 19, 2015 in class
Exam 2:Thursday, Apr. 9, 2015 in class
Final:Thursday, Apr. 30, 2:00pm - 4:00pm in CH3600

Lab Exams: As previously noted there will be two lab examinations. Unless announced otherwise in class these will take place in the evening on the following times and dates:

Lab Exam 1: Friday, Feb. 13, 2015 from 6:30pm to 8:00pm
Lab Exam 2: Friday, Apr. 3, 2015 from 6:30pm to 8:00pm

Students absent during the day of a written exam will be given the choice to count the final exam twice or to take a comprehensive make-up exam, time TBD by instructor. The final exam score will replace one regular (written) exam score if a student has a higher score on the final than on one of the two regular (written) exams. The instructor reserves the right to give a regular make-up exam to students having extenuating circumstances such as emergency illness.

Grading Policy:  Grades will be assigned based upon accumulated points as follows:

100% - 90% -->  A
89.99% - 80%  -->  B
79.99% - 70%  -->  C
69.99% - 60%  -->  D
59.99% - 0%    -->  F

The grade scale will not be raised; however, the instructor reserves the right to lower the grade scale without prior notice.

If you have a problem with a grade, please discuss it with the instructor.

Disabilities: Students in this course who need accommodations/modifications should present a copy of their official Northwest accommodation letter from the LAP/S Committee to the instructor as early in the term as possible. Additional information can be found at http://www.nwmissouri.edu/swd.

Academic Integrity: All assignments are to be completed individually unless otherwise designated. You may discuss the concepts of a current assignment with another person. Sharing code for a current assignment, handing in a program written by someone else, and all other obviously dishonest practices are prohibited.

Students are encouraged to come to office hours for help.

Students are expected to read and understand the CSIS Academic Integrity Policy available at http://www.nwmissouri.edu/mathcsis/pdf/AcademicIntegrityCSI.doc.

Disclaimer per http://www.nwmissouri.edu/cite/teach/syllabus.htm: The syllabus is not a contract and is subject to change at the discretion of the instructor to accommodate instructional and/or student needs. It is the sole responsibility of the student to maintain an updated course syllabus.