2 Write a message passing program to calculate whether a lis

2) Write a message passing program to calculate whether a list of parentheses match. The input is array Al0..N-11 located at Node 0. output is Answer a boolean. Use a serial method on single processors for load balancing.

Solution

One of the basic methods of programming for parallel computing is the use of message passing libraries. These libraries manage transfer of data between instances of a parallel program running on multiple processors in a parallel computing architecture.

public void reverseArray(int[] array, int startIndex, int endIndex){
if(startIndex > endIndex)

{
int temp = startIndex;
startIndex = endIndex;
endIndex = temp;
}
for (int start = startIndex, end = endIndex; start < end; start++, end--) {
int temp = array[start];
array[start] = array[end];
array[end] = temp;
}
}

public void leftRotateArray(int[] a, int n, int k){
reverseArray(a, 0, k-1);
reverseArray(a, k, n-1);
reverseArray(a, 0, n-1);
}

#include <iostream>

#include <stack>

#include <string>

using namespace std;

bool check_parathesis(string str, int len)

{

bool b=false;

stack<char> mystack;

string::const_iterator i;

for(i=str.begin();i != str.end(); i++)

{

if((*i == \'[\') || (*i == \'{\') || (*i == \'(\'))

mystack.push(*i);

else

{

if(mystack.empty())

return false;

else

{

b = (*i == \']\')?((\'[\'==mystack.top())?true:false):(((*i==\'}\')?((\'{\'==mystack.top())?true:false):(\'(\'==mystack.top())?true:false));

if (b)

mystack.pop();

else

return false;

}

}

}

return true;

}

int main()

{

string str = \"[{()()}]\";

bool b = check_parathesis(str, str.size());

cout << (int)b << endl;

return 0;

}

Performance analysis of parallel computing system is a complex task. This is due to factors that determine speedup and parallel slowdown parameters.

If a parallel program is executed on a computer having p processors, the highest value that can be obtained for the speedup is equal with the number of processors from the system.

The maximum speedup value could be achieved in an ideal multiprocessor system where there are no communication costs and the workload of processors is balanced.

every processor needs Ts/p time units in order to complete its job so the speedup value .

• Memory space. It means the amount of space used to store all data processed by the algorithm.

• Running time. It means the time needed to execute all the operations specified in the algorithm.