Bernstein conditions for detection of parallelism, Computer Engineering

Assignment Help:

Bernstein Conditions for Detection of Parallelism

For implementation of instructions or block of instructions in parallel, it should be guaranteed that the instructions are independent of each other. These instructions can be / control dependent / data dependent resource dependent on each other.  We are considering only data dependency between the statements for taking decisions of parallel implementation. A.J. Bernstein has implicated the work of data dependency and resultant some conditions based on which we can settle on the parallelism of processes or instructions.

Bernstein conditions are rely on the subsequent two sets of variables:

i)  The input set or Read set RI that consists of memory locations examine by the statement of instruction I1.

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

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

The following are Bernstein Parallelism conditions which are determine to conclude whether the statements are parallel or not:

1) Position in R1 from which S1 reads and the Position W2  onto which S2 writes must be commonly exclusive. It  means S1does'nt read from any memory location onto which S2 writes. It can be indicated as:

                                                                     1510_Bernstein Conditions for Detection of Parallelism.png

 

2) Likewise, locations in R2 from which S1 writes and the locations W1 onto which S2 reads must be commonly exclusive.It means S2  does not read from some memory location onto which S1 writes. It can be indicate as:

                                                                       138_Bernstein Conditions for Detection of Parallelism 1.png

3) The memory locations W1 and W2 onto which S1 and S2 write, should not be examine by S1 and S2. It means R1 and R2 should be free of W1 and W2.  It can be indicated as :

                                                                      661_Bernstein Conditions for Detection of Parallelism 2.png

To demonstrate the operation of Bernstein's conditions, let consider the following 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 given:

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

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

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

 

Now let us search out whether I1 and I2 are parallel or not

 

 

314_Bernstein Conditions for Detection of Parallelism 3.png

                                                        418_Bernstein Conditions for Detection of Parallelism 4.png


Related Discussions:- Bernstein conditions for detection of parallelism

Why we use addressing schemes, Q Why we use addressing schemes? An ope...

Q Why we use addressing schemes? An operation code of an instruction tells the operation to be performed. This operation is executed on some data stored in memory or register.

What is the syntax of the assembler directive equ, The syntax of the assemb...

The syntax of the assembler directive EQU is ? Ans. The syntax of the assembler directive EQU is as given below: EQU

Access to external identifiers, Access to External Identifiers: An external...

Access to External Identifiers: An external identifier is one which is referred in one module though defined in another. You can declare an identifier to be external by including i

Symbol for the new euro currency in my spreadsheet, How can I go in the sym...

How can I go in the symbol for the new Euro currency in my spreadsheet? Ans) Microsoft suggestted a new Tahoma font with the Euro symbol.

Explain about the voice recognition system, Explain about the Voice recogni...

Explain about the Voice recognition system These voice recognition systems recognise spoken words e.g. for disabled people who can't use keyboards where they speak commands rat

Define the architectural framework for electronic commerce, Define the Arch...

Define the Architectural framework for electronic commerce. An application independent framework to categorize service interaction relies onto four fundamental dimensions a.

Layered architecture of edi, Layered Architecture of EDI: EDI is most c...

Layered Architecture of EDI: EDI is most commonly applied in the implementation and settlement phases of the trade cycle. In implementation of a simple trade exchange, the cust

Demux., Implement the full substractor using 8:1demux

Implement the full substractor using 8:1demux

Draw state diagram, Draw the state diagram of a process from its creation t...

Draw the state diagram of a process from its creation to termination, including all transitions, and briefly elaborate every state and every transition. When a process executes

What are the four factors of open source software, What are the four signif...

What are the four significant factors that led to the development of open source software? 1. To diminish the high control value of the Proprietary Software 2. To avoid disc

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