Strumenti di programmazione per sistemi paralleli e distribuiti

Teacher: Dr. Massimo Coppola

Contact info
e-mail : massimo.coppola@isti.cnr.it
Phone : 050 315 2992
Office location : CNR Reseach Area, ISTI-CNR, Building C, room 33
Alternate Office : C.S. Dept., Room 388

Course info

• This page concerns the SPD course (535AA) for the academic year 2014-2015, which gives you 6 credits.
• The previous SPD course (308AA, 9 credits) can still be taken only by those who had it in their study plan since previous years (that is, two years ago: before or during 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.

Temporary timetable

• 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.

• No question time on Thursday 26/03 due to other work commitments.
• Lesson on Wednesday 25/03 will be a two-hour lab session on MPI from 15-17, again in the C.S. Dept. building; and a one-hour lesson from 17 to 18, Room N1.
• Lesson on Wednesday 17/03 will be a lab session on MPI, tbh in the Parallel Architectures lab, C.S. Dept. (Room 308).
• Lesson on Tuesday 10/03 is moved to Thursday 12/03, 16-18; it will be a lab session on MPI, tbh in the Parallel Architectures lab, C.S. Dept. (Room 308).
• First lesson on 24/02/2015 as per current temporary schedule. Timetable may be modified during the first week according to avoid conflicting time slots for students, please state your requirements clearly.

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

The final test is composed of two parts - a software development project, including a written short report with discussion on the implementation and experimental results of the project. - oral examination with the teacher, discussing the project and the report, as well as the topics within the course program. Project-related discussion can be at a different time than the rest of the oral examination, upon student's request.

Final projects can be assigned in one of two alternative ways.

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 short 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 they shall show their ability in coding with at least one of the frameworks studied during 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. These proposals apply by default to all students (possibly with a choice of the implementation method). More students can share this topic (but they cannot work together and share the work results). In this case the emphasis in the report is on test results and their discussion, in order 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.
• If the project discussion fails, the same project cannot be discussed/presented again unless substantial changes are made.