int rank;//номер процесса
int size;//число процессов
int n;//число элементов
int xx;
int *buffer;//буфер для рассылки данных
int *data;//данные для параллельного вычисления
int *data1;//данные для последовательного вычисления
int *mybuf;//буфер для алгоритма
double start, finish, time1, time2;
//Инициализация
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &size);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Barrier(MPI_COMM_WORLD);
int *count = new int[size];
srand((unsigned)time(0));
//Ввод
if (rank == 0) {
do {
printf("Enter n: ");
scanf("%d", &n);
data = new int[n];
data1 = new int[n];
}
while (n <= 0);
if (n < 30)
for (int i = 0; i < n; i++) {
printf("Element %d is: ",i);
scanf("%d", &data[i]);
data1[i] = data[i];
}
else {
printf("Generating %d randoms\n", n);
for (int i = 0; i < n; i++) {
data[i]= rand()%100-50;
data1[i] = data[i];
}
printf("%d randoms generated\n", n);
}
}
start = MPI_Wtime();

//Рассылка n
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
//Вычисление count[]
for (int i = 0; i <= size-2; i++)
count[i] = n/size;
count[size-1] = n - (size-1)*count[size-2];

//Выделение памяти под буфер
buffer = new int[20*n];
MPI_Buffer_attach(buffer,20*n);
mybuf = new int[n];

//Рассылка данных
if (rank == 0) {
xx = 0;
for (int i = 0; i < size; i++){
MPI_Bsend(data+xx, count[i], MPI_INT, i, DATA_TO_PROC, MPI_COMM_WORLD);
xx = xx + count[i];
}
}

//Получение данных
MPI_Recv(mybuf, n, MPI_INT, 0, DATA_TO_PROC, MPI_COMM_WORLD,&status);

//Сортируем блоки
xx = count[rank]-1;
mergeSort(mybuf, 0, xx);
MPI_Barrier(MPI_COMM_WORLD);

//Фазы алгоритма чет-нечет
for (int i = 1; i < size; i++) {
if (i%2 == 0){
if (rank%2 == 1) {
if (rank != (size-1)){
MPI_Bsend(mybuf,count[rank], MPI_INT, rank+1, SEND, MPI_COMM_WORLD);
for (int j = 0; j < count[rank+1]; j++)
mybuf[j+count[rank+1]] = mybuf[j];
MPI_Recv(mybuf, count[rank+1], MPI_INT, rank+1, SEND, MPI_COMM_WORLD,&status);
xx = (count[rank]+count[rank+1])-1;
mergeSort(mybuf, 0, xx);
}
}
if (rank%2 == 0) {
if (rank != 0){
MPI_Bsend(mybuf,count[rank], MPI_INT, rank-1, SEND, MPI_COMM_WORLD);
for (int j = 0; j < count[rank-1]; j++)
mybuf[j+count[rank-1]] = mybuf[j];
MPI_Recv(mybuf, count[rank-1], MPI_INT, rank-1, SEND, MPI_COMM_WORLD,&status);
xx = (count[rank]+count[rank-1])-1;
mergeSort(mybuf, 0, xx);
for (int j = 0; j < count[rank-1]; j++) mybuf[j] = mybuf[j+count[rank-1]];
}
}
}
if (i%2 == 1) {
if (rank%2 == 1)
{ MPI_Bsend(mybuf,count[rank], MPI_INT, rank-1, SEND, MPI_COMM_WORLD);
for (int j = 0; j < count[rank-1]; j++) mybuf[j+count[rank-1]] = mybuf[j];
MPI_Recv(mybuf, count[rank-1], MPI_INT, rank-1, SEND, MPI_COMM_WORLD,&status);
xx = (count[rank]+count[rank-1])-1;
mergeSort(mybuf, 0, xx);
for (int j = 0; j < count[rank-1]; j++) mybuf[j] = mybuf[j+count[rank-1]];
}
if (rank%2 == 0) {
if (rank != (size-1)){
MPI_Bsend(mybuf,count[rank], MPI_INT, rank+1, SEND, MPI_COMM_WORLD);
for (int j = 0; j < count[rank+1]; j++) mybuf[j+count[rank+1]] = mybuf[j];
MPI_Recv(mybuf, count[rank+1], MPI_INT, rank+1, SEND, MPI_COMM_WORLD,&status);
xx = (count[rank]+count[rank+1])-1;
mergeSort(mybuf, 0, xx);
}
}
}
}
MPI_Barrier(MPI_COMM_WORLD);

//Собрать все данные
if (rank == size-1){
MPI_Bsend(mybuf, count[rank], MPI_INT, 0, GATHER, MPI_COMM_WORLD);
}
else{
MPI_Bsend(mybuf, count[rank], MPI_INT, 0, GATHER, MPI_COMM_WORLD);
}
if (rank == 0) {
for (int i = 0; i <= size-2; i++){
MPI_Recv(mybuf, count[i], MPI_INT, i, GATHER, MPI_COMM_WORLD,&status);
for (int j = 0; j < count[i]; j++)
data[i*count[i]+j]=mybuf[j];
}
MPI_Recv(mybuf, count[size-1], MPI_INT, size-1, GATHER, MPI_COMM_WORLD,&status);
for (int j = 0; j < count[size-1]; j++)
data[(size-1)*count[size-2]+j]=mybuf[j];

//Вывод данных, итог
finish = MPI_Wtime();
time1 = finish - start;
printf("Runtime parallel = %f sec\n", time1);
}