The University of Western Ontario
London, Canada

Department of Computer Science

CS3101b -- Theory and Practice of High-performance Computing

Course Web Site -- Winter 2015

Course Description

The efficient usage of parallel and distributed systems (multi-core processors, general purpose graphics processing units, computer networks, etc.) is nowadays an essential task for computer scientists.

This course is built on the principle that, in parallelism, the models of computation that have a practical value are those which bear a relationship to what happens in hardware. Thus this course will interleave fundamental topics from computer architecture and algorithms including: memory hierarchy and issues with data traffic, performance analysis, control parallelism architecture models, highly data parallel architecture models, models of parallel computations and complexity analysis of parallel algorithms, patterns and paradigms of parallel algorithms, concurrent data structures, synchronization and scheduling.

Part of the materials from the course CS 2101a - Foundations of Programming for High Performance Computing and from the from last year's edition of CS 9535 and CS 4402 - Distributed and Parallel Systems.

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

Instructor

Name:Marc Moreno Maza
Office:MC 327
Office Hours: Tuesday 2:30-4:40 pm and Thursday 1:30-3:30 pm in MC327
Email:morenoATcsd.uwo.ca
Phone:661-2111 x3741

Lecture Notes and Textbook

Notes of each lecture are available on the course website, approximately one or two days after the oral presentation. Lecture notes will be found in under "Lecture Topics". There is one suggested (but not required) textbook: Parallel Algorithms by Henri Casanova, Arnaud Legrand and Yves Robert.

Course Website

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!

Course outline

Please find the course outlie here.

Lecture Topics

The list of topics will be something on the order of:

  1. Distributed and parallel computing with the Julia interactive system
  2. Cache memories and their impact on the performance of computer programs
  3. Multicore architectures and the fork-join multithreaded parallelism
  4. Analysis of fork-join multithreaded algorithms
  5. Practical issues with data locality and parallelism on multicore architectures
  6. Fundamental models of concurrent computations (PRAM and its variants)
  7. Highly data parallel architecture models (pipeline, stream, vector, etc.)
  8. Many-core processors (GPGPUs) with an overview of many-core programming
  9. Multi-processed parallelism with an overview of message passing (MPI)

Lecture Notes

  • Introduction to CS3101:     pdf
  • Parallel Computing with Julia:     pdf
  • Multicore Programming. slides and my dotbashrc for running CilkPlus in the lab.
  • Multithreaded Parallelism and Performance Measures. slides
  • Issues with Multithreaded Parallelism on Multicore Architectures. slides and handouts.
  • Analysis of divide and conquer algorithms. slides and handouts.
  • Analysis of multithreaded algorithms. slides and handouts.
  • Parallel Random-Access Machines. slides and handouts.
  • Problem sets

  • Lab 2:     pdf and Lab 2: Solution hints
  • Lab 3:     pdf and Lab 3: Solution hints
  • Problem set 1
  • testplt.sh: GNUplot script example
  • xyz.tsv: input date for testplt.sh
  • Quiz 1 with solutions.
  • Problem set 2
  • Midterm with solutions to exercises 2 and 3.
  • Quiz 2 with solutions.
  • Problem set 3
  • Quiz 3 with solutions.
  • lower_trianguular_matrix.cpp and its Makefile
  • Class Schedule

    Each student is expected to attend all the lectures. In particular, quizzes (short written tests) may take place without notice.

    Student Evaluation

    Assignment/Exams/Quiz Schedule

    All dates are tentative and currently subject to change, although it is doubtful by any significant amount.

    Evaluation Technique Weight Posted Date (tentative!) Due Date (tentative!) Workload
    Assignment One10%Th, Jan. 22Fr, Feb. 13regular
    Assignment Two10%Wed, Feb. 11Tu, Feb. 3regular
    Assignment Three10%Th, Mar. 12Fr, Mar. 27regular
    Midterm exam 20%N/AWed, Mar. 4heavy
    Quizzes5% eachN/AvariousN/A

    Quizzes

    Quizzes may be held without being announced in advance.

    Quizzes will be closed book.

    Assignments

    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.

    Computing Facilities

    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 Rules of Ethical Conduct

    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 Room 346.

    Email Contact

    The instructor will occasionally need to send email messages to the whole class, or to students individually. Email will be sent to your GAUL email address. You must make sure that you read your email on GAUL on a frequent and regular basis, or have it forwarded to an alternative email address if you prefer to read it there.

    However, you should note that email at ITS (your UWO account) and other email providers such as hotmail.com or yahoo.com may have quotas or limits on the amount of space they can use. If you let your email accumulate there, your mailbox may fill up and you may lose important email from the instructor. Losing email that you have forwarded to an alternative email address is not an excuse for not knowing about the information that was sent.

    Students can ask questions via email, however if there are any large, somewhat complicated issues, it is recommended to discuss them during office hours. Moreover, you MUST use your UWO account or your GAUL account in order to write to the instructor. (Emails from non-academic accounts will be automatically ignored.) In addition, you must include "CS4402" in the subject line.

    Academic Accommodation for Medical Illness

    If you are unable to meet a course requirement due to illness or other serious circumstances, you must provide valid medical or other supporting documentation to your Dean's office as soon as possible and contact your instructor immediately. It is the student's responsibility to make alternative arrangements with their instructor once the accommodation has been approved and the instructor has been informed. In the event of a missed final exam, a "Recommendation of Special Examination" form must be obtained from the Dean's Office immediately. For further information please see http://www.uwo.ca/univsec/handbook/appeals/medical.pdf.

    All students who are in emotional/mental distress should refer to Mental Health@Western. for a complete list of options about how to obtain help. For further information please see http://www.uwo.ca/univsec/handbook/appeals/medical.pdf.

    A student requiring academic accommodation due to illness should use the Student Medical Certificate when visiting an off-campus medical facility or request a Record's Release Form (located in the Dean's Office) for visits to Student Health Services. The form can be found at https://studentservices.uwo.ca/secure/medical_document.pdf.

    Accessibility Statement

    Please contact the course instructor if you require material in an alternate format or if you require any other arrangements to make this course more accessible to you. You may also wish to contact Services for Students with Disabilities (SSD) at 661-2111 x 82147 for any specific question regarding an accommodation.

    Ethical Conduct

    All assignments are individual assignments. You may discuss approaches to problems among yourselves; however, the actual details of the work (assignment coding, answers to concept questions, etc.) must be an individual effort. Assignments that are judged to be the result of academic dishonesty will, for the student's first offense, be given a mark of zero with an additional penalty equal to the weight of the assignment also being applied.

    Students must write their essays and assignments in their own words. Whenever students take an idea, or a passage from another author, they must acknowledge their debt both by using quotation marks where appropriate and by proper referencing such as footnotes or citations. Plagiarism is a major academic offense (see Scholastic Offense Policy in the Western Academic Calendar).

    The University of Western Ontario uses software for plagiarism checking. Students may be required to submit their written work and programs in electronic form for plagiarism checking.

    Scholastic offenses are taken seriously  and students are directed to read the appropriate policy, specifically, the definition of what constitutes a Scholastic Offense, at the following Web site: http://www.uwo.ca/univsec/handbook/appeals/scholoff.pdf.


    Marc Moreno Maza
    Last modified: Mon Jan 7 10:21:44 EDT 2013