What is Parallel System ?

Parallel systems improve processing and I/O speeds by using multiple CPUs and disks in parallel. Many operations are executed simultaneously.
There are two types of parallel machines :

1. A Coarse-grain Parallel Machine : Which consists of a small number of powerful processors.
2. A Massively Parallel or Fine-grain Machine : Which uses thousands of smaller processors.

Massively parallel computers are distinguished from the coarse-grain parallel machines by the degree of parallelism that they support.
Most high-end machines today offer some degree of course-grain parallelism. Two or four processor machines are common. Parallel computers with hundreds of CPUS are also available.

There are two main measures of performance of the database system.

1. Throughput : The number of tasks/queries executed per unit amount of time leads to throughput. According to parallel system design point of view, throughput is always high.
2. Response Time : Amount of time it takes to complete a single task from the time when it is submitted. This time should be minimal and its achievable if one uses parallel systems.

A system that processes large number of small transactions can improve throughput 11 processing many transactions in parallel.

A system that processes large transactions can improve response time as well as throupr t by performing subtasks of each transaction in parallel.

The two important issues in studying the parallelism are :

1. Speed-up
2. Scale-up.

1. Speed-up

speed-up refers to handling large number of tasks by increasing the degree of parallelism.

consider a database application running on a parallel system with certain number of processors and disks.

Suppose that we increase the size of the system by increasing the number of processors, disks and other components of the system.

Let the execution time of a task on the large machine is TL and that the execution time of the same task on the smaller machine is Ts.

The speed-up due to parallelism is defined as Ts/TL.

The parallel system demonstrate linear speed-up if the speed-up is N when the larger system has N times the resources of smaller system.

If the speed-up is less than N, system is said to demonstrate sublinear speed-up.

2. Scale-up

The scale-up refers to handling larger tasks by increasing the degree of parallelism. Let Q be a task and let QN be a task that is N times larger than Q.

Suppose that execution time of Q on a given machine Ms is Ts and the execution time of task QN on a parallel machine ML which is N times larger than Ms is TL.

The scale-up is defined as Ts/TL.
If Parallel system demonstrate-linear scale-up on task Q if TL = Ts.
If TL > Ts, the system is said to demonstrate sublinear scale-up.
Fig. 9.8 illustrates the linear and sublinear scale-up.

There are two kinds of scale-up depending on how the size of the task is measured.

1. Batch Scale-up
2. Transaction Scale-up.

Scale-up is a more important metric for measuring the efficiency of parallel database system. Following are the factors which work against efficient parallel operation and diminish both speed-up and scale-up.

1. Startup Costs : There is a start-up cost associated with initiating a single process. In parallel operation consisting of thousands of processes, the start-up time may overshadow the actual processing time, affecting speed-up adversely.
2. Interference : Since processes executing in a parallel system often access shared resources, a slowdown may result from the interference of each new process, as it competes with existing processes for commonly held resources such as a system bus or shared disks or locks. Both speed-up and scale-up are affected by this phenomenon.
3. Skew : By breaking down a single task into a number of parallel steps, we can reduce the size of the average step. The service time for the single slowest step will determine the service time for the task as a whole. It is difficult to divide a task into exactly equal sized parts and the way that the sizes are distributed is therefore skewed.

For example : If the task size is 100 and it is divided into 10 parts. If the division is skewed there may be some tasks of size less than 10 and some tasks of size more than 10. If ever one task happens to be of size 20, the speed-up obtained by running tasks in parallel is only five, instead of ten.

Interconnection Network :

Parallel system consists of components (processors, memory and disks) that a communicate with each other via a connection network.

Interconnection network include:

BUS : All the system components can send data on and receive data from a single communication bus. The bus could be an Ethernet or parallel interconnect.

Bus architectures work well for small number of processors, since it can handle communication from only one component at a time.

Mesh : The components are arranged in a grid and each component is connected to all its
adjacent nodes.

In a two-dimensional mesh, each node is connected to four adjacent nodes. In a three-dimensional mesh each node is connected to six adjacent nodes.

Nodes that are not directly connected can communicate with one another by routing messages via a sequence of intermediate nodes that are directly connected to one another.

The number of communication links as the number of components grows and the communication capacity of mesh therefore scales better with increasing parallelism.

Hypercube : The components are numbered in binary and a component is connected to another, if the binary representations of their numbers differ exactly by one bit.

This each of the n components is connected to log (n) of other components.

In a hypercube interconnection, a message from a component can reach any other component by going via. at most log (n) links (in mesh it is  √n -1 links).
Thus communication delays in hypercube interconnection network are significantly lower than in a mesh.

Read More About Parallel Database Architectures : Go Here