GPU621 Course Outline

Course Code: GPU621
Course Name: Parallel Algorithms and Programming Techniques
Offered Date: Winter - 2022 | Other versions
Print Outline
Course 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)
Prerequisite: OOP345
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
Learning Outcomes:
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
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
Prescribed Text(s):

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
Supply:

Multi-Core Desktop or Laptop

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.senecacollege.ca/about/policies/student-progression-and-promotion-policy.html

Grading Policyhttp://www.senecacollege.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.senecacollege.ca/about/policies/academics-and-student-services.html) or at Seneca's Registrar's Offices. (https://www.senecacollege.ca/registrar.html).


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%

Approved By:
Mary-Lynn Manton
Cheating and Plagiarism:
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.senecacollege.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 and 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@senecacollege.ca.
Accomodation 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.