PART I: BASIC CONCEPTS

1. Introduction (figures: [PDF] [PS])

• Motivating Parallelism
• Scope of Parallel Computing
• Organization and Contents of the Text

2. Parallel Programming Platforms (figures: [PPT] [PDF] [PS])
    (GK lecture slides [PDF]) (AG lecture slides [PPT][PDF][PS])

• Implicit Parallelism: Trends in Microprocessor Architectures
• Limitations of Memory System Performance
• Dichotomy of Parallel Computing Platforms
• Physical Organization of Parallel Platforms
• Communication Costs in Parallel Machines
• Routing Mechanisms for Interconnection Networks
• Impact of Process-Processor Mapping and Mapping Techniques
• Bibliographic Remarks

3. Principles of Parallel Algorithm Design (figures: [PPT] [PDF] [PS], algorithms: [PDF] [PS])
    (GK lecture slides [PDF]) (AG lecture slides [PPT][PDF][PS])

• Preliminaries
• Decomposition Techniques
• Characteristics of Tasks and Interactions
• Mapping Techniques for Load Balancing
• Methods for Containing Interaction Overheads
• Parallel Algorithm Models
• Bibliographic Remarks

4. Basic Communication Operations (figures: [PPT] [PDF] [PS], algorithms: [PDF] [PS])
    (GK lecture slides [PDF]) (AG lecture slides [PPT][PDF][PS])

• One-to-All Broadcast and All-to-One Reduction
• All-to-All Broadcast and Reduction
• All-Reduce and Prefix-Sum Operations
• Scatter and Gather
• All-to-All Personalized Communication
• Circular Shift
• Improving the Speed of Some Communication Operations
• Summary
• Bibliographic Remarks

5. Analytical Modeling of Parallel Programs (figures: [PPT] [PDF] [PS])
    (GK lecture slides [PDF]) (AG lecture slides [PPT][PDF][PS])

• Sources of Overhead in Parallel Programs
• Performance Metrics for Parallel Systems
• Effect of Granularity and Data Mapping on Performance
• Scalability of Parallel Systems
• Minimum Execution Time and Minimum Cost-Optimal Execution Time
• Asymptotic Analysis of Parallel Programs
• Other Scalability Metrics
• Bibliographic Remarks

PART II: PARALLEL PROGRAMMING

6. Programming Using the Message Passing Paradigm (figures: [PPT] [PDF] [PS])
    (GK lecture slides [PDF]) (AG lecture slides [PPT][PDF][PS])

• Principles of Message-Passing Programming
• The Building Blocks: Send and Receive Operations
• MPI: The Message Passing Interface
• Topologies and Embedding
• Overlapping Communication with Computation
• Collective Communication and Computation Operations
• Groups and Communicators
• Bibliographic Remarks

7. Programming Shared Address Space Platforms (figures: [PPT] [PDF] [PS])
    (GK lecture slides [PDF]) (AG lecture slides [PPT][PDF][PS])
    (A complete set of Pthread programs)

• Thread Basics
• Why Threads?
• The POSIX Thread Application Programmer Interface
• Synchronization Primitives in POSIX
• Controlling Thread and Synchronization Attributes
• Thread Cancellation
• Composite Synchronization Constructs
• Tips for Designing Asynchronous Programs
• OpenMP: A Standard for Directive Based Parallel Programming
• Bibliographic Remarks

PART III: PARALLEL ALGORITHMS AND APPLICATIONS

8. Dense Matrix Algorithms (figures: [PPT] [PDF] [PS], algorithms: [PDF] [PS])
    (GK lecture slides [PDF]) (AG lecture slides [PPT][PDF][PS])

• Matrix-Vector Multiplication
• Matrix-Matrix Multiplication
• Solving a System of Linear Equations
• Bibliographic Remarks

9. Sorting (figures: [PPT] [PDF] [PS], algorithms: [PDF] [PS])
    (GK lecture slides [PDF]) (AG lecture slides [PPT][PDF][PS])

• Issues in Sorting on Parallel Computers
• Sorting Networks
• Bubble Sort and its Variants
• Quicksort
• Bucket and Sample Sort
• Other Sorting Algorithms
• Bibliographic Remarks

10. Graph Algorithms (figures: [PPT] [PDF] [PS], algorithms: [PDF] [PS])
    (GK lecture slides [PDF]) (AG lecture slides [PPT][PDF][PS])

• Definitions and Representation
• Minimum Spanning Tree: Prim's Algorithm
• Single-Source Shortest Paths: Dijkstra's Algorithm
• All-Pairs Shortest Paths
• Transitive Closure
• Connected Components
• Algorithms for Sparse Graphs
• Bibliographic Remarks

11. Search Algorithms for Discrete Optimization Problems (figures: [PPT] [PDF] [PS])
    (GK lecture slides [PDF]) (AG lecture slides [PPT][PDF][PS])

• Definitions and Examples
• Sequential Search Algorithms
• Search Overhead Factor
• Parallel Depth-First Search
• Parallel Best-First Search
• Speedup Anomalies in Parallel Search Algorithms
• Bibliographic Remarks

12. Dynamic Programming (figures: [PPT] [PDF] [PS])
    (AG lecture slides [PPT][PDF][PS])

• Overview of Dynamic Programming
• Serial Monadic DP Formulations
• Nonserial Monadic DP Formulations
• Serial Polyadic DP Formulations
• Nonserial Polyadic DP Formulations
• Summary and Discussion
• Bibliographic Remarks

13. Fast Fourier Transform  (figures: [PDF] [PS], algorithms: [PDF] [PS])
   

• The Serial Algorithm
• The Binary-Exchange Algorithm
• The Transpose Algorithm
• Cost-Effectiveness of Parallel FFT Algorithms
• Bibliographic Remarks