Parallel Processing

Parallel Programming Platforms

• 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

Principles of Parallel Algorithm Design algorithms

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

Basic Communication Operations, algorithms

• 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

Analytical Modeling of Parallel Programs

• 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

Programming Using the Message Passing Paradigm

• 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

Programming Shared Address Space Platforms Thread Basics

• Why Threads?
• The POSIX Thread Application Programmer Interface
• Synchronization Primitives in POSIX
• Controlling Thread and Synchronization Attributes
• Thread Cancellation
• Composite Synchronization Constructs

Dense Matrix Algorithms

• Matrix-Vector Multiplication
• Matrix-Matrix Multiplication


Issues in Sorting on Parallel Computers
• Sorting Networks
• Bubble Sort and its Variants
• Quick sort

Graph Algorithms

• Definitions and Representation
• Minimum Spanning Tree: Prim’s Algorithm
• Single-Source Shortest Paths: Dijkstra’s Algorithm
• All-Pairs Shortest Paths