F21DP: Parallel and Distributed Technology

• Home
• Course structure
• Slides
• Tutorials
• FAQ
• Coursework
• Reading List

This page covers the 2016/17 instance of the course. Follow this link to get to the latest instance of t\ he course.

This page collects material for my part of the course F21DP --- Parallel and Distributed Technology. Check these slides for overview, admin info and learning outcomes for the course.

Unless announced otherwise, the teaching slots for this course are:

• Mon 10:15 EM 3.06 Lecture
• Thu 15:15 EM 3.03 Lecture
• Thu 17:15 EM 2.50 Lab

Purpose and Learning Objectives

Software is no longer sequential. Many programs are now concurrent, parallel, distributed or mobile. This course explores technologies that enable, the design issues that concern, and the hierarchy of architectures that deliver, distributed and parallel systems.

The parallel strand starts by reviewing basic concepts including brief overviews of the need for parallelism, parallel architectures and programming approaches. The main focus is then on parallel programming models, namely

• explicit distribution using MPI with C,
• explicit accelerator (GPU) programming using OpenCL,
• explicit shared-memory programming using OpenMP,
• functional task parallelism using Glasgow parallel Haskell,
• skeleton programming using Hadoop,
• data parallelism using SaC.

The course also provides revisions of C and Haskell to ensure a sufficient level of background knowledge in these languages and their tools. Students not fluent in these languages will need to allocate extra time for revision.

Pre-requisites:

• F29OC: Operating Systems & Concurrency, or equivalent
• Solid C programming skills (there will be a quick C revision)

Course Structure & Learning Material

The planned topics by-week are (slides will be posted here each week):

	Lecture	Lab	Sample Sources	Bg Reading
Week 1 (HWL):	Introducing Parallelism; C Revision I & II	C Tutorial	sources	"The C book"
Week 2 (HWL):	Communication Libraries (MPI) I    & II	MPI Tutorial	sources	hi-perf mat-mult
Week 3 (SBS):	OpenCL I & II	OpenCL Tutorial I:(work sheet)	openCL_lab01.tar.gz	Khronos openCL reference
Week 4 (SBS):	Advanced OpenCL I & II	OpenCL Tutorial II :(work sheet)
Week 5 (SBS):	OpenMP I & II	OpenMP lab :(work sheet)
Week 6 (SBS):	Data-Parallel Programming I & II	SaC Tutorial: (work sheet)
Week 7 (SBS):	Thinking arrays I & II	SaC lab:(work sheet)	SaC_lab01.tar.gz
Week 8 (HWL):	Haskell I & II	Haskell lab	sources	Real World Haskell book
Week 9 (HWL):	Glasgow parallel Haskell (GpH) I & II	GpH Lab	sources	Milan'15 slides (4up)
Week 10 (HWL):	Higher-order Parallelism (Skeletons)	Hadoop Tutorial	Docker image for GpH
Week 11 (HWL):	Hadoop I   &   II     Hadoop (2024)	MapReduce Tutorial
Week 12 (HWL/SBS):	Revision: HaWo, Bodo

Sreencast of Revision (HWL) (.mpg) and Sreencast of Revision (HWL) (.mkv)
or use the embedded video below for on-line streaming (video/webm with VP8 codec; maximise when viewing):

Powerpoint versions of Bodo's slides: openCL_01, openCL_02, openCL_03, openCL_04, openMP_01, openMP_02, SaC_01, SaC_02, SaC_03, SaC_04.

You can find past exam papers here and directly: Past exam papers

• 14-15
• 13-14

Sample Sources

(Sequential) C sample sources:

1. Sources from Lecture 2: C Revision (Part 1)
2. Sources from Lecture 3: C Revision (Part 2)
3. Sequential matrix multiplication (2D arrays)
4. Sequential matrix multiplication (array of vectors)
5. Sequential matrix multiplication (using transpose)
6. Sequential matrix multiplication (cache-optimised)
7. Input matrices: 5x5, 80%, max value 99
8. Input matrices: 2000x2000, density 10%, max value 65536
9. MPI host file (mpi4)

C+MPI sample sources:

1. MPI-style Hello world (simpler version)
2. Thinker/Guesser example using MPI
3. Parallel matrix multiplication (using transpose)
4. Parallel matrix multiplication (send rows once)
5. Parallel matrix multiplication (send result by rows)
6. Parallel matrix multiplication (arbitrary number of processors)

(Parallel) Haskell sample sources:

1. Haskell:
   1. simple examples from slides;
   2. sum-of-squares examples from slides;
   3. tree example with exercises
2. Glasgow parallel Haskell:
   1. parsum.hs,
   2. parfib.hs
3. Using strategies with Glasgow parallel Haskell:
   1. foo.hs
4. Case Study: parallel matrix multiplication
   1. seq matrix multiplication
   2. parallel matrix multiplication

Tutorials

Lab exercises and tutorials are on separate pages:

1. C+MPI Tutorials

Assessment

Assessment will be partly by coursework and by a final 2-hour exam. The weighting of these components is as follows:

• Assessed Coursework: 30% (2 pieces)
• Exam: 70%

Coursework

Students will undertake two pieces of coursework comparing low-level and high-level parallel software engineering technologies using both the department's Beowulf cluster, and multicore resources. Each coursework will be done in pairs, with each student picking one implementation technology.

You can find tips on measuring programs and parallel performance tuning here (4up). Take a look before you start on the CW!

The first assessed coursework can be found here:

• CW1 spec for F20DP (BSc students)
• CW1 spec for F21DP (MSc students)

The sequential source code for the Totient function is available in C.

The assessed coursework will be handed out in Weeks 4 and 10.

The second assessed coursework can be found here:

• CW2 spec for F20DP (BSc students)
• CW2 spec for F21DP (MSc students)

The sequential source code for the Totient function is available in C and in Haskell.

Submission deadline is Fri Week 12. Submission should be via Vision, using the sub-menu Assessment.

Reading List

No single book or web resource covers the course, but recommended reading is associated with many lectures. Some useful links are on my web page on parallel computing.

Specific topics:

• C programming: "The C Programming Language", Kernighan and Ritchie. Pearson. ISBN: : 9780131103627. author page
  (standard textbook on C progamming, available from the library)
  "The C book", by Mike Banahan, Declan Brady and Mark Doran
  (a completely on-line version of another C introduction)
• Parallel Programming: "Designing and Building Parallel Programs -- Concepts and Tools for Parallel Software Engineering", Ian T. Foster, Addison Wesley, Reading, MA, 1995. ISBN: 9780201575941. on-line version, Google books
  (a good but dated introductory on-line textbook on parallel programming; focus on Part I, covering concepts and parallel program design)
• Message Passing: "Parallel Programming in C with MPI and OpenMP" Quinn, Michael J., 2004, McGraw Hill, ISBN: 0072822562. Google books
  (standard textbook on parallel programming; mainly numerical algorithms and message passing but also a little bit OpenMP (shared-memory))
• Skeletons and Parallel Patterns: "Structured Parallel Programming" Michael McCool, James Reinders, Arch Robison.
  Morgan Kaufmann Publishers, Jul 2012. ISBN10: 0124159931 (paperback) Google books
  (a book on parallel patterns, aimed at practitioners in parallel programming, using Cilk and TBB as frameworks)
• Parallel Haskell: "Parallel and concurrent programming in Haskell" by Simon Marlow. O'Reilly, 2013. ISBN: 9781449335946.
  (covers several techniques of high-level parallel programming in Haskell)

Further reading:

• "The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software", Herb Sutter. Dr. Dobb's Journal, 30(3), March 2005.
  (discusses the shift in focus from increasing clock-rates to multi-cores)
• The Landscape of Parallel Computing Research: A View From Berkeley A View of the Parallel Computing Landscape, CACM 2009.
  (an influential position paper, and a community around it)
• "MapReduce: Simplified Data Processing on Large Clusters" J. Dean, S. Ghemawat, Commun. ACM 51(1):107--113, 2008. DOI: 10.1145/1327452.1327492
  (summary of Google's MapReduce pattern and implementation)

Other Resources

• Icelandic Data Center Cuts Power Costs, Carbon Footprint for ThreatMetrix (Feb'17)
• CACM Article on Apache Spark, (Nov 2016)
• World’s First 1,000-Processor Chip (June 2016)
• Fighting spam with Haskell, an article on Facebook's anti-abuse engine "Sigma" which is implemented in Haskell and uses parallelism
• Wired article on Facebook's new spam filtering engine, implemented in Haskell
• building-a-complete-tweet-index (using Hadoop and Pig to analyse Twitter data)

Copyright

Except where stated otherwise, all teaching material, including lecture notes, tutorials and lab exercises, are Copyright (C) Heriot-Watt University, and respective authors. Please respect our rights over this material and contact us if you want to use it in another context.