Teacher: Dr. Massimo Coppola

Contact info
e-mail : [email protected]
Phone : 050 315 2992
Office : CNR Reseach Area, ISTI-CNR, Building C, room 33

Course info

• This page concerns the SPD course (535AA) for the academic year 2013-2014, which gives you 6 credits.
• The previous SPD course (308AA, 9 credits) can still be taken by those who had it in their study plan since previous years (before or on the academic year 2011-12). Different program and possibly different rules for the final test will be applied in that case.
• Be sure to alway check the NEWS section in this page.
• Information about past editions of the SPD course can be found at the following links.

This is the final timetable

• Lesson schedule changed after the first week.
• In case of exceptions, notice will be given in the News section below in this page.

Question time
Students should contact the teacher in advance by phone / e-mail. A different time can be agreed upon if needed.

• New dates added for individual question time in July.

• Final projects can be decided in two alternative ways for this year. In both cases the target is developing a parallel application using one of the technologies seen during the course (MPI, TBB, OpenCL) or a combination of them. Please see the detailed explanation.

• There are available dates for question time in June, to help with the projects.
  Please confirm that you will come and agree on a location (either CNR or C.S. Dept.) at least three days in advance. July dates to be confirmed later on.
  NOTE (added on 16/05/14 to avoid misunderstandings) these are available dates for individual question time for students working on the projects.

• New lessons scheduled on 9/5/2014 and 16/05/2014, 14-18 (half lesson, half laboratory). See course journal page for details.
• (29/04/2014) lesson was canceled due to the didactic activity break for elections
• (15/04/2014) extra lab lessons to be confirmed on : 9/5, 16/5, 23/5 in the slot 14-18 (depending on lab/room availability).

The course journal is a separate page in this wiki.

The course will provide a description and analysis of a few key parallel and distributed programming platforms and models, starting from their theoretical foundations, where not covered by previous courses, and focusing on (1) existing standards for platforms and programming systems and (2) State-of-the-art solutions. The course will include practical use of those systems to develop simple applications.

The course will cover the following topics.

• Parallel Programming systems/frameworks
  • MPI message-passing programming (the core part of the MPI 2.2 standard)
  • TBB Thread Building Blocks Multicore oriented, shared-memory programming framework
  • Massively Multicore computation and GPGPU frameworks: OpenCL (references to CUDA, Brooks+ possibly)
  • ASSIST a framework for parallel high-level parallel programming with autonomic management
• Example Applications
  • K-means
• Foundation, Technologies
  • Elementary mechanisms to distribute computation: message passing, shared memory, massive multicore
  • Basics of scheduling algorithms and resource management
  • Basics of Service Oriented Architectures SOA
• Service oriented Platforms, Cloud Computing and Cloud Federations
  • Contrail
  • OpenNebula, Open Stack, Rackspace

• Standard MPI 2.2 Only those parts that we will specify during the lessons.
  On the MPI forum web site you will find alternate formattings and some translations; version 2.2 of the MPI standard collects all the material from previous versions of the standard (1.0, 1.1, 2.0 and so on) within a single document.
• B. Wilkinson, M. Allen – Parallel Programming, 2nd edition. 2005, Prentice-Hall. This book will be also used; at least the 1st edition is available in the University Library of Math/Comp.Sc./Physiscs, under code C.1.2 w74 INF .
• Michael Mc Cool, Arch D. Robinson and James Reinders – Structured Parallel Programming (patterns for Efficient Computation) 2012, Morgan Kaufmann.
  Chapters 1 to 3 cover background topics which should be already known from previous courses (SPA, SPD courses). Stundents need to focus on the TBB material throughout the book: Appendix C and D, and the TBB examples in the book that appendix C references from chapters 4, 5, 8 and 9. Check also Chapter 11 on k-means.
• Alternate book: An introduction to TBB is also found in James Reinders – Intel Threading Building Blocks 2007, O'Reilly Media. More focused on TBB alone, but describes a quite old release of the framework, hence you need to look at online documentation for some of the features.
• Tutorial on the Assist Compiler. Old version:Tutorial ASSIST Febbraio 2007
  Slightly newer version (in English) Assist Tutorial Nov 2007
  Tutorial of the deployment server GEA GEA documentation, November 2006.

Virtualization

• An Overview of Virtual Machine Architectures J. E. Smith and Ravi Nair
• The architecture of virtual machines J.E. Smith, Ravi Nair. IEEE Computer Vol. 38, Issue 5, 2005, Pages 32 - 38.

Data Mining Algorithms

• Dhillon & Modha Technical Report about parallel K-means A Data-Clustering Algorithm On Distributed Memory Multiprocessors. I.S. Dhillon, D.S.Modha, LNAI 1759, pag 245. Note: same-title paper from LNCS version has a misprint, where the MPI algorithm is actually missing. The T.R. is correct and presents the same results.
• Sequential and parallel optimization of the K-means algorithm Large-Scale Parallel Data Clustering. Dan Judd, Philip K. Mckinley, Anil K. Jain. Ieee Transaction On Pattern Analysis And Machine Intelligence, Vo. 20, No. 8 August 1998.

Specific prerequisite knowledge from the first-level degree, which we assume known, includes in particular the basics of Computer Architecture (AE) as well as programming in C/C++ (AIL, PRL). Knowledge of basic techniques for testing program performance and behaviour is also assumed known.

Typical prerequisites of this course within the Master Degree are presented in the SPA course, and some topics are closely related to the SPM course, which is a suggested prerequisite although within the same year.

For transfer students and students belonging to a different Master course, we shall say that while all the topics in the SPA and SPM courses are related to SPD, a minimal subset of topics the student shall master includes

• Parallelization methodology and models
• Support to parallel programming models and software development tools
• Parallel Architectures
• Performance evaluation (cost models)
• Basics of parallel architectures
  • Parallel processors
  • Multiprocessors
  • Multicore / manycore / … / GPU
  • Shared vs distributed memory architectures
• Modularity, software reuse, incremental design
• Performance modelling and portability

In both cases the target is developing a parallel application using one of the technologies seen during the course (MPI, TBB, OpenCL) or a combination of them.

The project must solve a well specified problem, with a known algorithm, and the project result must include test results and a shor report about the issues in the parallelization and in the performance/ efficiency optimization of the application developed. Students are not required to invent new parallel solutions, but thay shall show their ability in coding with at least one of the frameworks in the course.

How to get a project assigned: there are two ways.

1. Student proposes a topic, details are agreed with the teacher, a one-page project proposal is written detailing the problem, the technology to use and how the project app will be tested (datasets to use and the like). In this case the final report shall contain the proposal and a description of the application implemented.
2. A proposal is made by the teacher, see this page These proposals apply by default to all students (possibly with a choice of the implementation method). More students can share this topic (but not the work results). In this case the emphasis in the report is on test results and their discussion to show the performance, efficiency and level of parallelism obtained.

• As soon as the project topic is agreed with the teacher, you are expected to send a two-page summary of the problem to tackle / application to write, in which you explain it, state which parallel/distributed tools you are going to use and how you will evaluate the project results. For projects assigned by the teacher in year 2013-2014 the description can be shorter; please state which tools you will use and how you will test the project anyway.
• When the project is completed , students shall send a short report (about 20 pages) about project development and analysis of the results, including test results.
• Contact the teacher if you have issues, or if you are unsure how to deal with the rules in a specific case (e.g. you need to write a longer report, test with specific hardware etc. )

• Individual projects are assigned to the students by the teacher, but can be proposed by the students.
• For difficult projects, at most 2 students can work on the same project. This is an exception to the rule that each project is a personal work and it must be authorized: joint work on projects it is not granted a priori.
• Projects can be assigned during the second half of the term, or later on, during the academic year.
• Project can be experimental work (coding + testing + written relation), to be discussed with the teacher.
• Before academic year 2011-2012 a project could also be a seminarial activity (relation and public talk about assigned papers) to be presented during one exam session.
• If the project discussion fails, the same project cannot be discussed/presented again unless substantial changes are made.