###### Computer-Organization

October 5, 2023###### Computer-Organization

October 5, 2023# Computer-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:

I

O

P

I

I

O

Note that I

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

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:

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}= 0I

_{2}∩ O_{1}= 0O

_{1}∩ O_{2}= 0Note 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<>jThe 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:

I

O

P

I

I

O

Note that I

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

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:

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}= 0I

_{2}∩ O_{1}= 0O

_{1}∩ O_{2}= 0Note 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<>jThe 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