Computer-Organization
October 5, 2023Computer-Organization
October 5, 2023Computer-Organization
|
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:
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.
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.
Correct Answer: A
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.
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.
Subscribe
Login
0 Comments