PARALLEL PROCESSING CHALLENGES

Concurrency
 Concurrency is a property of a system representing the fact that multiple
activities can be executed at the same time

 If an algorithm cannot be divided into groups of operations that can

execute concurrently, performance improvements due to parallelism
cannot be achieved, and any processors after the first will be of limited
use in accelerating the algorithm

 To a large extent, different problems inherently have differing amounts

of concurrency. For most problems, developing an algorithm that
achieves its maximal concurrency requires a combination of cleverness
and experience from the programmer

 The three fundamental ways of improving the performance of the

application using concurrency:
1. Reduce latency: A unit of work is executed in shorter time by
subdivision into parts that can be executed concurrently
2. Hide latency:

 Multiple long-running tasks are executed together by the

underlying system

 Effective when the tasks are blocked because of external

resources they must wait upon, such as disk or network I/O
operations

3. Increase throughput
1. By executing multiple tasks concurrently, the
general system throughput can be increased
2. Also speeds up independent sequential tasks that have
not been specifically designed for concurrency yet.

2. Data Distribution

 Another challenge in parallel programming is the distribution of a problem’s

data

 Most conventional parallel computers have a notion of data locality

o Implies that some data will be stored in memory that is
“closer” to a particular processor and can therefore be
accessed much more quickly
o Data locality may occur
 due to each processor having its own distinct local
memory—as in a distributed memory machine
 due to processor-specific caches as in a shared memory system.
  Due to the impact of data locality, a parallel programmer must pay
attention to where data is stored in relation to the processors that will be
accessing it
 The more local the values are, the quicker the processor will be able to
access them and complete its work
 It should be evident that distributing work and distributing data are
tightly coupled, and that an optimal design will consider both aspects
together
3. Inter-process Communication
 Inter-process communication (IPC) is a set of programming interfaces
that allow a programmer to coordinate activities among different
program processes that can run concurrently in an operating system.
o Allows a program to handle many user requests at the same time
 Factors to Consider
o Cost of communications
 Inter-processor communication virtually always implies
overhead.
 Machine cycles and resources that could be used for
computation are instead used to package and transmit
data.
o Latency vs. Bandwidth
 Latency is the time it takes to send a minimal (0
byte) message from point A to point B. Commonly
expressed as microseconds.
 Bandwidth is the amount of data that can be
communicated per unit of time. Commonly expressed
as megabytes/sec or gigabytes/sec.
 Sending many small messages can cause latency
to dominate communication overheads.
o More efficient to package small messages into a larger message,
thus increasing the effective communications
[Link] of communications
 With the Message Passing Model, communications are
explicit and generally quite visible and under the control
of the programmer.
 With the Data Parallel Model, communications often
occur transparently to the programmer, particularly on
distributed memory architectures. The programmer may
not even be able to know exactly how inter-task
communications are being accomplished
 o Synchronous vs. asynchronous communications
 Synchronous communications are often referred to as
blocking communications since other work must wait
until the communications have completed
 Asynchronous communications are often referred to as
non- blocking communications since other work can be
done while the communications are taking place

 Interleaving computation with communication is the

single greatest benefit for using asynchronous
communications.

o Scope of communications
 Knowing which tasks must communicate with each other
is critical during the design stage of a parallel code.

o Efficiency of communications
4. Load Balancing

 Load balancing refers to the practice of distributing

approximately equal amounts of work among tasks so that all
tasks are kept busy all of the time.

 Load balancing is important to parallel programs for performance reasons.

 Steps for achieving

o Equally partition the work each task receives
 For array/matrix operations where each task
performs similar work, evenly distribute the data
set among the tasks.

 For loop iterations where the work done in each

iteration is similar, evenly distribute the iterations
across the tasks.
 If a heterogeneous mix of machines with varying
performance characteristics is being used, be
sure to use some type of performance analysis tool
to detect any load imbalances. Adjust work accordingly

 Use dynamic work assignment

o Certain classes of problems result in load imbalances even if
data is evenly distributed among tasks:
 Sparse arrays - some tasks will have actual data to
work on while others have mostly "zeros"

 Adaptive grid methods - some tasks may need to

 refine their mesh while others don't
 N-body simulations - where some particles may
migrate to/from their original task domain to another
task's; where the particles owned by some tasks
require more work than those owned by other tasks
o When the amount of work each task will perform is
intentionally variable, or is unable to be predicted, it may be
helpful to use a scheduler - task pool approach. As each
task finishes its work, it queues to get a new piece of work
o It may become necessary to design an algorithm which
detects and handles load imbalances as they occur
dynamically within the code
5. Implementation and Debugging
 Programmers often implement parallel algorithms by creating a single
executable that will execute on each processor
 The program is designed to perform different computations and
communications based on the processor’s unique ID to ensure that the
work is divided between instances of the executable.
o Referred to as the Single Program, Multiple Data (SPMD) model
 Attractiveness stems from the fact that only one
program must be written
o Alternative is to use the Multiple Program, Multiple Data (MPMD)
model
 Several cooperating programs are created for
execution on the processor set
o In either case, the executables must be written to cooperatively
perform the computation while managing data locality and
communication
o They must also maintain a reasonably balanced load across
the processor set
o It should be clear that implementing such a program will
inherently require greater programmer effort than writing the
equivalent sequential program

6. Speed up Challenge

 To get good speed-up on a multiprocessor while keeping the

problem size fixed is harder than getting good speed-up by
increasing the problem size
 Strong Scaling means measuring speed-up while keeping the
problem size fixed
 Weak Scaling means that the program size grows
proportionally to the increase in the number of processors.
  Amdahl’s Law says

 Modified Amdahl’s Law in terms of speed-up versus the original

execution time:

 Assuming Execution time before = 1 and

Execution time affected = fraction of time