Parallel Programming
Platforms
Two views
• Logical Organization: Programmer’s View
• Physical Organization: Organization of Hardware
Logical Organization: Programmer’s
view
• Two critical considerations for a programmer:
• How does the parallelism exhibit
Control Structure
• How to specify the interaction between parallel tasks
Logical Organization: Programmer’s
view
• Two critical considerations for a programmer:
• How does the parallelism exhibit
Control Structure
• How to specify the interaction between parallel tasks
Communication model
Control Structure
• Parallelism can be induced in two ways
1. Each program in a set of programs can be viewed as one parallel task.
2. Individual instructions within a program can be viewed as parallel tasks.
Control Structure
• Parallelism can be induced in two ways
1. Each program in a set of programs can be viewed as one parallel task.
2. Individual instructions within a program can be viewed as parallel tasks.
Execution of Parallel Units
• Processing units either operate under the centralized control of a single control unit or work
independently.
Execution of Parallel Units
• Processing units either operate under the centralized control of a single control unit or
work independently.
SIMD MIMD
SIMD
• In this type of parallel computer same instruction is
executed synchronously by all processing units.
• Relies on highly structured (regular) nature of the
underlying computations, for example
• in image processing and graphics, to deliver improved
performance.
• Require
• Less H/W because of 1 Global CU.
• Less Memory for one copy of code
• Less Specialised H/W for Design constraints, Product life
cycle.
• Performance fall with Branching conditions e.g. with
if-else
MIMD
• Each PE is capable of executing a different program
independent of the other processing elements.
• A simple variant of MIMD, is
SPMD, relies on multiple instances of the same
program executing on different data.
• Here, Branching instructions can be put as multiple
programs into one large if-else block.
• SPMD is widely used by many parallel platforms and
requires minimal architectural support.
• Require
• More H/W.
• More Memory
• Good for irregular execution
Communication Model
• Two primary forms of data exchange between parallel tasks:
• accessing a shared data space, and
• exchanging messages.
Shared-Address-Space Platforms
• Supports a common data space that is accessible to all
processors where they interact by modifying data objects.
• Memory in this platform can be local (exclusive to a
processor) or global (common to all processors).
• The sub-figures (a) and (b) can be classified as UMA
multicomputer while sub-figure (c) as NUMA multicomputer.
• UMA follows the Shared-memory computer architecture in which the memory
is physically shared i.e., each processor has equal access to any memory
segment, whereas
• A distributed-memory computer architecture, in which different segments of
the memory are physically associated with different PEs. It is identical to a
NUMA machine.
Shared-Address-Space Platforms
(contd.)
• Presence of a global memory space makes programming
such platforms much easier because
• All read-only interactions are invisible to the programmer.
• Read/write interactions are harder to program as these operations require
mutual exclusion for concurrent accesses.
• These programming paradigms such as threads (POSIX)
and OpenMP, support synchronization using locks and
related mechanisms.
Message-Passing Platforms
• It consists of p processing nodes, each with its own exclusive address space where
• Each of the nodes can either be single processors or a shared-address-space multiprocessor.
• Interactions between processes running on different nodes must be accomplished using messages
• This exchange of messages among the processes is used to transfer
• Data
• Work, and
• To synchronize actions.
• Basic operations in this message passing paradigm is
• send, receive, whoami and numprocs (specifies the number of processes participating in the ensemble).
• Message-passing APIs like MPI, support these basic operations and a variety of higher level
functionality under different function names.
Ideal architecture of Parallel
Machine: PRAM
• It is an extension of serial model of computation (the Random Access
Machine, or RAM) consisting of
• p processors and
• a global memory of unbounded size that is uniformly accessible to
all processors.
• All processors access the same address space.
• Processors share a common clock but may execute different
instructions in each cycle.
Subclasses of PRAM (contd.)
• Depending on how simultaneous memory accesses are handled,
PRAMs can be divided into four subclasses.
1. Exclusive-read, exclusive-write (EREW) PRAM
2. Concurrent-read, concurrent-write (CRCW) PRAM.
3. Concurrent-read, exclusive-write (CREW) PRAM.
4. Exclusive-read, concurrent-write (ERCW) PRAM.
Protocols for R/W
• Concurrent read access does not create any semantic discrepancies in
the program.
• Concurrent write access to a memory location requires some
protocols like:
1. Common: write is allowed if all the values that the processors are
attempting to write are identical.
2. Arbitrary: an arbitrary processor is allowed to write and the rest fail.
3. Priority: All processors are organized into a predefined prioritized list, and
the processor with the highest priority succeeds and the rest fail.
4. Sum: in which the sum of all the quantities is written