Parallel Programming and Distributed Systems

>>Lecture Time >>Lecture Slides >>Assessment >>Mid-Term Exam >>Assignment >>Lab Work >>References

---

News

• Some examples on lexicographical comparison between two ordered list N(Ti) and N(Tj):
  • If N(Ti) = {2, 4, 5} and N(Tj) = {2} then N(Tj) < N(Ti)  (convert N(Ti) into a three digit integer 245 and N(Tj) into a three digit integer 200, by padding two zeros to the right side of '2'; as 200< 245, so N(Tj) < N(Ti))
  • If N(Ti) = {2, 4, 5} and N(Tj) = {3} then N(Ti) < N(Tj) (as 245 < 300)
  • If N(Ti) = {2, 4, 5} and N(Tj) = {2, 6} then N(Ti) < N(Tj) (as 245 < 260)
  • if N(Ti) = {2, 4, 5} and N(Tj) = {1, 2, 5, 6} then N(Tj) < N(Ti) (as 1256 < 2450 -- convert the two lists into two four digit numbers)
  • For more detail, visit http://en.wikipedia.org/wiki/Lexicographical_order

Lecture time

Lecture slides

Lecture	Week	Topic	References	Notes
1	W1-1	Introduction to Parallel Programming	[1]
2	W1-2	Message Passing Interface	[3]
3	W2-1	Abstract Machine Models	[1][2]
4	W2-2	Parallel Computer Architectures	[1][2]
5	W3-1	Parallel Computer Architectures (cont')
6	W3-2	Lab: Multithread programming	[3]	Room: 103-104 C6 Extra reading: Pipeline [1][2]
7	W4-1	Speed up	[1][2]
8	W4-2	Lab: MPI Point-to-Point communication	[1][2]	Room: 103-104 C6
9	W5-1	Processor organization and mapping	[1]
10	W5-2	Lab: MPI Collective communication		Room: 103-104 C6
11	W6-1	Parallel Job Scheduling	[1]	Reading: Parallel Job Scheduling, Shared Memory Scheduling
12	W6-2	Lab: MPI Master/Slave model		Room: 103-104 C6
13	W7-1	Parallel Programming Models
14	W7-2	Map-Reduce
		Mid-term exam
15	W10-1	Parallel Algorithms	[1]
16	W10-2	Parallel Algorithms (cont') Matrix Multiplication	[1]
17	W11-1	Distributed Systems Introduction	[4]
18	W11-2	Distributed System Communication	[4]
19	W12-1	Seminar: Parallel distributed computing techniques	[3]	Mai Xuan Minh Nguyen Kim Dien
20	W12-2	Lab: MPI Master/Slave model	[4]	Room: 103-104 C6
21	W13-1	Seminar: Name services	[4]	Nguyen Nam Chuong
22	W13-2	Lab: Map-Reduce		Room: 103-104 C6
23	W14-1	Seminar: Distributed file systems	[4]	Nguyen Phan Hong Tien
24	W14-2	Lab: Map-Reduce		Room: 103-104 C6
25	W15-1	Seminar: Time and Global States	[4]	Vuong Dieu Huyen Nguyen Thi Thu Huong
26	W15-2	Seminar: Web services	[4]	Nguyen Tuan Cuong Nguyen Minh Tuan
27	W16-1	Seminar: Peer-to-Peer Systems	[4]	Cao Van Hung Tran Chau Bao Long
28	W16-2	Review

Assessment

• Exercises and seminar: 20%
• Mid-term exam: 20%
• Final exam: 60%

Mid-term Exam

• Format: Multiple choice question and open book exam
• Worth 20% of the module

Assignment

• Assignment specification and guides
• Input generator

Assessment

• This assignment is worth 20% of the module

Task

You are asked to write an MPI program for solving a system of linear equations.

Requirements

• The program must be able to solve systems of linear equations with various sizes
• Parallelism strategy must be able to run on different numbers of processors

Submission

• Report on:
  • Justification of parallelism strategy used in program
  • Theoretical speed up of the strategy used in program (ignore the cost of message passing)
  • Practical speed up measured by experiments on the MPI program and the sequential version
  • Calculation of theoretical and practical efficiency
• Source code of the program
• Demonstration of the program in the lab

Due date: 5PM Monday, 31 May 2010

You have to submit by the deadline:

• A printed hardcopy version of your report
• An electronic copy of all your work including your report (in Word or PDF) and source code of your program to sakai.

Make sure that both of your submissions must have your name and student number on them.

Lab exercises

Materials

Lab 1: Introduction to MPI

Lab 2: Group communication

Lab 3: Define new datatype

Lab 4: Master/Slave Model

Lab 5: Process Farm and Work pool

Lab 6: Advanced MPI Datatype

Lab 7: MapReduce

References

1. Scalable Parallel Computing: Technology, Architecture, Programming, Kai Hwang & Zhiwei Xu, McGRAW-HILL, 1997.(*)
2. Parallel Computing - theory and practice, Michael J. Quinn, McGRAW-HILL, 1994.(*)
3. Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers, Barry Wilkinson and MiChael Allen, Second Edition, Prentice Hall, 2005.
4. Distributed Systems: Concepts and Design, George Coulouris, Jean Dillimore, Tim Kindberg, Addison-Wesley, 2005.(*)
5. Distributed Algorithms, Nancy Lynch, Morgan Kaufmann, 1997.
6. Distributed Operating Systems, Andrew S. Tanenbaum, Prentice Hall, 1990.
7. MPI: http://www.mpi-forum.org/docs/docs.html
8. PVM: http://www.csm.ornl.gov/pvm/pvm_home.html
9. The GRID2: Blueprint for a New Computing Infrastructure, Ian Foster and Carl Kesselman, Morgan Kaufmann 2004.
10. Grid Computing: Making the Global Infrastructure a Readlity, Fran Berman, Geoffgrey Fox and Tony Hey.