DF21500
Multicore Computing (7.5hp)
Architectures, Models, Methods, Languages

HT1/2013

Recommended for
Graduate (CUGS, CIS, ...) students interested in the areas of parallel computer architecture, parallel programming, software engineering, optimization, compiler construction, or algorithms and complexity.
The course is hosted by the CUGS graduate school as an Advanced Course.
Undergraduate and master-level students are kindly referred to the similar course TDDD56 Multicore and GPU Programming (ht2) instead.

Registration (internal access only).
(If you have no IDA research account, please contact the CUGS secretary, Anne Moe (annes \at ida.liu.se) for registration.)
List of participants 2013 (internal access only).

Organization
Lectures (ca. 32h), programming exercises, optional theoretical exercises for self-assessment, programming lab assignment, student presentations.
The course will be held as block course with two intensive weeks in Linköping.

The course was last given
in 2011 and 2009.

Goals
The course emphasizes fundamental aspects of shared-memory and accelerator-based parallel programming, such as shared memory parallel architecture concepts, programming models, performance models, parallel algorithmic paradigms, parallelization techniques and strategies, scheduling algorithms, optimization, composition of parallel programs, and concepts of modern parallel programming languages and systems. Practical exercises help to apply the theoretical concepts of the course to solve concrete problems in a real-world multicore system.

Prerequisites
Data structures and algorithms (e.g. TDDB57) are absolutely required; knowledge in complexity theory and compiler construction is useful. Some basic knowledge of computer architecture is assumed. A basic course in concurrent programming (e.g. TDDB68) is recommended.
Programming in C and some familiarity with Linux (or similar OS) is necessary for the practical exercises.

Contents/Schedule
Lecture block in 2 intensive weeks (weeks 35, 36) in Linköping:

monday 26/8 kl 13-16,
tuesday, wednesday 9-12, 13:15-16,
thursday 29/8 kl 9-12

monday 2/9 kl 13-16,
tuesdag, wednesday  kl 9-12, 13:15-16,
thursday 5/9 kl 9-12

Lecture Notes

Schedule (prel.)

(still under construction, but the dates are fixed)

The mapping of topics to time slots as given below is approximate; if necessary, we might dynamically shift contents back and forth as appropriate.

Lectures are given in the room Donald Knuth.
Lab sessions are given in the room Konrad Zuse (IDA Multicore Lab)

Labs

In 2013 we offer a single lab suite covering both CPU and GPU labs (3hp). Both parts need to be done.

1. CPU Lab: TBA
   • Prerequisites for the labs: C programming, Linux, and a basic course in concurrent programming and operating systems (e.g. TDDB68).
   • Lab-kickoff session: Mandatory presence
   • Deadline: 23/9/2013

   Supervision and examination: Nicolas Melot

2. GPU-Lab: Programming assignment for GPUs with CUDA or OpenCL.
   • Mandatory introductory lecture and lesson
   • several scheduled lab sessions, see above
   • Lab presentation (PDF).
   • Lab assignment (PDF). Deadline: 23/9/2013
   • lab_src_code.tar.gz source code snippet for the GPU lab

   Prerequisites for the labs: C programming, Linux, and a basic course in concurrent programming and operating systems (e.g. TDDB68).

   Supervision and examination: Usman Dastgeer

Exercises

Some theory exercises are collected here.

Literature

See also the Literature list for TDDD56.

Background reading on the theory of parallel computation and on parallel algorithms:

• J. Keller, C. Kessler, J. Träff: Practical PRAM Programming. Wiley Interscience, New York, 2001. ISBN 0-471-35351-5.
• J. JaJa: An introduction to parallel algorithms. Addison-Wesley, 1992.
• T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms, Chapter 28 (Sorting Networks) and Chapter 30 (Algorithms for Parallel Computers). MIT press, 1989.
• Jordan, Alaghband: Fundamentals of Parallel Processing. Prentice Hall, 2003.

• Nir Shavit: Data structures in the multicore age. Comm. ACM 54(3), pp. 76-84, March 2011.

Further literature references may be added later.

Teachers

• Christoph Kessler, Linköpings universitet (course leader, lecturer, examiner)
• Welf Löwe, Univ. Växjö (lecturer, examiner)
• Ingemar Ragnemalm, ISY, Linköpings universitet (guest lecturer)
• Usman Dastgeer (lab/lesson assistant)
• Nicolas Melot (lab/lesson assistant)

Examination

TEN1: Written exam, 3hp.

• Allowed aids: pocket calculator, English dictionary. No books, no slides, no papers.
• Old exam (from FDA125 Advanced Parallel Programming, March 2007)

UPG2: Paper presentation, opposition, and written summary (1-2 pages, deadline 4/10/2013) of the presented paper, 1.5hp.

Credit
7.5hp if all examination moments are fulfilled.
Partial credits can be given, too, but the written exam must be passed.

If you already have taken TDDD56 Multicore and GPU Programming earlier, which overlaps with most of this course, you need only do the presentation moment (UPG2) and can get 1.5hp for the course.

Comments
There is a partial overlap in contents with the earlier course FDA125 Advanced Parallel Programming which was last given 2007, corresponding to 1p = 1.5hp in the written exam.
It overlaps to a major extent (ca. 5hp) with the master-level course TDDD56 Multicore and GPU Programming and to a minor extent (1.5hp) with the master-level course TDDC78 Programming of Parallel Computers.

In contrast to FDA125 and TDDC78, we focus in this course on shared memory and multicore systems, also heterogeneous multicore and GPU architectures, and add more material on software engineering techniques for parallel systems, such as design patterns for synchronization and optimized composition of parallel components. We also give more emphasis to parallelization techniques that are especially useful for multicore systems, such as SIMD programming, speculative parallelization, transactional programming and lock-free synchronization. Scheduling for shared memory systems will be considered in more detail, in particular scheduling algorithms for malleable task graphs.