Практическая часть

Расчет производиться для массивов размеров 10000, 30000, 50000, 70000, 100000.

Ниже представлен код, реализующий алгоритм в соответствии с поставленной задачей:

Реализация с использованием MPI:

Программный код файла main.с

#include <stdio.h>

#include <stdlib.h>

#include <mpi.h>

#include "utils.h"

#include "g2draw.h"

#define QTY_ARRAY_SIZE 5

int main(int argc, char ** argv)

{

int qtyArray[ QTY_ARRAY_SIZE ] = { 10000, 30000, 50000, 70000, 100000 };

double timeArray[ QTY_ARRAY_SIZE ];

int procRank, procGroupSize;

MPI_Init(&argc, &argv);

MPI_Comm_size(MPI_COMM_WORLD, &procGroupSize);

MPI_Comm_rank(MPI_COMM_WORLD, &procRank);

int i = 0;

for ( ; i < QTY_ARRAY_SIZE; ++i )

{

double sortTime = quickSortMPI( procGroupSize, procRank, qtyArray[i] );

if ( procRank == 0 )

{

timeArray[i] = sortTime;

printf("Time required was %lf seconds for %d.\n", timeArray[i], qtyArray[i] );

}

}

if ( procRank == 0 )

{

draw_result( qtyArray, timeArray, QTY_ARRAY_SIZE, procGroupSize );

}

MPI_Finalize();

return 0;

}

Программный код файла utils.* (Функции для расчета)

#include "../qs_mpi/utils.h"

#include <stdlib.h>

#include <stdio.h>

#include <mpi.h>

void quicksort(int * arr, int lo, int hi)

{

if(lo < hi)

{

int p = partition(arr, lo, hi);

quicksort(arr, lo, p - 1);

quicksort(arr, p + 1, hi);

}

}

int partition(int * arr, int lo, int hi)

{

int pivotIdx = choosePivot(arr, lo, hi);

int pivotVal = arr[pivotIdx];

swap(&arr[pivotIdx], &arr[hi]);

int storeIdx = lo;

int i = lo;

for( ; i < hi; i++)

{

if(arr[i] < pivotVal)

{

swap(&arr[i], &arr[storeIdx]);

storeIdx++;

}

}

swap(&arr[storeIdx], &arr[hi]);

return storeIdx;

}

void swap(int * x, int * y)

{

int temp = *x;

*x = *y;

*y = temp;

}

int choosePivot(int * arr, int lo, int hi)

{

int mid = (lo+hi)/2;

if( arr[lo] > arr[hi] )

{

int temp = lo;

lo = hi;

hi = temp;

}

if( arr[lo] > arr[mid] )

{

int temp = mid;

mid = lo;

lo = temp;

}

if( arr[mid] > arr[hi] )

{

int temp = mid;

mid = hi;

hi = temp;

}

return mid;

}

void showarray( int* arr, int size, const char* msg, int rank)

{

printf("%s (process = %d): ", msg, rank);

int i = 0;

for( ; i < size; i++)

{

printf("%d ", arr[i]);

}

printf("\n");

}

void showarrayidx( int* arr, int lowIdx, int highIdx, const char* msg, int rank)

{

printf("%s (process = %d): from %d to %d = ", msg, rank, lowIdx, highIdx);

int i = lowIdx;

for( ; i < highIdx; i++)

{

printf("%d ", arr[i]);

}

printf("\n");

}

void fillarray( int* arr, int size, int rank)

{

srand(123456 + 10000*rank);

int i = 0;

for( ; i < size; i++)

{

arr[i] = -1000 + rand()%RANGE;

}

}

int getPivotIdx( int * arr, int arrSize, int pivot)

{

int storePivotIdx = 0;

int i = 0;

for( ; i < arrSize; i++)

{

if (arr[i] < pivot )

{

swap(&arr[i], &arr[storePivotIdx]);

storePivotIdx++;

}

}

return storePivotIdx;

}

int *mergeArrWithRecvUpper(int *arr, int *recvBuff, int recvSize, int storePivotIdx, int *newArrSize)

{

int* newArr = (int *) malloc(sizeof(int)*( recvSize + storePivotIdx ));

int i = 0;

for( ; i < storePivotIdx; i++)

newArr[i] = arr[i];

int j = 0;

for( i = storePivotIdx; i < recvSize + storePivotIdx; i++, j++)

newArr[i] = recvBuff[j];

free((void *) arr);

arr = newArr;

newArr = 0;

*newArrSize = recvSize + storePivotIdx;

return arr;

}

int *mergeArrWithRecvLower(int *arr, int *recvBuff, int recvSize, int storePivotIdx, int *newArrSize)

{

int* newArr = (int *) malloc(sizeof(int)*( recvSize + ( *newArrSize - storePivotIdx)));

int j = 0;

int i = storePivotIdx;

for( ; i < *newArrSize; i++, j++)

{

newArr[j] = arr[i];

}

for(j = 0, i = *newArrSize - storePivotIdx; i < recvSize + ( *newArrSize - storePivotIdx); i++, j++)

{

newArr[i] = recvBuff[j];

}

free((void *) arr);

arr = newArr;

newArr = 0;

*newArrSize = recvSize + ( *newArrSize - storePivotIdx);

return arr;

}

int *getRecvArray(int *recvBuffer, int recvSize, int source, int tag)

{

free((void *) recvBuffer);

recvBuffer = (int *) malloc(sizeof(int)*recvSize);

MPI_Request request;

MPI_Status status;

MPI_Irecv( recvBuffer, recvSize, MPI_INT, source, tag, MPI_COMM_WORLD, &request);

MPI_Wait(&request, &status);

return recvBuffer;

}

int arraysorttest( int* arr, int size)

{

int i = 1;

for( ; i < size; i++)

{

if ( arr[i -1] > arr[i])

{

return 0;

}

}

return 1;

}

double quickSortMPI(const int size, const int rank, const int arrsize)

{

int finalArraySize = arrsize;

int * arr = (int *) malloc(sizeof(int) * finalArraySize/size);

int * recvBuffer = (int *) malloc(sizeof(int) * finalArraySize/size);

fillarray( arr, finalArraySize/size, rank);

quicksort( arr, 0, finalArraySize/size - 1);

double start, end;

MPI_Status status;

int pivot;

if(rank == 0)

{

start = MPI_Wtime();

pivot = choosePivot(arr, 0, finalArraySize/size-1);

}

MPI_Bcast(&pivot, 1, MPI_INT, 0, MPI_COMM_WORLD);

int storePivotIdx = 0;

int arrSize = finalArraySize/size;

int partner, recvSize;

for( partner = size/2; partner > 0; partner = partner >> 1)

{

storePivotIdx = getPivotIdx( arr, arrSize, pivot);

MPI_Request request, requestSend;

if ( (rank / partner) % 2 == 0 )

{

int upperPivotArrSize = arrSize - storePivotIdx;

MPI_Isend(&upperPivotArrSize, 1, MPI_INT, rank+partner, partner+size, MPI_COMM_WORLD, &requestSend);

recvSize = 0;

MPI_Irecv(&recvSize, 1, MPI_INT, rank+partner, partner+size, MPI_COMM_WORLD, &request);

MPI_Wait(&request, &status);

if ( upperPivotArrSize > 0)

{

MPI_Isend( arr + storePivotIdx, upperPivotArrSize, MPI_INT, rank + partner, partner,MPI_COMM_WORLD, &requestSend);

}

if ( recvSize > 0 )

{

recvBuffer = getRecvArray( recvBuffer, recvSize, rank + partner, partner);

}

}

else

{

int lowerPivotArrSize = storePivotIdx;

MPI_Isend(&lowerPivotArrSize, 1, MPI_INT, rank-partner, partner+size, MPI_COMM_WORLD, &requestSend);

recvSize = 0;

MPI_Irecv(&recvSize, 1, MPI_INT, rank-partner, partner+size, MPI_COMM_WORLD, &request);

MPI_Wait(&request, &status);

if ( storePivotIdx > 0 )

{

MPI_Isend( arr, lowerPivotArrSize, MPI_INT, rank - partner, partner, MPI_COMM_WORLD, &requestSend);

}

if ( recvSize > 0 )

{

recvBuffer = getRecvArray( recvBuffer, recvSize, rank - partner, partner);

}

}

MPI_Barrier(MPI_COMM_WORLD);

if(recvSize > 0)

{

if((rank / partner) % 2 == 0)

{

arr = mergeArrWithRecvUpper( arr, recvBuffer, recvSize, storePivotIdx, &arrSize );

}

else

{

arr = mergeArrWithRecvLower( arr, recvBuffer, recvSize, storePivotIdx, &arrSize );

}

}

else

{

arrSize = 0;

}

if(rank % partner == 0)

{

pivot = choosePivot(arr, 0, arrSize-1);

int i = 1;

for( ; i < partner; i++)

{

MPI_Send(&pivot, 1, MPI_INT, rank+i, partner+1, MPI_COMM_WORLD);

}

}

else

{

MPI_Recv(&pivot, 1, MPI_INT, partner*(rank/partner), partner+1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);

}

}

if(arrSize > 0)

{

quicksort(arr, 0, arrSize-1);

}

int * sizeArr, * fullArr, * displacement;

if(rank == 0)

{

sizeArr = (int *) malloc(sizeof(int)*size);

fullArr = (int *) malloc(sizeof(int)* finalArraySize);

displacement = (int *) malloc(sizeof(int)*size);

}

MPI_Gather(&arrSize, 1, MPI_INT, sizeArr, 1, MPI_INT, 0, MPI_COMM_WORLD);

if ( rank == 0 )

{

int i = 0;

displacement[0] = 0;

for(i = 1; i < size; i++)

{

displacement[i] = sizeArr[i-1] + displacement[i-1];

}

}

MPI_Gatherv(arr, arrSize, MPI_INT, fullArr, sizeArr, displacement, MPI_INT, 0, MPI_COMM_WORLD);

MPI_Barrier(MPI_COMM_WORLD);

if ( arrSize > 0 )

{

free((void *) arr);

}

if ( rank == 0 )

{

printf("Final Array with size %d test return %s. \n", finalArraySize, (arraysorttest( fullArr, finalArraySize)) ? "SUCCESS" : "FAIL");

end = MPI_Wtime();

free((void *) fullArr);

free((void *) sizeArr);

free((void *) displacement);

}

return end-start;

}

Программный код файла g2draw.*( функции для рисования графика времени расчета от размера массива).

#include "g2draw.h"

#include <stdio.h>

#include <g2.h>

#include <g2_X11.h>

#define NUMBERS_NUM 10

typedef char char7[7];

double getUpperBound( double value );

double getMaxValue( double* arr, int arrSize);

void generateXNumbers( int xBound, char7* xNumbers );

void generateYNumbers( double yBound, char7* yNumbers );

void coordinatePlane(int window, char7* xNumbers, char7* yNumbers, int plotXSize, int plotYSize, int plotXMargin, int plotYMargin);

void pointsOnPlane(int window, int* xValues, double* yValues, int valuesQty, int x0, int y0, double xScale, double yScale);

void draw_result(int* xValues, double* yValues, int valuesQty, int processQty)

{

const int plotXSize = 500; // points

const int plotYSize = 500; // points

const int plotXMargin = 50;

const int plotYMargin = 50;

int window = g2_open_X11( plotXSize + 2*plotXMargin, plotYSize + 2*plotYMargin );

const int maxXValue = xValues[ valuesQty - 1];

char7 xNumbers[ NUMBERS_NUM ];

generateXNumbers( maxXValue, xNumbers );

double maxYValue = getUpperBound( getMaxValue( yValues, valuesQty ) );

char7 yNumbers[ NUMBERS_NUM ];

generateYNumbers( maxYValue, yNumbers );

coordinatePlane(window, xNumbers, yNumbers, plotXSize, plotYSize, plotXMargin, plotYMargin);

double xScale = (double)plotXSize/(double)maxXValue;

double yScale = (double)plotYSize/maxYValue;

pointsOnPlane(window, xValues, yValues, valuesQty, plotXMargin, plotXMargin, xScale, yScale);

char title[ 64 ];

sprintf( title, "MPI QuickSort result (%d process)", processQty);

g2_string(window,200, 5, title);

getchar();

g2_close(window);

}

void coordinatePlane(int window, char7* xNumbers, char7* yNumbers, int plotXSize, int plotYSize, int plotXMargin, int plotYMargin)

{

int x0 = plotXMargin;

int y0 = plotYMargin;

int X = plotXSize;

int Y = plotYSize;

int dx = plotXSize/ NUMBERS_NUM;

int dy = plotYSize/ NUMBERS_NUM;

int rx = 5;

int ry = 5;

int i = y0;

int k = -1;

for ( ; i <= Y + y0 ; i += dy, ++k)

{

g2_line(window,x0-rx,i,x0+X,i); //

if ( k == -1 )

{

g2_string(window,x0/4,i, "0");

}

else

{

g2_string(window,x0/4,i, yNumbers[ k ]); // y-axis numbers

}

}

g2_line(window,x0,y0,x0,y0+Y); // y-axis

g2_string(window,50, 570, "Time(sec.)");

int j = y0;

k = -1;

for ( ; j <= X + x0 ; j += dx, ++k)

{

g2_line(window,j,y0-ry,j,y0); // horizontal lines with marks; for j = y0 - x-axis

if ( k == -1 )

{

g2_string(window, (j == y0) ? j : (j - dx/4) , y0/2, "0");

}

else

{

g2_string(window, (j == y0) ? j : (j - dx/4) , y0/2, xNumbers[ k ]);

}

}

g2_string(window,470, 10, "Sorted array size");

}

void pointsOnPlane(int window, int* xValues, double* yValues, int valuesQty, int x0, int y0, double xScale, double yScale)

{

g2_pen(window, 3);

int prevX = 0;

int prevY = 0;

int i = 0;

for ( ; i < valuesQty; ++i)

{

int x = (double) xValues[i] * xScale;

int y = yValues[i] * yScale;

g2_filled_circle(window, x0 + x, y0 + y, 2);

if ( i > 0 )

{

g2_line(window,x0 + prevX, y0 + prevY, x0 + x, y0 + y );

}

prevX = x;

prevY = y;

}

}

double getMaxValue( double* arr, int arrSize)

{

double result = arr[0];

int i = 1;

for (; i < arrSize; ++i )

{

if ( result < arr[i] )

{

result = arr[i];

}

}

return result;

}

double getUpperBound( double value )

{

int deg = 0;

if ( value > 10 )

{

while( value < 10. && value > 0.1 )

{

value /= 10.;

deg++;

}

}

else if ( value < 1.)

{

while( value < 1. )

{

value *= 10.;

deg--;

}

deg++;

}

else

{

deg = 1;

}

double mult = ( value > 5. ) ? 1. : .5;

return mult*pow( 10., deg);

}

void generateXNumbers( int xBound, char7* xNumbers )

{

int i = 0;

int dx = xBound/NUMBERS_NUM;

for ( ; i < NUMBERS_NUM; ++i )

{

sprintf( xNumbers[i], "%d", (i+1)*dx);

}

return ;

}

void generateYNumbers( double yBound, char7* yNumbers )

{

int i = 0;

double dy = yBound/NUMBERS_NUM;

for ( ; i < NUMBERS_NUM; ++i )

{

sprintf( yNumbers[i], "%1.3f", (i+1)*dy);

}

return ;

}

Протестируем разработанный параллельный алгоритм, вычислив ускорение и эффективность работы алгоритма в зависимости от размера матрицы.

Ускорением параллельного алгоритма называют отношение времени выполнения лучшего последовательного алгоритмам к времени выполнения параллельного алгоритма:

???? = ???? / ????????

???? − время работы последовательного алгоритма

???????? − время работы параллельного алгоритма

Параллельный алгоритм может давать большое ускорение, но использовать для этого множество процессов неэффективно.

Для оценки масштабируемости параллельного алгоритма используется понятие эффективности:

???? = ???? / ????

???? − ускорение ???? − количество процессоров.

Таблица 1 – Результаты вычислительных экспериментов

Рисунок 2 – Зависимость времени выполнения от размера массива

Рисунок 3– Зависимость ускорения от размера массива

Рисунок 4 – Зависимость эффективности от размера массива

Реализация с использованием OpenMP

Программный код файла main.с

#include "g2draw.h"

#include "utils.h"

#include <stdio.h>

#define THREAD_QTY 8

#define ARRAY_SIZES_NUM 5

int main()

{

int sortArraySizes[ARRAY_SIZES_NUM] = { 10000, 30000, 50000, 70000, 100000 };

int threadNum[ THREAD_QTY ] = { 1,2,3,4,5,6,7,8 };

double result[ARRAY_SIZES_NUM][THREAD_QTY];

int k = 0;

for ( ; k < ARRAY_SIZES_NUM; ++k)

{

result[k][0] = serialsortarray( sortArraySizes[k] );

int j = 2;

for ( ; j <= THREAD_QTY ; ++j)

{

result[k][j - 1] = sortarray( sortArraySizes[k], j );

}

}

draw_result( threadNum, THREAD_QTY, result, ARRAY_SIZES_NUM, sortArraySizes);

}

Программный код файла utils.* (Функции для расчета)

#include "utils.h"

#include <omp.h>

#include <stdio.h>

#include <stdlib.h>

void quicksort(int arr[], int low_index, int high_index, int thread_num)

{

int j;

if(low_index < high_index)

{

j = partition(arr, low_index, high_index);

#pragma omp parallel sections num_threads(thread_num)

{

#pragma omp section

{

quicksort(arr, low_index, j - 1, thread_num);

}

#pragma omp section

{

quicksort(arr, j + 1, high_index, thread_num);

}

}

}

}

void serialquicksort(int arr[], int low_index, int high_index)

{

int j;

if(low_index < high_index)

{

j = partition(arr, low_index, high_index);

serialquicksort(arr, low_index, j - 1);

serialquicksort(arr, j + 1, high_index);

}

}

void swap(int * x, int * y)

{

int temp = *x;

*x = *y;

*y = temp;

}

int choosePivot(int * arr, int lo, int hi)

{

int mid = (lo+hi)/2;

if (arr[lo] > arr[hi] )

{

int temp = lo;

lo = hi;

hi = temp;

}

if( arr[lo] > arr[mid] )

{

int temp = mid;

mid = lo;

lo = temp;

}

if( arr[mid] > arr[hi] )

{

int temp = mid;

mid = hi;

hi = temp;

}

return mid;

}

int partition(int * arr, int lo, int hi)

{

int pivotIdx = choosePivot(arr, lo, hi);

int pivotVal = arr[pivotIdx];

swap(&arr[pivotIdx], &arr[hi]);

int storeIdx = lo;

int i;

for(i = lo; i < hi; i++)

{

if(arr[i] < pivotVal)

{

swap(&arr[i], &arr[storeIdx]);

storeIdx++;

}

}

swap(&arr[storeIdx], &arr[hi]);

return storeIdx;

}

int* generatearray(const int size)

{

srand( time(NULL) );

int* array = (int*) malloc( size * sizeof(int) );

int index = 0;

for ( ;index < size; ++index)

{

array[index] = LOWER_BAND + rand() % (UPPER_BAND - LOWER_BAND);

}

return array;

}

void purgearray(int* arr)

{

free( arr );

}

void showarray(int arr[], int size)

{

int i = 0;

for( ;i < size;i++)

{

printf("%d\t",arr[i]);

}

}

void showDoubleArray(double arr[], int size)

{

int i = 0;

for( ;i < size;i++)

{

printf("%f\t",arr[i]);

}

}

double sortarray( int size, int thread_num)

{

int* arr = generatearray( size );

double start_time = omp_get_wtime();

quicksort ( arr, 0, size - 1, thread_num);

double end_time = omp_get_wtime();

double elapsed = end_time - start_time;

if ( checkarray( arr, size) )

{

printf("Array size %d thread num %d: time = %g seconds.\n", size, thread_num, elapsed);

}

else

{

printf("Array size %d thread num %d: sort failed!\n", size, thread_num);

}

purgearray( arr );

return elapsed;

}

double serialsortarray( int size)

{

int* arr = generatearray( size );

double start_time = omp_get_wtime();

serialquicksort ( arr, 0, size - 1);

double end_time = omp_get_wtime();

purgearray( arr );

printf("Array size %d: time = %g seconds.\n", size, end_time - start_time);

return end_time - start_time;

}

int checkarray(int arr[], int size)

{

int i = 1;

for( ;i < size ;i++)

{

if ( arr[i - 1] > arr[i] )

{

return 0;

}

}

return 1;

}

Программный код файла g2draw.*( функции для рисования графика времени расчета от размера массива).

#include "g2draw.h"

#include <stdio.h>

#include <g2.h>

#include <g2_X11.h>

#include <math.h>

#define NUMBERS_NUM 10

typedef char char7[7];

double getUpperBound( double value );

double getMaxValue( double* arr, int arrSize);

void generateXNumbers( int xBound, char7* xNumbers );

void generateYNumbers( double yBound, char7* yNumbers );

void coordinatePlane(int window, char7* xNumbers, char7* yNumbers, int plotXSize, int plotYSize, int plotXMargin, int plotYMargin);

void pointsOnPlane(int window, int* xValues, double* yValues, int valuesQty, int x0, int y0, double xScale, double yScale, int color, const char* title);

void draw_result(int* xValues, int xValuesQty, double* yValues, int yValuesQty, int* categoryValues)

{

const int plotXSize = 500; // points

const int plotYSize = 500; // points

const int plotXMargin = 50;