Home

DPS921 Course Outline

Course Code: DPS921
Course Name: Parallel Algorithms And Programming Techniques
Offered Date: Fall - 2017 | 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 BSD - Bachelor of Technology (Software Development)
Prerequisite: BTP305
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
6. Analyze a parallel algorithm using a debugging tool to locate errors in the algorithm
Topic Outline:
Introduction - 15%
        Complexity Theory
        Terminology
            Tasks, Data, Dependencies
            Granularity, Locality, Scalability, Parallel Slack
        Performance Theory
            Amdahl, Gustafson-Barsis, Work-Span
            Big-O, Big-Omega, Big-Theta
        Architectures and Models
            Processes, Threads
            Shared Memory, Distributed Memory
            Hardware Mechanisms
        Design Issues
            Identifying Dependencies
            Communication Issues
            Implementing Granularity
            Input and Output
        Programming Models
            Shared Memory
            Distributed Memory
            Composability
            Compilers - Parallel Studio, GNU g++

Shared Memory Programming - 45%
        OpenMP
            Fundamentals
            Map, Reduce, Scan
        Cilk Plus
            Fundamentals
            Map, Reduce, Scan, Fork-Join, Pipeline, Geometric Decomposition
        Threading Building Blocks
            Fundamentals
            Map, Reduce, Scan, Fork-Join, Pipeline, Geometric Decomposition

Distributed Memory Programming - 20%
        Message-Passing Interface
            Fundamentals
                Primitives, P2P, Environment Management
            Collectives
                Broadcast, Scatter, Gather, Reduction, Scan

Patterns and Algorithms - 10%
        Control Flow
        Data Management

Tools - 10%
        Profiling, Analysis, Debugging
Prescribed Text(s):

Parallel Algorithms and Progrmamming Techniques
By C.M. Szalwinski
https://scs.senecac.on.ca/~gpu621

Reference Material:

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

Supply:
Desktop or Laptop with an Accelerator
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


Grading Policy
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/academic-policy) or at Seneca's Registrar's Offices.


Evaluation:

Assignment 30%

Labs 20%

Test 20%

Exam 30%

Approved By:
Mary-Lynn Manton
Cheating and Plagiarism:
Each student should be aware of the College's policy regarding Cheating and Plagiarism. Seneca's Academic Policy will be strictly enforced.

To support academic honesty at Seneca College, all work submitted by students may be reviewed for authenticity and originality, utilizing software tools and third party services. Please visit the Academic Honesty site on http://library.senecacollege.ca for further information regarding cheating and plagiarism policies and procedures.
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 Disabilities Services Office at ext. 22900 to initiate the process for documenting, assessing and implementing your individual accommodation needs.