Syllabus and Material for Data Parallel Programming (DPP)

Welcome to the course website for DPP! All material and general information will be provided here. Announcements, assignment handin, and the discussion forum remains on Absalon. While this website is a Git repository, you are not required or expected to use Git to interact with it, but feel free to do so if convenient for you.

Course Structure

DPP is structured around five weeks with lectures and lab sessions on Monday and Wednesday, followed by a final project to be presented orally at the exam. Throughout the course, you will hand in four weekly assignments. The assignments count for 40% of the grade, while the exam counts for 60%.

The teachers are Cosmin Oancea and Troels Henriksen.

All lectures and lab sessions will be delivered in English. The assignments and projects will be posted in English, and while you can chose to hand in solutions in either English or Danish, English is preferred.

There is no mandated textbook for the course - you will be assigned reading material from papers and such.

We have also begun work on some DPP course notes PDF, although they are currently quite embryonic, and it is not certain we will have time to add much content this year. Please let us know if there is anything in particular you would like to see.

Course schedule

TBA once KU fights off all those villanous hackers.

Lectures:

• Monday 13:00 - 15:00 in Aud 03 at August Krogh (AKB)
• Wednesday 10:00 - 12:00 in 1-0-37 at the DIKU Pavillon

Labs:

• Monday 15:00 - 17:00 in Aud 02 at August Krogh (AKB).
• Wednesday 13:00 - 15:00 in 1-0-37 at the DIKU Pavillon.

This course schedule is tentative and will be updated as we go along. The lab sessions are aimed at providing help for the weeklies and group project. Do not assume you can solve them without showing up to the lab sessions.

Lecture plan

Week 1

Monday

• Theme: Intro, deterministic parallelism, data parallelism, Futhark.

• Material:

  • Parallel Programming in Futhark (particularly Practical Matters)

  • Futhark exercises

Wednesday

• Theme: Cost models, advanced Futhark.

• Material:

  • Guy Blelloch: Programming Parallel Algorithms

  • Prefix Sums and Their Applications

  • A Provable Time and Space Efficient Implementation of NESL

Week 2

Monday

• Theme: Part I: Flattening Nested and Irregular Parallelism

• Demo Code

  • Lecture's Running Example

• Facultative Material:

  • Various papers related to SCAN and flattening, but which are not very accessible to students

  • PMPH Lecture Notes, chapter 4(pdf and bib)

Wednesday

• Theme: Part II: Flattening Nested and Irregular Parallelism

• Demo Code

  • ``To flatten or not To flatten, that is the question'': Matrix Multiplication Demo

• Facultative Material:

  • same as above

Week 3

Monday

• Theme: Composing list homomorphisms

• Material:

  • More Fun with Monoids

Wednesday

• Theme: Pointer Structures

• Material:

  • The Complexity of Parallel Computations (section 4.1.2)

  • Data Parallel Algorithms by Hillis and Steele

  • Aaron Hsu's PhD dissertation (sections 3.2 and 3.3, but the lecture slides should be enough)

Week 4

Monday

• Theme: Part I: Automatic Differentiation

• Facultative Material consists of several papers:

  • "Automatic Differentiation in Machine Learning: a Survey" (generic)

  • "AD for an Array Language with Nested Parallelism" (Futhark)

  • "Reverse-Mode AD of Multi-Reduce and Scan in Futhark" (Futhark)

  • "Parallelism-Preserving Automatic Differentiation for Second-Order Array Languages"

Wednesday

• Theme: Part II: Automatic Differentiation

• Facultative Material:

  • same as above

Week 5

Monday

• Theme: ISPC (maybe)

• Material:

  • ispc: A SPMD Compiler for High-Performance CPU Programming

  • Exercises

Wednesday

• Theme: Introduction to Polyhedral Analysis

• Demo Code

  • You will need the islpy python module ($ pip install islpy)

  • Several solved examples

  • Several facultative exercises mentioned in the last section of the slides

• Facultative Material:

  • Chapter 5 of PMPH Lecture Notes, entitled "Loop-based data-dependence analysis and applications" introduces a simpler analysis based on direction vectors

  • Presentations, tutorial and paper related to polyhedral analysis, whose internet references were linked from the slides as well

Weekly assignments

The weekly assignments are mandatory, must be solved individually, and make up 40% of your final grade. Submission is on Absalon.

The assignment text and handouts will be linked in the schedule above.

Feedback and resubmission

Your TA, Lilje, will be grading and providing feedback on your weekly assignments. You receive feedback within a week of the handin deadline, and one resubmission attempt is granted for each weekly assignment, which may be used to solve tasks missing in the original hand-in and/or to improve on the existing hand-in (but note that feedback may be sparse for resubmissions).

As a rule of thumb, the resubmission deadline is two weeks from the original handin deadline, but it is negotiable.

Extensions may be granted on weekly assignment (re-)submission deadlines -- please ask Lilje if for any reason, personal or otherwise, you need an extension (no need to involve Cosmin or Troels unless you wish to complain about Liljes decision).

Group project and exam

The final project, along with the exam as a whole, contributes 60% of your grade, and is done in groups of 1-3 people (although working alone is strongly discouraged). We have a tenative list of project suggestions, but you are free to suggest your own (but please talk with us first). Since the time to work on the project is rather limited, and there is no possibility of resubmission, you should ask for help early and often if you are having trouble making progress. The project should be handed in via Absalon in TBA. Send an email if you have trouble meeting this deadline.

Most of the projects are about writing some parallel program, along with a report describing the main points and challenges of the problem. The exam format is a group presentation followed by individual questions about both your project and anything else in the curriculum. Each group prepares a common presentation with slides, and each member of the group presents non-overlapping parts of the presentation for about 10 min (or less). Then each member of the group will answer individual questions for about 10 min.

Practical information

TA

Your TA is Lilje Henrich Due (due@di.ku.dk). Lilje will be grading your weekly assignments.

Hendrix GPU cluster

You may find it useful to make use of DIKUs GPU machines in your work. We recommend using the so-called Hendrix cluster. If you are enrolled in the course, you should already have access. Otherwise contact Troels at athas@sigkill.dk. For how to access Hendrix, follow the first link in this paragraph.

Consider using sshfs to mount the remote file system on your local machine:

$ mkdir remote
$ sshfs hendrix:/ remote

Also see here for more hints.

Using Hendrix

The DIKU systems have a conventional HPC modules setup, meaning you can make additional software available with the module command. You may need to do this inside SLURM jobs.

Loading CUDA

$ module load cuda

Loading Futhark

$ module load futhark

Loading ISPC

$ module load ispc

(Although there is no reason to use Hendrix for ISPC - it will run fine on your machine.)

Other resources

You are not expected to read/watch the following unless otherwise noted, but they contain useful and interesting background information.

• The Futhark User's Guide, in particular Futhark Compared to Other Functional Languages

• Troels' PhD thesis on the Futhark compiler

• A library of parallel algorithms in NESL

• Functional Parallel Algorithms by Guy Blelloch

• "Performance Matters" by Emery Berger

• The story of ispc (you can skip the stuff about office politics, although it might ultimately be the most valuable part of the story)

• Scientific Benchmarking of Parallel Computing Systems (we benchmark much simpler systems and don't expect anywhere near this much detail, but it's useful to have thought about it)

Acknowledgements

NVIDIA has donated GPUs used for teaching DPP for several years.

Thanks to Filippa Biil for the hedgehogs above, and Lilje Due for the ones below.