October 5, 2023
October 5, 2023
October 5, 2023
###### Computer-Organization
October 5, 2023
 Question 498
A set of processors P1, P2, ……, Pk can execute in parallel if Bernstein’s conditions are satisfied on a pairwise basis; that is

P1 || P2 || P3 || ….. || Pk if and only if :

 A Pi || Pj for all i ≠ j B Pi || Pj for all i = j+1 C Pi || Pj for all i ≤ j D Pi || Pj for all i ≥ j
Question 498 Explanation:
Bernstein’s conditions for parallelism:
Define:
Ii as the input set of a process Pi
Oi as the output set of a process Pi
P1 and P2 can execute in parallel (denoted as P1 || P2) under the condition:
I1 ∩ O2 = 0
I2 ∩ O1 = 0
O1 ∩ O2 = 0
Note that I1 ∩ I2 <> 0 does not prevent parallelism.
Input set: also called read set or domain of a process
Output set: also called write set or range of a process
A set of processes can execute in parallel if Bernstein’s conditions are satisfied on a pairwise basis; that is, P1 || P2 || … || PK if and only if Pi || Pj for all i<>j
The parallelism relation is commutative: Pi || Pj implies that Pj || Pi
The relation is not transitive: Pi || Pj and Pj || Pk do not necessarily mean Pi || Pk
Associativity: Pi || Pj || Pk implies that (Pi || Pj) || Pk = Pi || (Pj || Pk)
For n processes, there are 3n(n-1)/2 conditions; violation of any of them prohibits parallelism collectively or partially
Statements or processes which depend on run-time conditions are not transformed to parallelism. (IF or conditional branches)
The analysis of dependences can be conducted at code, subroutine, process, task, and program levels; higher-level dependence can be inferred from that of subordinate levels.
Question 498 Explanation:
Bernstein’s conditions for parallelism:
Define:
Ii as the input set of a process Pi
Oi as the output set of a process Pi
P1 and P2 can execute in parallel (denoted as P1 || P2) under the condition:
I1 ∩ O2 = 0
I2 ∩ O1 = 0
O1 ∩ O2 = 0
Note that I1 ∩ I2 <> 0 does not prevent parallelism.
Input set: also called read set or domain of a process
Output set: also called write set or range of a process
A set of processes can execute in parallel if Bernstein’s conditions are satisfied on a pairwise basis; that is, P1 || P2 || … || PK if and only if Pi || Pj for all i<>j
The parallelism relation is commutative: Pi || Pj implies that Pj || Pi
The relation is not transitive: Pi || Pj and Pj || Pk do not necessarily mean Pi || Pk
Associativity: Pi || Pj || Pk implies that (Pi || Pj) || Pk = Pi || (Pj || Pk)
For n processes, there are 3n(n-1)/2 conditions; violation of any of them prohibits parallelism collectively or partially
Statements or processes which depend on run-time conditions are not transformed to parallelism. (IF or conditional branches)
The analysis of dependences can be conducted at code, subroutine, process, task, and program levels; higher-level dependence can be inferred from that of subordinate levels.