King Fahd University of Petroleum & Minerals
College of Computer Sciences and Engineering
Computer Engineering Department

COE 420 Parallel Computing

• Instructor: Professor Mayez Al-Mouhamed (Email: mayez@kfupm.sa.edu)
• Office: Room 22-400-3 (Tel. 2934) and Lab 22-339 (Tel. 3536).
• Text Book and references:
  • Introduction to Parallel Computing 2nd Edition, Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar, The Addison Wesley Publishing Company, ISBN 0-201-64865
  • Parallel Programming in C with MPI and OpenMP, by Michael Quinn, McGraw-Hill Higher Education, ISBN: 0072822562, 2004.
  • Designing and Building Parallel Programs, by Ian Foster, Addision-Wesley Publishing. (Available Online)
  • Introduction to parallel computing : Design and Analysis of parallel algorithms, by Vipin Kumar, Benjamin-Cummings Publishing.
  • Sourcebook of Parallel Computing, Jack Dongarra, Ian Foster, et al, Morgan Kauffman Publishing (Course Reserves)
  • Designing and Building Parallel Programs, by Ian Foster, Addision-Wesley Publishing. (Available Online)
  • Intro. Parallel Processing: Algorithms and Architectures, Parhami, B., Plenum, 1999.
  • Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers, 2nd edition, by Barry Wilkinson and Michael Allen, ISBN:0131405632, Prentice Hall, 2005.
  • Foundations of Multithreaded, Parallel, and Distributed Programming, by Gregory R. Andrews, ISBN: 0201357526, Addison Wesley, 2000.
  • Introduction to Parallel Computing, by Ananth Grama, ISBN:0201648652, Addison Wesley, 2003.
     
  • MPI/OpenMP/Matlab*P Documentation
    • MPI Forum
    • OpenMP Official Site
    • A User's Guide to MPI by Peter Pacheco (ps) (pdf)
    • A User's Guide to MPI by Peter Pacheco (ps) (pdf)
    • Introduction to OpenMP - tutorial from WOMPEI  (link)
    • Writing and Tuning OpenMP Programs on Distributed Shared Memory Machines (link)
    • Matlab*P Quick Start Guide (pdf)

  • Interesting Links

    • Top 500 SuperComputers
    • Dead SuperComputer Society
    • Flash mob computing
    • Top 10 Algorithms

     

• Grading Policy: Exam 1: 20/100, Exam 2: 20/100, Course project: 20/100, Homework: 10/100, and Final Exam: 30/100 (scheduled by the registrar).
• Project: An optional course project can also be taken and will be given the weight of one exam. In this case, the two exams will be rated 40/100 and the project will be rated 20/100.
• Attendance: attendance is required by all students. Excuse for official authorized must be presented to the instructor no later than one week following the absence. Unexcused absences lead to a ``DEN'' grade.

• Course Description: Introduction to parallel computing. Parallel architectures, MIMD, SIMD, interconnection topologies. Performance measures, speedup, efficiency, limitations of parallel processing. Parallel programming paradigms, shared memory, message passing, data parallel, data flow. Parallelizing compiler techniques, code and data partitioning, vectorization. Parallel programming environments and tools. Examples of parallel algorithms.

  Pre-requisite: senior standing.
  

• Course Outline

1.      Concept of Parallel Computing

a.      Parallel Programming Platforms: Implicit parallelism, limitations of memory system, performance, parallel platforms, communication and mapping techniques. (4 lectures)

b.     Principles of Parallel Algorithm Design: Decomposition, mapping, and load balancing. (3 lectures)

c.      Basic Communication: Broadcast, reduction, scatter and gather. (3 lectures)

d.     Analytical Modeling of Parallel Programs: Overhead, performance, granularity, data mapping, scalability, minimum execution time. (4 lectures)

2.     Parallel Programming

a.      Programming distributed-memory: message-passing, send and receive, interface, overlapping communication with computation, collective communication, and communicators. (7 lectures)

b.     Programming Shared Address: thread, API, synchronization, control, composite constructs, and standard for directive based parallel programming. (7 lectures)

3.     Parallel algorithms and applications

a.      Dense matrix, matrix multiplication, solving a system of linear equations. (3 lectures)

b.     Sorting: bubble sort and bucket sorting. (3 lectures)

c.      Graph algorithms: spanning tree, single-source shortest paths, transitive closure, algorithms for sparse graphs. (4 lectures)

d.     Search Algorithms: sequential search, parallel depth-first search, parallel best-first search and speedup anomalies (4 lectures)

 

• Computer Usage: Programming assignments may be required to determine the speed-up when a program is run on the IBM E1350 Cluster computer which can be accessed from anywhere over the University.

• Working Groups: The instructor encourages the students to work in groups for reviewing the class lectures, preparation for exams, and discussion (only) of homework problems. Participants receive bonus grades for such activities. The organization of these groups is as follows. Any student with a GPA above 3.0 can be considered as a class leader. Each class leader is encouraged to create a Working Group of 2, 3, or 4 students to review the course material of the course. A Bonus will be given to all members of a Working Group for each meeting of the group. Students with a GPA above 3.0 wishing to participate in this activity are pleased to give their name and ID to the instructor. Students wishing to participate as group members may ask the instructor about the class leaders and their groups. The class leader has the responsibility of providing the instructor the list of students who attended a meeting. This list should include the students name, date of meeting, and signatures.