Реализация алгоритма
Программа реализует параллельный вариант сортировки чётно-нечётными
перестановками.
Рассмотрим основные этапы реализации.
1. процесс с номером 0 рассылает массив по блокам на все процессы. Каждый
процесс принимает и сортирует свой блок бысторой сортировкой: if
(rank==0) {
int* pArray=arr;
elementsOnProc=elemAmount/procAmount;
for (int
i=0;i < procAmount;i++)
{
MPI_Send(pArray, elementsOnProc, MPI_INT, i, 1,
MPI_COMM_WORLD);
pArray+=elementsOnProc;
}
}
MPI_Recv(buf, BUFL, MPI_INT, 0, 1, MPI_COMM_WORLD,
&status);
MPI_Get_count(&status,MPI_INT,&elementsOnProc);
qsort
(buf, elementsOnProc, sizeof(int),
compare);
MPI_Barrier(MPI_COMM_WORLD);
2. Обмен данными между
процессами и сортировка блоков: for (int j=1;j<=procAmount;j++) {
if (IsOdd(j))//если нечётная перестановка
{
if (IsOdd(rank))//если ранг процесса нечётный
{
MPI_Send(buf,elementsOnProc, MPI_INT, rank-1, 17,
MPI_COMM_WORLD);//шлёт свои данные "левому" соседу
for (int i=0;i <
elementsOnProc;i++) buf[i+elementsOnProc]=buf[i];//переписывает
собственные данные, так, чтобы не затереть их на следующем
шаге
MPI_Recv(buf, elementsOnProc, MPI_INT, rank-1, 17,
MPI_COMM_WORLD,&status);//получает данные "левого" соседа
qsort
(buf, elementsOnProc*2, sizeof(int), compare);//сортирует образовавшийся
удвоенный блок
for (int i=0;i < elementsOnProc;i++)
buf[i]=buf[i+elementsOnProc];//оставляет себе только правую часть
отсотированного массива
}
if
((!IsOdd(rank))&&(rank!=procAmount-1))//если ранг процесса чётный и
это не последний процесс
{
MPI_Send(buf,elementsOnProc, MPI_INT, rank+1, 17,
MPI_COMM_WORLD);//шлёт свои данные "левому" соседу
for (int i=0;i <
elementsOnProc;i++) buf[i+elementsOnProc]=buf[i];
MPI_Recv(buf,
elementsOnProc, MPI_INT, rank+1, 17,
MPI_COMM_WORLD,&status);//получает данные "левого" соседа
qsort
(buf, elementsOnProc*2, sizeof(int), compare);
}
}
if
(!IsOdd(j))//если чётная перестановка
{
if ((IsOdd(rank))&&(rank!=procAmount-1))//если ранг процесса
нечётный и это не последний процесс
{
MPI_Send(buf,elementsOnProc, MPI_INT, rank+1, 17,
MPI_COMM_WORLD);
for (int i=0;i < elementsOnProc;i++)
buf[i+elementsOnProc]=buf[i];
MPI_Recv(buf, elementsOnProc, MPI_INT,
rank+1, 17, MPI_COMM_WORLD,&status);
qsort (buf, elementsOnProc*2,
sizeof(int), compare);
}
if
((!IsOdd(rank))&&(rank!=0))//если ранг процесса чётный и это не
нулевой процесс
{
MPI_Send(buf,elementsOnProc, MPI_INT, rank-1, 17,
MPI_COMM_WORLD);
for (int i=0;i < elementsOnProc;i++)
buf[i+elementsOnProc]=buf[i];
MPI_Recv(buf, elementsOnProc, MPI_INT,
rank-1, 17, MPI_COMM_WORLD,&status);
qsort (buf, elementsOnProc*2,
sizeof(int), compare);
for (int i=0;i < elementsOnProc;i++)
buf[i]=buf[i+elementsOnProc];
}
}
MPI_Barrier(MPI_COMM_WORLD);
} 3.Собираем
отсортированный массив. MPI_Send(buf,elementsOnProc, MPI_INT, 0, 239,
MPI_COMM_WORLD);//каждый процесс шлёт нулевому свои данные if
(rank==0) {
for (int i=0;i < procAmount;i++)
{
MPI_Recv(buf, elementsOnProc, MPI_INT, i, 239,
MPI_COMM_WORLD,&status);//нулевой принимает данные с i-ого
процесса
for (int j=0;j < elementsOnProc;j++)
{arr[i*elementsOnProc+j]=buf[j];}//записывает в свой буфер на нужную
позицию
}
for (int i=0;i < elementsOnProc*procAmount;i++) printf("%d
",arr[i]);//вывод отсортированного массива
}
|
