The University of Western Ontario
Department of Computer Science
Distributed and Parallel Systems
Course Web Site -- Winter 2018
To best utilize parallel and distributed systems (multi-core,
many-core and cluster) is nowadays an essential task for computer
This course studies the fundamental aspects of parallel systems and
aims at providing an integrated view of the various facets of software
development on such systems: hardware architectures, programming
languages and models, software development tools, software engineering
concepts and design patterns, performance modelling and analysis,
experimenting and measuring, application to scientific computing.
Course topics may include but are not limited to:
- multi-core, GPGPU, cluster, distributed and shared memory, hierarchical memory,
- multi-thread (Julia, CilkPlus, OpenMP), multi-process, message passing (Julia, MPI),
- scheduling (work-stealing scheduler) and synchronization,
- parallel algorithm design and multithreaded program analysis: parallelism, granularity, memory bandwidth issue, scalability, data locality and cache complexity,
- Intel Parallel Composer (Cilk Plus, ArBB, TBB), data race and performance analyzer (Cilkview, Vtune)
- NVIDIA's CUDA for GPU
- Message Passing Interface (MPI)
- high-performance software engineering techniques,
- fundamental applications: matrix multiplication, matrix transposition, FFT, reduction, scan, sort, etc.
Follow this link for various resources
(software tools and tutorials, hardware documentation,
conferences, other HPC course web sites, etc.)
regarding this course and HPC in general
Prerequisites for Undergraduate Students
Students must be fluent in C or C++; they must also be familiar
with UNIX software tools (shell scripts, makefiles, debuggers).
|Name:||Marc Moreno Maza
|Office Hours:|| Tuesday 1:30-3:20 pm in MC 327
Lecture Notes and Textbook
Notes of each lecture will be available on the course website, approximately one
or two days after the oral presentation.
There is no textbook.
The course web site is accessible from: http://www.csd.uwo.ca/~moreno/CS9635-4402-1718.html
Please check the site often for updates on lecture notes and errata.
Also be aware that
the course website is not a substitute for actual classroom attendance!
Please find the course outline
The list of topics will be something in the order of:
Overview of parallel computing
Parallel and distributed computing with Julia
The Cilk concurrency platform
Multithreaded parallelism and performance
Scheduling and Synchronizing
Pipelining (Cilk-P, TBB)
Many-core programming (GPGPUs)
Code optimization techniques for multi-cores and GPGPUs
High-Performance Computing with CUDA
Multiprocessed parallelism, message passing (MPI)
Other concurrency platforms (Open MP, Array Building Blocks, Threading Building Blocks)
Relation of CS4402 to CS3101
CS3101 is a new course which has started in the 2012-2013 academic year. Its web site is http://www.csd.uwo.ca/~moreno/CS3101-1415.html This course is meant to provide the necessary theoretical background (architectures, models of computations, algorithms) to understand and practice high-performance computing.
CS3101 can be seen as an extension of other CS courses such as
thus providing the parallel dimension
of Today's Computer Science.
3331A - Foundations of Computer Science I,
3305B - Operating Systems,
3340B - Analysis of Algorithms I,
3350B - Computer Architecture,
Students who are taking CS4402 the academic year 2017-2018
are likely not to have taken CS3101 in previous years since it was not offered last year.
Therefore, for the academic year 2017-2018, CS4402 is a self-contained
course (as in previous years)
where a sufficient subset of this
theoretical background is presented.
Lecture Notes from 2016-2017
An introduction to parallel and distributed computing
slides (long version) and
slides (short version).
Parallel and distributed computing with Julia
The Fork-Join Model and its Implementation in Cilk
slides. Some examples of CilkPlus programs and a few more
Analysis of Multithreaded Algorithms.
Cache memories: complexity analysis and practical issues.
Parallel Prefix Sum
MetaFork: A Compilation Framework for
Concurrency Platforms Targeting Multicores
(by Xiaohui Chen).
Many-core Computing with CUDA.
simple CUDA programs.
High-Performance Computing with CUDA.
Parallel Random-Access Machines.
A Many-core Machine Model for Designing Algorithms with Minimum
Synchronizing without locks.
Issues in Parallelism (by Matteo Frigo).
Problem Sets from 2016-2017
Problem set 1
Problem set 2
Readings for Problem Set 1
All-Pair Shortest Paths: course notes.
All Pair Shortest Paths and Matrix Multiplication: book chapter
Parallel Algorithms for the All-Sources Generalized Shortest Paths Problem: article by Jeffrey D. Oldham and Vaughan Pratt.
Quiz corrections from 2014-2015
Quiz 1: elements of corrections for a 2014 quiz.
A CUDA quiz and its
elements of correction.
2015 Quiz 2 with elements of corrections.
Quiz corrections from 2016-2017
Quiz 1 with elements of corrections.
Quiz 2 with elements of corrections.
Lectures: 3 hours (Tuesdays 15:30 - 16:20 in MC 320 and Wednesdays15:30 - 17:20 in MC-320.
Each student is expected to attend the lectures. In particular, quizzes (short written tests) may take place without notice.
Evaluation methods are quizzes, assignments and projects.
Assignments and projects constitute
1/3 and 1/3 of the course mark, respectively.
There is no midterm examination and no final examination.
However, there will be at least three quizzes.
Quizzes constitute the last 1/3 of the course mark.
Assignments consist of theoretical and programming exercises.
CS 4402 projects can be theoretical work (research article
(programming, experimentation and analysis)
or a combination of both.
CS 9635 projects are more advanced and must deal with current
research topics, see details below.
A quiz is a series of short and simple exercises similar
to the examples of the course notes, whereas assignments consist
of more advanced exercises.
In order to successfully complete the course, a student
must achieve at least 50% on assignments, 50% on projects and 50% on quizzes.
This is to prevent a serious lack of effort in either area.
Thus, a student cannot get 100% on assignments and projects
and barely pass the quizzes.
A CS4402 project topic is chosen by the student
from a list of topics proposed by the instructor.
Project topics will be posted by February 14 (tentative)
and each student must choose a project topic by March 21 (at the very latest).
The projects will be presented in class by the students during the last
week of classes. Each presentation will consist
of a 15 minute talk followed by questions for 10 minutes.
A detailed project report will also be required and due
by April 6.
For CS9635, there is no Assignment Two, while the Project
is of much larger scale and start during the Assignment Two period.
CS9635 projects must deal with current
research topics (in the scope of this course's contents)
and can be related to the student thesis (in fact, this is
The topic of each CS9635 project must be discussed
individually with the instructor during the Assignment Two period.
This implies a literature review to be done by the student
and presented to the instructor during a face-to-face meeting.
By March 7, (preferably earlier) the objectives of each
CS9635 project must be well-defined by the student
and approved by the instructor. Together with the literature review,
this will give the mark for
Projects must then be implemented and will be presented
in class during the last week of classes, as for CS4402.
With this definition of the CS9635 project and CS9635 Assignment Two,
the mark allotment is the same as for CS4402. That is,
assignments, projects and quizzes constitute
1/3, 1/3 and 1/3 of the CS9635 mark, respectively.
All dates are tentative and currently subject to change, although it is
doubtful by any significant amount.
||Posted Date (tentative!)
||Due Date (tentative!)
|Assignment One||1/6||Tu, Jan. 23||Fr, Feb. 16||regular
|Assignment Two||1/6||Tu, Mar. 7||Tu, Mar. 21||regular
|Project ||1/3||Fr, Feb. 14||Wed, Apr. 6||heavy
If for any reason the schedule given above cannot be adhered to, the
assignment, project and quiz marks will be pro-rated. For instance,
if an assignment has to be cancelled for
any reason, the remaining assignment weight will be prorated to add up to 1/3.)
Every effort will be made to have assignments, projects and quizzes marked and handed
back within 3 weeks of the hand-in date, preferably sooner.
Quizzes may be held without being announced in advance.
Quizzes will be closed book.
Assignments will be due on the (tentative) dates listed above.
The assignment will be sent by email to the instructor.
Extensions will be granted only by the course instructor. If you have
serious medical or compassionate grounds for an extension, you
should take supporting documentation to the office of the Dean
of your faculty, who will contact the instructor.
Each student will be given an account on the Computer Science Department senior
undergraduate computing facility, GAUL. In accepting the GAUL account, a student agrees
to abide by the department's
Note: After-hours access to certain Computer Science lab rooms is by student card. If a
student card is lost, a replacement card will no longer open these lab rooms, and the
student must bring the new card to a member of the Systems Group in Middlesex College
Marc Moreno Maza
Last modified: Mon Jan 10 EDT 2017