CENG 471 Parallel Computing
Fall 2008

Most recent announcement: Jan31

Announcements

Watch this space for the latest updates (If the characters do not show properly, please try viewing this page with Unicode (UTF-8) encoding). Last updated:

31.Ocak.2009 16:10 Distribution of the grades is given.

January 27, 2009 00:04 Do not forget to bring your calculators for the final exam, you may need it. Lab project reports are postponed to Thursday. Some hints:

• Do not involve “tiny” for the calculations, just use the flag “nolocal”

• Repeat the same calculations at least twice and take average for your final table entry

• Choose the input values carefully, such that the resulting graphs are meaningful.

January 25, 2009 21:18 Project topics: (There will be presentations after final exam on January 29 Thursday, 13.00 at A-319 ).

1. Mehmet Kadri Toprak - Parallel Computing with CORBA

2. Sina Çetiner - Parallel Processing Granularity, Fine and Coarse Grained Parallelism

3. Ali Evren Küt - General-Purpose Computing on Graphics Processing Units (GPGPU)

4. Batuhan Demirkan - COPACOBANA, The Cost-Optimized Parallel Code Breaker

5. Hüseyin Burhan Özkan - Applications of Parallel Computing and Some Real World Examples

6. Oğuzhan Yücetürk - Design Patterns for Parallel Programming

7. Mehmet Elvanağaç - Types of Parallel Computing

8. Bilal Genç - High Performance Computing in Microsoft Server Platforms Using MS MPI

9. Ebru Gündede - Parallel Operating Systems

10. Esin Karabacakoğlu - Linux Clustering

11. Özge Gürbüz - Parallel Programming Languages

12. Ayşegül Özkaya - Advantages and Disadvantages of Parallel Computing

13. Selma Duman - Parallel File Systems

14. Afşar Türk - Storage Area Network (SAN)

15. Fahreddin Şükrü Torun - Grid Computing

16. Erdem Demir - Message Passing in Java

Please visit the previous years' class pages for other possible titles or you pick one by yourself and submit to my approval.

January 11, 2009 21:40 There will be NO LECTURE and LAB at Jan 12, 2009. I will possibly not available on Monday. The solution of “Exercise: Incomplete thread code segment” of tenth week lab study is given, thanks and credits go to Sina Çetiner and Ali Evren Küt.

January 5, 2009 10:20 Project topics:

January 4, 2009 21:59 The table obtained at the lab study for the parallel summation is available.

January 4, 2009 21:53 The lecture notes and lab notes for the sixteenth week is available, see Course Schedule section.

December 31, 2008 14:59 The date for final exam is announced, see Course Schedule section.

December 29, 2008 18:36 Project topics:

December 28, 2008 17:49 The lecture notes and lab notes for the fifteenth week is available, see Course Schedule section.

December 22, 2008 13:58 The lecture hall is INT-1 due to failure projection equipment at B-301.

December 22, 2008 12:25 The lecture notes and lab notes for the fourteenth week is available, see Course Schedule section.

December 19, 2008 16:06 Project topics:

December 16, 2008 11:38 Project topics:

December 14, 2008 14:59 The lab project is given as follows and due to the final exam date (the submission date may subject to change).

1. Parallel Summation

• General Solution

• with point-to-point communications

• with collective communicatins

• performance analysis (Speed-Up, efficiency, (Amdahl and Gustafson laws : optional))

2. Parallel vector-vector multiplication

• General Solution

• with point-to-point communications

• with collective communicatins

• performance analysis (Speed-Up, efficiency, (Amdahl and Gustafson laws : optional))

3. Parallel matrix-vector multiplication (Optional)

• General Solution

• with point-to-point communications

• with collective communicatins

• performance analysis (Speed-Up, efficiency, (Amdahl and Gustafson laws : optional))

December 14, 2008 14:46 Project topics:

December 14, 2008 14:40 The lecture notes and lab notes for the thirteenth week is available, see Course Schedule section.

November 30, 2008 23:48 The lecture notes and lab notes for the eleventh week is available, see Course Schedule section.

November 23, 2008 12:41 There is no class at this week because of the midterm week.

November 17, 2008 11:12 The lecture notes and lab notes for the nineth week is available, see Course Schedule section.

November 10, 2008 12:44 The lecture notes and lab notes for the eighth week is available, see Course Schedule section.

October 27, 2008 13:09 There will be no lecture at November 3^rd because of the workshop

October 27, 2008 13:09 The lecture notes and lab notes for the sixth week is available, see Course Schedule section.

October 20, 2008 12:20 The lecture notes and lab notes for the fifth week is available, see Course Schedule section.

October 13, 2008 00:26 The lecture notes and lab notes for the fourth week is available, see Course Schedule section.

October 6, 2008 11:57The lecture notes and lab notes for the third week is available, see Course Schedule section.

6. October 2008 11:47 THIS WEB PAGE IS FINALLY AVAILABLE. In the first lecture, there will be first metting. The lecture notes for the third week will be published soon, see Course Schedule section.

Overview

This course provides an introduction to parallel and distributed computing and practical experiences in writing parallel programs on a cluster of computers. You will learn about the following topics:

• Parallel Computers

• Message Passing Computing

• Embarrassingly Parallel Computations

• Partitioning and Divide-and-Conquer Strategies

• Pipelined Computations

• Synchronous Computations

• Load Balancing

• Programming with Shared Memory

Topics might be classifed into two main parts as;

• Parallel computers: architectural types, shared memory, message passing, interconnection networks, potential for increased speed.

• Basic techniques: embarrassingly parallel computations, partitioning and divide and conquer, pipelined computations, synchronous computations, load balancing, shared memory programming.

Lecture Information

There is one group for lecturing. You will be expected to do significant programming assignments, as well as run programs we supply and analyze the output. Since we will program in C on a UNIX environment, some experience using C on UNIX will be important. We will provide tutorials for basic C on UNIX during the first few class periods.

In lab sessions, we will concentrate upon the message-passing method of parallel computing and use the standard parallel computing environment called MPI (Message Passing Interface). Thread-based programming will also be outlined, and the distributed shared memory (DSM) approach (If we have enough time). Each student will complete a project based on parallel computing for the laboratory study.

Also, each student will complete a project based on parallel computing, (distributed computing, cluster computing) for the midterm exam.

Important announcements will be posted to the Announcements section of this web page above, so please check this page frequently. You are responsible for all such announcements, as well as announcements made in lecture.

Course Outline

• Contents

• List of Tables

• List of Figures

• Introduction

  • Four Decades of Computing

  • Flynn's Taxonomy of Computer Architecture

  • SIMD Architecture

  • MIMD Architecture

    • Shared Memory Organization

    • Message Passing Organization

• Introduction to MPI

  • Parallel Computing

  • Types of parallel computing

  • Communicating with other processes

  • Hardware models

  • What is MPI?

  • Who Designed MPI?

  • MPI Implementations

  • Is MPI Large or Small?

  • Where to use MPI?

  • How To Use MPI?

  • Getting started

    • Writing MPI programs

    • Compiling and linking

    • Running MPI programs

    • Finding out about the environment

    • A simple program

    • Exercise - Getting Started

  • MPI Hands-On; Sending and Receiving messages

    • Current Message-Passing

    • The Buffer

    • Sample Program using Library Calls

    • MPI Basic Send/Receive

    • Exercise/Example: Translate this Fortran http://siber.cankaya.edu.tr/ParallelComputing/cfiles/sendreceive.fcode to C

    • Exercise/Example: An example for communication world http://siber.cankaya.edu.tr/ParallelComputing/cfiles/code1.ccode.

    • Exercise/Example: An example http://siber.cankaya.edu.tr/ParallelComputing/cfiles/code2.ccode for sending receiving.

• Performance Analysis

  • Computational Models

    • Equal Duration Model

    • Parallel Computation with Serial Sections Model

  • Skeptic Postulates For Parallel Architectures

    • Grosch's Law

    • Amdahl's Law

    • Gustafson-Barsis's Law

  • MPI Hands-On; Examples

    • Study the previous week's examples

    • Sending in a ring

    • Another simple example for sending and receiving.

    • The same simple example with the previous one but now it uses a MPMD programming style.

    • Synchronous sending.

• Programming Using the Message-Passing Paradigm

  • Principles of Message-Passing Programming

    • Structure of Message-Passing Programs

  • The Building Blocks: Send and Receive Operations

    • Blocking Message Passing Operations

    • Non-Blocking Message Passing Operations

  • MPI Hands-On; Examples

    • Study the previous week's examples

    • Synchronous sending.

    • Buffered sending.

    • Non-blocking sending I.

    • Non-blocking sending II.

  • MPI: the Message Passing Interface

    • Starting and Terminating the MPI Library

    • Communicators

    • Getting Information

    • Sending and Receiving Messages

      • Avoiding Deadlocks

      • Sending and Receiving Messages Simultaneously

  • MPI Hands-On; Examples - Calculating pi number

    • Study the previous week's examples

    • Using an integral approximation

    • Analogy with a dartboard

      • One-to-one communications

      • Collective communications

  • Overlapping Communication with Computation

    • Non-Blocking Communication Operations

  • Collective Communication and Computation Operations

    • Reduction

    • Gather

    • Scatter

    • All-to-All

  • Groups and Communicators

  • MPI Hands-On; Collective Communications

    • Study the previous week's examples

    • Broadcasting the name of the master process

    • Broadcasting an integer value to all of the MPI processes

    • Different datatypes with a single MPI broadcast

    • Exercise: Rewrite these codes with send/recieve pairs

• Programming Shared Memory

  • Why Threads?

  • Thread Basics: Creation and Termination

  • Synchronization Primitives in Pthreads

    • Mutual Exclusion for Shared Variables

  • MPI Hands-On; Collective Communications II

    • Study the previous week's examples

    • A simple MPI example program using broadcast and non-blocking receive

    • A simple MPI example program that uses MPI_Scatter

    • A simple MPI example program that uses MPI_Gather

    • Computation of PI as an example

    • Condition Variables for Synchronization

  • Controlling Thread and Synchronization Attributes

    • Attributes Objects for Threads

  • Thread Cancellation

  • Composite Synchronization Constructs

    • Barriers

  • Tips for Designing Asynchronous Programs

  • OpenMP: a Standard for Directive Based Parallel Programming

    • The OpenMP Programming Model

  • MPI Hands-On; Performance tuning/analysis I

    • Study the previous week's examples

    • Buffer Limit; Determining the amount of MPI buffering

    • Barrier; Benchmarking collective barrier

    • Exercise; Write a program to add n numbers

  • MPI Hands-On; Performance tuning/analysis II

    • Study the previous week's examples

    • Analysis of Parallel Summation with Point-to-Point Communications

• Cluster Computing

  • Introduction

    • Definitions and Taxonomy

    • Opportunities and Advantages

    • Elements of a Cluster

  • An Overview of Cluster Computing

    • A Taxonomy of Parallel Computing

  • Shared Memory I; Processes, Threads

    • Processes

    • Threads

    • Exercise: Incomplete thread code segment

  • Linux & Cluster

    • Why Use Linux for a Beowulf?

    • Kernel

    • File Systems

    • Other Considerations

      • TCP Messaging

      • Hardware Performance Counters

    • Tuning with /proc

  • Shared Memory II; Threads, OpenMP

    • OpenMP

      • Hello world

      • Loop work-sharing

    • Threads; Computing the value of

• References:

• vita

• About this document ...

Text Book

Required

Recommended

• Parallel Programming: Techniques and Application Using Networked Workstations and Parallel Computers, 2^nd edition, by B. Wilkinson and M. Allen, Prentice Hall Inc., 2005, ISBN 0-13-140563-2.

• Beowulf Cluster Computing with Linux, 2nd edition, edited by William Gropp, Ewing Lusk, Thomas Sterling, MIT Press, 2003, ISBN 0-262-69292-9.

• Beowulf Cluster Computing with Windows, Thomas Sterling , MIT Press, 2001, ISBN 0-262-69275-9.

• Using MPI , Portable Parallel Programming with the Message Passing Interface, William Gropp, Ewing Lusk and Anthony Skjellum, The MIT Press, 1999, ISBN 0-262-57132-3.

• Using MPI-2, Advanced Features of the Message Passing Interface, William Gropp, Ewing Lusk, Rajeev Thakur, The MIT Press, 1999, ISBN 0-262-57133-1.

• MPI: The Complete Reference (Vol. 1) - The MPI Core, Marc Snir, Steve Otto, Steven Huss-Lederman, David Walker and Jack Dongarra, The MIT Press, 1998, ISBN 0-262-69215-5.

• MPI: The Complete Reference (Vol. 2) - The MPI-2 Extensions, William Gropp, Steven Huss-Lederman, Andrew Lumsdaine, Ewing Lusk, Bill Nitzberg, William Saphir and Marc Snir, The MIT Press, 1998, ISBN 0-262-57123-4.

• In Search of Clusters: The ongoing battle in lowly parallel computing, Second Edition, by Gregory F. Pfister, Prentice Hall Publishing Company, 1998, ISBN: 0-13-899709-8.

• How to Build a Beowulf – A Guide to the Implementation and Application of PC Clusters, by Thomas Sterling, John Salmon, Donald J. Becker and Daniel F. Savarese, MIT Press, 1999, ISBN 0-262-69218-X.

• PVM: Parallel Virtual Machine, A Users' Guide and Tutorial for Network Parallel Computing, Al Geist, Adam Beguelin, Jack Dongarra, Weicheng Jiang, Robert Manchek and Vaidyalingam S. Sunderam, MIT Press, 1994, ISBN 0-262-57108-0.

This texts are only recommended rather than required. This books are useful for reference, for an alternative point of view.

Online References

Some materials are given. Please inform me about the usefullness of the materials. Check this place for updates.

The following references are available online

• Take a look at the TOP500 list

• MPI: The Complete Reference

• Message Passing Interface Forum

• MPICH Home Page

• MPI Man pages (Web format)

• ANSI C for Programmers on UNIX Systems

• Greg Wilson's Parallel Computing Timeline (1955 to 1993)

• I. Foster. Designing and Building Parallel Programs, Addison-Wesley, 1995 available on-line

• Glossary of Terms

Grading Criteria

• There will be a final exam: 40%

• Term Project as Midterm exam: 25%

• Term Project as Lab. exam: 25%

• Attendance is required and constitutes part of your course grade; 10%

Policies

• Attendance is not compulsory, but you are responsible for everything said in class.

• I encourage you to ask questions in class. You are supposed to ask questions. Don't guess, ask a question!

• You may discuss homework problems with classmates (although it is not to your advantage to do so).

• You can use ideas from the literature (with proper citation).

• You can use anything from the textbook/notes.

• The code you submit must be written completely by you.

Course Schedule

The following schedule is tentative; it may be updated later in the semester, so check back here frequently.