Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <pthread.h>
- #include <stdlib.h>
- #include <time.h>
- void quicksort (int *A, int len);
- #define MIN_LENGTH 4
- int DEBUG;
- typedef struct
- {
- int *array;
- int left;
- int right;
- int tid;
- } thread_data_t;
- int number_of_threads;
- pthread_mutex_t lock_number_of_threads;
- int
- my_comp (const void *larg, const void *rarg)
- {
- int l = *(int *) larg;
- int r = *(int *) rarg;
- if (l < r)
- {
- return -1;
- }
- else if (l == r)
- {
- return 0;
- }
- return 1;
- }
- void
- merge (int *data, int left, int right, int tid)
- {
- if (DEBUG)
- {
- printf ("[%d] Merging %d to %d\n", tid, left, right);
- }
- int ctr = 0;
- int i = left;
- int mid = left + ((right - left) / 2);
- int j = mid + 1;
- int *c = (int *) malloc ((right - left + 1) * sizeof (int));
- while (i <= mid && j <= right)
- {
- if (data[i] <= data[j])
- {
- c[ctr++] = data[i++];
- }
- else
- {
- c[ctr++] = data[j++];
- }
- }
- if (i == mid + 1)
- {
- while (j <= right)
- {
- c[ctr++] = data[j++];
- }
- }
- else
- {
- while (i <= mid)
- {
- c[ctr++] = data[i++];
- }
- }
- i = left;
- ctr = 0;
- while (i <= right)
- {
- data[i++] = c[ctr++];
- }
- free (c);
- return;
- }
- void *
- merge_sort_threaded (void *arg)
- {
- thread_data_t *data = (thread_data_t *) arg;
- int l = data->left;
- int r = data->right;
- int t = data->tid;
- if (r - l + 1 <= MIN_LENGTH)
- {
- if (DEBUG)
- {
- printf ("[%d] Calling qsort(%d, %d).\n", t, l, r);
- }
- qsort (data->array + l, r - l + 1, sizeof (int), my_comp);
- }
- else
- {
- int m = l + ((r - l) / 2);
- thread_data_t data_0;
- data_0.left = l;
- data_0.right = m;
- data_0.array = data->array;
- pthread_mutex_lock (&lock_number_of_threads);
- data_0.tid = number_of_threads++;
- pthread_mutex_unlock (&lock_number_of_threads);
- pthread_t thread0;
- NULL,
- merge_sort_threaded,
- &data_0);
- if (rc)
- {
- if (DEBUG)
- {
- data_0.tid);
- }
- qsort (data->array + l, m - l + 1, sizeof (int), my_comp);
- }
- thread_data_t data_1;
- data_1.left = m + 1;
- data_1.right = r;
- data_1.array = data->array;
- pthread_mutex_lock (&lock_number_of_threads);
- data_1.tid = number_of_threads++;
- pthread_mutex_unlock (&lock_number_of_threads);
- pthread_t thread1;
- if (rc)
- {
- if (DEBUG)
- {
- data_1.tid);
- }
- qsort (data->array + m + 1, r - m, sizeof (int), my_comp);
- }
- {
- pthread_join (thread0, NULL);
- }
- {
- pthread_join (thread1, NULL);
- }
- merge (data->array, l, r, t);
- }
- pthread_exit (NULL);
- return NULL;
- }
- void
- merge_sort (int *array, int start, int finish)
- {
- thread_data_t data;
- data.array = array;
- data.left = start;
- data.right = finish;
- number_of_threads = 0;
- pthread_mutex_init (&lock_number_of_threads, NULL);
- data.tid = 0;
- pthread_t thread;
- NULL,
- merge_sort_threaded,
- &data);
- if (rc)
- {
- if (DEBUG)
- {
- }
- qsort (array + start, finish - start + 1, sizeof (int), my_comp);
- }
- pthread_join (thread, NULL);
- return;
- }
- int
- max (int *a, int n, int i, int j, int k)
- {
- int m = i;
- if (j < n && a[j] > a[m])
- {
- m = j;
- }
- if (k < n && a[k] > a[m])
- {
- m = k;
- }
- return m;
- }
- void
- downheap (int *a, int n, int i)
- {
- while (1)
- {
- int j = max (a, n, i, 2 * i + 1, 2 * i + 2);
- if (j == i)
- {
- break;
- }
- int t = a[i];
- a[i] = a[j];
- a[j] = t;
- i = j;
- }
- }
- void
- heapsort (int *a, int n)
- {
- int i;
- for (i = (n - 2) / 2; i >= 0; i--)
- {
- downheap (a, n, i);
- }
- for (i = 0; i < n; i++)
- {
- int t = a[n - i - 1];
- a[n - i - 1] = a[0];
- a[0] = t;
- downheap (a, n - i - 1, 0);
- }
- }
- void
- quicksort (int *A, int len)
- {
- if (len < 2)
- return;
- int pivot = A[len / 2];
- int i, j;
- for (i = 0, j = len - 1;; i++, j--)
- {
- while (A[i] < pivot)
- i++;
- while (A[j] > pivot)
- j--;
- if (i >= j)
- break;
- int temp = A[i];
- A[i] = A[j];
- A[j] = temp;
- }
- quicksort (A, i);
- quicksort (A + i, len - i);
- }
- int
- main ()
- {
- printf ("Select benchmark mode");
- printf ("\n(1) Multthread Mergesort (Using POPCNT)\n");
- printf ("(2) Singlethread Heapsort (Using BMI)\n");
- printf ("(3) Exit\n");
- int selval, mode;
- scanf ("%d", &selval);
- if (selval < 1 || selval > 3)
- {
- printf ("Invalid input.. aborting!");
- return 0;
- }
- mode = selval;
- printf ("\nSimple Heapsort benchmarking tool\n");
- printf ("\nCopyright (C) 2017 Fabian Druschke (Knogle)");
- printf
- printf
- ("\nThis is free software, and you are welcome to redistribute it \n \n \n");
- if (selval == 3)
- {
- return 1;
- }
- sleep (3);
- if (mode == 1)
- {
- int size = 100000000, loop, qrand;
- int *array;
- array = (int *) malloc (size * sizeof (int));
- if (array != NULL)
- {
- if ((size * sizeof (int)) < 1000)
- {
- printf ("\n %lu Bytes allocated\n", (size * sizeof (int)));
- }
- else if ((size * sizeof (int)) >= 1000)
- {
- printf ("\n %lu Kilobytes allocated\n",
- ((size * sizeof (int)) / 1000));
- }
- else if ((size * sizeof (int)) >= 1000 * 1000)
- {
- printf ("\n %lu Megabytes allocated\n",
- ((size * sizeof (int)) / 1000 * 1000));
- }
- sleep (1);
- printf ("\nFilling array.\n");
- sleep (3);
- srand ( time(NULL) );
- for (loop = 0; loop < size; loop++)
- {
- qrand = rand () % 20;
- array[loop] = qrand;
- printf ("%d", qrand);
- }
- }
- else
- printf ("\nKein freier Speicher vorhanden.\n");
- printf ("\nMerge Sort..\n");
- clock_t t;
- t = clock ();
- merge_sort (array, 0, size - 1);
- for (loop = 0; loop < size; loop++)
- {
- printf ("%d", array[loop]);
- }
- if ((size * sizeof (int)) < 1000)
- {
- printf ("\n %lu Bytes wurden freigegeben\n", (size * sizeof (int)));
- }
- else if ((size * sizeof (int)) >= 1000)
- {
- printf ("\n %lu Kilobytes wurden freigegeben\n",
- ((size * sizeof (int)) / 1000));
- }
- else if ((size * sizeof (int)) >= 1000 * 1000)
- {
- printf ("\n %lu Megabytes wurden freigegeben\n",
- ((size * sizeof (int)) / 1000 * 1000));
- }
- t = clock () - t;
- printf ("Sorting took %f seconds to finish \n", time_taken);
- double score = (sizeof (int) / time_taken);
- printf ("Your total score: %f", score * 1000);
- printf ("\nPress ENTER to exit");
- getchar ();
- pthread_mutex_destroy (&lock_number_of_threads);
- free (array);
- }
- if (mode == 2)
- {
- int size = 100000000, loop, qrand;
- int *array;
- array = (int *) malloc (size * sizeof (int));
- if (array != NULL)
- {
- if ((size * sizeof (int)) < 1000)
- {
- printf ("\n %lu Bytes allocated\n", (size * sizeof (int)));
- }
- else if ((size * sizeof (int)) >= 1000)
- {
- printf ("\n %lu Kilobytes allocated\n",
- ((size * sizeof (int)) / 1000));
- }
- else if ((size * sizeof (int)) >= 1000 * 1000)
- {
- printf ("\n %lu Megabytes allocated\n",
- ((size * sizeof (int)) / 1000 * 1000));
- }
- sleep (1);
- printf ("\nFilling array.\n");
- sleep (3);
- srand ( time(NULL) );
- for (loop = 0; loop < size; loop++)
- {
- qrand = rand () % 20;
- array[loop] = qrand;
- printf ("%d", qrand);
- }
- }
- else
- printf ("\nKein freier Speicher vorhanden.\n");
- printf ("\n\n");
- printf ("\nHeapsort..\n");
- sleep (3);
- clock_t t;
- t = clock ();
- heapsort (array, size);
- for (loop = 0; loop < size; loop++)
- {
- printf ("%d", array[loop]);
- }
- if ((size * sizeof (int)) < 1000)
- {
- printf ("\n %lu Bytes reallocated\n", (size * sizeof (int)));
- }
- else if ((size * sizeof (int)) >= 1000)
- {
- printf ("\n %lu Kilobytes reallocated\n",
- ((size * sizeof (int)) / 1000));
- }
- else if ((size * sizeof (int)) >= 1000 * 1000)
- {
- printf ("\n %lu Megabytes reallocated\n",
- ((size * sizeof (int)) / 1000 * 1000));
- }
- free (array);
- t = clock () - t;
- printf ("Sorting took %f seconds to finish \n", time_taken);
- double score = (sizeof (int) / time_taken);
- printf ("Your total score: %f", score * 1000);
- printf ("\nPress ENTER to exit");
- getchar();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement