CENG 471 Parallel Computing
Fall 2005

Most recent announcement: Jan30

Announcements

Watch this space for the latest updates. Last updated: 30.Ocak.2006 11:52 Evaluation of the final exam is completed.

24.Ocak.2006 14:48 Last day to submit for lab-projects is Jan 31, 2006. You do not have to defend your projects BUT you should run your code both in serial and parallel and make Speed Up and Efficiency tables, graphs, etc. and your comments on these outcomes.

16.Ocak.2006 15:54 Final exam will be open book (any source (on paper)). You should bring calculator to the exam hall. You have time to submit your lab-projects until to the last day of grades submission to the registary office. Salih Körpeoğlu, Yaman Çakmakçı should present their term-study on Friday.

23.Aralık.2005 13:57 The lab notes for the thirteenth week is published, see Course Schedule section.

16.Aralık.2005 13:55 The lab notes for the twelfth week is published, see Course Schedule section.

12.Aralık.2005 15:14 The lecture notes for the twelfth week is published, see Course Schedule section.

9.Aralık.2005 14:15 The lab notes for the tenth week is published, see Course Schedule section.

5.Aralık.2005 16:17 The lecture notes for the eleventh week is published, see Course Schedule section.

28.Kasım.2005 16:32 The lecture notes for the tenth week is published, see Course Schedule section. The presentations will be on the last week of the semester.

25.Kasım.2005 14:06 The lab notes for the nineth week is published, see Course Schedule section. The projects are distributed as;

Sorting Algorithms: Şenay Büyükarslan, Yaren Ilgaz, Ayşe Meydan

Numerical Algorithms: Nevrez İmamoğlu, Alp Eren Özkul, Çağatay Bal

Image Processing: Ufuk Gün, Ömer Sezgin Uğurlu

Searching and Optimization: Neslihan Nailli, Gülistan Özdemir, Salih Körpeoğlu

The others should talk to me. The presentations will be at the last week of the semester.

22.Kasım.2005 08:55The lecture notes for the nineth week is published, see Course Schedule section.

10.Kasım.2005 18:28 The lab notes for the seventh week is published, see Course Schedule section.

8.Kasım.2005 08:54 The lecture notes for the seventh week is published, see Course Schedule section.

31.Ekim.2005 17:53 The lecture notes for the sixth week is published, see Course Schedule section.

27.Ekim.2005 15:37 There will be no class on Friday (Republican Day).

24.Ekim.2005 11:14 The lecture notes for the fifth week is published, see Course Schedule section.

20.Ekim.2005 14:45 The lab notes for the fourth week is published, see Course Schedule section.

17.Ekim.2005 14:58 For home accesing to siber, you should supply to me a static IP. This acces will be valid during semester. The lecture notes for the fourth week is published, see Course Schedule section.

14.Ekim.2005 13:50 The lab notes for the third week is published, see Course Schedule section.

10.Ekim.2005 14:46 The lecture notes for the third week is published, see Course Schedule section.

7.Ekim.2005 10:14 All the c-files (for lecturing and hands-on sessions) will be accessible via the link. The lab notes for the second week is published, see Course Schedule section.

3.Ekim.2005 11:40 The lecture notes for the second week is published, see Course Schedule section.

26.Eylül.2005 15:00 In the first lecture, there will be first metting. The lecture notes for the second 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 (LAB.) Outline

• Contents

• List of Tables

• List of Figures

• 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

• 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

  • Computation of PI as an example

  • Exercise

  • Examples

• Evaluating Parallel Programs

  • Parallel Execution Time

  • Time complexity of a Parallel Algorithm

  • Geometrical Transformations of Images

  • Monte Carlo Methods

  • Performance tuning MPI

  • Performance tuning MPI 2

  • Parallel Summation

• Examples; Buffer Limit, Barrier, Collective Communications and Parallel Matrix Multiplication.

  • Shared Memory; Processes, Threads, OpenMP Examples

• vita

• About this document ...

Text Book

Required

Readings will be assigned in 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.

Recommended

• 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.