Explain bernstein conditions for detection of parallelism, Computer Engineering

Assignment Help:

Bernstein Conditions for Detection of Parallelism

For execution of a number of instructions or a block of instructions in parallel, it must be made certain that instructions are independent of one another. These instructions may be control dependent / resource dependent / data dependent on one another. Here we think about just data dependency among the statements for taking decisions of parallel execution. A.J. Bernstein has elucidated the work of data dependency and derived a number of conditions based on that we can decide the parallelism of processes or instructions.

Bernstein conditions are derived from the subsequent two sets of variables:

i)  The Read set or we can say input set RI which consists of memory locations read by statement of instruction I1.

ii) The Write set or output set WI which consists of memory locations written into by instruction I1.

The sets WI and RI are not disjoint as the similar locations are used for reading and writing by SI.

The following are 'Bernstein Parallelism conditions' that are used to conclude whether statements are parallel or not:

1)  Locations in R1 from which S1 reads and locations W2 on which S2 writes should be mutually exclusive. Which means S1 doesn't read from any memory location on which S2 writes. It can be indicated as

  R1 ∩ W2= ?

2)  In the same way, locations in R2 from that S2 reads and the locations W1 on that S1 writes should be mutually exclusive. Which means S2 doesn't read from any memory location onto that S1 writes. It can be designated as: 

R2 ∩ W1= ?

3)  The memory locations W1 and W2, on that S1 and S2 write must not be read by S1 and S2. Which means R1 and R2 must be independent of W1 and W2.  It can be indicated as:

W1 ∩ W2= ?

To demonstrate the operation of Bernstein's conditions, think about subsequent instructions of sequential program:

I1: x = (a + b) / (a * b)

I2: y = (b + c) * d

I3: z = x2 + (a * e)

Now the read set and write set of I1, I2 and I3 are as follows:

R1 = {a, b}        W1 = {x}

R2 = {b, c, d}    W2 = {y}

R3 = {x, a, e}    W3 = {z}

Now let's find out whether I1 and I2 are parallel or not

            R1 ∩ W2 = ?

            R2 ∩ W1 = ?

            W1 ∩ W2 = ?

Which means I1 and I2 are independent of each other.

Similarly for I1 || I3,

R1 ∩ W3= ?

R3 ∩ W1 ≠ ?

W1 ∩ W3= ?

Therefore I1 and I3 aren't independent of each other.

For I2 || I3,


R2 ∩ W3= ?

            R3 ∩ W2= ?

W3 ∩ W2= ?

Therefore, I2 and I3 are independent of one another. So I1 and I2, I2 and I3 are parallelizable however I1 and I3 are not.


Related Discussions:- Explain bernstein conditions for detection of parallelism

Microprocessors and interfaces, #question.write cycle timing diagram for ma...

#question.write cycle timing diagram for maximum mode of 8086 microprocessor.

Creation deductive inferences, Creation Deductive Inferences : Here we...

Creation Deductive Inferences : Here we have shown how knowledge can be represented in first-order logic or how rule-based expert systems expressed in logic can be constructed

How to make frames for web documents, Q. How to make frames for web documen...

Q. How to make frames for web documents? Intelligent use of frames can give your pages a cleaner look and make easier to navigate. The fundamental concept goes like this: Every

Explain difference between scanning and parsing, Explain difference between...

Explain difference between Scanning and parsing. Scanning and parsing: Scanning process is the process of recognizing the lexical components in a source string whereas parsin

What is an xml entity, Problem : (a) Show whether or not a standard for...

Problem : (a) Show whether or not a standard format for representing data, such as XML, is needed. (b) Using an appropriate example, describe how data is organized in a dat

How to copy files from a drive and directory, Q. How to copy files from a d...

Q. How to copy files from a drive and directory? You can copy files from a drive and directory other that the currently selected one. However in that case, you need to speci

Failures, FAILURES Since reliability engineering is focused on the surv...

FAILURES Since reliability engineering is focused on the survivability or absence of failures, it is more concerned about failures,  understanding  their causes and defining re

Convergence mean with respect to e-commerce, What does the term convergence...

What does the term convergence mean with respect to E-commerce? Convergence with respect to e-commerce   The ability to leverage and integrate the several data sources and

Every sheet in a workbook in excel, Is there a way to apply the same format...

Is there a way to apply the same formatting to every  sheet in a workbook in Excel? Ans)  Yes. To do this, you will require to right click on one of the worksheet tabs and th

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd