TDT 4200 Parallel Computing – Fall 2011

Instructor (Faglærer): Assoc. Prof. Anne C.Elster

Teaching Assistant (Øvingsleder): Ivar Nikolaisen

Student Assistant (Und.ass.er): Ruben Spaans

Student contacts/representatives: Nicholas Gerstle (ngerstle at gmail.com) , David Hebbeker (david.hebbeker at rwth-aachen.de) and Ole Andreas Rydland (orydland at gmail.com)

Credits (Studiepoeng): 7,5

Examination form: Written (skriftlig) midterm: 25% and final: 50% + mandatory graded assignments ( obligatoriske og tellende øvinger):25%

Time and place:

Wednesdays 10:15-12:00 in F3 (Gamle Fysikk)
Thursdays 13:15-14:00 in F2 (Gamle Fysikk) (note change as of Sept 1!)
Recitations (Øvingstimer): Thursdays 14:15-16:00 in EL1 starting Week 36
NO MIDTERM (se studiekatalogen)
FINAL EXAM is 9am-1pm on Dec. 7, 2011 See also link to NTNU's final exam schedule.

You have to notify the instructor at the beginning of the semester if you cannot attend all lectures.

Goal: To give the students a good understanding of how to optimize serial algorithms and programs, as well as teach them how to develop efficient programs on modern multiprocessor systems.

Prerequisites (forutsetninger): Algorithms and Datastructures and Computers and Operating Systems, or the equivalent.

Content (Innhold): Optimization of algorithms and programs for both serial and multi-processor systems. How to choose algorithhms, use of optimized libraries, compiler optimizations, and program profiling. How to take advantage of PC clusters for large computational tasks which would otherwise not fit on a single CPU/PC system, will also be covered.

Teaching form (undervisningsform): Lectures (forelesninger) and recitations/assignments (øvingstimer/øvinger).

PRELIMINARY Syllabus (more details posted soon + see “Pensum” below):

MPI (Message Passing Interface)

Optimizations of serial & parallel codes

Open MP/Phreads

GPU Programming – CUDA and Open CL

Problem Assignments (Øvinger)

All assignments are mandatory (obligatoriske) and at least 3 (selected by instructor) count for a portion of the total grade. They must be done individually, unless otherwise specified! Plagiarism (koking) will not be tolerated.

Assignments handed in after the deadlines without prior authorization from the instructor will not be counted unless a formal medical note can be provided.
(see Syllabus and It's Learning for details re. assignment deadlines.)
Contact the TAsto get on the initial mailing list, get a cluster account, and to make sure to receive the assignments. The first assignment will be posted on August 25 and due 8am on Thursday Sep 1. (extended deadline Sept 8)

We are now a CUDA Teaching Center so a significant portion of the course will be done in CUDA, thanks to NVIDIAs recent donations of 25 GTX480 cards.

Problem set topics due dates (See It’s Learning for final dates and times):

Basic C (Due Sep 9, 10pm) – Pass/Fail
More C and Intro MPI (Handed out September 8, Due Sept 16, 10pm) -- Pass/Fail (see below)
MPI (Part A: Due Sept 27, Part B: Oct 7 at 22:00)) – Graded, 2 weeks total
Optimizations – (Due Oct. 21 at 22:00) -- Graded
OpenMP/Pthreads (Due Oct 28 at 22:00) – Pass/Fail
Intro to GPU (Due Nov 4 at 22:00) – Pass/Fail
GPU CUDA (Part A due Nov 11, Part B due Nov 18 at 22:00) – Graded, 2 weeks total
CUDA/OpenCL (last day of “class” Nov 24 at 16:00)

Late PS 8 accepted last week of class, with approval from instructor,

Note: You need to do PS1 before being allowed to hand in subsequent problem sets. PS1 is mandatory (obligatorisk), but will not count towards your final grade (i.e. not "tellende").
It is strongly recommended that you hand this assignment in by Thursday Sept. 8. If for some reason you cannot make this deadline, please contact the instructor ASAP (as soon as possible).

Student Photos

Photos of students will be taken an provided on-line either here on It’s Learning (depending on permissions)

Material covered (Pensum):

· Wed Aug 24: Lect 1 & 2 – Intro slides by Elster

· Thurs Aug 25: Lect 3 & 4 – More intro slides by Elster (no recitation/øvingstime this week) also material from MPI Tutorial by Pacheco

· Wed Aug 31: Lect 5 & 6 -- slides (also on black board)

· Thurs Sep 01:

· Sep 01 Lect 7/Recitation: C- crash course (se It’s learning for slides by Ivar) and http://www.cprogramming.com/begin.html

· -

· Wed Sep 07: Lect 8: “Amdal’s (& Gutavson’s) Law int the Multicore Era”, IEEE Computer, pp33-38, July 2008

· Lect 7 contin: “Why Computer Architecture Matters: Memory Access”, IEEE Computing in Science & Enginering, pp 71-74, July/Aug 2008

· Lect 9: Grouping date for communication (material taken from Ch 6 of Pacheco’s original book on MPI programming)

· Thurs Sep 08: Lec 10: More on MPI (Material taken from MPI Tutorial (see above) and slides from Ch2 from Wilkenson and Allen found here

· Recitation: See slides by Ivar on It’s Learning (C pointers, info re. PS 1 and PS 2)

· -

· Wed Sep 14: Lect 11&12: More on MPI – see It’s learning and some slides from UNC

· Thu Sep 15: Lect 13: More on MPI – see It’s learning

· -

· Tue Sep 20 – PS 3 handed out (MPI, 2 weeks, graded, Part A due Sep 27, Part B due Oct 7)

· Wed Sep 21 – Lect 14 & 15: Final comments on MPI

· Thur Sep 22 – Lect 16: Intro to Optimizations, PS 1 & 2 solutions, PS3 hints

· -

· Tue September 27, PS 3 Part A due

· Wed Sep 28 – Lect 17 & 18: Optimizations

· Thu Sep 29 – Lect 19

· -

· Wed Oct 5 – NO CLASS (Lect postponed to tomorrow due to Elster attending meeting)

· Thu Oct 6, 13-15 -- Lect 20 & 21 – more on Optimizations and SIMD

· Thur Oct 6, 15-16 – Recitation: PS 4 hints, PS 4 posted.

· Fri Oct 7 PS 3 due at 10pm

· -

· Wed Oct 12 – Lect 22 & 23 Final notes on SSE, intro to threads (handouts)

· Thu Oct 13 13-15: Recitation only – SSE and other hints

· --

· Wed Oct 19—Lect 24 & 25 : Threading and Open MP

o Handouts/foils and source codes used during lecture can be found at http://www.elsevierdirect.com/companion.jsp?ISBN=9780123742605

· Thu Oct 20 – Lect 25 & 26, Intro to GPU

· Fri Oct 21 – PS 4 due (Optimization, 2 weeks, graded)

· --

· Wed Oct 26 – Lect 27 & 28: GPUs and CUDA

· Thu Oct 27 – Lect 29 & 30, Recitation, PS 6 hints/CUDA intro contin.

· Fri Oct 28 – PS 5 due (OpenMP & Pthreads, 1 week, Pass/Fail)

· --

· Wed Nov 2 – Lect 30 & 31: GPUs

· Thu Nov 3 – Lect 32-33 Open CL, Paralell computing wrap-up

· Thu Nov 3, Recitation: PS 7 hints

· Fri Nov 7 – PS 6 due (GPU CUDA Intro), PS 7 posted

· --

· Wed Nov 9– Lect/Recitation: CUDA + work on PS 7

· Thu Nov 10 – NO CLASSES – work on PS 7!!

· Fri Nov 11 – PS 7 Part A due , PS 8 posted?

· --

· Wed & Thu Nov 19 – NO CLASSES Work on PS 7 & 8!!

· Fri Nov 21 – PS 7 due

· --

· Wed Nov 26 – No class, Work on PS 8

· Thu Nov 27, last class / PS 8due at 16:00!!!

Pacheco’s new book “An Introduction to Parallel Programming” is required for this course and now available at Tapir.

Since the above book was late in arriving at Tapri, some of the MPI material was taken from the following:

Peter S. Pacheco: Parallel Programming with MPI (finnes på Tapir)

Additional material to be covered re. MPI may also be taken from:

An Overview of PETSc is also given. More info:

Links to PETSc: http://www-fp.mcs.anl.gov/petsc/

Additional material will be presented from overheads and handouts and may be taken from:

Wilkinson & Allen: Parallel Programming 2nd edition
Gerber: "The Software Optimization Cookbook"

ALSO CHECK "It's learning" FOR COURSE ANNOUNCEMENTS, INFORMATION RE: ASSIGNMENTS, GRADES, ETC

This Page is maintained by Dr. Anne C. Elster. – Updated: Sep 10, 2011 Comments welcome.

All above notes and assignments for TDT 4200 are COPYRIGHTed by Dr. Elster and/or the author(s). Any copying or further publication without the authors' consent is a COPYRIGHT violation.