Распараллеливание алгоритма сортировки массива

Министерство образования Российской Федерации

Новосибирский Государственный Технический Университет

кафедра параллельных вычислительных технологий

Лабораторная работа №3

по дисциплине «Основы параллельного программирования»

на тему «Распараллеливание алгоритма сортировки массива»

Факультет:         ПМИ

Группа:               ПМ-91

Студент:             Мульцын К.А., Королькова М.С., Какаулина Л.А.

Преподаватель: Медведев Ю.Г.

г. Новосибирск, 2002

1. Постановка задачи

Отсортировать массив вещественных чисел по не убыванию. Массив составляется:

1) случайными числами

2) числами, отсортированными в обратном порядке, без повторных элементов.

2.Анализ задачи

Распараллеливание производилось по данным, следующим образом: каждый процесс получает (размерность массива/количество элементов) элементов, оставшиеся элементы добавляются по порядку к каждому процессу, начиная с первого.

Сначала каждый процесс сортирует свои данные по не убыванию (в программе использовалась сортировка пузырьком).

Далее процессы обмениваются соответствующими крайними элементами.

Полученный элемент сравнивается с соответствующим крайним элементом, и если порядок нарушается, то он вставляется в массив на это место, и производится один проход «пузырька» от этого элемента к концу массива. В противном случае замены не производится и выставляется флаг о правильной сортировке.

Проверка  флагов  производится с помощью функции  MPI_Allreduce.

Входные данные: Файл , где первое число – размерность вектора, а далее через пробел или разрыв строки – элементы вектора. Тестирование проведено на двух массивах: массив состоящий из равномерно-распределенных чисел  на отрезке [0,1000]  и массив отсортированный в обратном порядке, т.е. по убыванию.

Выходные данные: В начале файла выводится время работы алгоритма, а затем элементы отсортированного массива.

3.Текст программы

//--------------------------------------------------------------------------#include <stdlib.h>                      // Подключаем необходимые библиотеки

#include <stdio.h>

#include <mpi.h>

#include <time.h>

#define ST_WORKING     0                 // Определяем статусы работы

#define ST_NOEXCHANGE  1

//--------------------------------------------------------------------------int RightWiseSort(int rows, float *x)    // Процедура делает один проход

{                                        //   сортировки методом пузырька

int i,flag;                              //   слева направо и возвращает 0

float el;                                //   если перестановок не было

flag = 0;                                // Пока перестановок нет

for (i = 0; i < rows - 1; i++)           // Пробегаем все элементы

if (x[i] > x[i+1])                     // Если перестановка нужна, делаем

{                               

el = x[i];

x[i] = x[i+1];

x[i+1] = el;

flag = 1;                            // И выставляем признак

}

return flag;                             // Который затем и возвращаем

}                                   

//--------------------------------------------------------------------------int LeftWiseSort(int rows, float *x)     // То же, но справа налево

{                                   

int i,flag;

float el;

flag = 0;

for (i = rows - 2; i >= 0; i--)

if (x[i] > x[i+1])

{

el = x[i];

x[i] = x[i+1];

x[i+1] = el;

flag = 1;

}

return flag;

}

//--------------------------------------------------------------------------int main(int argc, char* argv[])         // Главная программная функция

{

int rank, rank_k;                        // Номер компа своего и для рассылок

int rows_k;                              // Кол-во эл-ов у к-ого проца

int size;                                // Кол-во процов

int rows;                                // Кол-во эл-ов у себя

int remainder;                           // Нераспределенные строки, если

//   всем делить поровну

int N;                                   // Кол-во элементов общее

int flag, status;                        // Признаки завершенности задачи

int i;                                   // Индекс для счета

long t_st,t_en;                          // Переменные для засекания времени

float *x;                                // Массив элементов

float el;                                // Переменная для обмена эл-ами

FILE *fp;                                // Переменная для чтения из файла

MPI_Status st;                           // Служебная переменная MPI

MPI_Init(&argc,&argv);                   // Инициализируем MPI

MPI_Comm_rank(MPI_COMM_WORLD,&rank);     // Выясняем собственные характеристики

MPI_Comm_size(MPI_COMM_WORLD,&size);    

if (rank == size - 1)                    // Последний комп читает данные и

{                                      //   рассылает их по процам

fp = fopen("_v.txt","r");           

fscanf(fp,"%d",&N);                    // Чтение размерности вектора данных

rows = (int)(N/size);                  // Кол-во эл-ов для себя

remainder = N%size;                    // Кол-во нераспределенных эл-ов

if (remainder > 0)                     // Выделяем память по максимуму

x = (float*)malloc((rows+1)*sizeof(float)); // т.к. из этой памяти будет

else                                   //   вестись рассылка

x = (float*)malloc(rows*sizeof(float));

for (i = 0; i < rank; i++)             // Рассылка: i - номер проца

{

rows_k = rows;                       // Вычисляем, сколько ему надо эл-ов

if (i < remainder) rows_k++;

// Отправляем общую размерность и кол.

MPI_Send(&N,1,MPI_INT,i,15,MPI_COMM_WORLD);

MPI_Send(&rows_k,1,MPI_INT,i,15,MPI_COMM_WORLD);

for (k = 0; k < rows_k; k++)         // Читаем и отправляем данные

fscanf(fp,"%f ",&x[k]);

MPI_Send(x,rows_k,MPI_FLOAT,i,15,MPI_COMM_WORLD);

}

for (k = 0; k < rows; k++)             // Читаем данные для себя