CS Elect 3

Parallel and Distributed Computing

COURSE CONTENTS

• Introduction to Parallel and Distributed Computing

• Flynn’s Taxonomy, Introduction to Multi-Threading
• parallel algorithms & architectures, parallel I/O
• programming models (data-parallel, task-parallel, process-centric,
shared/distributed memory)
• Introduction to Parallel Programming using OpenMP
• performance analysis and tuning, scalability and performance studies
• scheduling, load balancing, memory consistency model, memory hierarchies,
• Case Studies: From problem specification to a parallelized solution
• GPU architecture and programming, heterogeneity, Introduction to OpenCL
• power and energy consumption storage systems, and synchronization
• Message passing interface (MPI),
• concurrency control
• fault tolerance, interconnection topologies
• Asynchronous/synchronous computation/communication, concurrency control,
fault tolerance,
• Advanced topics in parallel and Distributed computing
INTRODUCTION TO PARALLEL AND
DISTRIBUTED COMPUTING
INTRODUCTION

The simultaneous growth in availability of big data and in the number of simultaneous
users on the Internet places particular pressure on the need to carry out computing tasks
“in parallel,” or simultaneously. Parallel and distributed computing occurs across many
different topic areas in computer science, including algorithms, computer architecture,
networks, operating systems, and software engineering. During the early 21st century
there was explosive growth in multiprocessor design and other strategies for complex
applications to run faster. Parallel and distributed computing builds on fundamental
systems concepts, such as concurrency, mutual exclusion, consistency in state/memory
manipulation, message-passing, and shared-memory models.

The main purpose of parallel computing is to perform computations faster than that can
be done with a single processor by using a number of processors concurrently. The need
for faster solutions and for solving larger size problems arises in a wide variety of
applications. These include fluid dynamics, weather predictions, modeling and
simulation of large systems, information processing and extraction, image processing,
artificial intelligence and automate manufacturing
 What is Parallel Computing?

Parallel Computer: A parallel Computer is simply a collection of processors,

typically of the same type, interconnected in a certain fashion to allow the
coordination of their activities and the exchange of data.
• It is the use of multiple processing elements simultaneously for solving any
problem. Problems are broken down into instructions and are solved
concurrently as each resource which has been applied to work is working
at the same time.
Parallel Computing resembles the study of designing algorithms such that the time
complexity is minimum. Thus the speed up factor is taken into consideration.

Speed up: Let C be a computational problem and let n is the input size.
Ts(n)= Time complexity of best sequential algorithm.
Tp(n)= Time complexity of the parallel algorithm with p processors. Then
speed up S(n,p)=Ts(n)/Tp(n)
Parallel Computing
A single job is concurrently executed by multiple processors for shorter time-to-
solution. The system might be
• A single workstation with a multi-core processor
• Each core executes parts of the job
• Data exchange through shared memory
• A cluster of computers connected by high speed network
• All cores in the cluster participates in execution
• Data exchange through message passing across network

Advantages of Parallel Computing over Serial Computing are as follows:

1. It saves time and money as many resources working together will reduce the
time and cut potential costs.
2. It can be impractical to solve larger problems on Serial Computing.
3. It can take advantage of non-local resources when the local resources are
finite.
4. Serial Computing ‘wastes’ the potential computing power, thus Parallel
Computing
makes better work of hardware.
Types of Parallelism:
1. Bit-level parallelism: It is the form of parallel computing which is based on the
increasing processor’s size. It reduces the number of instructions that the
system must execute in order to perform a task on large-sized data.
Example: Consider a scenario where an 8-bit processor must compute the sum of
two 16-bit integers. It must first sum up the 8 lower-order bits, then add the 8
higher-order bits, thus requiring two instructions to perform the operation. A 16-
bit processor can perform the operation with just one instruction.
2. Instruction-level parallelism: A processor can only address less than one
instruction for each clock cycle phase. These instructions can be re-ordered and
grouped which are later on executed concurrently without affecting the result of
the program. This is called instruction-level parallelism.

3. Task Parallelism: Task parallelism employs the decomposition of a task into

subtasks and then allocating each of the subtasks for execution. The processors
perform execution of sub tasks concurrently.
Why parallel computing?
• The whole real world runs in dynamic nature i.e. many things happen at a certain
time but at different places concurrently. This data is extensively huge to manage.
• Real world data needs more dynamic simulation and modeling, and for achieving the
same, parallel computing is the key.
• Parallel computing provides concurrency and saves time and money.
• Complex, large datasets, and their management can be organized only and only
using parallel computing’s approach.
• Ensures the effective utilization of the resources. The hardware is guaranteed to be
used effectively whereas in serial computation only some part of hardware was used
and the rest rendered idle.
• Also, it is impractical to implement real-time systems using serial computing.

Applications of Parallel Computing:

• Data bases and Data mining.
• Real time simulation of systems.
• Science and Engineering.
• Advanced graphics, augmented reality and virtual reality.
Limitations of Parallel Computing:
• It addresses such as communication and synchronization between multiple sub-tasks
and processes which is difficult to achieve.
• The algorithms must be managed in such a way that they can be handled in the
parallel mechanism.
• The algorithms or program must have low coupling and high cohesion. But it’s difficult
to create such programs.
• More technically skilled and expert programmers can code a parallelism based
program well.

Future of Parallel Computing: The computational graph has undergone a great

transition from serial computing to parallel computing. Tech giant such as Intel
has already taken a step towards parallel computing by employing multicore
processors. Parallel computation will revolutionize the way computers work in
the future, for the better good. With all the world connecting to each other
even more than before, Parallel Computing does a better role in helping us
stay that way. With faster networks, distributed systems, and multi-processor
computers, it becomes even more necessary.
Parallel System Are Ubiquitous Today
• Processors ranging from high end in servers to low power in mobiles systems
• CMP technology with multiple cores
• High end server processors Xeon and Opteron
• Quad-core or six-core processors
• Atom processors in netbooks
• Dual-core
• Processors in cell phones
• Dual-core
Parallel Computing Resources
• The compute resources can include
• A single computer with multiple processors
• A single computer with (multiple) processor(s)
and some specialized computer resources (GPU,
FPGA )
• An arbitrary number of computers connected by a
network
• A combination of both.
Parallel Computing what for? (1)
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 sequence.
• Planetary and galactic orbits
• Weather and ocean patterns
• Tectonic plate drift
• Automobile assembly line
• Daily operations within a business
• Building a shopping mall
Traditionally, parallel computing has been considered to be "the high end of computing"
and has been motivated by numerical simulations of complex systems and "Grand
Challenge Problems“ such as
• weather and climate
• chemical and nuclear reactions
• biological, human genome
• geological, seismic activity
• mechanical devices - from prosthetics to
spacecraft
• electronic circuits
• manufacturing processes
Parallel Computing what for? (3)
Today, commercial applications are providing 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. Example applications include
• parallel databases, data mining
• oil exploration
• web search engines, web based business services
• computer-aided diagnosis in medicine
• 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
• Ultimately, parallel computing is an attempt to maximize the infinite but
seemingly scarce commodity called time.
Why Parallel Computing?
Parallel computing is complex on any aspect! The primary reasons for using parallel
computing

• Save time - wall clock time

• Solve larger problems
• Provide concurrency (do multiple things at the same time)

Other reasons might include

• Taking advantage of non-local resources – using available compute resources on a wide
area network, or even the Internet when local compute resources are scarce.
• Cost savings - using multiple "cheap" computing resources instead of paying for time on a
supercomputer.
• Overcoming memory constraints - single computers have very finite memory resources.
For large problems, using the memories of multiple computers may overcome this
obstacle.
Limitations of Serial Computing
• 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.
• 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.

The future
• during the past 10 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.
• It will be multi-forms, mixing general purpose solutions (your PC) and very speciliazed
solutions as IBM Cells, ClearSpeed, GPGPU from Nvidia.
Distributed computing
• We have multiple autonomous computers which seems to the user as single
system. In distributed systems there is no shared memory and computers
communicate with each other through message passing. In distributed computing a
single task is divided among different computers
• Within the context where concurrency is not usually required for a single job.
• Peer-to-peer (P2P) computing systems
• Participants that make a portion of their resources directly available to other
network participants
• Example: Napster
• Mobile computing network
• Distributed transactions
A distributed system contains multiple nodes that are physically separate but linked
together using the network. All the nodes in this system communicate with each other
and handle processes in tandem.
A diagram to better explain the distributed
system is −

Types of Distributed Systems The nodes in the distributed systems can be arranged in
the form of client/server systems or peer to peer systems. Details about these are as
follows
Client/Server Systems In client server systems, the client requests a resource and the
server provides that resource. A server may serve multiple clients at the same time
while a client is in contact with only one server. Both the client and server usually
communicate via a computer network and so they are a part of distributed systems.
Peer to Peer Systems
The peer to peer systems contains nodes that are equal participants in data sharing. All
the tasks are equally divided between all the nodes. The nodes interact with each
other as required as share resources. This is done with the help of a network.

Advantages of Distributed Systems Some advantages of Distributed Systems are as

follows −
• All the nodes in the distributed system are connected to each other. So nodes
can easily share data with other nodes.
• More nodes can easily be added to the distributed system i.e. it can be scaled as
required.
• Failure of one node does not lead to the failure of the entire distributed system.
Other nodes can still communicate with each other.
• Resources like printers can be shared with multiple nodes rather than being
restricted to just one.
Disadvantages of Distributed Systems Some disadvantages of Distributed Systems are as
follows −
• It is difficult to provide adequate security in distributed systems because the nodes
as well as the connections need to be secured.
• Some messages and data can be lost in the network while moving from one node to
another.
• The database connected to the distributed systems is quite complicated and difficult
to handle as compared to a single user system.
• Overloading may occur in the network if all the nodes of the distributed system try
to send data at once.
DISTRIBUTED COMPUTING MODELS
There are certain technologies working behind the cloud computing platforms
making cloud computing flexible, reliable, and usable. These technologies are listed
below:
• Virtualization
• Service-Oriented Architecture (SOA)
• Grid Computing
• Utility Computing
Virtualization
Virtualization is a technique, which allows to share single physical instance of an
application or resource among multiple organizations or tenants (customers). It does this
by assigning a logical name to a physical resource and providing a pointer to that physical
resource when demanded.

The Multitenant architecture offers virtual isolation among the multiple tenants. Hence,
the organizations can use and customize their application as though they each have their
instances running.
Service-Oriented Architecture (SOA)
Service-Oriented Architecture helps to use applications as a service for other applications
regardless the type of vendor, product or technology. Therefore, it is possible to exchange
the data between applications of different vendors without additional programming or
making changes to services. The cloud computing service oriented architecture is shown in
the diagram below

Grid Computing
Grid Computing refers to distributed
computing, in which a group of
computers from multiple locations are
connected with each other to achieve
a common objective. These computer
resources are heterogeneous and
geographically dispersed. Grid
Computing breaks complex task into
smaller pieces, which are distributed
to CPUs that reside within the grid.
Utility Computing
Utility computing is based on Pay-per-Use model. It offers computational resources on
demand as a metered service. Cloud computing, grid computing, and managed IT
services are based on the concept of utility computing.
DISTRIBUTED COMPUTING MODELS
In distributed architecture, components are presented on different platforms and
several components can cooperate with one another over a communication network in
order to achieve a specific objective or goal.
• In this architecture, information processing is not confined to a single machine rather
it is distributed over several independent computers.
• A distributed system can be demonstrated by the client-server architecture which
forms the base for multi-tier architectures; alternatives are the broker architecture such
as CORBA, and the Service-Oriented Architecture (SOA).
• There are several technology frameworks to support distributed architectures,
including .NET, J2EE, CORBA, .NET Web services, AXIS Java Web services, and Globus
Grid services.
• Middleware is an infrastructure that appropriately supports the development and
execution of distributed applications. It provides a buffer between the applications and
the network.
• It sits in the middle of system and manages or supports the different components of
a distributed system. Examples are transaction processing monitors, data convertors
and communication controllers etc
Difference between Parallel Computing and Distributed Computing:
Parallel vs. Distributed System Within the context of concurrent computing of a single job,
which takes a long time or is infeasible on one processor
• strongly-coupled example: multiprocessor systems
• Multiple processors, each with its own cache
• Data exchange through shared memory among processors
• Single operating system
• loose-coupled example: Google data center
• Multiple, independent workstations
• Connected by networks

Von Neumann Architecture

• For over 40 years, virtually all computers have followed a common machine model
known as the von Neumann computer. Named after the Hungarian mathematician
John von Neumann.
• A von Neumann computer uses the stored-program concept. The CPU executes a
stored program that specifies a sequence of read and write operations on the
memory.
Scope of Parallel Computing:
Parallel computing has made a tremendous impact on a variety of areas ranging
from computational simulations for scientific and engineering applications to
commercial applications in data mining and transaction processing. The cost benefits
of parallelism coupled with the performance requirements of applications present
compelling arguments in favor of parallel computing.
Sample of the diverse applications of parallel computing
1. Applications in Engineering and Design
• Parallel computing has traditionally been employed with great success in the
design of airfoils (optimizing lift, drag, stability), internal combustion engines
(optimizing charge distribution, burn), high-speed circuits (layouts for delays and
capacitive and inductive effects
• structures (optimizing structural integrity, design parameters, cost, etc.), among
others. More recently, design of microelectromechanical and
nanoelectromechanical systems (MEMS and NEMS) has attracted significant
attention
• Other applications in engineering and design focus on optimization of a variety of
processes. Parallel computers have been used to solve a variety of discrete and
continuous optimization problems. Algorithms such as Simplex, Interior Point
Method for linear optimization and Branch- and-bound, and Genetic programming
for discrete optimization have been efficiently parallelized and are frequently
used.
2. Scientific Applications
• Functional and structural characterization of genes and proteins hold the
promise of understanding and fundamentally influencing biological processes.
• Analyzing biological sequences with a view to developing new drugs and cures
for diseases and medical conditions requires innovative algorithms as well as
large-scale computational power.

• Advances in computational physics and chemistry have focused on understanding

processes ranging in scale from quantum phenomena to macromolecular
structures. These have resulted in design of new materials, understanding of
chemical pathways, and more efficient processes.
• Applications in astrophysics have explored the evolution of galaxies, thermonuclear
processes, and the analysis of extremely large datasets from telescopes. Weather
modeling, mineral prospecting, flood prediction, etc., rely heavily on parallel
computers and have very significant impact on day-to- day life.

• Bioinformatics and astrophysics also present some of the most challenging

problems with respect to analyzing extremely large datasets
3. Commercial Applications
• Parallel platforms ranging from multiprocessors to linux clusters are frequently
used as web and database servers.
• The availability of large-scale transaction data has also sparked considerable
interest in data mining and analysis for optimizing business and marketing
decisions.
• The sheer volume and geographically distributed nature of this data require
the use of effective parallel algorithms for such problems as association rule
mining, clustering, classification, and time-series analysis.
4. Applications in Computer Systems
• As computer systems become more pervasive and computation spreads over the
network, parallel processing issues become engrained into a variety of
applications.
• In computer security, intrusion detection is an outstanding challenge. In the case
of network intrusion detection, data is collected at distributed sites and must be
analyzed rapidly for signaling intrusion.
The infeasibility of collecting this data at a central location for analysis
requires effective parallel and distributed algorithms
Flynn's Classical Taxonomy
• There are different ways to classify parallel computers. One of the more widely
used classifications, in use since 1966, is called Flynn's Taxonomy.
• Flynn's taxonomy distinguishes multi-processor computer architectures according
to how they can be classified along the two independent dimensions of
Instruction and Data. Each of these dimensions can have only one of two possible
states Single or Multiple.

Flynn Matrix.
The matrix below defines the 4 possible classifications according to Flynn
1. Single Instruction, Single Data (SISD)
• A serial (non-parallel) computer
• Single instruction only one instruction stream is being acted on by the CPU during
any one clock cycle
• Single data only one data stream is being used as input during any one clock cycle
• Deterministic execution
• This is the oldest and until recently, the most prevalent form of computer
• Examples most PCs, single CPU workstations and mainframes
2. Single Instruction, Multiple Data (SIMD)
• A type of parallel computer
• Single instruction All processing units execute the same instruction at any
given clock cycle
• Multiple data Each processing unit can operate on a different data element
• This type of machine typically has an instruction dispatcher, a very high-
bandwidth internal network, and a very large array of very small-capacity
instruction units.
• Best suited for specialized problems characterized by a high degree of
regularity,such
as image processing.
• Synchronous (lockstep) and deterministic execution
• Two varieties Processor Arrays and Vector Pipelines
• Examples - Processor Arrays Connection Machine CM-2, Maspar
MP-1, MP-2 Vector Pipelines IBM 9000, Cray C90, Fujitsu VP,
NEC SX-2, Hitachi S820
3. Multiple Instruction, Single Data (MISD)
• A single data stream is fed into multiple processing units.
• Each processing unit operates on the data independently via independent instruction
streams.
• Few actual examples of this class of parallel computer have ever existed. One is the
experimental Carnegie-Mellon C.mmp computer (1971).
• Some conceivable uses might be
• multiple frequency filters operating on a single signal stream
• multiple cryptography algorithms attempting to crack a single coded message.

4. Multiple Instruction, Multiple Data (MIMD)

• Currently, the most common type of parallel computer. Most modern computers fall
into this category.
• Multiple Instruction every processor may be executing a different instruction stream
• Multiple Data every processor may be working with a different data stream
• Execution can be synchronous or asynchronous, deterministic or non-deterministic
• Examples most current supercomputers, networked parallel computer "grids" and
multi-processor SMP computers - including some types of PCs.