Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <malloc.h>
- #include <math.h>
- #include <time.h>
- #include "mpi.h"
- #define DEBUG 1
- typedef unsigned char uint8_t;
- typedef signed int int32_t;
- typedef unsigned int uint32_t;
- typedef signed long long int int64_t;
- typedef unsigned long long int uint64_t;
- #define NCASES 5
- uint32_t testCases[NCASES] =
- {
- 100,
- 200,
- 400,
- 800,
- 1600
- };
- #define RANK_MASTER 0
- int32_t maxProcessors, rank;
- void quickSort(int32_t arr[], int32_t left, int32_t right)
- {
- int32_t i = left, j = right, tmp, pivot = arr[left];
- while (i <= j)
- {
- while (arr[i] < pivot) i++;
- while (arr[j] > pivot) j--;
- if (i <= j)
- {
- tmp = arr[i];
- arr[i] = arr[j];
- arr[j] = tmp;
- i++;
- j--;
- }
- }
- if(left < j)
- quickSort(arr, left, j);
- if(i < right)
- quickSort(arr, i, right);
- }
- int32_t **splitArray(int32_t *array, int32_t size, int32_t *piecesToCut, int32_t *mod)
- {
- int32_t pieces = *piecesToCut;
- int32_t piecesPerChunk = size / pieces;
- int32_t i, **result, j, k = 0, numAllocations = pieces + 1;
- *mod = size - piecesPerChunk * pieces;
- if(*mod == 0)
- numAllocations--;
- *piecesToCut = numAllocations;
- result = (int32_t**) malloc( sizeof(int32_t*) * numAllocations);
- for(i = 0; i < numAllocations; i++)
- {
- if(i == numAllocations-1 && (*mod != 0))
- {
- result[i] = (int32_t*) malloc( sizeof(int32_t) * (*mod));
- for(j = 0; j < *mod; j++)
- result[i][j] = array[k++];
- }
- else
- {
- result[i] = (int32_t*) malloc( sizeof(int32_t) * piecesPerChunk);
- for(j = 0; j < piecesPerChunk; j++)
- result[i][j] = array[k++];
- }
- }
- return result;
- }
- int32_t *joinArrays(int32_t **arrays, int32_t size, int32_t piecesPerChunk, int32_t mod, int32_t modIndex)
- {
- int32_t sizeTemp = size;
- if(mod != 0)
- sizeTemp--;
- int32_t *result = (int32_t*) malloc( sizeof(int32_t) * (piecesPerChunk*sizeTemp + mod)), i, j, k = 0;
- for(i = 0; i < size; i++)
- {
- int32_t tempSize = piecesPerChunk;
- if(i == modIndex)
- tempSize = mod;
- for(j = 0; j < tempSize; j++)
- result[k++] = arrays[i][j];
- }
- return result;
- }
- void swapArrays(int32_t **v, int32_t i)
- {
- int32_t *aux;
- aux = v[i];
- v[i] = v[i+1];
- v[i+1] = aux;
- }
- void sortArrays(int32_t **v, int32_t size, int32_t piecesPerChunck, int32_t mod, int32_t *mIndex)
- {
- int32_t i;
- uint8_t swept;
- int32_t sizeOriginal = size;
- int32_t modIndex = sizeOriginal-1;
- do
- {
- size--;
- swept = 0;
- for(i = 0; i < size; i++)
- {
- int32_t sizeTemp = piecesPerChunck;
- if(i+1 == modIndex && mod != 0)
- sizeTemp = mod;
- if(v[i][0] > v[i+1][sizeTemp-1])
- {
- if(sizeTemp == mod)
- modIndex = i;
- swapArrays(v, i);
- swept = 1;
- }
- }
- } while(swept);
- if(mod == 0)
- modIndex = -1;
- *mIndex = modIndex;
- }
- void releaseArrays(int32_t **arrays, int32_t size)
- {
- int32_t i;
- for(i = 0; i < size; i++)
- free(arrays[i]);
- }
- int main(int argc, char* argv[])
- {
- int32_t rc = MPI_Init(&argc, &argv);
- if (rc == MPI_SUCCESS)
- {
- MPI_Comm_size(MPI_COMM_WORLD, &maxProcessors);
- MPI_Comm_rank(MPI_COMM_WORLD, &rank);
- if(rank == RANK_MASTER)
- {
- uint8_t i;
- int32_t *v, j;
- for(i = 0; i < NCASES; i++)
- {
- uint32_t numElements = testCases[i] * 1000, sizeTemp;
- int32_t mod, numArrays = maxProcessors-1, intPieces = maxProcessors-1;
- v = (int32_t*)malloc( sizeof(int32_t) * numElements );
- for(j = 0; j < numElements; j++)
- v[j] = numElements - j;
- int32_t **arrays = splitArray(v, numElements, &numArrays, &mod);
- sizeTemp = (numElements / intPieces);
- int32_t nodeCalcMod = (mod == 0 ? -1 : maxProcessors-1);
- MPI_Bcast(&nodeCalcMod, 1, MPI_INT, RANK_MASTER, MPI_COMM_WORLD);
- for(j = 1; j <= numArrays; j++)
- {
- int32_t destination = j, tagModifier = 0;
- if(j == numArrays && mod != 0)
- {
- sizeTemp = mod;
- destination = j-1;
- tagModifier = 10;
- }
- if(DEBUG >= 3)
- printf("Sent to rank %d, array of size %d to process\n", destination, sizeTemp);
- MPI_Send(&tagModifier, 1, MPI_INT, destination, 1, MPI_COMM_WORLD);
- MPI_Send(&sizeTemp, 1, MPI_UNSIGNED, destination, 10+tagModifier, MPI_COMM_WORLD);
- MPI_Send(arrays[j-1], sizeTemp, MPI_INT, destination, 20+tagModifier, MPI_COMM_WORLD);
- }
- uint64_t processTime = 0, tempTime;
- for(j = 1; j <= numArrays; j++)
- {
- int32_t source = j, tagModifier = 0;
- MPI_Status status;
- if(j == numArrays && mod != 0)
- {
- source = j-1;
- tagModifier = 10;
- }
- MPI_Recv(&sizeTemp, 1, MPI_UNSIGNED, source, 1+tagModifier, MPI_COMM_WORLD, &status);
- MPI_Recv(arrays[j-1], sizeTemp, MPI_INT, source, 2+tagModifier, MPI_COMM_WORLD, &status);
- MPI_Recv(&tempTime, 1, MPI_UNSIGNED_LONG_LONG, source, 3+tagModifier, MPI_COMM_WORLD, &status);
- if(tempTime > processTime)
- processTime = tempTime;
- if(DEBUG >= 3)
- printf("Received sorted array from rank %d with %d elements\n", source, sizeTemp);
- }
- if(DEBUG >= 2)
- {
- printf("\n\n");
- sizeTemp = (numElements / intPieces);
- for(j = 0; j < numArrays; j++)
- {
- int32_t end = sizeTemp-1;
- if(j == numArrays-1 && mod != 0)
- end = mod-1;
- 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);
- }
- }
- int32_t modIndex;
- sortArrays(arrays, numArrays, (numElements / intPieces), mod, &modIndex);
- if(DEBUG >= 2)
- for(j = 0; j < numArrays; j++)
- {
- int32_t end = sizeTemp-1;
- if(j == modIndex)
- end = mod-1;
- 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);
- }
- v = joinArrays(arrays, numArrays, floor(numElements / intPieces), mod, modIndex);
- releaseArrays(arrays, numArrays);
- if(DEBUG)
- printf("\nArray final, first %d, last %d\n", v[0], v[numElements-1]);
- if(DEBUG >= 4)
- for(j = 0; j < numElements; j++)
- printf("%d\n", v[j]);
- //uint32_t clocks = clock();
- //quickSort(v, 0, numElements-1);
- //clocks = clock() - clocks;
- //printf("Vetor de %u elementos ordenado com quicksort sequencial em %u ciclos de clock\n", numElements, clocks);
- 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);
- free(v);
- free(arrays);
- }
- }
- else
- {
- uint32_t i;
- for(i = 0; i < NCASES; i++)
- {
- uint8_t left = 1;
- int32_t nodeCalcMod;
- MPI_Bcast(&nodeCalcMod, 1, MPI_INT, RANK_MASTER, MPI_COMM_WORLD);
- if(nodeCalcMod == rank)
- left++;
- while(left > 0)
- {
- uint32_t size;
- int32_t *array, tagModifier;
- MPI_Status status;
- MPI_Recv(&tagModifier, 1, MPI_INT, RANK_MASTER, 1, MPI_COMM_WORLD, &status);
- MPI_Recv(&size, 1, MPI_UNSIGNED, RANK_MASTER, 10+tagModifier, MPI_COMM_WORLD, &status);
- array = (int32_t*)malloc( sizeof(int32_t) * size);
- MPI_Recv(array, size, MPI_INT, RANK_MASTER, 20+tagModifier, MPI_COMM_WORLD, &status);
- if(DEBUG >= 3)
- printf("Received on rank %d, array of size %d; first %d, last %d, tagModifier %d\n", rank, size, array[0], array[size-1], tagModifier);
- uint64_t clocks = clock();
- quickSort(array, 0, size-1);
- clocks = clock() - clocks;
- MPI_Send(&size, 1, MPI_UNSIGNED, RANK_MASTER, 1+tagModifier, MPI_COMM_WORLD);
- MPI_Send(array, size, MPI_INT, RANK_MASTER, 2+tagModifier, MPI_COMM_WORLD);
- MPI_Send(&clocks, 1, MPI_UNSIGNED_LONG_LONG, RANK_MASTER, 3+tagModifier, MPI_COMM_WORLD);
- if(DEBUG >= 3)
- printf("Sent from rank %d to master the array sorted\n", rank);
- left--;
- }
- }
- }
- MPI_Finalize();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement