ComputerOrganization
October 5, 2023ComputerOrganization
October 5, 2023ComputerOrganization
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 :
Pi  Pj for all i ≠ j


Pi  Pj for all i = j+1


Pi  Pj for all i ≤ j


Pi  Pj for all i ≥ j

Question 498 Explanation:
Bernstein’s conditions for parallelism:
Define:
I_{i} as the input set of a process P_{i}
O_{i }as the output set of a process P_{i}
P_{1 }and P_{2} can execute in parallel (denoted as P_{1}  P_{2}) under the condition:
I_{1} ∩ O_{2} = 0
I_{2} ∩ O_{1} = 0
O_{1} ∩ O_{2} = 0
Note that I_{1} ∩ I_{2} <> 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, P_{1}  P_{2}  …  P_{K} if and only if P_{i}  P_{j} 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(n1)/2 conditions; violation of any of them prohibits parallelism collectively or partially
Statements or processes which depend on runtime 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; higherlevel dependence can be inferred from that of subordinate levels.
Define:
I_{i} as the input set of a process P_{i}
O_{i }as the output set of a process P_{i}
P_{1 }and P_{2} can execute in parallel (denoted as P_{1}  P_{2}) under the condition:
I_{1} ∩ O_{2} = 0
I_{2} ∩ O_{1} = 0
O_{1} ∩ O_{2} = 0
Note that I_{1} ∩ I_{2} <> 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, P_{1}  P_{2}  …  P_{K} if and only if P_{i}  P_{j} 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(n1)/2 conditions; violation of any of them prohibits parallelism collectively or partially
Statements or processes which depend on runtime 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; higherlevel dependence can be inferred from that of subordinate levels.
Correct Answer: A
Question 498 Explanation:
Bernstein’s conditions for parallelism:
Define:
I_{i} as the input set of a process P_{i}
O_{i }as the output set of a process P_{i}
P_{1 }and P_{2} can execute in parallel (denoted as P_{1}  P_{2}) under the condition:
I_{1} ∩ O_{2} = 0
I_{2} ∩ O_{1} = 0
O_{1} ∩ O_{2} = 0
Note that I_{1} ∩ I_{2} <> 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, P_{1}  P_{2}  …  P_{K} if and only if P_{i}  P_{j} 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(n1)/2 conditions; violation of any of them prohibits parallelism collectively or partially
Statements or processes which depend on runtime 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; higherlevel dependence can be inferred from that of subordinate levels.
Define:
I_{i} as the input set of a process P_{i}
O_{i }as the output set of a process P_{i}
P_{1 }and P_{2} can execute in parallel (denoted as P_{1}  P_{2}) under the condition:
I_{1} ∩ O_{2} = 0
I_{2} ∩ O_{1} = 0
O_{1} ∩ O_{2} = 0
Note that I_{1} ∩ I_{2} <> 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, P_{1}  P_{2}  …  P_{K} if and only if P_{i}  P_{j} 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(n1)/2 conditions; violation of any of them prohibits parallelism collectively or partially
Statements or processes which depend on runtime 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; higherlevel dependence can be inferred from that of subordinate levels.
Subscribe
Login
0 Comments