Parallel Processing

Definition: What does parallel processing mean?

Parallel processing is a method of simultaneously breaking up and running program tasks on
multiple microprocessors, thereby reducing processing time. Parallel processing may be
accomplished via a computer with two or more processors or via a computer network.
Parallel processing is also called parallel computing.
Parallel processing is particularly useful when running programs that perform complex
computations, and it provides a viable option to the quest for cheaper computing alternatives.
Supercomputers commonly have hundreds of thousands of microprocessors for this purpose.
Parallel processing should not be confused with concurrency, which refers to multiple tasks
that run simultaneously.

What is the Difference Between Serial and Parallel

Processing in Computer Architecture
The main difference between serial and parallel processing in computer architecture is that
serial processing performs a single task at a time while parallel processing performs
multiple tasks at a time.
Computer architecture defines the functionality, organization, and implementation of a
computer system. It explains how the computer system is designed and the technologies it is
compatible with. The processor is one of the most essential components in the computer
system. It executes instructions and completes the tasks assigned to it. There are two main types
of processing as serial and parallel processing.

Difference Between Serial and Parallel Processing in

Computer Architecture
Definition
Serial processing is a type of processing in which one task is completed at a time and all the
tasks are executed by the processor in a sequence. Parallel processing is a type of processing
in which multiple tasks are completed at a time by different processors. Thus, this is the
fundamental difference between Serial and Parallel Processing.

Number of processors
A major difference between serial and parallel processing is that there is a single processor in
serial processing, but there are multiple processors in parallel processing.
Performance
Therefore, the performance of parallel processing is higher than in serial processing.

Work Load
In serial processing, the workload of the processor is higher. However, in parallel processing,
the workload per processor is lower. Thus, this is an important difference between serial and
parallel processing.

Data transferring
Moreover, in serial processing, data transfers are in bit by bit format. However, in parallel
processing, data transfers are in byte form (8 bits).

Required time
Time taken is also a difference between serial and parallel processing. That is; serial processing
requires more time than parallel processing to complete a task.

Cost
Furthermore, parallel processing is more costly than serial processing as it uses multiple
processors.

Parallel Processing Systems are designed to speed up the execution of programs by dividing
the program into multiple fragments and processing these fragments simultaneously. Such
systems are multiprocessor systems also known as tightly coupled systems. Parallel systems
deal with the simultaneous use of multiple computer resources that can include a single
computer with multiple processors, a number of computers connected by a network to form a
parallel processing cluster or a combination of both.
Parallel computing is an evolution of serial computing where the jobs are broken into discrete
parts that can be executed concurrently. Each part is further broken down to a series of
instructions. Instructions from each part execute simultaneously on different CPUs.
Parallel systems are more difficult to program than computers with a single processor because
the architecture of parallel computers varies accordingly and the processes of multiple CPUs
must be coordinated and synchronized. Several models for connecting processors and memory
modules exist, and each topology requires a different programming model. The three models
that are most commonly used in building parallel computers include synchronous processors
each with its own memory, asynchronous processors each with its own memory and
asynchronous processors with a common, shared memory. Flynn has classified the computer
systems based on parallelism in the instructions and in the data streams. These are:
1. Single instruction stream, single data stream (SISD).
2. Single instruction stream, multiple data stream (SIMD).
3. Multiple instruction streams, single data stream (MISD).
4. Multiple instruction stream, multiple data stream (MIMD).
The above classification of parallel computing system is focused in terms of two independent
factors: the number of data streams that can be simultaneously processed, and the number of
instruction streams that can be simultaneously processed. Here 'instruction stream' we mean an
algorithm that instructs the computer what to do whereas 'data stream' (i.e. input to an
algorithm) we mean the data that are being operated upon.
Even though Flynn has classified the computer 'systems into four types based on parallelism
but only two of them are relevant to parallel computers. These are SIMD and MIMD
computers.

Flynn’s taxonomy
Parallel computing is a computing where the jobs are broken into discrete parts that can be
executed concurrently. Each part is further broken down into a series of instructions.
Instructions from each part execute simultaneously on different CPUs. Parallel systems deal
with the simultaneous use of multiple computer resources that can include a single computer
with multiple processors, a number of computers connected by a network to form a parallel
processing cluster, or a combination of [Link] systems are more difficult to program than
computers with a single processor because the architecture of parallel computers varies
accordingly and the processes of multiple CPUs must be coordinated and synchronized.
The crux of parallel processing is CPUs. Based on the number of instruction and data streams
that can be processed simultaneously, computing systems are classifies into four major
categories:
Flynn’s classification—
1. Single-instruction, single-data (SISD) systems—
An SISD computing system is a uniprocessor machine that is capable of executing a
single instruction and operating on a single data stream. In SISD, machine instructions
are processed in a sequential manner, and computers adopting this model are popularly
called sequential computers. Most conventional computers have SISD architecture. 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(dependent) by the
rate at which the computer can transfer information internally. Dominant representative
SISD systems are IBM PC, workstations.

2. Single-instruction, multiple-data (SIMD) systems –

A SIMD system is a multiprocessor machine capable of executing the same instruction +
5n 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. So that the information can be passed to all the processing elements (PEs)
organized data elements of vectors can be divided into multiple sets (N-sets for N PE
systems) and each PE can process one data set.

Dominant representative SIMD systems is Cray’s vector processing machine.

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 dataset .
 Example Z = sin(x)+cos(x)+tan(x)
The system performs different operations on the same data set. Machines built using the
MISD model are not useful in most of the application, a few machines are built, but
none of them are available commercially.
4. Multiple-instruction, multiple-data (MIMD) systems –
An MIMD system is la multiprocessor machine which is capable of executing multiple
instructions on multiple data sets. Each PE in the MIMD model has separate instruction
and data streams; therefore, machines built using this model are capable 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.
In the shared memory MIMD model (tightly coupled multiprocessor systems), all the PEs are
connected to a single global memory and they all have access to it. 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).
In Distributed memory MIMD machines (loosely coupled multiprocessor systems) all PEs
have a local memory. The communication between PEs in this model takes place through the
interconnection network (the inter process communication channel, or IPC). The network
connecting PEs can be configured to tree, mesh or in accordance with the requirement.
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 of practical outcomes and user’s requirement, distributed memory MIMD
architecture is superior to the other existing models.

APPLICATIONS OF PARALLEL PROCESSING

Parallel computing is an evolution of serial computing that attempts to emulate what has always been
the state of affairs in the natural world. In the natural world, it is quite common to find many complex,
interrelated events happening at the same time. Examples of concurrent processing in natural and
man-made environments include:
• Automobile assembly line
• Daily operations within a business
• Building a shopping mall
• Ordering an aloo tikki burger at the drive through.

Hence, 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 forecasting
• Predicting results of chemical and nuclear reactions
• DNA structures of various species
• Design of mechanical devices
• Design of electronic circuits
• Design of complex manufacturing processes
• Accessing of large databases
• Design of oil exploration systems
• Design of web search engines, web-based business services
• Design of computer-aided diagnosis in medicine • Development of MIS for national and multi-
national corporations
• Development of advanced graphics and virtual reality software, particularly for the entertainment
industry, including networked video and multi-media technologies
• Collaborative work (virtual) environments
concurrent access
The ability to gain admittance to a system or component by more than one user or
process. For example, concurrent access to a computer means multiple users are
interacting with the system simultaneously. Concurrent access to a hardware
component, such as a memory chip or memory bank, means that the circuits are
built with two or more input or signalling channels.

n Cache Memory in Computer Organization

Cache Memory is a special very high-speed memory. It is used to speed up and synchronizing
with high-speed CPU. Cache memory is costlier than main memory or disk memory but
economical than CPU registers. Cache memory is an extremely fast memory type that acts as
a buffer between RAM and the CPU. It holds frequently requested data and instructions so that
they are immediately available to the CPU when needed.
Cache memory is used to reduce the average time to access data from the Main memory. The
cache is a smaller and faster memory which stores copies of the data from frequently used main
memory locations. There are various different independent caches in a CPU, which store
instructions and data.

Levels of memory:
● Level 1 or Register –
It is a type of memory in which data is stored and accepted that are immediately stored
in CPU. Most commonly used register is accumulator, Program counter, address
register etc.
● Level 2 or Cache memory –
It is the fastest memory which has faster access time where data is temporarily stored
for faster access.
● Level 3 or Main Memory –
It is memory on which computer works currently. It is small in size and once power is
off data no longer stays in this memory.
● Level 4 or Secondary Memory –
It is external memory which is not as fast as main memory but data stays permanently
in this memory.
Cache Performance:
When the processor needs to read or write a location in main memory, it first checks for a
corresponding entry in the cache.
● If the processor finds that the memory location is in the cache, a cache hit has occurred
and data is read from cache
● If the processor does not find the memory location in the cache, a cache miss has
occurred. For a cache miss, the cache allocates a new entry and copies in data from main
memory, then the request is fulfilled from the contents of the cache.

The performance of cache memory is frequently measured in terms of a quantity called Hit
ratio.
Hit ratio = hit / (hit + miss) = no. of hits/total accesses
We can improve Cache performance using higher cache block size, higher associativity,
reduce miss rate, reduce miss penalty, and reduce Reduce the time to hit in the cache.
Application of Cache Memory –
1. Usually, the cache memory can store a reasonable number of blocks at any given time,
but this number is small compared to the total number of blocks in the main memory.
2. The correspondence between the main memory blocks and those in the cache is
specified by a mapping function.

Types of Cache –
● Primary Cache –
A primary cache is always located on the processor chip. This cache is small and its
access time is comparable to that of processor registers.
● Secondary Cache –
Secondary cache is placed between the primary cache and the rest of the memory. It is
referred to as the level 2 (L2) cache. Often, the Level 2 cache is also housed on the
processor chip.

Cache Coherence
In computer architecture, cache coherence is the uniformity of shared resource data that ends up
stored in multiple local caches. When clients in a system maintain caches of a common memory
resource, problems may arise with incoherent data, which is particularly the case with CPUs in a
multiprocessing system.

How Cache Memory works

Cache is term which is common heard today. With exponential advancement in field of faster processors
popping up every day, the usage of this terminology has increased rapidly. This has also been the most major
parameter in faster processing, but what is cache actually. Is it processing unit or memory? What is L1, L2 and
L3 cache? To understand this first we need to have insight about how CPU works or how it processes. So let us
take a look.
MEMORY ORGANIZATION

CPU – Central Processing Unit is just like brain of a computer; and performs the arithmetical, logical

operations of the system by carrying instructions on the code.

The memory organization of a system is shown below:

At the core is CPU, and then are cache, then RAM and then storage device.

But how do these work?

When an application starts or data is to be read/written or any operation is to be performed then the data

and commands associated with the specific operation are shifted from a slow moving storage device

(magnetic device – hard disk, optical device – CD drive etc.) to a faster device. This faster device is

RAM – Random Access Memory. This RAM is type of DRAM (Dynamic Random Access Memory).

RAM is placed here because it is a faster device, and whenever data/ commands/instructions are needed

by Processor, they provide them at a faster rate than slow storage devices. They serve as a cache memory

for the storage devices. Although they are much faster than slow storage device but the processor

processes at much a faster pace and they are not able to provide the needed data/instructions at that rate.

So, there is need of a device that is faster than RAM which could keep up with the speed of processor
needs. Therefore, the data required is transmitted to the next level of fast memory, which is known as

CACHE memory. CACHE is also a type of RAM, but it is Static RAM – SRAM. SRAM are faster and

costlier than DRAM because it has flip-flops (6 transistors) to store data unlike DRAM which uses 1

transistor and capacitor to store data in form of charge. Moreover, they need not be refreshed

periodically (because of bistable latching circuitry) unlike DRAM making it faster.

Part II
This memory is generally divided into different level. In the following figure we see the process flow:

Let us suppose that the system has cache of three levels (level means that overall cache memory is split

into different hardware segments which vary in their processing speed and memory). From RAM data

is transferred into cache of 3rd level (L3 cache). L3 cache is a segment of overall cache memory. L3

cache is faster than RAM but slower then L2 cache. To further fasten up the process cache of second

order L2 cache are used. They are located at immediate vicinity of processor. But in some of the modern

processors L2 cache is inbuilt making the process faster. It should be noted that it is not necessary that

a system has 3 levels of cache; it might have 1 or 2 level of cache. At the core level is cache of first
level that is L1 cache memory. The commonly used commands/instructions/data is stored in this

section of memory. This is built in the processor itself. Thus this is fastest of all the cache memory.

PROCESS FLOW

So whenever the processor needs to perform an action or execute any command then it first checks the

state of the data registers. If the required instruction/data is not present over there, then it looks in the

first level of cache memory – L1, and if there also data is not present it further goes to second and

further third level of cache memory. Whenever the data needed by processor is not found in the cache

it is known as CACHE MISS and it leads to delay in the execution thus making the system slow. If the

data is found in cache memory it is known as CACHE HIT.

If the data needed is not found in any of the cache memory, the processor checks in RAM. And if this

also fails then it goes to look onto the slower storage device.

So the above process can be graphically summarized as:

 Part III
CACHE CONTROLLER (Best part of all)

So we can say that cache is used to make the system fast by making the processing/execution fast. But

that is not the end of cache. The question arises that how does cache knows that piece of data or

commands/instructions are important and in near future processor might ask about it. The answer is

cache controller that is associated with cache. It implements the following 2 principles upon cache:

· First Case: Cache is used to hold the instructions/data which are very commonly used or computer

uses frequently.

· Second case: Cache is used to read the likely data; that is data which is to be most probably read in

near future.

Let us understand these by example.

Take the first case. Consider an example. You are studying a subject and solving numerical related to a

topic.

· Now to solve the 1st numerical you need a formula, so you open chapter 1 of the book and look at the

formula and then solve the numerical.

· Now you move on to next numerical. To solve 2nd numerical, you again need to access the chapter 1

and look at the formula.

· Suppose this goes on…

The better way will be to write th8e formula on a piece of paper and pin it on the desk. This will save

time and speed up the process. This is how cache controller works hence making the most probable data

to be present in cache even before the processor asks for it.

Let us consider the second case. This is just an illustration to understand the case. Let us say that a user

opens a folder which has 5 images named 1,2,3,4 and 5. Let us say a person opens 1 image.
Now the controller will judge the probability of user opening image 2 and hence will beforehand move

image 2 in cache, hence making a cache hit, making execution fast.

CONCLUSION

So, we can say that Cache memory is a high-speed random-access memory which is used by a system

Central processing unit for storing the data/instruction temporarily. It decreases the execution time by

storing the most frequent and most probable data and instructions “closer” to the processor, where the

systems CPU can quickly get it.