How to find the amount of read and write contention and synchronization overheads for a shared memory program? For example, the OpenMP program below: int main(int argc, char** argv) { int* arr = NULL; double start_time, run_time; if (!(argc >= 3)) { printf("Number of array elements must be provided as first argument and number of threads as second argument to program\n"); exit(-1); } long int n = atoi(argv[1]); if (n > MAXSIZE) { n = MAXSIZE; } int p = atoi(argv[2]); if (p > MAXWORKERS) { p = MAXWORKERS; } omp_set_num_threads(p); arr = (int*)malloc(n * sizeof(int)); // Initialize and print the array to be sorted int i; for (i = 0; i < n; i++) arr[i] = ((int)random() % n) + 1; #ifdef DEBUG printf("initial arr: \n"); for (i = 0; i < n; i++) printf(" %3d", arr[i]); printf("\n"); #endif start_time = omp_get_wtime(); // Sorting is done in a parallel region #pragma omp parallel { // The first call to quicksort is done only once #pragma omp single quicksort(0, (n - 1), arr); } run_time = omp_get_wtime() - start_time; // check if the array is sorted and print the sorted array for (i = 0; i < n - 1; i++) if (arr[i] > arr[i + 1]) { printf("The resulting arr is not sorted!\n"); //return(1); } #ifdef DEBUG printf("sorted arr: \n"); for (i = 0; i < n; i++) printf(" %3d", arr[i]); printf("\n"); #endif printPerformanceResults(n, p, run_time); fprintf(stderr, "%f\n", run_time); return 0; } /* Regular quiksort algorithm, with the only exception being that * the recursive step is done in parallel with OpenMp tasks */ void quicksort(int first, int last, int arr[]) { int pivot, i_pivot, temp, left, right; if (first >= last) return; // no need to sort // otherwise select a pivot i_pivot = (first + last) / 2; pivot = arr[i_pivot]; left = first; right = last; while (left <= right) { if (arr[left] > pivot) { // swap left element with right element temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; if (right == i_pivot) { i_pivot = left; } right--; } else { left++; } } // Put the pivot in place (i.e. swap with right element) temp = arr[right]; arr[right] = pivot; arr[i_pivot] = temp; // The recursive steps in quicksort execution are implemented as separate tasks #pragma omp task quicksort(first, (right - 1), arr); #pragma omp task quicksort((right + 1), last, arr); }

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question

How to find the amount of read and write contention and synchronization overheads for a shared memory program?

For example, the OpenMP program below:

int main(int argc, char** argv) {
int* arr = NULL;
double start_time, run_time;

if (!(argc >= 3)) {
printf("Number of array elements must be provided as first argument and number of threads as second argument to program\n");
exit(-1);
}
long int n = atoi(argv[1]);
if (n > MAXSIZE) { n = MAXSIZE; }
int p = atoi(argv[2]);
if (p > MAXWORKERS) { p = MAXWORKERS; }

omp_set_num_threads(p);
arr = (int*)malloc(n * sizeof(int));

// Initialize and print the array to be sorted
int i;
for (i = 0; i < n; i++)
arr[i] = ((int)random() % n) + 1;
#ifdef DEBUG
printf("initial arr: \n");
for (i = 0; i < n; i++)
printf(" %3d", arr[i]);
printf("\n");
#endif

start_time = omp_get_wtime();

// Sorting is done in a parallel region
#pragma omp parallel
{
// The first call to quicksort is done only once
#pragma omp single
quicksort(0, (n - 1), arr);
}

run_time = omp_get_wtime() - start_time;

// check if the array is sorted and print the sorted array
for (i = 0; i < n - 1; i++)
if (arr[i] > arr[i + 1]) {
printf("The resulting arr is not sorted!\n");
//return(1);
}
#ifdef DEBUG
printf("sorted arr: \n");
for (i = 0; i < n; i++)
printf(" %3d", arr[i]);
printf("\n");
#endif

printPerformanceResults(n, p, run_time);
fprintf(stderr, "%f\n", run_time);

return 0;
}

/* Regular quiksort algorithm, with the only exception being that
* the recursive step is done in parallel with OpenMp tasks
*/
void quicksort(int first, int last, int arr[]) {
int pivot, i_pivot, temp, left, right;
if (first >= last) return; // no need to sort
// otherwise select a pivot
i_pivot = (first + last) / 2;
pivot = arr[i_pivot];
left = first;
right = last;
while (left <= right) {
if (arr[left] > pivot) { // swap left element with right element
temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
if (right == i_pivot) {
i_pivot = left;
}
right--;
}
else {
left++;
}
}
// Put the pivot in place (i.e. swap with right element)
temp = arr[right];
arr[right] = pivot;
arr[i_pivot] = temp;

// The recursive steps in quicksort execution are implemented as separate tasks
#pragma omp task
quicksort(first, (right - 1), arr);
#pragma omp task
quicksort((right + 1), last, arr);

}

Expert Solution
steps

Step by step

Solved in 2 steps

Blurred answer
Knowledge Booster
Stack
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education