Parallel and Distributed Programming
Kenjiro Taura

Note: Slides and materials are written in English. Lectures will be in Japanese. Presentations by students may be in Japanese or English.

This class is a mixture of usual lectures (by the lecturer) and presentation by students. For topics covered in this lecture, we typically proceed as follows.

• In week X, I briefly talk about basics using the last 20-30 minutes or so.
• In week X+1, assigned students will talk about more in-depth or specific materials (e.g., book chapters, survey articles, journal papers, and conference papers).

For each topic, we assign two kinds of students.

Presentors/speakers

One or two students are assigned as presentors or speakers. They talk about the assigned topic in a class.

Discussion leaders

One or two students are assigned to specifically lead discussions.

Both types should carefully read and understand the assigned materials in depth. Some of the expected roles of discussion leaders include:

• answer to questions together with speakers
• stimulate discussions when the audience is silent
• complement the speakers explanation

Here are the topics that will be convered by the lecture. Red items with [NN] indicate student presentations. Links point to the papers available online. Items without links are book chapters. For [1] and [2], presentations sholud be with some experimental results (see below).

10/2: Introduction and assignments

10/16: Basics of parallel and distributed programming

Parallel programming models. Theoretical models of computation. Causal order. Event diagram. Logical clocks.

10/23: Parallel programming in practice I

[1] MPI: explanation and experiments.

10/30: Parallel programming in practice II

[2] UPC: explanation and experiments.
[3] OpenMP: explanation

11/6: Routing

[4] Routing. Cahpter 4 in Tel. Introduction to Distributed Algorithms
[5] Lenore J. Cowen. Compact routing with minimum stretch (more advanced: Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, Mikkel Thorup. Compact name-independent routing with minimum stretch)

11/13: Checkpointing

[6] E. N. (Mootaz) Elnozahy, Lorenzo Alvisi, Yi-Min Wang, David B. Johnson. A survey of rollback-recovery protocols in message-passing systems

Model Checking I

[7] Chapter 3 and 4 of Gerard J. Holzmann. The SPIN Model Checker

Model Checking II

[8] Chapter 8 and 9 of Gerard J. Holzmann. The SPIN Model Checker

Fault Tolerance

Impossibility of consensus in asynchronous networks

Scalable Broadcast

[9] P. Th. Eugster, R. Guerraoui, S. B. Handurukande, P. Kouznetsov, A.-M. Kermarrec. Lightweight probabilistic broadcast

Scalable Data Aggregation

[10] Mark Jelasity, Alberto Montresor, and Ozalp Babaoglu. Gossip-based aggregation in large dynamic networks

Memory Consistency

Sequential consistency.

[11] Jeremy Manson, William Pugh, and Sarita V. Adve. The Java memory model.
William Pugh. Fixing the Java memory model

• Get an account on istbs cluster (ask me).
• MPI and UPC are already installed.
• Write a program that broadcasts a file from one node to all other nodes. Evaluate performance (bandwidth) with various file sizes.
• Write a program that does a simple N-body simulation algorithm taking O(N^2) force calculations. Evaluate performance and speedup with various problem sizes and number of nodes.

• Speakers and discussion leaders ("Tsukkomi") will get credits.
• Those who are not assigned as speakers or discussion leaders will get credits, either by

  One original report:

  an in-depth report that is related to, but not directly covered by, the lectures. it may be an extension of one of the lectures. it may contain some experiments.

  Two summary reports:

  two reports on the topics directly covered in the lecture or the papers related to them.

• If you want to get a credit by reports, you should declare what your report will be about, before the last lecture. Send an Email to me (tau at logos at .......)
• The deadline of the report will be around Feb. 15 (The exact date will be announced later).

Interesting topics related to lecture include but are not limited to the following. If you want to propose one you like to work on, please contact me.

• Practical parallel programming: Play with UPC or MPI, or both, and
  • Measure basic 1-1 communication performance (bandwidth and latency). Change data size and data.
  • Measure collective communication performance and analyze how they are implemented. Change data size and number of processors.
  • Write a sorting or a simple N-body simulation and measure speedup. Think about how to get good speedup.
• Routing I: Implement and have experimnts on Cowen's compact routing scheme. It does not have to be implemented as a distributed routing algorithm. It suffices to implement it as a `simulator', which is a serial program on generated graphs. Generate many graphs and compare it with the simple shortest-path routing and some others you may want to give a try. Observe that the Cowen's one has the claimed property.
• Routing II: Understand and summarize Abraham et al.'s paper if you are interested in the theory. Do not choose this one unless you really understand it.
• Model Checking I: A detailed analysis of how SPIN optimizes verification. Run experiments, read books, and analyze generated source (pan.c) to understand what is really happening.
• Model Checking II: A survey of a symbolic model checking (an interesting topic that is not covered in lecture). This book is a good book that covers the topic.
• Fault tolerance: A detailed understanding and report on communication-induced checkpointing based on the original literature and some papers that follow.
• Gossip based broadcast and aggregation: to be announced
• Memory Consistency: to be announced

	Spearker	Discussion Leader
1	Taro L Saito
2	Miwa Shusaku, Ali Najand	Hironaka
3
4	Kenichi Watanabe
5	Kei Takahashi	Takeshi Sekiya
6	Hiroyuki Osumi	Ryu Tatsumi, Eric Tschetter
7	Duc, Sawai
8	Hironaka, Watanabe
9	Saito Dai	Shimada Kenta, Kurasawa Hisashi
10	Dun Nan
11	Katsunuma Satoshi	Hirose Kenichiro