CPTR 551
Parallel and Distributed Systems Winter 2016

Rick Halterman

School of Computing
1117E Hickman Hall
Southern Adventist University
Collegedale, TN 37315-0370
423-236-2871

halterman@southern.edu
http://computing.southern.edu/halterman

Office Hours: http://computing.southern.edu/halterman/General/OfficeHours

HSC 1307   Monday 5:15pm–7:45pm

• Main textbook: Herlihy, Maurice and Sahvit, Nir. The Art of Multiprocessor Programming. 2012.

• Programming language support:
  • Halterman, Richard. Object-oriented Programming in Java. 2007.
  • Halterman, Richard. Fundamentals of C++ Programming. 2016.

CPTR 365, CPTR 318 or equivalents

Catalog description:

CPTR 551. Parallel and Distributed Systems 3 hours
Prerequisite(s): CPTR 365, CPTR 318 or equivalents
Fundamentals of parallel and distributed computing, computational models, parallel/concurrency languages and algorithm, performance evaluations, and multi-tier computing. (Winter Even Years)

Class Work. The following class activities, weighted as indicated, determine the student's overall average for the course.

Activity	Weight
Quizzes	20%
Project/Report 1	20%
Project/Report 2	20%
Project/Report 3	20%
Project/Report 4	20%

Grade Distribution. The overall average determines the course grade according to the following table:

Overall Average (a)	Letter Grade
92 ≤ a	A
90 ≤ a < 92	A–
88 ≤ a < 90	B+
82 ≤ a < 88	B
80 ≤ a < 82	B–
78 ≤ a < 80	C+
70 ≤ a < 78	C
60 ≤ a < 70	C–
58 ≤ a < 60	D+
52 ≤ a < 58	D
50 ≤ a < 52	D–
a < 50	F

Programming Experience. This course assumes students have a working knowledge of a C-like programming language: C++, C, Java, C#, or Objective-C. Java and C++ are the primary languages used in the course. The supplemental programming books above introduce Java and C++ to students with no experience in those languages. Please review the material at The C++ Language Tutorial website to brush up on your C++ skills. This site also has a downloadable PDF version of its C++ tutorial. Oracle provides a comprehensive Java tutorial.

This course is project-intensive. This means you should expect to spend considerable time working on the programming projects. Generally, you must submit each project electronically, as described in class. Your code will be compiled and checked for correctness and completeness. You may elect to work in any environment and upon any platform, but Java programs must compile and run correctly under Oracle's Java 8 (JDK 1.8.0_66, available for free at http://www.oracle.com/technetwork/java/javase/downloads/index.html). A number of free professional grade Java IDEs exist, including Eclipse (https://eclipse.org), NetBeans (https://netbeans.org), and IntelliJ IDEA (https://www.jetbrains.com/idea/ free community edition). Your C++ programs compile and run correctly under Microsoft Visual Studio 2015 Community Edition using Visual C++. Visual Studio is available on the departmental lab workstations, and students can get Visual Studio for free from https://www.visualstudio.com/en-us/downloads/download-visual-studio-vs.aspx. Any modern C++ compiler that supports C++14 features (such as the current versions of GCC and Clang) is an acceptable alternative.

Class Work and and Projects. Appropriate study for the course includes reading the textbook (at least as far as last class's lecture material) and working through the exercises at the end of each chapter. Periodic quizzes encourage students to remain current in their class preparation. Usually quizzes will appear on eclass and have a fixed time window for completion.

Students will investigate and report on several topics not included in the textbook. As set of potential projects will be provided. Each investigation will involve implementing a software system that showcases the topic's utility. Students then will introduce their topic to the rest of the class and share their experiences.

Ethics. It is expected that each student work individually on projects. Any work or portion thereof derived from an outside source must be documented as such. Students representing the work of others as their own without giving due credit to the original authors risk receiving zero credit for the project and a grade of F in the course.

All incidents of academic dishonesty will be reported to the Associate Vice-president of Academic Affairs.

Class decorum. Please comply with the standards of classroom attire as specified in the Student Handbook.  Notebook computers are welcome, and the classroom and lab (generally) have an excellent wireless signal.  Those with computers should mute the volume and sit in the rear of the class so as not to distract students behind them.

Students are expected to attend class and participate. Electronic attendance is possible with instructor approval.

Extra credit. Since the assigned activities are sufficient for most students, no extra credit will be available for additional work. However, well-prepared students wishing to enhance their learning experience beyond the class activities will be directed, upon request, to additional resources. Any such additional work will not influence the grade for this class.  

SAU account.  All students must have an active Southern Adventist University email account. This account is necessary to receive class messages and to be able to use the computers in the programming lab. If you normally use a different email address, please set up your SAU account to forward your email to your preferred address; instructions about how to do this are available upon request.

Learning Success Services. In keeping with University policy, any student with a disability who needs academic accommodations must call Disability Support Services at 236-2574 or stop by Lynn Wood Hall, room 308, to arrange a confidential appointment with the Disability Services Coordinator during the first week of classes. (Students who request accommodations after the third week of the semester should not depend on receiving accommodations for that semester. Legally, no retroactive accommodations can be provided. For more details, visit the Learning Success Services Web site at http://lss.southern.edu/.) Students whose accommodations requests are approved will be provided confidential letters for them to deliver to their professors for review and discussion about how to implement the accommodations in relation to particular course requirements. Accommodations for disabilities are available only as recommended by Disability Support Services.

Date	Text Chapter	Topics
January 11	1	Introduction to parallelization: shared objects and synchronization, producer-consumer problem, readers-writers problem, parallel programming
January 18	–	No class: Martin Luther King Jr. Day/Community Service Day
January 25	2, 3	Mutual exclusion and concurrent objects: critical sections, two-thread solutions, filter lock, fairness, Bakery algorithm, bounded timestamps, concurrency correctness, quiescent consistency, sequential consistency, linearizability, progress conditions
February 1	4, 5	Foundations of shared memory, primitive synchronization primitives: space of registers, register construction, atomic snapshots, consensus numbers and protocols, atomic registers, FIFO queues, read-modify-write operations
February 8	6	Universality of consensus: universality, lock-free universal construction, wait-free universal construction
February 15	7	Spin locks and contention Spin locks, monitors, and blocking synchronization: test-and-set locks, exponential backoff, queue locks, composite lock, hierarchical locks
February 22	8	Monitors and blocking synchronization: monitor locks and conditions, readers-writers locks, semaphores
February 29	9	Concurrent lists: locking, concurrent reasoning, coarse- vs. fine-grained synchronization, optimistic, lazy, and non-blocking synchronization
March 7	–	No class: Spring Break
March 14	10, 11	Concurrent queues and stacks: locking, ABA problem, bounded and unbounded queues, lock-free queues and stacks, elimination
March 21	12	Counting, sorting, and distributed coordination: shared counting, software combining, quiescently consistent pools and counters, counting networks, diffracting trees, parallel sorting, sorting networks, distributed coordination
March 28	13	Concurrent hashing and natural parallelism: closed-address hash sets, lock-free hash sets, open-address has sets
April 4	14, 15	Skiplists, balanced search, priority queues: lock-based vs. lock-free skiplists, array-based bounded priority queues, tree-based bounded priority queues, heap-based unbounded priority queues, skiplist unbounded priority queues
April 11	16	Futures, scheduling, and work coordination: analyzing parallelism, realistic multiprocessor scheduling, work stealing dequeues, work balancing
April 18	17	Barriers: sense reversing barrier, combining tree barrier, static tree barrier
April 25	18	Transactional memory: atomicity, software vs. hardware transactional memory
May 2	—	Project Presentations

Individual student project presentations will be scheduled at various dates throughout the semester.

• Monday, January 11: first day of class
• Monday, January 18: no class (MLK Jr./Community Service Day)
• Monday, March 7: no class (spring break)
• Thursday, March 24: Last day to drop a class and receive a W

Code we develop in class is available at here.