Parallel Processing

Preliminaries and Decomposition

Preliminaries Dividing a computation into smaller computations and assigning them to different processors for parallel execution are the two key steps in the design of parallel algorithms. In this...

Principles of Parallel Algorithm Design

Algorithm development is a critical component of problem solving using computers. A sequential algorithm is essentially a recipe or a sequence of basic steps for solving a given problem...

Impact of Process-Processor Mapping and Mapping Techniques

The programmer has no control over how logical processes are mapped to network nodes. This can lead to congestion problems if the programmer does not understand the mapping algorithm...

Routing Mechanisms for Interconnection Networks

Routing mechanism – determines the path a message takes from source to sink. Input: source and sink nodes Output: One or more paths from source to sink Types of...

Communication Costs in Parallel Machines

Communication Costs – Overhead for communicating between processing elements. 1 Message Passing Costs in Parallel Computers Communication time = Message prep time + Network traversal time Startup time –...

Physical Organization of Parallel Programs

1 Architecture of an Ideal Parallel Computer Parallel Random Access Machine (PRAM) – The parallel computer consists of p processors and a global memory of unbounded size that is...

Dichotomy of Parallel Computing Platforms

Logical organization of platforms: The programmer’s view of the platform Physical organization of platforms: The hardware view of the platform Control structure: Ways of expressing parallel tasks Communication model:...

Limitations of Memory System Performance

Latency: The time it takes for a block of data to be retrieved from memory after a request has been made. Bandwidth: The rate at which data can be...

Implicit Parallelism: Trends in Microprocessor Architectures

The tremendous gains in microprocessor clock speed since the 1980s have failed to provide similar gains in overall processing speed due to the slower pace of improvements in memory...

Introduction to Parallel Computing

Parallel computing is a type of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones,...