DF21500
Multicore Computing (5p / 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.
Interested undergraduate students are also welcome, as long as there are free seats left.

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 2011 (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. It partly overlaps (1p = 1.5hp) with the older course Advanced Parallel Programming which was last given 2007.
This course complements the existing graduate course FDA101 on Parallel Programming (4p), which is aliased to the undergraduate course TDDC78.

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. TDDB63/68/72) and parallel programming (e.g. FDA101/TDDC78 or TANA77) are 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 (2 x 4 days at 4..6 hours) in Linköping. Weeks 7 (14-17/2/2011) and 9 (28/2-3/3) are confirmed.
Rooms: Alan Turing and John von Neumann (see the schedule)

Lecture Notes

Schedule (prel.)

Labs

You can do either the Cell lab or the GPU lab (or both).
The lab moment of the course (1.5hp) is passed if the Cell lab OR the GPU lab is passed. An extra 1.5 hp is awarded if you pass both.

1. Cell-Lab: Programming assignment with the CELL BE, a heterogeneous multicore processor.

   • Mandatory introductory lecture and lesson
   • 2 scheduled lab sessions (bring your laptop!)
   • Lab assignment (PDF). Deadline: 1/4/2011
   • Cell lab introduction slides

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

   Supervision and examination: Erik Hansson

2. GPU-Lab: Programming assignment for GPUs with CUDA or OpenCL.
   • Mandatory introductory lecture and lesson
   • 1 scheduled lab session (bring your laptop!)
   • Lab presentation (PDF).
   • Lab assignment (PDF). Deadline: 1/4/2011
   • src_code.tgz 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

Literature
As main course book, we will use:

• Maurice Herlihy, Nir Shavit: The Art of Multiprocessor Programming, Morgan Kaufmann, 2008. ISBN 978-0-12-370591-4.

• C. Kessler: Programming the Cell Processor. Book chapter, 42 pages, to appear 2011. Handed out.
• Matthew Scarpino: Programming the Cell Processor for Games, Graphics, and Computation. Prentice Hall, 2008. ISBN 978-0-13-600886-6. - Available in Kvartersbibliotek B
• The IBM Cell SDK documentation and tutorial material is available on the IBM developerWorks site for Cell.

• Karl-Filip Faxén, ed., and C. Bengtsson, M. Brorsson, H. Grahn, E. Hagersten, B. Jonsson, C. Kessler, B. Lisper, P. Stenström, B. Svensson: Multicore computing--the state of the art.
  Report, The Swedish Multicore Initiative, 2008

• 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 will be added later.

Teachers

• Christoph Kessler, Linköpings universitet (course leader, lecturer, examiner)
• Welf Löwe, Univ. Växjö (lecturer, examiner)
• Jörg Keller, FernUniversität in Hagen, Germany (guest lecturer)
• Jens Ogniewski, ISY, Linköpings universitet (guest lecturer)
• Ingemar Ragnemalm, ISY, Linköpings universitet (guest lecturer)
• Håkan Sundell, Scalable Parallel Solutions AB and University of Borås
• Usman Dastgeer (lab/lesson assistant)
• Erik Hansson (lab/lesson assistant)

Examination

TEN1: Written exam (Welf, Christoph) 3p = 4.5hp. Due to partial overlap, 2p = 3hp for those who already have passed the exam in FDA125 Advanced Parallel Programming earlier.

• Allowed aids: pocket calculator, English dictionary. No books, no slides, no papers.
• Old exam (from FDA125 Advanced Parallel Programming, March 2007)
• If you want to practise more, here are some partly relevant theoretical exercises from FDA125 for self-assessment (no supervision, no correction):
  - Exercises on parallel algorithm theory
  - Exercises on shared memory consistency issues
  - Exercises on Cilk
  

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

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

Comments
There is a partial overlap in contents with the earlier course FDA125 Advanced Parallel Programming, corresponding to 1p = 1.5hp in the written exam.

In contrast to FDA125, 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.