UNIT 3

CLOUD COMPUTING
Principle of Parallel and Distributed Computing
AGENDA

Principles of Parallel and Distributed Computing

Parallel v/s Distributed Computing
Elements of parallel Computing
Hardware architecture for parallel processing
Approaches to Parallel Programming
Laws Of Caution
• Cloud computing is a new technological trend that supports better
utilization of IT infrastructures, services, and applications.
• It adopts a service delivery model based on a pay-per-use approach, in
which users do not own infrastructure,platform,or applications but use
them for the time they need them.
• These IT assets are owned and maintained by service providers who
make them accessi- ble through the Internet.
INTRODUCTSCALABLE COMPUTING OVER THE
INTERNET
•Instead of using a centralized computer to solve
computational problems, a parallel and
distributed computing system uses multiple
computers to solve large-scale problems over
the Internet.
•Thus, distributed computing becomes data-
intensive and network-centric.
The Platform Evolution

• Computer technology has gone through five generations of development,

with each generation lasting from 10 to 20 years.
• Successive generations are overlapped in about 10 years. For instance, from
1950 to 1970, a handful of mainframes, including the IBM 360 and CDC
6400, were built to satisfy the demands of large businesses and government
organizations.
• From 1960 to 1980, lower-cost mini computers such as the DEC PDP 11
and VAX Series became popular among small businesses and on college
campuses.
• From 1970 to 1990, we saw widespread use of personal computers built
with VLSI microprocessors.
• From 1980 to 2000, massive numbers of portable computers
and pervasive devices appeared in both wired and wireless
applications.
• Since 1990, the use of both HPC and HTC systems hidden in
clusters, grids, or Internet clouds has proliferated. These
systems are employed by both consumers and high-end web-
scale computing and information services
Three New Computing Paradigms
• Centralized computing:
This is a computing paradigm by which all computer resources
are centralized in one physical system.
All resources (processors, memory, and storage) are fully
shared and tightly coupled within one integrated OS.
Many data centers and supercomputers are centralized
systems, but they are used in parallel, distributed, and cloud
computing applications
 Parallel computing
• In parallel computing, all processors are either tightly coupled with
centralized shared memory or loosely coupled with distributed
memory.
• Some authors refer to this discipline as parallel processing.
• Interprocessor communication is accomplished through shared
memory or via message passing.
• A computer system capable of parallel computing is commonly known
as a parallel computer .
• Programs running in a parallel computer are called parallel programs.
The process of writing parallel programs is often referred to as parallel
programming .
Distributed computing
• This is a field of computer science/engineering that studies distributed
systems.
• A distributed system consists of multiple autonomous computers,
each having its own private memory, communicating through a
computer network.
• Information exchange in a distributed system is accomplished
through message passing.
• A computer program that runs in a distributed system is known as a
distributed program. The process of writing distributed programs
is referred to as distributed programming.
Cloud computing

• An Internet cloud of resources can be either a centralized or a

distributed computing system.
• The cloud applies parallel or distributed computing, or both.
• Clouds can be built with physical or virtualized resources over
large data centers that are centralized or distributed.
• Some authors consider cloud computing to be a form of utility
computing or service computing.
Elements of parallel computing
• It is now clear that silicon-based processor chips are reaching their
physical limits.
• Processing speed is constrained by the speed of light, and the density
of transistors packaged in a processor is constrained by
thermodynamic limitations.
• A viable solution to overcome this limitation is to connect multiple
processors working in coordination with each other to solve “Grand
Challenge” problems.
• The first steps in this direction led to the development of parallel
computing, which encompasses techniques, architectures, and systems
for performing multiple activities in parallel
What is parallel processing?

•Processing of multiple tasks

simultaneously on multiple
processors is called parallel
processing.
• The parallel program consists of multiple active processes
(tasks) simultaneously solving a given problem.
• A given task is divided into multiple subtasks using a divide-
and-conquer technique, and each subtask is processed on a
different central processing unit (CPU).
• Programming on a multiprocessor system using the divide-
and-conquer technique is called parallel programming
• Many applications today require more computing power than a
traditional sequential computer can offer.
• Parallel processing provides a cost-effective solution to this problem
by increasing the number of CPUs in a computer and by adding an
efficient communication system between them.
• Many applications today require more computing power than a
traditional sequential computer can offer.
• Parallel processing provides a cost-effective solution to this problem
by increasing the number of CPUs in a computer and by adding an
efficient communication system between them
• The development of parallel processing is being influenced by many
factors. The prominent among them include the following:
• Computational requirements are ever increasing in
the areas of both scientific and business computing.
• The technical computing problems, which require
high-speed computational power, are related to life
sciences, aerospace, geographical information
systems, mechanical design and analysis, and the
like
• Sequential architectures are reaching physical
limitations as they are constrained by the speed of light
and thermodynamics laws.
• The speed at which sequential CPUs can operate is
reaching saturation point (no more vertical
growth), and hence an alternative way to get high
computational speed is to connect multiple CPUs
(opportunity for horizontal growth)
•The technology of parallel processing is mature
and can be exploited commercially; there is
already significant R&D work on
development tools and environments.
•Significant development in networking
technology is paving the way for heterogeneous
computing.
Hardware architectures for parallel
processing
• The core elements of parallel processing are CPUs. Based on the
number of instruction and data streams that can be processed
simultaneously, computing systems are classified into the following
four categories:
• Single-instruction, single-data (SISD) systems
• Single-instruction, multiple-data (SIMD) systems
• Multiple-instruction, single-data (MISD) systems
• Multiple-instruction, multiple-data (MIMD) systems
1.Single-instruction, single-data (SISD) systems
• An SISD computing system is a uniprocessor machine capable of executing
a single instruction, which operates on a single data stream.
• In SISD, machine instructions are processed sequentially; hence
computers adopting this model are popularly called sequential computers.
• Most conventional computers are built using the SISD model. All the
instructions and data to be processed have to be stored in primary
memory.
• The speed of the processing element in the SISD model is limited by the
rate at which the computer can transfer information internally. Dominant
representative SISD systems are IBM PC, Macintosh, and workstations.
2.Single-instruction, multiple-data (SIMD)
systems
• An SIMD computing system is a multiprocessor machine capable of
executing the same instruction on all the CPUs but operating on
different data streams .
• Machines based on an SIMD model are well suited to scientific
computing since they involve lots of vector and matrix operations.
• For instance, statements such as
can be passed to all the processing elements (PEs); organized data elements
of vectors A and B can be divided into multiple sets (N-sets for N PE
systems);
• Each PE can process one data set. Dominant representative SIMD systems
are Cray’s vector processing machine and Thinking Machines’ cm*
3. Multiple-instruction, single-data (MISD)
systems
• An MISD computing system is a multiprocessor machine capable of
executing different instructions on different PEs but all of them operating
on the same data set . For instance, statements such as

• perform different operations on the same data set. Machines built using
the MISD model are not useful in most of the applications;
• a few machines are built, but none of them are available commercially.
They became more of an intellectual exercise than a practical
configuration.
4.Multiple-instruction, multiple-data
(MIMD) systems
• An MIMD computing system is a multiprocessor machine capable of
executing multiple instructions on multiple data sets.
• Each PE in the MIMD model has separate instruction and data
streams; hence machines built using this model are well suited to
any kind of application.
• Unlike SIMD and MISD machines, PEs in MIMD machines work
asynchronously. MIMD machines are broadly categorized into shared-
memory MIMD and distributed-memory MIMD based on the way PEs
are coupled to the main memory.
• Shared memory MIMD machines In the shared memory MIMD model, all
the PEs are connected to a single global memory and they all have access
to it .
• Systems based on this model are also called tightly coupled multiprocessor
systems.
• The communication between PEs in this model takes place through the
shared memory;
• modification of the data stored in the global memory by one PE is visible to
all other PEs.
• Dominant representative shared memory MIMD systems are Silicon
Graphics machines and Sun/IBM’s SMP (Symmetric Multi-Processing)
Distributed memory MIMD machines

In the distributed memory MIMD model, all PEs have a local memory.
Systems based on this model are also called loosely coupled
multiprocessor systems.
• The communication between PEs in this model takes place through the
interconnection network (the interprocess communication channel, or
IPC).
• The network connecting PEs can be configured to tree, mesh, cube,
and so on. Each PE operates asynchronously, and if
communication/synchronization among tasks is necessary, they can do
so by exchanging messages between them
• The shared-memory MIMD architecture is easier to program but is
less tolerant to failures and harder to extend with respect to the
distributed memory MIMD model.
• Failures in a shared-memory MIMD affect the entire system, whereas
this is not the case of the distributed model, in which each of the PEs
can be easily isolated. Moreover, shared memory MIMD architectures
are less likely to scale because the addition of more PEs leads to
memory contention.
• This is a situation that does not happen in the case of distributed
memory, in which each PE has its own memory. As a result,
distributed memory MIMD architectures are most popular today
Approaches to parallel programming
• A sequential program is one that runs on a single processor and has a
single line of control.
• To make many processors collectively work on a single program, the
program must be divided into smaller independent chunks so that each
processor can work on separate chunks of the problem.
• The program decomposed in this way is a parallel program. A wide
variety of parallel programming approaches are available. The most
prominent among them are the following
•Data parallelism
• Process parallelism
• Farmer-and-worker model
Data Parallelism

•In the case of data parallelism, the divide-and-

conquer technique is used to split data into
multiple sets,
• and each data set is processed on different PEs
using the same instruction.
•This approach is highly suitable to processing on
machines based on the SIMD model
Process parallelism and Farmer worker model
• In the case of process parallelism, a given operation has multiple (but
distinct) activities that can be processed on multiple processors.
• In the case of the farmer and-worker model, a job distribution
approach is used: one processor is configured as master and all other
remaining PEs are designated as slaves;
• the master assigns jobs to slave PEs and, on completion, they inform
the master, which in turn collects results. These approaches can be
utilized in different levels of parallelism.
Levels of parallelism
• As shown in the table and depicted in Figure 2.7,
parallelism within an application can be detected at
several levels:
• Large grain (or task level)
• Medium grain (or control level)
• Fine grain (data level)
• Very fine grain (multiple-instruction issue)
LAWS OF CAUTION
• Now that we have introduced some general aspects of parallel
computing in terms of architectures and models, we can make some
considerations that have been drawn from experience designing and
implementing such systems.
• These considerations are guidelines that can help us understand how
much benefit an application or a software system can gain from
parallelism. In particular, what we need to keep in mind is that
parallelism is used to perform multiple activities together so that the
system can increase its throughput or its speed
•But the relations that control the increment
of speed are not linear. For example, for a
given n processors, the user expects speed
to be increased by n times.
• This is an ideal situation, but it rarely
happens because of the communication
overhead.
• Here are two important guidelines to take into account:
• Speed of computation is proportional to the square root of
system cost; they never increase linearly. Therefore, the
faster a system becomes, the more expensive it is to increase
its speed (Figure 2.8).
• Speed by a parallel computer increases as the logarithm of
the number of processors (i.e., y 5 k*log(N)). This concept is
shown in Figure 2.9
• The very fast development in parallel processing and related areas has
blurred conceptual boundaries, causing a lot of terminological
confusion.
• Even well-defined distinctions such as shared memory and distributed
memory are merging due to new advances in technology. There are no
strict delimiters for contributors to the area of parallel processing.
• Hence, computer architects, OS designers, language designers, and
computer network designers all have a role to play.