Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Jun 14th, 2011  |  syntax: C  |  size: 10.10 KB  |  views: 405  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include <math.h>
  4. #include <time.h>
  5. #include "mpi.h"
  6.  
  7. #define DEBUG 1
  8.  
  9. typedef unsigned char uint8_t;
  10. typedef signed int int32_t;
  11. typedef unsigned int uint32_t;
  12. typedef signed long long int int64_t;
  13. typedef unsigned long long int uint64_t;
  14.  
  15. #define NCASES 5
  16.  
  17. uint32_t testCases[NCASES] =
  18. {
  19.     100,
  20.     200,
  21.     400,
  22.     800,
  23.     1600
  24. };
  25.  
  26. #define RANK_MASTER 0
  27.  
  28. int32_t maxProcessors, rank;
  29.  
  30. void quickSort(int32_t arr[], int32_t left, int32_t right)
  31. {
  32.     int32_t i = left, j = right, tmp, pivot = arr[left];
  33.  
  34.     while (i <= j)
  35.     {
  36.         while (arr[i] < pivot) i++;
  37.         while (arr[j] > pivot) j--;
  38.         if (i <= j)
  39.         {
  40.               tmp = arr[i];
  41.               arr[i] = arr[j];
  42.               arr[j] = tmp;
  43.               i++;
  44.               j--;
  45.         }
  46.     }
  47.  
  48.     if(left < j)
  49.         quickSort(arr, left, j);
  50.  
  51.     if(i < right)
  52.         quickSort(arr, i, right);
  53. }
  54.  
  55. int32_t **splitArray(int32_t *array, int32_t size, int32_t *piecesToCut, int32_t *mod)
  56. {
  57.     int32_t pieces = *piecesToCut;
  58.     int32_t piecesPerChunk = size / pieces;
  59.     int32_t i, **result, j, k = 0, numAllocations = pieces + 1;
  60.  
  61.     *mod = size - piecesPerChunk * pieces;
  62.  
  63.     if(*mod == 0)
  64.         numAllocations--;
  65.  
  66.     *piecesToCut = numAllocations;
  67.  
  68.     result = (int32_t**) malloc( sizeof(int32_t*) * numAllocations);
  69.  
  70.     for(i = 0; i < numAllocations; i++)
  71.     {
  72.         if(i == numAllocations-1 && (*mod != 0))
  73.         {
  74.             result[i] = (int32_t*) malloc( sizeof(int32_t) * (*mod));
  75.  
  76.             for(j = 0; j < *mod; j++)
  77.                 result[i][j] = array[k++];
  78.         }
  79.         else
  80.         {
  81.             result[i] = (int32_t*) malloc( sizeof(int32_t) * piecesPerChunk);
  82.  
  83.             for(j = 0; j < piecesPerChunk; j++)
  84.                 result[i][j] = array[k++];
  85.         }
  86.     }
  87.  
  88.  
  89.  
  90.     return result;
  91. }
  92.  
  93. int32_t *joinArrays(int32_t **arrays, int32_t size, int32_t piecesPerChunk, int32_t mod, int32_t modIndex)
  94. {
  95.     int32_t sizeTemp = size;
  96.  
  97.     if(mod != 0)
  98.         sizeTemp--;
  99.  
  100.     int32_t *result = (int32_t*) malloc( sizeof(int32_t) * (piecesPerChunk*sizeTemp + mod)), i, j, k = 0;
  101.  
  102.     for(i = 0; i < size; i++)
  103.     {
  104.         int32_t tempSize = piecesPerChunk;
  105.  
  106.         if(i == modIndex)
  107.             tempSize = mod;
  108.  
  109.         for(j = 0; j < tempSize; j++)
  110.             result[k++] = arrays[i][j];
  111.     }
  112.  
  113.     return result;
  114. }
  115.  
  116. void swapArrays(int32_t **v, int32_t i)
  117. {
  118.     int32_t *aux;
  119.     aux = v[i];
  120.     v[i] = v[i+1];
  121.     v[i+1] = aux;
  122. }
  123.  
  124. void sortArrays(int32_t **v, int32_t size, int32_t piecesPerChunck, int32_t mod, int32_t *mIndex)
  125. {
  126.     int32_t i;
  127.     uint8_t swept;
  128.     int32_t sizeOriginal = size;
  129.     int32_t modIndex = sizeOriginal-1;
  130.  
  131.     do
  132.     {
  133.         size--;
  134.         swept = 0;
  135.  
  136.         for(i = 0; i < size; i++)
  137.         {
  138.             int32_t sizeTemp = piecesPerChunck;
  139.  
  140.             if(i+1 == modIndex && mod != 0)
  141.                 sizeTemp = mod;
  142.  
  143.             if(v[i][0] > v[i+1][sizeTemp-1])
  144.             {
  145.                 if(sizeTemp == mod)
  146.                     modIndex = i;
  147.  
  148.                 swapArrays(v, i);
  149.                 swept = 1;
  150.             }
  151.         }
  152.     } while(swept);
  153.  
  154.     if(mod == 0)
  155.         modIndex = -1;
  156.  
  157.     *mIndex = modIndex;
  158. }
  159.  
  160. void releaseArrays(int32_t **arrays, int32_t size)
  161. {
  162.     int32_t i;
  163.  
  164.     for(i = 0; i < size; i++)
  165.         free(arrays[i]);
  166. }
  167.  
  168. int main(int argc, char* argv[])
  169. {
  170.     int32_t rc = MPI_Init(&argc, &argv);
  171.  
  172.     if (rc == MPI_SUCCESS)
  173.     {
  174.         MPI_Comm_size(MPI_COMM_WORLD, &maxProcessors);
  175.         MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  176.  
  177.         if(rank == RANK_MASTER)
  178.         {
  179.             uint8_t i;
  180.             int32_t *v, j;
  181.  
  182.             for(i = 0; i < NCASES; i++)
  183.             {
  184.                 uint32_t numElements = testCases[i] * 1000, sizeTemp;
  185.                 int32_t mod, numArrays = maxProcessors-1, intPieces = maxProcessors-1;
  186.  
  187.                 v = (int32_t*)malloc( sizeof(int32_t) * numElements );
  188.  
  189.                 for(j = 0; j < numElements; j++)
  190.                     v[j] = numElements - j;
  191.  
  192.                 int32_t **arrays = splitArray(v, numElements, &numArrays, &mod);
  193.  
  194.                 sizeTemp = (numElements / intPieces);
  195.  
  196.                 int32_t nodeCalcMod = (mod == 0 ? -1 : maxProcessors-1);
  197.                 MPI_Bcast(&nodeCalcMod, 1, MPI_INT, RANK_MASTER, MPI_COMM_WORLD);
  198.  
  199.                 for(j = 1; j <= numArrays; j++)
  200.                 {
  201.                     int32_t destination = j, tagModifier = 0;
  202.  
  203.                     if(j == numArrays && mod != 0)
  204.                     {
  205.                         sizeTemp = mod;
  206.                         destination = j-1;
  207.                         tagModifier = 10;
  208.                     }
  209.  
  210.                     if(DEBUG >= 3)
  211.                         printf("Sent to rank %d, array of size %d to process\n", destination, sizeTemp);
  212.  
  213.                     MPI_Send(&tagModifier, 1, MPI_INT, destination, 1, MPI_COMM_WORLD);
  214.                     MPI_Send(&sizeTemp, 1, MPI_UNSIGNED, destination, 10+tagModifier, MPI_COMM_WORLD);
  215.                     MPI_Send(arrays[j-1], sizeTemp, MPI_INT, destination, 20+tagModifier, MPI_COMM_WORLD);
  216.                 }
  217.  
  218.                 uint64_t processTime = 0, tempTime;
  219.  
  220.                 for(j = 1; j <= numArrays; j++)
  221.                 {
  222.                     int32_t source = j, tagModifier = 0;
  223.                     MPI_Status status;
  224.  
  225.                     if(j == numArrays && mod != 0)
  226.                     {
  227.                         source = j-1;
  228.                         tagModifier = 10;
  229.                     }
  230.  
  231.                     MPI_Recv(&sizeTemp, 1, MPI_UNSIGNED, source, 1+tagModifier, MPI_COMM_WORLD, &status);
  232.                     MPI_Recv(arrays[j-1], sizeTemp, MPI_INT, source, 2+tagModifier, MPI_COMM_WORLD, &status);
  233.                     MPI_Recv(&tempTime, 1, MPI_UNSIGNED_LONG_LONG, source, 3+tagModifier, MPI_COMM_WORLD, &status);
  234.  
  235.                     if(tempTime > processTime)
  236.                         processTime = tempTime;
  237.  
  238.                     if(DEBUG >= 3)
  239.                         printf("Received sorted array from rank %d with %d elements\n", source, sizeTemp);
  240.                 }
  241.  
  242.                 if(DEBUG >= 2)
  243.                 {
  244.                     printf("\n\n");
  245.  
  246.                     sizeTemp = (numElements / intPieces);
  247.  
  248.                     for(j = 0; j < numArrays; j++)
  249.                     {
  250.                         int32_t end = sizeTemp-1;
  251.  
  252.                         if(j == numArrays-1 && mod != 0)
  253.                             end = mod-1;
  254.  
  255.                         printf("Array of index %d starts in %d and ends in %d, end is %d, mod %d, numarrays %d\n", j, arrays[j][0], arrays[j][end], end, mod, numArrays);
  256.                     }
  257.                 }
  258.  
  259.                 int32_t modIndex;
  260.                 sortArrays(arrays, numArrays, (numElements / intPieces), mod, &modIndex);
  261.  
  262.                 if(DEBUG >= 2)
  263.                     for(j = 0; j < numArrays; j++)
  264.                     {
  265.                         int32_t end = sizeTemp-1;
  266.  
  267.                         if(j == modIndex)
  268.                             end = mod-1;
  269.  
  270.                         printf("2 Array of index %d starts in %d and ends in %d, end is %d\n", j, arrays[j][0], arrays[j][end], end);
  271.                     }
  272.  
  273.                 v = joinArrays(arrays, numArrays, floor(numElements / intPieces), mod, modIndex);
  274.  
  275.                 releaseArrays(arrays, numArrays);
  276.  
  277.                 if(DEBUG)
  278.                     printf("\nArray final, first %d, last %d\n", v[0], v[numElements-1]);
  279.  
  280.                 if(DEBUG >= 4)
  281.                     for(j = 0; j < numElements; j++)
  282.                         printf("%d\n", v[j]);
  283.  
  284.  
  285.                 //uint32_t clocks = clock();
  286.                 //quickSort(v, 0, numElements-1);
  287.                 //clocks = clock() - clocks;
  288.  
  289.                 //printf("Vetor de %u elementos ordenado com quicksort sequencial em %u ciclos de clock\n", numElements, clocks);
  290.  
  291.                 printf("Vetor de %u elementos ordenado com quicksort em paralelo (%d threads). \nDentre o tempo de processamento de cada node, o maior foi %llu, %.2f seconds.\n\n", numElements, maxProcessors-1, processTime, (float)processTime/CLOCKS_PER_SEC);
  292.  
  293.                 free(v);
  294.                 free(arrays);
  295.             }
  296.         }
  297.         else
  298.         {
  299.             uint32_t i;
  300.             for(i = 0; i < NCASES; i++)
  301.             {
  302.                 uint8_t left = 1;
  303.                 int32_t nodeCalcMod;
  304.                 MPI_Bcast(&nodeCalcMod, 1, MPI_INT, RANK_MASTER, MPI_COMM_WORLD);
  305.  
  306.                 if(nodeCalcMod == rank)
  307.                     left++;
  308.  
  309.                 while(left > 0)
  310.                 {
  311.                     uint32_t size;
  312.                     int32_t *array, tagModifier;
  313.                     MPI_Status status;
  314.  
  315.                     MPI_Recv(&tagModifier, 1, MPI_INT, RANK_MASTER, 1, MPI_COMM_WORLD, &status);
  316.  
  317.                     MPI_Recv(&size, 1, MPI_UNSIGNED, RANK_MASTER, 10+tagModifier, MPI_COMM_WORLD, &status);
  318.  
  319.                     array = (int32_t*)malloc( sizeof(int32_t) * size);
  320.  
  321.                     MPI_Recv(array, size, MPI_INT, RANK_MASTER, 20+tagModifier, MPI_COMM_WORLD, &status);
  322.  
  323.                     if(DEBUG >= 3)
  324.                         printf("Received on rank %d, array of size %d; first %d, last %d, tagModifier %d\n", rank, size, array[0], array[size-1], tagModifier);
  325.  
  326.                     uint64_t clocks = clock();
  327.                     quickSort(array, 0, size-1);
  328.                     clocks = clock() - clocks;
  329.  
  330.                     MPI_Send(&size, 1, MPI_UNSIGNED, RANK_MASTER, 1+tagModifier, MPI_COMM_WORLD);
  331.                     MPI_Send(array, size, MPI_INT, RANK_MASTER, 2+tagModifier, MPI_COMM_WORLD);
  332.                     MPI_Send(&clocks, 1, MPI_UNSIGNED_LONG_LONG, RANK_MASTER, 3+tagModifier, MPI_COMM_WORLD);
  333.  
  334.                     if(DEBUG >= 3)
  335.                         printf("Sent from rank %d to master the array sorted\n", rank);
  336.  
  337.                     left--;
  338.                 }
  339.             }
  340.         }
  341.  
  342.         MPI_Finalize();
  343.     }
  344.  
  345.     return 0;
  346. }
clone this paste RAW Paste Data