What is parallelism? What are the various conditions of parallelism?

What is parallelism? What are the various conditions of parallelism?

Answer:

When two process runs simultaneously within the CPU then this condition is known as parallelism.

If there is n parallel process (p 1,p 2,p 3,.............,p n-1,p n) then we can denote it as (p 1//p 2//p 3//....p n-1 //p n).

Conditions of parallelism:

1. Data Dependency Analysis.
2. Bernstein's Condition
3. Hardware parallelism
4. Software parallelism

1. Dependency Analysis :

•  By Analyzing dependency graph we can see the opportunity of parallelism.
•  If data is dependent than parallelism is not possible.

Example of dependent data: Suppose there are two process S1 & S2. If the input/output of S1 will be dependent on the input/output of S2 then S1 & S2 will be considered as dependent data.

S1:     A = B + C

S2:     D = A + E

• If data is indipendent than parallelism is possible.

There are 5 types of dependency:

1.1. Flow Dependency: If S2 follows S1 and there is at least one output of S1 feed as input to S2 then it is said to be flow dependency.

    Example:   S1: C = A + B

                      S2: D = C + E

1.2. Anti Dependency: ( Reverse of flow dependency) 

 If S2 follows S1 and there is at least one output of S2 feed as input to S1 then it is said to be Anti dependency.

    Example:   

                      S1:         D = C + E

                      S2:         C = A + B

1.3. Output Dependency: (two statement producing same output)

    Example:     S1: C = A + B

                         S2:  C = D + E

1.4 Input/Output Dependency: When the Same file is referred by both input and output statement.

1.5 Unknown Dependency: If the dependency relation can not be found through the above relations than it is known as Unknown Dependency.

2. Bernstein's Condition of Parallelism:

  If two processes P1 & P2 are not (flow-dependent, anti dependent and output dependent) then the process P1 and P2 are parallel.

3. Hardware parallelism: Achieving parallelism using hardware is known as hardware parallelism. It is defined by machine Architecture and hardware multiplicity.

4. Software parallelism: Achieving parallelism using the software is known as software parallelism. It is defined by the control and data dependency of the program and is revealed in the program flow graph.