Outline
Foster’s Parallel Algorithm Design Methodology
SCK 4213: High Performance &
Parallel Computing
Chapter 3: Parallel Algorithm Design
Ismail Fauzi Isnin
Department of Computer Systems & Communications
Faculty of Computer Science & Information Systems,
Universiti Teknologi Malaysia
Semester 1 - 2011/2012
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline
Parallel Algorithm Models
Foster’s Parallel Algorithm Design Methodology
Outline
1 Principles of of Parallel Algorithm Design
2 Parallel Algorithm Models
3 Parallel Programming Models
4 Foster’s Design Methodology
1 Partitioning
2 Communication
3 Agglomeration
4 Mapping
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline
Parallel Algorithm Models
Foster’s Parallel Algorithm Design Methodology
Principles of Parallel Algorithm Design
In practice, specifying a nontrivial parallel algorithm
may include some or all of the following:
Identifying portions of the problem that can be
performed concurrently.
Mapping the concurrent pieces of computation
onto multiple processes running in parallel.
Distribute inputs, outputs and intermediate
data among the processes.
Managing access to data shared by multiple
processes.
Synchronizing the processors at various stages
of the parallel program execution.
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline
Parallel Algorithm Models
Foster’s Parallel Algorithm Design Methodology
Parallel Algorithm Models
1 Data Parallel Model
the tasks are statically or semi statically
mapped onto processes and each tasks
performs similar operations.
2 Task Graph Model
Computations in any parallel algorithm can be
viewed a task dependency graph. The
task-graph is used to map the task onto
processes.
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline
Parallel Algorithm Models
Foster’s Parallel Algorithm Design Methodology
Parallel Algorithm Models
1 Work Pool Model / Task Pool Model
The work pool or task pool model is
characterised by a dynamic mapping of tasks
into process for load balancing in which any
task may potentially be performed by any
process. there is no desired premapping of
tasks onto processes.
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline
Parallel Algorithm Models
Foster’s Parallel Algorithm Design Methodology
Parallel Algorithm Models
1 The Master-Slave Model
In the master-slave or the manager-worker
model, one or more master process generate
work and allocate it to worker processes.
2 The Pipeline Model
In the pipeline mode, a stream of data is
passed through a succession of process, each of
which perform different task on the data. this
simulatneous execution of different process on
a data stream is called stream parallelism.
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline Parallel Algorithm Models
Foster’s Parallel Algorithm Design Methodology Parallel Programming Models
Parallel Programming Models
1 Task and Channel Model
2 Message Passing Model
3 Data Parallelism
4 Shared Memory
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline Parallel Algorithm Models
Foster’s Parallel Algorithm Design Methodology Parallel Programming Models
Tasks and Channels Model
channel
task
inport
- program
outport - local data
- I/O ports
example of sending message instruction
"send message on channel X"
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline Parallel Algorithm Models
Foster’s Parallel Algorithm Design Methodology Parallel Programming Models
Tasks and Channels Model
Task
a task consists of program (instructions), local
memory and collection of I/O ports.
local memory contains the program instruction and
local data
a task sending local data to other tasks through
outports.
a task receiving external data through inports.
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline Parallel Algorithm Models
Foster’s Parallel Algorithm Design Methodology Parallel Programming Models
Tasks and Channels Model
Channel
a channel is a message queue that connects an
outport of a task to an inport of another task.
received data appear at the same order as they
were placed through outport of the sending task.
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline Parallel Algorithm Models
Foster’s Parallel Algorithm Design Methodology Parallel Programming Models
Message Passing Model
task 0 task 0
task 0
task 0
task 0
example of sending message instruction
"send message to Task X" - program
- local data
- I/O ports
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline Partitioning
Foster’s Parallel Algorithm Design Methodology Communication
Foster’s Parallel Algorithm Design
Methodology
1 Partitioning
2 Communication
3 Agglomeration
4 Mapping
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline Partitioning
Foster’s Design Methodology Communication
Foster’s Parallel Algorithm Design
Methodology
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing 13 / 29
Outline Partitioning
Foster’s Parallel Algorithm Design Methodology Communication
Partitioning
1 Partitioning
The process of dividing the computation task into
smaller pieces of tasks (primitive tasks).
A good partitioning splits data and computations
into many primitive tasks.
2 Aim of partitioning
To discover as much parallelism as possible.
3 Two approaches of partitioning
Data centric approach: Domain decomposition.
Computation-centric approach: Functional
decomposition.
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline Partitioning
Foster’s Parallel Algorithm Design Methodology Communication
Data-centric approach: Domain
decomposition
Domain decomposition divide data into pieces
and then determine how to associate
computation with the data.
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
1D Domain Decomposition
a) Decomposed in Y-direction
b) Decomposed in X-direction
How many primitive tasks presented?
2D Domain Decomposition
a) Decomposed in Z and Y directions How many
b) Decomposed in Z and X directions primitive tasks
c) Decomposed in X and Y directions presented?
3D Domain Decomposition?
Outline Partitioning
Foster’s Parallel Algorithm Design Methodology Communication
Computation-centric approach: Functional
decomposition
Functional decomposition is the
complimentary strategy that divide the
computation into pieces, and then determine
how to associate data with the individual
computations.
Oftenly, functional decompositions yield
collection of tasks that achieve concurrency
through pipeline parallelism.
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline Partitioning
Foster’s Parallel Algorithm Design Methodology Communication
Decomposition analogy
100 cars to be fixed 100 working cars
input Workshop output
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline Partitioning
Foster’s Parallel Algorithm Design Methodology Communication
Decomposition analogy (2)
100 cars to be fixed
Domain decomposition
50 cars 50 cars
Functional
decomposition
(complementary
fix air-cond fix wiring fix air-cond strategy)
(10 cars) (30 cars) (20 cars)
fix engine fix engine fix wiring
(10 cars) (10 cars) (20 cars)
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Decomposition Techniques
• The decomposition techniques we will
discuss :-
- Recursive decomposition
- Data decomposition
- Exploratory decomposition
- Speculative decomposition
Recursive Decomposition
• Recursive decomposition is a method for inducing
concurrency in problems that can be solved using the
divide and conquer strategy.
• A problem is solved by first dividing it into a set of
independent subproblems. Each of it is solved by
recursively applying a similar division into smaller
subproblems followed by a combination of the their
results.
Data Decomposition
• In this method, the decomposition is done in two steps. In
the first step, the data on which the computations are
performed is partitioned. In the second step, this data
partitioning is used to induce a partitioning of the
computation into tasks.
• The operations that these tasks performs on different data
partitions are usually similar.
• The partitioning can be done on input data, output data,
both input and output data and also immediate data (output
that is produced from one stage will be input to the
subsequent stage).
Exploratory Decomposition
• This technique is used to decompose
problems whose underlying operations
corresponds to a search of a space for
solutions.
• The search space is partitioned into smaller
parts concurrently, until the desired
solutions are found.
Speculative Decomposition
• Speculative decomposition is used when a program may
take one of many possible computationally significant
branches depending on the output of other computations
that precede it.
• In this situation, while one task is performing the
computation whose output is used in deciding the next
computation, other tasks can concurrently start the
computation of the next stage.
Outline Partitioning
Foster’s Parallel Algorithm Design Methodology Communication
Foster’s Partitioning Checklist
number of primitive tasks (outcome of
partitioning process) should be higher than
number of processors in the target parallel
computer. This increase the flexibility on
subsequent design stages.
minimize redundant data structure storage and
redundant computations.
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline Partitioning
Foster’s Parallel Algorithm Design Methodology Communication
Foster’s Partitioning Checklist
primitive tasks are roughly the same size.
The number of primitive tasks is an increasing
function of the problem size.
Maximize the flexibility of subsequent design
stages by considering several alternative
partitioning? Domain decomposition,
functional or both.
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline Partitioning
Foster’s Parallel Algorithm Design Methodology Communication
Communication
Typically, data must be transferred between tasks so
as to allow computation to proceed. This
information flow is specified in the communication
phase of a parallel algorithm design.
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline Partitioning
Foster’s Parallel Algorithm Design Methodology Communication
Communication categories
local and global communication
structured and unstructured communication
static and dynamic communication
synchronous and asynchronous
communication
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline Partitioning
Foster’s Parallel Algorithm Design Methodology Communication
Communication categories
local communication - when a task
communicates with a small set of other tasks
(its neighbours).
global communication - when a task
communicates with many other tasks.
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing 22 / 27
Outline Partitioning
Foster’s Parallel Algorithm Design Methodology Communication
Communication categories
structured communication - route of tasks
communication form a structured network such
as tree or grid.
unstructured communication - route of
tasks communication form an arbitrary network.
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline Partitioning
Foster’s Parallel Algorithm Design Methodology Communication
Communication categories
static communication - the identity of
communication partners does not change over
time.
dynamic communication - identity of
communication partners may be determined by
data computed at runtime and may be highly
variable.
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline Partitioning
Foster’s Parallel Algorithm Design Methodology Communication
Communication categories
synchronous communication - producer and
consumer execute in coordinated fashion.
producer and consumer pairs cooperating in
data transfer operations.
asynchronous communication - may
requires that a task obtain/transmit data
without the cooperation of the other tasks.
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Outline Partitioning
Foster’s Parallel Algorithm Design Methodology Communication
Issues in Communication phase
Communications between tasks may be
considered as part of overhead of a parallel
algorithm.
Therefore, minimizing communication overhead
is an important consideration to take while
designing a parallel algorithm.
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing
Methods of Containing
Interaction Overheads
• Maximizing data locality
- minimize volume of shared data
- minimize frequency of interaction among
tasks
• Minimizing contention
• Replicating data or computations
Foster’s design method:
communication checklist
• The communication operations are balanced
among tasks.
• Each tasks communicates with only a small
number of neighbors.
• Tasks can perform their communications
concurrently.
• Tasks can perform their computations
concurrently.
Foster’s design methodology:
Agglomeration
• Agglomeration
– Process of grouping tasks into larger tasks in order to
improve performance or simplify the programming.
– Goals of agglomeration:
• Lower communication overhead.
– Reduce number of communication channels.
– Reduce number of message transmissions.
• Maintain scalability of the parallel design.
– Ensure the algorithm is applicable on machine with higher
number of processors.
• Reduce software engineering cost.
– while parallelizing sequential algorithm, sometime it is better to
remain some part of the sequential algorithm.
Foster’s Agglomeration checklist
• The agglomeration has increased the
locality of the parallel algorithm
• Replicated computations take less time than
the communications they replace.
• The amount of replicated data is small
enough to allow the algorithm to scale.
• Agglomerated tasks has similar
computational and communications costs.
Foster’s Agglomeration checklist
• The number of tasks is an increasing function of
the problem size.
• The number of tasks is as small as possible, at
least as great as number of processors in the target
computers.
• The trade-off between the chosen agglomeration
and the cost of modification in existing sequential
code is reasonable.
Foster’s design method:
Mapping
• Mapping
– is the process of assigning tasks to processors.
• Goals of mapping:
– Maximize processor utilization
– Minimize inter-processor communication.
• Processor Utilization
– the average percentage of time the system’s processors
are actively executing tasks necessary for the solution
of the problem.
– Processor utilization is maximized when computation is
balanced evenly.
Foster’s design method:
Mapping
• Inter-processor communication decreases when
two tasks connected by a channel are mapped to
the same processor.
Mapping
• Map all tasks into a single processor will reduce
the inter-processor communication to zero, but
will results in poor processor utilization.
• Mapping tasks into a good processor utilization
sometimes will results poor inter-processor
communication.
• Increasing processor utilization and
minimizing inter-processor communication are
often conflicting goals.
Mapping example
A Assume that:
- equal processors speed
C - equal computation by
B each task
E - equal inter-processor
F communication delay
D
H Map these tasks into a
parallel computer with
G 3 processors?
Mapping example
P1 P2 P3
If each tasks requires p seconds
to complete,
A C What is the utilization period
of P1, P2 and P3?
E
H What is the idle period of P1,
P2 and P3?
B F
Can you propose others
D mapping that will improve the
G
utilization or the idle period of
P1, P2 and P3?
Mapping Techniques
• Mapping techniques can be broadly classified into two
categories: static and dynamic.
• Static mapping techniques distribute tasks among
processes prior to the execution of the algorithm.
• Dynamic mapping techniques distribute the work among
processes during the execution of the algorithm.
Schemes for Static Mapping
• Mappings base on Data Partitioning
Array Distribution Schemes
Block Distribution
In these distributions a d-dimensional array
is distributed among the processes. Each
process receives a contiguous block of array
entries along a specified subset of array
dimensions.
Schemes for Static Mapping (2)
Array Distribution Schemes
Block Cyclic Distribution
A variation of the block distribution scheme
that can be used to alleviate load imbalance
and idling problems. The central idea behind a block cyclic
distribution is to partition an array into many more blocks
than the number of available processes. Then we assign the
partitions to processes in a round robin manner.
Schemes for Static Mapping (3)
Array Distribution Schemes
Randomized Block Distribution
In this scheme, the array is partitioned into many more
blocks than the number of the available processes. The
blocks are uniformly and randomly distributed among the
processes.
Schemes for Static Mapping (4)
• Mappings based on Task Partitioning
A mapping based on partitioning a task-
dependency graph and mapping its nodes
onto processes can be used when the
computation is naturally expressible in the
form of a static task-dependency graph with
task of known sizes.
Schemes for Dynamic Mapping
• Centralized Schemes
In a centralized dynamic load balancing scheme, all
executable tasks are maintained in a common central data
structure by a special process. If this process is designated
to manage a pool of available tasks, then it is often referred
as the master and other processes that depend on that
master to obtain work as slaves.
Schemes for Dynamic Mapping
(2)
• Distributed Schemes
In a distributed dynamic load balancing
scheme, the set of executable tasks are
distributed among processes which
exchange tasks at run time to balance work.
Each process can send work or receive work
from any other process.
Outline Partitioning
Foster’s Design Methodology Communication
References
Ian Foster, Designing and Building Parallel
Programs: Concepts and Tools for Parallel
Software Engineering, Addison-Wesley, 1995.
Barry Wilkinson and Michael Allen, Parallel
Programming: Techniques and Applications
Using Networked Workstation and Parallel
Computers, 2nd Edition, Pearson Prentice Hall,
2005.
Michael T. Heath, CSE 512 / CS 554 Lecture
slides, University of Illinois.
Michael J. Quinn, Parallel Programming in C
with MPI and OpenMP, McGraw Hill, 2003.
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing 27 / 28
Outline Partitioning
Foster’s Parallel Algorithm Design Methodology Communication
Q&A
Ismail Fauzi Isnin SCK 4213: High Performance & Parallel Computing 27 / 27