Теория и практика параллельных вычислений

         

Функция для выполнения обощенного алгоритма


// Функция для выполнения обощенного алгоритма быстрой сортировки
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;
}
}

Содержание  Назад  Вперед







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий