CSIS 599 Parallel Programming and Algorithms Spring 2015 Syllabus
Updated Friday, Jan. 9, 2015
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.
Introduction to Parallel Programming 2nd Ed.
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
Hadoop: The Definitive Guide 3rd
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)
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
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
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.
Shared Memory Programming (pThreads and OpenMP)
Message Passing and MPI
Floyd's Algorithm, Dynamic Programming, and Fast Fourier Transform as time permits
Map-Reduce Paradigm and Hadoop
Matrix Multiplication using CUDA
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
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
up to 715
*The instructor reserves the right to give a quiz in lieu of
**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.