GPU621 - Parallel Algorithms and Programming Techniques

Outline info
Semester
School
Last revision date 2023-10-02 00:46:54.89
Last review date 2023-12-04 00:15:10.425


Subject Title
Parallel Algorithms and Programming Techniques

Subject Description

Data-intensive and compute-intensive problems benefit from programming solutions that execute instructions in parallel. A variety of programming models are available for implementing parallel algorithms. Students study industry-standard parallel patterns and learn how to implement parallel algorithms on multi-processor accelerators, shared-memory systems and distributed-memory systems using these programming models.

Credit Status
1 credit (3 units)
Professional Option for CPA - Computer Programming and Analysis (Ontario College Advanced Diploma)
Professional Option for CPD - Computer Programmer (Ontario College Diploma)

Learning Outcomes
Upon successful completion of this subject the student will be able to:

1. Create a programming solution using a parallel pattern to solve a specific problem in algorithm design
2. Design a shared-memory solution using directives or extensions to implement a task-parallel or data-parallel pattern
3. Design a distributed-memory solution using a message passing library to scale the solution
4. Compose a programming solution using multiple models to optimize the solution's performance
5. Tune a parallel algorithm using an analysis tool to optimize the algorithm's performance

Academic Integrity
Seneca upholds a learning community that values academic integrity, honesty, fairness, trust, respect, responsibility and courage. These values enhance Seneca's commitment to deliver high-quality education and teaching excellence, while supporting a positive learning environment. Ensure that you are aware of Seneca's Academic Integrity Policy which can be found at: http://www.senecapolytechnic.ca/about/policies/academic-integrity-policy.html Review section 2 of the policy for details regarding approaches to supporting integrity. Section 2.3 and Appendix B of the policy describe various sanctions that can be applied, if there is suspected academic misconduct (e.g., contract cheating, cheating, falsification, impersonation or plagiarism).

Please visit the Academic Integrity website http://open2.senecac.on.ca/sites/academic-integrity/for-students to understand and learn more about how to prepare and submit work so that it supports academic integrity, and to avoid academic misconduct.

Discrimination/Harassment
All students and employees have the right to study and work in an environment that is free from discrimination and/or harassment. Language or activities that defeat this objective violate the College Policy on Discrimination/Harassment and shall not be tolerated. Information and assistance are available from the Student Conduct Office at student.conduct@senecapolytechnic.ca.

Accommodation for Students with Disabilities
The College will provide reasonable accommodation to students with disabilities in order to promote academic success. If you require accommodation, contact the Counselling and Accessibility Services Office at ext. 22900 to initiate the process for documenting, assessing and implementing your individual accommodation needs.

Camera Use and Recordings - Synchronous (Live) Classes
Synchronous (live) classes may be delivered in person, in a Flexible Learning space, or online through a Seneca web conferencing platform such as MS Teams or Zoom. Flexible Learning spaces are equipped with cameras, microphones, monitors and speakers that capture and stream instructor and student interactions, providing an in-person experience for students choosing to study online.

Students joining a live class online may be required to have a working camera in order to participate, or for certain activities (e.g. group work, assessments), and high-speed broadband access (e.g. Cable, DSL) is highly recommended. In the event students encounter circumstances that impact their ability to join the platform with their camera on, they should reach out to the professor to discuss. Live classes may be recorded and made available to students to support access to course content and promote student learning and success.

By attending live classes, students are consenting to the collection and use of their personal information for the purposes of administering the class and associated coursework. To learn more about Seneca's privacy practices, visit Privacy Notice.

Prerequisite(s)
OOP345

Topic Outline

  • Introduction - 15%
    • Complexity and Performance
      • Complexity Classes, P versus NP
      • Big-O, Big-Theta, Big-Omega
      • Amdahl, Gustafson, Work-Span
    • Parallel Platforms
      • High Performance Computing
      • Machine Architectures, Hardware
    • Programming Models
      • Shared Memory, Distributed Memory
      • PGAS, SPMD, Manager Worker
    • Elements of Design
      • Granularity, Locality, Scalability, Portability
      • Hardware Mechanisms: Threads, Vectors
      • Task Units, Data Units, Dependencies
      • Domain, Functional Decomposition
    • Parallel Patterns
      • Control Flow, Data Management, Overview
    • Compiler Support
      • C, C++11, GCC, Visual Studio, Parallel Studio
  • Languages - 60%
    • OpenMP
      • Fundamentals - Directives, Environment, Runtime
      • Dependencies - Loop Level
      • False Sharing
      • Examples - Map, Reduce, Scan, Convolution
    • Threading Building Blocks
    • Cilk Plus
      • Fundamentals - Environment, Keywords
      • Task Parallelism, Data Parallelism
      • Fork Join
    • Message Passing Interface
      • Fundamentals - Primitives, P2P
      • Collectives - Scatter, Gather, Reduction
      • Examples - Data Decomposition
  • Programming Support - 15%
    • Parallel Profiling
    • Debugging
    • Memory Checking - Inspector
    • Optimization, Fine Tuning - VTune
  • Case Studies - 10%
    • Design Patterns
    • Math Libraries
    • Data Libraries

Mode of Instruction
Modes: In-class lecture, in-class exercises, and hands-on activity
Hours per week: 4
Room configurations: Computer lab
Typical scheduling pattern: Winter term

Prescribed Texts

Parallel Algorithms and Programming Techniques (online)
By Szalwinski, C.M.
https://scs.senecac.on.ca/~gpu621

Reference Material
Structured Parallel Programming
by McCool, M., Robison, A.D., Reinders, J.,
Published by Morgan Kaufmann
ISBN 978-0-12-415993-8

Required Supplies

Multi-Core Desktop or Laptop

Student Progression and Promotion Policy

  • Achieve a passing grade on the final exam
  • Satisfactorily complete all assignments
  • Achieve a passing grade on the weighted average of the tests and final exam
  • Achieve a passing grade on the overall course


http://www.senecapolytechnic.ca/about/policies/student-progression-and-promotion-policy.html

Grading Policyhttp://www.senecapolytechnic.ca/about/policies/grading-policy.html

A+ 90%  to  100%
A 80%  to  89%
B+ 75%  to  79%
B 70%  to  74%
C+ 65%  to  69%
C 60%  to  64%
D+ 55%  to  59%
D 50%  to  54%
F 0%    to  49% (Not a Pass)
OR
EXC Excellent
SAT Satisfactory
UNSAT Unsatisfactory

For further information, see a copy of the Academic Policy, available online (http://www.senecapolytechnic.ca/about/policies/academics-and-student-services.html) or at Seneca's Registrar's Offices. (https://www.senecapolytechnic.ca/registrar.html).


Modes of Evaluation

Workshops (minimum 10) - 30%

Project - 20%

Tests without Final Exam (minimum 5 tests) - 50%

Tests with a Final Exam (minimum 5 tests) - 35%

Final Exam (optional) - 15%

Late and/or missed assignments
Late and/or missed assignments: Assignments are expected to be handed in at the start of the class on the due date. If an extension has been negotiated, those submitted after that time will be subject to a penalty of one letter grade per day, to a maximum of seven days. After that time the assignment will no longer be accepted.
 
Class Presentations: Proper academic performance depends on students doing their work not only well, but on time. In the discipline of the film industry, absences are simply not accepted and will result in quick dismissal and a bruised reputation. Accordingly, class presentations for this course must be performed on the due dates specified for the assignment, as indicated in the class schedule, or as determined by the instructor.
 
Missed Class Presentation Penalty: Missed class presentations on the due date will be penalized with a grade of zero for the absent student.  Exceptions to the missed class presentation penalty for valid reasons such as illness, compassionate grounds, etc., may be entertained by the instructor but will require supporting documentation (e.g., a doctor’s letter). The instructor will attempt to reschedule the missed class presentation to facilitate scene partners or group members affected by the absence. Any student with an unexcused absence necessitating a rescheduled presentation will continue to receive a grade of zero for the presentation in question. Assigning alternate partners or proceeding with group presentations without the student with the unexcused absence may be implemented.
 
Attendance and punctuality are required in order to be successful in the business – to instill good habits now, you will be counted as ‘late’ 5 minutes after the official class start-time and counted as ‘absent’ 15 minutes after the official class start-time.

Approved by: Mary-Lynn Manton