PARALLEL COMPUTING

Introduction
• Parallel computing is the use of parallel computer to reduce the
time needed to solve a single computational problem.
• A parallel computer is a multiple-processor computer system
supporting parallel programming.
• Two important categories of parallel computers are multi-
computers and centralized multiprocessors.
– A multicomputer is a parallel computers constricted out of multiple
computers and an interconnected network. The processors on different
computers interact by passing message to each other
– A centralized multiprocessor (SMP) is more highly integrated system in
which all the CPUs share access to a single memory. This shared memory
supports communication and synchronization among processors.
• Parallel computing is now used to solve problems in areas as
diverse as galactic evolution, climate modeling, aircraft design etc.
 Continue…
• Parallel programming is programming in a language that
allows you to explicitly indicate how different portions of the
computation may be executed concurrently by different
processors.
What is exactly Parallel Computing
• Parallel computing is a form of computation in
which many instructions are carried out
simultaneously operating on the principle that
large problems can often be divided into
smaller ones, which are then solved
concurrently (in parallel).
 Why it is required
• With the increased use of computers in every
sphere of human activity, computer scientists
are faced with two crucial issues today.
– Processing has to be done faster like never
before
– Larger or complex computation problems need to
be solved
 Continue…
• Increasing the number of transistors as per
Moore’s Law isn’t a solution, as it also
increases the frequency scaling and power
consumption.
• Power consumption has been a major issue
recently, as it causes a problem of processor
heating.
• The perfect solution is PARALLELISM
• In hardware as well as software
 Parallel and distributed computing

• The terms "concurrent computing", "parallel computing", and

"distributed computing" have a lot of overlap, and no clear
distinction exists between them.
• The same system may be characterized both as "parallel" and
"distributed"; the processors in a typical distributed system
run concurrently in parallel.
• Parallel computing may be seen as a particular tightly coupled
form of distributed computing, and distributed computing
may be seen as a loosely coupled form of parallel computing.
 Continue…
• While the field of parallel algorithms has a different focus than the
field of distributed algorithms, there is a lot of interaction between
the two fields. For example, the Cole–Vishkin algorithm for graph
colouring was originally presented as a parallel algorithm, but the
same technique can also be used directly as a distributed algorithm.
• Moreover, a parallel algorithm can be implemented either in a
parallel system (using shared memory) or in a distributed system
(using message passing).
• The traditional boundary between parallel and distributed
algorithms (choose a suitable network vs. run in any given
network) does not lie in the same place as the boundary between
parallel and distributed systems (shared memory vs. message
passing).
 Difference with Distributed
Computing
• When different processors/computers work on a
single common goal, it is parallel computing.
Ten men pulling a rope to lift up one rock, supercomputers
implement parallel computing.
• Distributed computing is where several different
computers work separately on a multi-faced
computing workload.
– [Link] men pulling ten ropes to lift ten different
rocks, employees working in an office doing their
own work.
work
 ‘Qs’ Difference between Distributed
and Parallel system
• 1) Distributed Operating systemsare also referred to as Loosely Coupled
systems whereas parallel processing g systems are referred to as tightly
coupled systems.

2) A Loosely coupled system is one in which the processors do not share

memory and each processor has its own local memory whereas in a tightly
coupled system there is a single system with primary memory shared by
all the processors.

3) The processors of distributed operating systems can be placed far away

from each other to cover a wider geographic area which is not the case
with parallel processing systems.
 Continue…
• 4) The no. of processors that can be usefully deployed is
very small in a parallel processing operating system
whereas for a distributed operating system a larger no. of
processors can be usefully deployed.......

5) global clock is used for controlling SIMD n MIMD in

parallel..... .in distributed no global clock present
6) in the distributed operating system there is an
unpredictable communication delays between processors
whereas the processors in the parallel processing system
share over an interconnection network
 An Example
• Consider the computational problem of finding a coloring
of a given graph G. Different fields might take the following
approaches:
– Centralized algorithms:
• The graph G is encoded as a string, and the string is given as input to
a computer. The computer program finds a coloring of the graph,
encodes the coloring as a string, and outputs the result.
– Parallel algorithms

• Again, the graph G is encoded as a string. However, multiple

computers can access the same string in parallel. Each computer
might focus on one part of the graph and produce a coloring for that
part.

• The main focus is on high-performance computation that exploits

the processing power of multiple computers in parallel.
 Continue…
• Distributed algorithms:
– The graph G is the structure of the computer network.
There is one computer for each node of G and one
communication link for each edge of G. Initially, each
computer only knows about its immediate neighbors in
the graph G; the computers must exchange messages
with each other to discover more about the structure of
G. Each computer must produce its own colour as output.
– The main focus is on coordinating the operation of an
arbitrary distributed system.
Difference with Clustered Computing
• A computer cluster is a group of linked computers,
working together closely so that in many respects
they form a single computer.
– Eg., In an office of 50 employees, group of 15 doing some
work,25 some other, and remaining 10 something else.
– Similarly, in a network of 20 computers,16 working on a
common goal, whereas 4 on some other common goal.
• Cluster Computing is a specific case of parallel
computing.
 ‘Qs’Differences
Qs’Differences with Grid Computing
• Grid Computing makes use of computers
communicating over the Internet to work on a given
problem.
– When 3 persons, one of them from USA, another from
Japan and a third from Norway are working together
online on a common project.
– Websites like Wikipedia, Yahoo! Answers, YouTube, FlickR
or open source OS like Linux are examples of grid
computing.
• Again, it serves a SAN example of parallel
computing.
 The Concept of Pipeline
• In computing, a pipeline is a set of data processing
elements connected in series, so that the output of
one element is the input of the next one.

The elements of a pipeline are often executed in

parallel or in time-sliced fashion; in that case, some
amount of buffer storage is often inserted between
elements.
 Approach to Parallel Computing
Flynn’s Taxonomy
• The four classifications defined by Flynn are
based upon the number of concurrent
instruction (or control) and data streams
available in the architecture
– SISD(Single Instruction Single Data)
– SIMD(Single Instruction Multiple Data)
– MISD(Multiple Instruction Single Data)
– MIMD(Multiple Instruction Multiple Data)
 Continue…
• Single Instruction, Single Data stream (SISD):
– A sequential computer which exploits no parallelism in either the instruction
or data streams. Single control unit (CU) fetches single Instruction Stream (IS)
from memory. The CU then generates appropriate control signals to direct
single processing element (PE) to operate on single Data Stream (DS) i.e. one
operation at a time
• Single Instruction, Multiple Data streams (SIMD):
– A computer which exploits multiple data streams against a single
instruction stream to perform operations which may be naturally
parallelized. For example, an array processor.
 SISD

Instructions
Processing Main memory
element (PE) (M)
Data

IS
IS DS
Control Unit PE Memory

A processing elements is capable to process a instruction passed by another entity, where a memory can be used to hold computational values. The first figure
demonstrate the interaction between a processing element and its memory module.

A single instruction, single data architecture is represented in the second figure. The Control Unit will provide a instruction to the processing element and the
memory module will serve as mention above. Another function here of the memory module is that its capable store information provided by the processing
element and provide a instruction to the Control Unit
19
SIMD
Applications:
• Image processing
• Matrix manipulations
• Sorting

20
 xtra
This architecture is capable to run with a boost of speedup compared to a sequential architectures. Since all processors are running at the same
time, there a existence of certain processors waiting for others processors to finish running a specific instructions. The following example shows
the same instruction running on two different processors.
----------------- | -----------------
PROCESSOR 1 | PROCESSOR 2
----------------- |-----------------
INST 1 |INST 1
INST 2 |INST 2
IF (A > B) |IF (A > B) //this processor will not validate this condition and will jump to INST 4
INST 3 | INST 3
INST 4 |INST 4
When processor 1 validates the condition instruction, it will have to do more computation compared to processor 2 which jumps to INST 4 since
the condition is false.

•The SIMD model of parallel computing consists of two parts:

•a front-end computer of the usual von Neumann style,
•and a processor array.
•The processor array is a set of identical synchronized processing elements capable of simultaneously performing the same operation on
different data.
•Each processor in the array has a small amount of local memory where the distributed data resides while it is being processed in parallel.

A program can be developed and executed on the front end using a traditional serial programming language.
The application program is executed by the front end in the usual serial way, but issues commands to the processor array to carry out SIMD
operations in parallel.
The similarity between serial and data parallel programming is one of the strong points of data parallelism.
Synchronization is made irrelevant by the lock–step synchronization of the processors: Processors either do nothing or exactly the same
operations at the same time.

Fine-grained architectures: each processor processes few data elements

Processor complexity
 Continue…
• Multiple Instruction, Single Data stream (MISD):
– Multiple instructions operate on a single data stream. Uncommon
architecture which is generally used for fault tolerance.
Heterogeneous systems operate on the same data stream and must
agree on the result. Examples include the Space Shuttle flight control
computer.
• Multiple Instruction, Multiple Data streams (MIMD)
– Multiple autonomous processors simultaneously
executing different instructions on different data.
Distributed systems are generally recognized to be MIMD
architectures; either exploiting a single shared memory
space or a distributed memory space. A multi-core
superscalar processor is an MIMD processor
MIMD

23
 Example
• Comparison with car assembly:
– SISD – one person is doing all the tasks one at the
time
– MISD – one worker continues the work of the
previous worker
– SIMD – several workers perform the same task
concurrently; after all the workers are finished,
another task is given to them
– MIMD – each worker constructs a car independently
following his own set of instructions
 Types Of Parallelism
• Bit-Level
• Instructional
• Data
• Task
 Bit-Level Parallelism
• When an 8-bit processor needs to add two 16-
bit integers, it’s to be done in two steps.
– The processor must first add the 8 lower order
bits from each integer using the standard
addition instruction,
– Then add the 8 higher-order bits using an add-
with-carry instruction and the carry bit from the
lower order addition
 Instruction Level Parallelism
• The instructions given to a computer for
processing can be divided into groups, or re-
ordered and then processed without
changing the final result.
• This is known as instruction-level parallelism.
i.e., ILP.
 Continue…

• An Example (ILP)
1. e = a + b
2. f = c + d
3. g = e * f
• Here, instruction 3 is dependent on
instruction 1 and 2 .
• However, instruction 1 and 2 can be
independently processed.
 Data Parallelism
• Data parallelism focuses on distributing the
data across different parallel computing
nodes.
• It is also called as loop-level parallelism
 An Illustration
• In a data parallel implementation, CPU A could
add all elements from the top half of the
matrices, while CPU B could add all elements
from the bottom half of the matrices.
• Since the two processors work in parallel, the
job of performing matrix addition would take
one half the time of performing the same
operation in serial using one CPU alone.
 Task Parallelism (Imp.)
• Task Parallelism focuses on distribution of
tasks across different processors.
• It is also known as functional parallelism or
control parallelism
– As a simple example, if we are running code on a 2-
processor system (CPUs "a“ & "b") in a parallel
environment and we wish to do tasks "A" and "B" , it is
possible to tell CPU "a" to do task "A" and CPU "b“ to do
task 'B" simultaneously, thereby reducing the runtime of
the execution.
 Key Difference Between Data And
Task Parallelism
Data Parallelism Task Parallelism
It is the division of threads(processes) or It is the divisions among
instructions or tasks internally into sub- threads(processes) or instructions or tasks
parts for execution. themselves for execution.

A task ‘A’ is divided into sub- A task ‘A’ and task ‘B’ are
parts and then processed. processed separately by
different processors.