Parallel Programming
An Introduction

Thomas Bräunl

            

English version:                    Prentice-Hall, Englewood Cliffs NJ, 1993, pp. (X, 270)
                                               A teacher's manual with solutions to the exercises is available from Prentice-Hall
Ukrainian edition:                Vyschshaya Shkola Publishers, Kyiv, 1997, pp. (IX, 205)
German edition:                   Vieweg Verlag, Wiesbaden 1993


Contents

Preface

Part I  Fundamentals
1.      Introduction
2.      Classifications
        2.1     Computer System Classification
        2.2     Levels of Parallelism
        2.3     Parallel Operations
3.      Petri Nets
        3.1     Simple Petri Nets
        3.2     Extended Petri Nets
        3.3     Sample Petri Nets
4.      Parallel Processing Concepts
        4.1     Coroutines
        4.2     Fork and Join
        4.3     ParBegin and ParEnd
        4.4     Processes
        4.5     Remote Procedure Call
        4.6     Implicit Parallelism
        4.7     Explicit versus Implicit Parallelism
5.      Network Structures
        5.1     Bus Networks
        5.2     Switching Networks
        5.3     Point to Point Networks
        5.4     Comparison of Networks
Exercises  I

Part II  Asynchronous Parallelism
6.      Structure of a MIMD System
        6.1     MIMD Computer Systems
        6.2     Process States
7.      Synchronization and Communication in MIMD Systems
        7.1     Software Solution
        7.2     Hardware Solution
        7.3     Semaphores
        7.4     Monitors
        7.5     Message Passing and Remote Procedure Call
8.      Problems with Asynchronous Parallelism
        8.1     Inconsistent Data
        8.2     Deadlocks
        8.3     Load Balancing
9.      MIMD Programming Languages
        9.1     Concurrent Pascal
        9.2     Communicating Sequential Processes  CSP
        9.3     occam
        9.4     Ada
        9.5     Sequent-C
        9.6     Linda
        9.7     Modula-P
10.     Coarse-Grained Parallel Algorithms
        10.1    Bounded Buffer with Semaphores
        10.2    Bounded Buffer with a Monitor
        10.3    Assignment Distribution via Monitor
        10.4    Asynchronous Simulation
Exercises  II

Part III  Synchronous Parallelism
11.     Structure of a SIMD System
        11.1    SIMD Computer Systems
        11.2    Data Parallelism
        11.3    Virtual Processors
12.     Communication in SIMD Systems
        12.1    SIMD Data Exchange
        12.2    Connection Structures of SIMD Systems
        12.3    Vector Reduction
13.     Problems with Synchronous Parallelism
        13.1    Indexed Vector Operations
        13.2    Mapping Virtual Processors onto Physical Processors
        13.3    Bottlenecks from Peripheral Attachments
        13.4    Network Bandwidth
        13.5    Multi-User Operation and Fault Tolerance
14.     SIMD Programming Languages
        14.1    Fortran 90
        14.2    C*
        14.3    MasPar Programming Language
        14.4    Parallaxis
15.     Massively Parallel Algorithms
        15.1    Numerical Integration
        15.2    Cellular Automata
        15.3    Prime Number Generation
        15.4    Sorting
        15.5    Systolic Matrix Multiplication
        15.6    Generation of Fractals
        15.7    Stereo Image Analysis
Exercises  III

Part IV  Other Models of Parallelism
16.     Automatic Parallelization and Vectorization
        16.1    Data Dependence
        16.2    Vectorization of a Loop
        16.3    Parallelization of a Loop
        16.4    Solving Complex Data Dependences
17.     Non-Procedural Parallel Programming Languages
        17.1    *Lisp
        17.2    FP
        17.3    Concurrent Prolog
        17.4    SQL
18.     Performance of Parallel Systems
        18.1    Speedup
        18.2    Scaleup
        18.3    MIMD versus SIMD
        18.4    Validity of Performance Data
Exercises  IV

References
Index