SHARE
TWEET

Untitled

a guest Nov 22nd, 2019 93 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <pthread.h>
  4. #include <time.h>
  5. #include <string.h>
  6. #include <sys/time.h>
  7.  
  8. /*
  9.     This program aims to test the effect of using POSIX threads by using 4 pthreads to sort a given array using the merge sort algorithm.
  10.     Made by: Marwan Mokhles Abdallah ID  #4926
  11.  */
  12.  
  13. #define LINE_MAX 1024 // CONSTANT DEFINES HOW MANY CHARACTERS ALLOWED IN THE INPUT LINE
  14. #define MAX_THREADS 4 // MAX NUMBER OF THREADS TO BE USED IN THIS PROGRAM
  15. #define MAX_LENGTH 100 // MAX LENGTH OF THE ARRAY
  16.  
  17. int inputArray[MAX_LENGTH]; // THE ARRAY ON WHICH MERGE SORT IS TO BE APPLIED
  18. int input_count;    // STORING COUNT OF ELEMENTS INPUT INTO THE ARRAY
  19.  
  20. void parse2intarr(char* line, int elements[]);  // FUNCTION THAT SPLITS A LINE STRING AND PARSES THE OUTPUT TO AN INTEGER ARRAY
  21. void parallel_msort();                          // INTERMEDIATE FUNCTION THAT CALLS THE MERGE SORT - IRRELEVANT FUNCTIONS
  22. void *threaded_merge_sort(void* arg);           // FUNCTION THAT DIVIDES THE WORK AND ASSIGNS EACH PART TO A THREAD
  23. void copyInput(int arr[]);                      // FUNCTION THAT COPIES THE ELEMENTS ARRAY TO THE INPUTARRAY
  24. char* getCurrentTime();                         // FUNCTION THAT RETURNS THE CURRNT TIME IN A STRING FORMAT
  25. void merge(int low, int mid, int high);         // FUNCTION THAT APPLIES A MERGE ON THE SPLIT ARRAYS DURING MERGE SORT
  26. void msort(int low, int high);                  // FUNCTION THAT IS CALLED RECURSIVELY TO APPLY MERGE SORT
  27. void merge_resultant();                         // FUNCTION THAT MERGES THE RESULTANT SUBARRAYS
  28. void sortTest();                                // FUNCTION THAT TESTS FOR THE ASCENDING ORDER OF THE ARRAY
  29.  
  30. int main()
  31. {
  32.     clock_t tstart, tend;       // VARIABLES USED TO CALCULATE TIME TAKEN
  33.     FILE *f;
  34.     int i=0;
  35.     char line[LINE_MAX];        // STRING TO STORE THE INPUT LINE OF INTEGERS
  36.     f=fopen("input.txt", "r");
  37.     if (f != NULL)
  38.     {
  39.         while (fscanf(f,"%d\n",&input_count)!=-1)       //  READING THE INPUT.TXT FILE
  40.         {
  41.             fgets(line, LINE_MAX,f);
  42.         }
  43.         fclose(f);
  44.         printf("\n%s\n",getCurrentTime());              // PRINTS TO VALIDATE INPUT AND STARTING TIME
  45.         printf("\nElements Count: %d",input_count);
  46.         printf("\nElements: %s\n\n",line);
  47.         int elements[input_count];                      //  A TEMPORARY INTEGER ARRAY USED TO STORE THE VALUES RETURNED FROM PARSE2INTARRAY
  48.         parse2intarr(line,elements);                    //  FUNCTION CALL TO POPULATE ELEMENTS ARRAY
  49.         copyInput(elements);                            //  FUNCTION CALL TO POPULATE INPUTARRAY ARRAY
  50.         tstart = clock();                               //  START CALCULATING TIME
  51.         parallel_msort();                               //  START THE MERGE SORT
  52.         tend = clock();                                 //  END TIME CALCULATION
  53.         printf("\nArray in order: ");
  54.         for(i=0;i<input_count;i++)                      //  PRINT THE SORTED ARRAY
  55.         {
  56.             printf("%d ", inputArray[i]);
  57.         }
  58.         sortTest();
  59.         printf("\nTime Taken: %f\n\n",(tend - tstart) /(double)CLOCKS_PER_SEC);     // PRINT TIME TAKEN
  60.     }else{
  61.         printf("ERROR: Opening file failed!\n");                    // IN CASE OF NOT BEING ABLE TO OPEN THE FILE
  62.         exit(-1);
  63.     }
  64.     return 0;
  65. }
  66.  
  67. // FUNCTION THAT COPIES THE ELEMENTS ARRAY TO THE INPUTARRAY
  68. void copyInput(int arr[])
  69. {
  70.     int i, count = input_count;
  71.     for(i = 0; i < count; i++)
  72.     {
  73.         inputArray[i] = arr[i];
  74.     }
  75. }
  76.  
  77. // FUNCTION THAT RETURNS THE CURRNT TIME IN A STRING FORMAT
  78. char* getCurrentTime()
  79. {
  80.     time_t rawtime;
  81.     struct tm * timeinfo;
  82.     time ( &rawtime );
  83.     timeinfo = localtime (&rawtime);
  84.     return asctime (timeinfo);
  85. }
  86.  
  87. void sortTest() {
  88.     for (int i = 1; i < input_count; i ++) {
  89.         if (inputArray[i] < inputArray[i - 1]) {
  90.             printf("\nERROR: Element %d is not in the correct spot\n", inputArray[i]);
  91.             return;
  92.         }
  93.     }
  94.     printf("\n\nSORTING TEST RESULT: SUCCESSFUL! ARRAY IS SORTED ASCENDINGLY! \n");
  95. }
  96.  
  97. // FUNCTION THAT SPLITS A LINE STRING AND PARSES THE OUTPUT TO AN INTEGER ARRAY
  98. void parse2intarr(char* line, int elements[])
  99. {
  100.     int i=0;
  101.     char *token= strtok(line, " \t");           //  LINE TOKENIZED TO TOKEN
  102.     while (token) {
  103.         elements[i]=atoi(token);
  104.         token = strtok(NULL, " \t");            //  TOKEN TOKENIZED TO GET THE NEXT INTEGER
  105.         i++;
  106.      }
  107. }
  108.  
  109. // FUNCTION THAT MERGES ALL PARTS SORTED BY THREADS
  110. void merge_resultant()
  111. {
  112.     int low = 0;
  113.     int mid = (input_count / 2) - 1;
  114.     int high = input_count - 1;
  115.     merge(low, mid / 2, mid - 1);           // MERGING THE FINAL ARRAY PARTS
  116.     merge(mid, mid + (high-mid)/2, high);
  117.     merge(low, mid, high);
  118. }
  119.  
  120. // INTERMEDIATE FUNCTION THAT CALLS THE MERGE SORT - IRRELEVANT FUNCTIONS
  121. void parallel_msort(){
  122.     int thread_count, i, count = input_count;
  123.     if(count < MAX_THREADS)                                     // IN CASE THE ARRAY LENGTH IS LESS THAN THE MAX NUMBER OF THREADS
  124.         thread_count = count;                                   // THE NUMBER OF ELEMENTS IS EQUAL TO NUMBER OF THREADS
  125.     else
  126.         thread_count = MAX_THREADS;                             // ELSE MAX NUMBER OF THREADS IS USED
  127.     pthread_t threads[thread_count];
  128.     for(i = 0; i < thread_count ; i++)
  129.     {
  130.         if(pthread_create(&threads[i], NULL,threaded_merge_sort,(void *)i))         // CREATING THREADS
  131.         {
  132.             printf("ERROR: failed to create thread %d.", i);
  133.             exit(-1);
  134.         }
  135.         else{
  136.             merge_resultant();
  137.         }
  138.     }
  139.     for(i = 0; i < thread_count; i++) {                                 // JOINING THREADS
  140.         pthread_join(threads[i], NULL);
  141.     }
  142.  
  143. }
  144.  
  145. // FUNCTION THAT IS CALLED RECURSIVELY TO APPLY MERGE SORT
  146. void merge(int low, int mid, int high)
  147. {
  148.     int i = 0, j = 0, k = 0;
  149.     int right = high - mid;
  150.     int left = mid - low + 1;
  151.     int leftArr[left], rightArr[right];
  152.  
  153.  
  154.     for (int i = 0; i < left; i ++) {               // POPULATING THE LEFT ARRAY
  155.         leftArr[i] = inputArray[low + i];
  156.     }
  157.  
  158.     for (int j = 0; j < right; j ++) {              //  POPULATING THE RIGHT ARRAY
  159.         rightArr[j] = inputArray[mid + 1 + j];
  160.     }
  161.     i = 0;
  162.     j = 0;
  163.     while(i < left && j < right) {                  //  MERGING AND PLACING RESULTS IN THE INPUTARRAY
  164.         if (leftArr[i] <= rightArr[j]) {
  165.             inputArray[low + k] = leftArr[i];
  166.             i ++;
  167.         } else {
  168.             inputArray[low + k] = rightArr[j];
  169.             j ++;
  170.         }
  171.         k ++;
  172.     }
  173.     while (i < left) {                              //  MERGING THE REMAINING ARRAY PARTS
  174.         inputArray[low + k] = leftArr[i];
  175.         k ++;
  176.         i ++;
  177.     }
  178.     while (j < right) {
  179.         inputArray[low + k] = rightArr[j];
  180.         k ++;
  181.         j ++;
  182.     }
  183.     }
  184.  
  185.  
  186. // FUNCTION THAT APPLIES A MERGE ON THE SPLIT ARRAYS DURING MERGE SORT
  187. void msort(int low, int high)
  188. {
  189.     int mid = low + (high - low) / 2; // COMPUTING MID POINT OF THE ARRAY
  190.     if (low < high) {
  191.         msort(low, mid);         // RECURSIVELY SORTING THE  LEFT ARRAY
  192.         msort(mid + 1, high);    // RECURSIVELY SORTING THE RIGHT ARRAY
  193.         merge(low, mid, high);        // MERGING BOTH ARRAYS
  194.     }
  195. }
  196.  
  197. // FUNCTION THAT DIVIDES THE WORK AND ASSIGNS EACH PART TO A THREAD
  198. void *threaded_merge_sort(void* arg)
  199. {
  200.     int high, low, mid;
  201.     int thread_id = (int)arg;     // INITIALISING THREAD ID FROM THE COUNTER PARALLELM_SORT
  202.     printf("\nthread_id = %d",thread_id);
  203.     if(input_count < MAX_THREADS)           // IN CASE INPUT COUNT IS LESS THAN MAX_THREADS, LET 1 THREAD HANDLE THE INPUT
  204.     {
  205.         high = input_count-1;
  206.         low = 0;
  207.         mid = low + (high - low) / 2;
  208.         msort(low, mid);
  209.         msort(mid + 1, high);
  210.         merge(low, mid, high);
  211.     }
  212.     else                                // IN CASE INPUT COUNT IS EQUAL TO OR GREATER THAN MAX_THREADS, LET MAX_THREADS THREADS HANDLE THE INPUT
  213.     {
  214.         high = (thread_id + 1) * (input_count / MAX_THREADS) - 1;
  215.         low = thread_id * (input_count / MAX_THREADS);                // ARRAY IS SPLIT INTO PARTS DEPENDING ON MAX_THREADS SO THAT EACH THREAD GETS TO HAVE (1/MAX_THREADS) THE WORK
  216.         mid = low + (high - low) / 2;
  217.         if (low < high) {                                   // APPLYING MERGE SORT TO THE ASSIGNED PARTS OF THE ARRAY
  218.             msort(low, mid);
  219.             msort(mid + 1, high);
  220.             merge(low, mid, high);
  221.         }
  222.     }
  223.     return NULL;
  224. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top