CENG 505 Parallel Computing I
Fall 2010

Most recent announcement: Jan07

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:

January 7, 2011 17:54 Project topics:

1. Murat Altun - Storage Area Network (SAN)

2. Çağlar Günel - Design Patterns for Parallel Programming

3. Derya Akbulut - Parallel Algorithms for 2D Cutting Stock Problems

4. Atıl Kurt - Parallel Programming for Scheduling Algorithms

5. Funda Karabak - Branch and Bound Algorithms with Parallel Computing

6. Nizamettin Doğan Güner - Supercomputers Around the World

7. Duygu Özen - Travelling Salesman Problem

8. Mesut Körpe - Grid Computing

9. Özgür Pekçağlıyan - Parallelism In Databases

10. Sait Mutlu -Implementing MPI on Windows and Unix, Performance Comparison

11. Erdem Genç – Efficiency of Parallel Programming Using Microsoft Technologies

12. Tan Atagören - GPGPU (General-Purpose Computing On Graphics Processing Units)

December 31, 2010 16:44 Project presentations date: January 5, 2011 18:00 .

December 27, 2010 19:01 Project topics:

December 27, 2010 14:25 The fourth homework is given, see pdf-file. It is due to Jan 10, 2010. These homeworks will be your laboratory project. An additional laboratory project will be a plus for your grade. Read the following lines very carefully;

1. Compress all files to one file. Name this file as “yourstudentID.zip(/tar/rar/tgz/gz)” otherwise your assignment will not be evaluated.

2. When this file decompressed, all files should reside in a directory named with “yourstudentID”. otherwise your assignment will not be evaluated.

You should submit your code and results (tables, plots, comments,...) both via e-mail and in paper to me. otherwise your assignment will not be evaluated.

December 21, 2010 11:34 Project topics:

December 20, 2010 16:57 The lecture notes for the thirteenth and fourteenth weeks are available, see Course Schedule section.

December 20, 2010 11:16 Project topics:

December 13, 2010 16:52 The third homework is given, see pdf-file. It is due to Dec 27, 2010.

December 13, 2010 16:49 The lecture notes for the twelfth week is available, see Course Schedule section.

December 6, 2010 15:47 The lecture notes for the eleventh week is available, see Course Schedule section.

November 30, 2010 11:14 Project topics:

November 29, 2010 15:37 The lecture notes for the tenth week is available, see Course Schedule section.

November 22, 2010 12:54 The second homework is given, see pdf-file. It is due to Dec 13, 2010.

November 21, 2010 23:22 The lecture notes for the ninth week is available, see Course Schedule section.

November 1, 2010 17:25The lecture notes for the sixth week is available, see Course Schedule section.

October 26, 2010 15:03 The first homework is given, see pdf-file. It is due to Nov 5, 2010.

October 25, 2010 14:17 The lecture notes for the fifth week is available, see Course Schedule section.

October 18, 2010 11:36 The lecture notes for the fourth week is available, see Course Schedule section.

October 11, 2010 17:18 The lecture notes for the third week is available, see Course Schedule section.

October 4, 2010 16:05 The lecture notes for the second week is available, see Course Schedule section.

September 27, 2010 16:29 In the first lecture, there will be first meeting and introductory studies. The lecture notes for the second week will be published soon, see Course Schedule section. All the example c-files (for lecturing and hands-on sessions) will be accessible via the link.

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 classified 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

• First Meeting

  • Lecture Information

  • Overview

  • Text Book

  • Grading Criteria & Policies

  • Parallel Computing

  • MPI Hands-On; Performance Analysis

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

• Introduction

  • Four Decades of Computing

  • Flynn's Taxonomy of Computer Architecture

  • Parallel and Distributed Computers

  • SIMD Architecture

  • MIMD Architecture

  • Shared Memory Organization

  • Message Passing Organization

  • MPI Hands-On - Introduction to MPI

    • Parallel Computing

    • Communicating with other processes

    • What is MPI?

    • MPI Implementations

    • Is MPI Large or Small?

    • Where to use MPI?

    • How To Use MPI? Essential!!

    • Getting started

      • Writing MPI programs I

      • Writing MPI programs II

      • Writing MPI programs III

      • Exercise - Getting Started

• 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 - Sending and Receiving Messages I

    • Current Message-Passing

    • The Buffer

    • MPI Basic Send/Receive

    • Exercises/Examples

• 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; Sending and Receiving Messages 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; Sending and Receiving Messages III

    • HOMEWORK - Due to November 5, 2010

  • Overlapping Communication with Computation

    • Non-Blocking Communication Operations

  • Collective Communication and Computation Operations

    • Broadcast

    • Reduction

    • Gather

    • Scatter

    • All-to-All

  • Groups and Communicators

  • MPI Hands-On; Collective Communications I

• Programming Shared Memory

  • What is a Thread?

  • Threads Model

  • Why Threads?

  • Thread Basics: Creation and Termination

    • Thread Creation

    • Thread Termination

  • MPI Hands-On; Collective Communications II

    • HOMEWORK - Due to December 13, 2010

  • Thread Basics: Passing Arguments, Cancellation and Joining

    • Passing Arguments to Threads

    • Thread Cancellation

    • Joining and Detaching Threads

  • Synchronization Primitives in Pthreads

    • Mutual Exclusion for Shared Variables

  • Hands-on; Shared Memory I; Threads

  • Thread Examples

    • Computing the value of

    • Producer-consumer work queues

  • Condition Variables for Synchronization

  • Hands-on; Shared Memory II; Synchronization Primitives

  • Controlling Thread Attributes and Synchronization

    • Attributes Objects for Threads

  • Composite Synchronization Constructs

  • Tips for Designing Asynchronous Programs

  • OpenMP: a Standard for Directive Based Parallel Programming

    • The OpenMP Programming Model

  • Hands-on; Shared Memory III; MPI with Pthread, OpenMP

    • HOMEWORK - Due to December 27, 2010

• Network Computing

  • Computer Networks Basics

    • Network Performance

    • Other Network Technologies

  • Client/Server Systems

    • Sockets

    • A Client Server Framework for Parallel Applications

  • Clusters

    • Cluster Examples

  • Hands-on; Miscellaneous I

  • Interconnection Networks

    • Ethernet

    • Switches

    • Myrinet Clos Network

    • The Quadrics Network

  • Grid Computing

  • Hands-on; Miscellaneous II

    • HOMEWORK - Due to January 10, 2011

• References:

• vita

• About this document ...

Text Book

Required

Recommended

• Principles of Parallel Programming, by C. Lin and L. Snyder, Addison-Wesley 2009, ISBN 0-32-148790-7.

• 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

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 COMPULSORY, and 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.