Parallel and Distributed

Computing
Engr. Agha Shiraz A. Khan
 Text Books
[1] M Sasimumar, Dinesh Shikhere, ..”An
Introduction to Parallel Processing.”

[2] Annanth Grama, Anshul Gupta, Vipin

kumar,,,” Introduction to Parallel
Computing”.
If one man can carry 20 bricks in 20
minutes, how much would it take for 5 men
to carry 20 bricks?
Can you read two books simultaneously?

Simultaneous
Concurrent
Parallel
 Basic Terms (Review of old
concepts)

Process
Thread
Task
Multiprocess(ing)
Multithread(ing)
Multitask(ing)
 Overview
What is Parallel Computing?
• Traditionally, software has been written for serial
computation:
• To be run on a single computer having a single
Central Processing Unit (CPU);
• A problem is broken into a discrete series of
instructions.
• Instructions are executed one after another.
• Only one instruction may execute at any moment in
time.
• In the simplest sense, parallel computing is the
simultaneous use of multiple compute resources … to
solve a single computational problem:
• To be run using multiple CPUs
• A problem is broken into discrete parts that can be
solved concurrently
• Each part is further broken down to a series of
instructions
• Instructions from each part execute simultaneously on
different CPUs
 Dictionary Meaning
• par·al·lel pro·cess·ing
/ˈperəˌlel ˈpräˌsesiNG/
noun
noun: parallel processing

a mode of computer operation in which a

process is split into parts that execute
simultaneously on different processors
attached to the same computer.
• he compute resources might be:
• A single computer with multiple processors;
• An arbitrary number of computers connected by a
network;
• A combination of both.
• The computational problem should be able to:
• Be broken apart into discrete pieces of work that can
be solved simultaneously;
• Execute multiple program instructions at any moment
in time;
• Be solved in less time with multiple compute
resources than with a single compute resource.
 The Universe is Parallel:
Parallel computing is an evolution of serial
computing that attempts to emulate what
has always been the state of affairs in the
natural world: many complex, interrelated
events happening at the same time, yet
within a temporal sequence. For example:
The Real World is Massively Parallel
 Uses for Parallel Computing:
• Science and Engineering:
• Historically, parallel computing has been
considered to be "the high end of computing",
and has been used to model difficult problems
in many areas of science and engineering:
• Atmosphere, Earth, Environment
• Physics - applied, nuclear, particle, condensed
matter, high pressure, fusion, photonics
• Bioscience, Biotechnology, Genetics
• Chemistry, Molecular Sciences
• Geology, Seismology
• Mechanical Engineering - from prosthetics to
spacecraft
• Electrical Engineering, Circuit Design,
Microelectronics
• Computer Science, Mathematics
• Industrial and Commercial:
• Today, commercial applications provide an
equal or greater driving force in the
development of faster computers. These
applications require the processing of large
amounts of data in sophisticated ways. For
example:
• Databases, data mining
• Oil exploration
• Web search engines, web based business services
• Medical imaging and diagnosis
• Pharmaceutical design
• Financial and economic modeling
• Management of national and multi-national
corporations
• Advanced graphics and virtual reality, particularly
in the entertainment industry
• Networked video and multi-media technologies
• Collaborative work environments
Why Use Parallel Computing?

• Main Reasons:
• Save time and/or money: In theory, throwing
more resources at a task will shorten its time
to completion, with potential cost savings.
Parallel computers can be built from cheap,
commodity components.
• Eg: Clusters and grids
• Solve larger problems: Many problems are
so large and/or complex that it is impractical
or impossible to solve them on a single
computer, especially given limited computer
memory. For example:
• "Grand Challenge" (
en.wikipedia.org/wiki/Grand_Challenge) problems
requiring PetaFLOPS and PetaBytes of computing
resources.
• Web search engines/databases processing
millions of transactions per second
• Provide concurrency: A single compute
resource can only do one thing at a time.
Multiple computing resources can be doing
many things simultaneously. For example, the
Access Grid (www.accessgrid.org) provides a
global collaboration network where people
from around the world can meet and conduct
work "virtually".
• Use of non-local resources: Using compute
resources on a wide area network, or even
the Internet when local compute resources
are scarce. For example:
• SETI@home (setiathome.berkeley.edu) over 1.3
million users, 3.2 million computers in nearly every
country in the world. Source:
www.boincsynergy.com/stats/ (July, 2012).
• Folding@home (folding.stanford.edu) uses over
450,000 cpus globally (July 2011)
• Limits to serial computing: Both physical and practical
reasons pose significant constraints to simply building ever
faster serial computers:
• Transmission speeds - the speed of a serial computer is
directly dependent upon how fast data can move through
hardware. Absolute limits are the speed of light (30
cm/nanosecond) and the transmission limit of copper wire (9
cm/nanosecond). Increasing speeds necessitate increasing
proximity of processing elements.
• Limits to miniaturization - processor technology is allowing
an increasing number of transistors to be placed on a chip.
However, even with molecular or atomic-level components, a
limit will be reached on how small components can be.
• Moore’s Law:
• Moore's law refers to an observation
made by Intel co-founder
Gordon Moore in 1965.
• He noticed that the number of transistors
per square inch on integrated circuits had
doubled every year since their
invention. Moore's law predicts that this
trend will continue into the foreseeable
future
• Economic limitations - it is increasingly expensive
to make a single processor faster. Using a larger
number of moderately fast commodity processors
to achieve the same (or better) performance is less
expensive.
• Current computer architectures are increasingly
relying upon hardware level parallelism to improve
performance:
• Multiple execution units
• Pipelined instructions
• Multi-core
• GPUs
 Who is using Parallel
Computing and where?
• Top500.org provides statistics on parallel computing - the
charts below are just a sampling.
 The Earth’s Simulator
What 35.86 teraflops looked like in 2002.

In 2002, the fastest supercomputer in the world (i.e. “NEC Earth Simulator) was capable
of 35.86 teraflops.
What 50 teraflops looks
like today.
• Part List:
2 — AMD Radeon Vega Frontier Edition
16GB GPU $2,000
1 — G.SKILL 32GB (2 x 16GB) DDR4 Memory $200.99
1 — Crucial 525GB SATA III 3-D SSD $159.99
1 — EVGA Plus 1000W Gold Power Supply $119.99
1 —MSI X370 AM4 AMD Motherboard $129.99
1 —AMD RYZEN 7 1700 8-Core 3.0 GHz (3.7
GHz Turbo)Processor $314.99
1 — TOSHIBA 5TB 7200 RPM SATA Hard Drive $146.99
1 — Rosewill ATX Mid Tower Case $49
 The Future
• During the past 20+ years, the trends indicated by ever
faster networks, distributed systems, and multi-processor
computer architectures (even at the desktop level)
clearly show that parallelism is the future of
computing.
• In this same time period, there has been a greater than
1000x increase in supercomputer performance, with no
end currently in sight.
• The race is already on for Exascale Computing!
 Assignment # 1.
1. Write down any one of the Grand Challenge Problems which is
your favorite.
2. Go through the top500.org website and list down top ten
supercomputers in the world. Write down their performance speed,
application, number of cores, performance measurement etc.
3. Go through BIONC platform and describe some of its applications.
Also install BIONC platform on your computer and register to
SETI@home project.

4. Presentation Topics:
5. Quantum Computing
6. DNA Computing
7. Moor’s Law
 Part 2
• Physical Organization of Parallel
Computers
von Neumann Architecture
• Also known as "stored-program
computer" - both program instructions
and data are kept in electronic memory.
• Differs from earlier computers which were
programmed through "hard wiring".
• Since then, virtually all computers have
followed this basic design:

• Comprised of four main components:

• Memory
• Control Unit
• Arithmetic Logic Unit
• Input/Output
• Read/write, random access memory is
used to store both program instructions
and data
• Program instructions are coded data which
tell the computer to do something
• Data is simply information to be used by the
program
• Control unit fetches instructions/data from
memory, decodes the instructions and
then sequentially coordinates operations
to accomplish the programmed task.
• Arithmetic Unit performs basic arithmetic
operations
• Input/Output is the interface to the human
operator
Instruction Cycle
 Flynn’s Classical Taxonomy
• Flynn's taxonomy distinguishes multi-
processor computer architectures
according to how they can be classified
along the two independent dimensions of
Instruction Stream and Data Stream.
• Each of these dimensions can have only
one of two possible states: Single or
Multiple.
• SISD – Single Instruction, Single Data
• SIMD – Single Instruction, Multiple Data
• MISD – Multiple Instruction, Single Data
• MIMD – Multiple Instruction, Multiple Data
Flynn’s Classical Taxonomy:
SISD
• Serial
• Only one instruction
and data stream is
acted on during any
one clock cycle
Flynn’s Classical Taxonomy:
SIMD
• All processing units
execute the same
instruction at any
given clock cycle.
• Each processing unit
operates on a
different data
element.
 Flynn’s Classical Taxonomy:
MISD
• Different instructions operated on a single
data element.
• Very few practical uses for this type of
classification.
• Example: Multiple cryptography algorithms
attempting to crack a single coded
message.
Flynn’s Classical Taxonomy:
MIMD
• Can execute different
instructions on
different data
elements.
• Most common type of
parallel computer.
 Parallel Computer Memory
Architectures:
Shared Memory Architecture
• All processors access
all memory as a
single global address
space.
• Data sharing is fast.
• Lack of scalability
between memory and
CPUs
 Parallel Computer Memory
Architectures:
Distributed Memory
• Each processor has
its own memory.
• Is scalable, no
overhead for cache
coherency.
• Programmer is
responsible for many
details of
communication
between processors.