Summary of 30/04/14

This blog talks about the basics of the PRAM model and its variants. We would also be discussing a very important algorithm dealing with locating the greatest entry in an array using parallel processing.

PRAM models are classified on the basis of the methods employed in handling the various conflicts, and the speed at which they can solve problems. Hence the variants of PRAM model are:-

1. Exclusive Read Exclusive Write (EREW)

2. Exclusive Read Concurrent Write (ERCW)

3. Concurrent Read Exclusive Write (CREW)

4. Concurrent Read Concurrent Write (CRCW)

Here we would be focussing on the CRCW model only. Since multiple processors are interacting and accessing the memory at the same time, conflicts would be inevitable. In case of reading the memory at the same time, no conflicts would be expected because the processors need not enter the critical section when they are only reading concurrently. One way of achieving this would be making use of broadcasting, as do the crossbar and multistage networks. Here the broadcaster sends the duplicated value to the shared memory and these values can then be read by the processors. But in the case of concurrent write, since more than one processor try to access the memory and write into the same memory location at the same time, conflicts are unavoidable and the need for algorithms to tackle these conflicts arises.

Now let's talk about the algorithm which employs parallel processing to locate the element with the greatest value in an array. We would be inputting an array s[ ] from the user, which is the array in which the element with the maximum value is to be located. Since this algorithm makes use of parallel processing, it is way faster than the other methods, but the space complexity increases because of the use of nC2 processors. We are using nC2 processors because we need one processor per comparison and because the elements are being compared in pairs. For example, the processor p[1,2] compares the the values of the first and the second elements. We would also be using another array t[ ] to store locate the element we are searching for. In this array, the entry '1' for an element means that it hasn't been eliminated and '0' means that it has been eliminated and that it cannot be the element having the greatest value. For example, when the processor p[1,2] is done comparing the first two elements, the entry in t[ ] corresponding to the element with the lower value is changed to 0. Likewise, the entry in t[ ] corresponding to the element with the greater value is changed to 1.

The values of all the entries of t[ ] are calculated in a similar fashion and at the last stage of the algorithm, we are left with an array in which all the entries are 0 apart from the one we had planned on locating. Hence the algorithm can be summarized as follows :-

1. Reading the values from the input array

2. Comparing the values in pairs

3. Changing the values of the array t[] in the manner explained above.

4. Reading the array finally obtained to locate the element whose whose value is 1.

Algorithm :-

Keytype parlargest( int n, keytype s [ ])

{

int t[n];

initialization stage- change all t[i] to 1;

local index i, j;

local keytype first, second;

local int ch1, ch2;

i= first index of processor and j= second index of processor;

Read s[i] into first and s[j] into second;

Compare both,

  if(1st<2nd)

    t[i]=0;

   else

     t[j]=1;

Read t[i] into check 1 and t[j] into check 2;

Finally, if(t[i]==1)

          output s[i];

        else if( t[j]==1)

         output s[j];

}

VIVEK SEHGAL 374/CO/11

VIREN GULATI 369/CO/11