Introduction to Parallel and Distributed Computing

Wolfgang Schreiner
326.602, WS 2000/2001
Mon 8:30-10:00, Start: 23.10.2000
T811

The efficient application of parallel and distributed systems (multi-processors and computer networks) is nowadays an important task for computer scientists and mathematicians. The goal of this course is to provide an integrated view of the various facets of software development on such systems including the most important aspects of

• System architectures,
• Programming languages and models,
• Software development tools,
• Software engineering concepts and design patterns,
• Performance modeling and analysis,
• Experimenting and measuring.

Class presentation will be accompanied by hands-on experience on a SGI Origin 2000 distributed shared memory multiprocessor in

• data-parallel programming (C automatic parallelization),
• multi-threaded programming (C Posix threads),
• message passing programming (MPI-C).

Literature

Ian T. Foster

Designing and Building Parallel Programs -- Concepts and Tools for Parallel Software Engineering, Addison Wesley, Reading, MA, 1995.

Michael J. Quinn

Parallel Computing -- Theory and Practice, 2nd edition, McGraw-Hill, New York, NY, 1994.

Kai Hwang

Advanced Computer Architecture: Parallelism, Scalability, Programmability, McGraw-Hill, New York, 1993.

Contents

Introduction (PostScript Slides)

A cross-section of the course.

• Matrix multiplication in MPI

The SGI Origin System

Architecture and operating system

• The Origin in the JKU computing center.
• The SGI Origin: A ccNUMA Highly Scalable Server
• Hypercube Connectivity within ccNUMA architecture
• Models of Parallel Computation

Semiautomatic Parallelization

Basic concepts and their application on the Origin.

• Section 9 of the SPP Course Notes.
• Automatic Parallelization for MIPSpro Compilers, Understanding Incomplete Optimization, Assisting the MIPSpro Auto-Parallelizing Option, The Auto-Parallelizing Option (APO), Automatic Parallelization Pragma Directives, DSM Optimization Pragma Directives,
• Multiprocessing Directives, Multiprocessing Advanced Features, Multiprocessing Pragma Directives,
• The Parallel Analyzer View, Examining Loops for C Code, Parallel Analyzer View Reference

Performance of Parallel Programs (PostScript Slides)

Modeling and analyzing the performance of parallel programs, some material from Chapter 3 of Designing and Building Parallel Programs

MultiThreaded Programming

• Alle Fäden in der Hand
• Posix Threads on the Origin

Parallel Program Design (PostScript Slides)

The engineering of parallel programs based on Chapter 2 of Designing and Building Parallel Programs.

The MPI Message Passing Interface

• General
  • Chapter 8 of Foster's Book
  • Example Programs
  • MPICH Home Page.
• MPI on the Origin
  • Building MPI Applications, Using mpirun to Execute Applications, Setting Environment Variables, Debugging Programs on IRIX Systems,
  • XMPI (Screenshot, Screenshot)

Distributed Memory Programming (PostScript Slides)

Some algorithms for distributed memory multiprocessors.

Exercises

• Exercise 1 (Sequential C Program) Write a parallel C program solving the All-Pairs Shortest Path Problem using the automatic parallelization features of the SGI C compiler.
• Exercise 2 (Sequential C Program) Write a parallel C program solving the All-Pairs Shortest Path Problem using the MPI Message Passing Interface.