Теория и практика параллельных вычислений
Функция для выполнения обощенного алгоритма
|
// Функция для выполнения обощенного алгоритма быстрой сортировки void ParallelHyperQuickSort ( double *pProcData, int ProcDataSize) { MPI_Status status; int CommProcRank; // Ранг процессора, с которым выполняется // взаимодействие double *pData, // Часть блока, остающаяся на процессоре *pSendData, // Часть блока, передаваемая процессору // CommProcRank *pRecvData, // Часть блока, получаемая от процессора // CommProcRank *pMergeData; // Блок данных, получаемый после слияния int DataSize, SendDataSize, RecvDataSize, MergeDataSize; int HypercubeDim = (int)ceil(log(ProcNum)/log(2)); // размерность гиперкуба int Mask = ProcNum; double Pivot; // Первоначальная сортировка блоков данных на каждом процессоре LocalDataSort(pProcData, ProcDataSize); // Итерации обобщенной быстрой сортировки for (int i = HypercubeDim; i > 0; i-- ) { // Определение ведущего значения и его рассылка всем процессорам PivotDistribution(pProcData, ProcDataSize, HypercubeDim, Mask, i,&Pivot); Mask = Mask >> 1; // Определение границы разделения блока int pos = GetProcDataDivisionPos(pProcData, ProcDataSize, Pivot); // Разделение блока на части if ( ( (rank & Mask) >> (i - 1) ) == 0 ) { // старший бит = 0 pSendData = &pProcData[pos + 1]; SendDataSize = ProcDataSize - pos – 1; if (SendDataSize < 0) SendDataSize = 0; CommProcRank = ProcRank + Mask pData = &pProcData[0]; DataSize = pos + 1; } else { // старший бит = 1 pSendData = &pProcData[0]; SendDataSize = pos + 1; if (SendDataSize > ProcDataSize) SendDataSize = pos; CommProcRank = ProcRank – Mask pData = &pProcData[pos + 1]; DataSize = ProcDataSize - pos - 1; if (DataSize < 0) DataSize = 0; } // Пересылка размеров частей блоков данных MPI_Sendrecv(&SendDataSize, 1, MPI_INT, CommProcRank, 0, &RecvDataSize, 1, MPI_INT, CommProcRank, 0, MPI_COMM_WORLD, &status); // Пересылка частей блоков данных pRecvData = new double[RecvDataSize]; MPI_Sendrecv(pSendData, SendDataSize, MPI_DOUBLE, CommProcRank, 0, pRecvData, RecvDataSize, MPI_DOUBLE, CommProcRank, 0, MPI_COMM_WORLD, &status); // Слияние частей MergeDataSize = DataSize + RecvDataSize; pMergeData = new double[MergeDataSize]; DataMerge(pMergeData, pMergeData, pData, DataSize, pRecvData, RecvDataSize); delete [] pProcData; delete [] pRecvData; pProcData = pMergeData; ProcDataSize = MergeDataSize; } } |
| Пример 9.1. |
| Закрыть окно |
// Функция для выполнения обощенного алгоритма быстрой сортировки
void ParallelHyperQuickSort ( double *pProcData,
int ProcDataSize) {
MPI_Status status;
int CommProcRank; // Ранг процессора, с которым выполняется
// взаимодействие
double *pData, // Часть блока, остающаяся на процессоре
*pSendData, // Часть блока, передаваемая процессору
// CommProcRank
*pRecvData, // Часть блока, получаемая от процессора
// CommProcRank
*pMergeData; // Блок данных, получаемый после слияния
int DataSize, SendDataSize, RecvDataSize, MergeDataSize;
int HypercubeDim = (int)ceil(log(ProcNum)/log(2));
// размерность гиперкуба
int Mask = ProcNum;
double Pivot;
// Первоначальная сортировка блоков данных на каждом процессоре
LocalDataSort(pProcData, ProcDataSize);
// Итерации обобщенной быстрой сортировки
for (int i = HypercubeDim; i > 0; i-- ) {
// Определение ведущего значения и его рассылка всем процессорам
PivotDistribution(pProcData, ProcDataSize, HypercubeDim,
Mask, i,&Pivot);
Mask = Mask >> 1;
// Определение границы разделения блока
int pos = GetProcDataDivisionPos(pProcData, ProcDataSize, Pivot);
// Разделение блока на части
if ( ( (rank & Mask) >> (i - 1) ) == 0 ) { // старший бит = 0
pSendData = &pProcData[pos + 1];
SendDataSize = ProcDataSize - pos – 1;
if (SendDataSize < 0) SendDataSize = 0;
CommProcRank = ProcRank + Mask
pData = &pProcData[0];
DataSize = pos + 1;
}
else { // старший бит = 1
pSendData = &pProcData[0];
SendDataSize = pos + 1;
if (SendDataSize > ProcDataSize) SendDataSize = pos;
CommProcRank = ProcRank – Mask
pData = &pProcData[pos + 1];
DataSize = ProcDataSize - pos - 1;
if (DataSize < 0) DataSize = 0;
}
// Пересылка размеров частей блоков данных
MPI_Sendrecv(&SendDataSize, 1, MPI_INT, CommProcRank, 0,
&RecvDataSize, 1, MPI_INT, CommProcRank, 0, MPI_COMM_WORLD, &status);
// Пересылка частей блоков данных
pRecvData = new double[RecvDataSize];
MPI_Sendrecv(pSendData, SendDataSize, MPI_DOUBLE,
CommProcRank, 0, pRecvData, RecvDataSize, MPI_DOUBLE,
CommProcRank, 0, MPI_COMM_WORLD, &status);
// Слияние частей
MergeDataSize = DataSize + RecvDataSize;
pMergeData = new double[MergeDataSize];
DataMerge(pMergeData, pMergeData, pData, DataSize,
pRecvData, RecvDataSize);
delete [] pProcData;
delete [] pRecvData;
pProcData = pMergeData;
ProcDataSize = MergeDataSize;
}
}
