ex1.c (7929B)
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <mpi.h> 4 5 #define TAG_T 1 6 #define TAG_N 2 7 #define TAG_BUFSIZE 3 8 #define TAG_MENU 4 9 #define TAG_SORTED 5 10 #define TAG_VAL 6 11 #define TAG_PREV 7 12 13 int 14 main(int argc, char *argv[]) 15 { 16 MPI_Status status; 17 int nproc, rank, rc; 18 int *t, n, prev; 19 int bufsize, offset, remaining; 20 int val, sorted; /* results from each process */ 21 int f_val, f_sorted; /* final results */ 22 int found = 0; /* indicates that the first unsorted element has been found */ 23 int i, ch = 1; 24 25 /* just in case an error occurs during initialization */ 26 if ((rc = MPI_Init(&argc, &argv)) != 0) { 27 fprintf(stderr, "%s: cannot intialize MPI.\n", argv[0]); 28 MPI_Abort(MPI_COMM_WORLD, rc); 29 } 30 31 /* count how many processes we have running */ 32 MPI_Comm_rank(MPI_COMM_WORLD, &rank); 33 MPI_Comm_size(MPI_COMM_WORLD, &nproc); 34 35 /* main loop */ 36 while (ch != 2) { 37 if (rank == 0) { 38 printf("Enter N: \n"); 39 scanf("%d", &n); 40 getchar(); 41 42 t = malloc(n * sizeof(int)); 43 44 /* read whole array */ 45 for (i = 0; i < n; i++) { 46 printf("t[%d]: \n", i); 47 scanf("%d", &t[i]); 48 } 49 getchar(); 50 51 /* reset flag */ 52 sorted = 1; 53 /* see if there are any remaining elements */ 54 remaining = n % nproc; 55 56 /* calculate offsets and pass sub-array to each processor */ 57 for (i = 1; i < nproc; i++) { 58 /* calculate bufsize as if there are remaining == 0 */ 59 bufsize = n / nproc; 60 /* 61 * calculate which part of the array each process will get. 62 * the last parts makes sure that if there are any 63 * remaining elements, the offset will adapt properly 64 */ 65 offset = i * bufsize + (i - 1 < remaining ? i : remaining); 66 /* if there are any remaining elements, increment bufsize */ 67 if (i < remaining) 68 bufsize++; 69 70 /* each process gets the last element of the previous one */ 71 prev = t[offset - 1]; 72 73 /* send sub-array along with its size and sorted flag */ 74 MPI_Send(&bufsize, 1, MPI_INT, i, TAG_BUFSIZE, MPI_COMM_WORLD); 75 MPI_Send(t + offset, bufsize, MPI_INT, i, TAG_T, MPI_COMM_WORLD); 76 MPI_Send(&prev, 1, MPI_INT, i, TAG_PREV, MPI_COMM_WORLD); 77 MPI_Send(&sorted, 1, MPI_INT, i, TAG_SORTED, MPI_COMM_WORLD); 78 } 79 80 /* 81 * calculate bufsize for proc 0 in and increment 82 * in case there are still remaining elements 83 */ 84 bufsize = n / nproc; 85 if (remaining != 0) 86 bufsize++; 87 } else { 88 /* 89 * receive sub-arrays and sorted flag and allocate memory for each 90 * process' array 91 */ 92 MPI_Recv(&bufsize, 1, MPI_INT, 0, TAG_BUFSIZE, MPI_COMM_WORLD, &status); 93 t = malloc(bufsize * sizeof(int)); 94 MPI_Recv(t, bufsize, MPI_INT, 0, TAG_T, MPI_COMM_WORLD, &status); 95 MPI_Recv(&prev, 1, MPI_INT, 0, TAG_PREV, MPI_COMM_WORLD, &status); 96 MPI_Recv(&sorted, 1, MPI_INT, 0, TAG_SORTED, MPI_COMM_WORLD, &status); 97 } 98 99 /* check if array is unsorted */ 100 for (i = 0; i < bufsize - 1; i++) { 101 if (t[i] > t[i + 1]) { 102 val = t[i]; 103 sorted = 0; 104 break; 105 /* 106 * we check if the last element of the previous process 107 * is greater than t[i] so that each process doesn't compare 108 * only against its own elements. we make sure that the rank 109 * is not 0, since it doesn't have a previous rank. 110 */ 111 } else if (t[i] < prev && rank != 0) { 112 val = prev; 113 sorted = 0; 114 break; 115 } 116 } 117 118 /* we're done with t, free everything */ 119 free(t); 120 121 if (rank == 0) { 122 /* collect results from proc 0 first */ 123 f_sorted = sorted; 124 f_val = val; 125 /* if f_sorted is false already, don't bother searching below */ 126 found = f_sorted == 0; 127 128 /* receive results from the rest */ 129 for (i = 1; i < nproc; i++) { 130 MPI_Recv(&val, 1, MPI_INT, i, TAG_VAL, MPI_COMM_WORLD, &status); 131 MPI_Recv(&sorted, 1, MPI_INT, i, TAG_SORTED, MPI_COMM_WORLD, &status); 132 /* 133 * AND all flags to determine whether the array is sorted. 134 * if one of the flags is 0, res will be 0 even if the 135 * rest of the flags are 1 136 */ 137 f_sorted &= sorted; 138 /* 139 * get only the first unsorted element, we don't care about 140 * the rest, if any 141 */ 142 if (!sorted && !found) { 143 f_val = val; 144 found = 1; 145 } 146 } 147 148 if (f_sorted) 149 puts("Array is sorted."); 150 else 151 printf("Array is not sorted: first unsorted element: %d\n", f_val); 152 153 puts("Press [ENTER] to continue. . ."); 154 getchar(); 155 } else { 156 /* send results to processor 0 */ 157 MPI_Send(&val, 1, MPI_INT, 0, TAG_VAL, MPI_COMM_WORLD); 158 MPI_Send(&sorted, 1, MPI_INT, 0, TAG_SORTED, MPI_COMM_WORLD); 159 } 160 161 /* menu */ 162 if (rank == 0) { 163 system("clear || cls"); 164 printf("1. Continue\n2. Exit\nYour choice: \n\n"); 165 scanf("%d", &ch); 166 /* everyone has to know what the choice is */ 167 for (i = 1; i < nproc; i++) 168 MPI_Send(&ch, 1, MPI_INT, i, TAG_MENU, MPI_COMM_WORLD); 169 } else 170 MPI_Recv(&ch, 1, MPI_INT, 0, TAG_MENU, MPI_COMM_WORLD, &status); 171 } 172 173 MPI_Finalize(); 174 175 return 0; 176 }