Задача 2. Параллельная сортировка Бэтчера
Дана структура (или Класс)
Point{
float coord[2];
int index;
}
P[n1*n2];
Данная структура будет использоваться для работы с регулярной сеткой. Точки
данной сетки имеют координаты P[i*n2+j].coord[0] = x(i, j), P[i*n2+j].coord[1] =
y(i,j), где i = 0, …, n1-1, j = 1, …, n2-1. Индекс определяется соотношением
P[i*n2+j].index = i*n2+j
Особенности: для инициализации координат можете использовать функции,
принимающие на вход параметры (i, j), то есть фактически каждая точка этой сетки
однозначно определяется (i, j).
На входе: на каждом процессе одинаковое количество элементов структуры Point.
(Если на некоторых процессах элементов структуры Point меньше чем во всех
остальных, тогда необходимо ввести фиктивные элементы, например, с отрицательным
значением индекса.)
Цель: реализовать параллельную сортировку Бэтчера для структур Point вдоль одной
из координат x (или y). То есть с начала необходимо реализовать сортировку на
каждом отдельном процессе, а потом реализовать сеть слияния Бэтчера.
На выходе: на каждом процессе одинаковое количество элементов структуры Point.
Каждый элемент структуры Point одного процесса находиться левее по координате x
( или y) по сравнению с элементом структуры Point любого процесса с большим
рангом, за исключением фиктивных элементов.
Требования к программе:
1 Программа может быть гибридной: одновременно использовать технологию MPI, для
обеспечения взаимодействия вычислительных узлов, и одну из двух технологий posix
threads или OpenMP, для взаимодействия процессов, запущенных на ядрах
процессоров
2 Программа должна демонстрировать эффективность не менее 80% от максимально
возможной, на числе вычислительных ядер, не менее 128
Отчет должен содержать:
1. постановку задачи
2. описание метода решения
3. описание используемой вычислительной системы (число узлов, процессоров, ядер,
вид и топология интерконнекта, …)
3.1. Характеристики вычислительной системы: число операций в секунду на
ядро, латентность и пропускная способность интерконнекта, …
4. таблицу и графики, содержащие сведения о размерах сеток, времени решения и
эффективности распараллеливания
5. Анализ полученных результатов
5.1. Сравнение с наилучшим (выполняющимся наименьшее время) доступным
последовательным алгоритмом. В отчете должно быть указано время выполнения
последовательного алгоритма на одном ядре – T1. Сравнивать следует с этим
временем. Укажите явно значение величины T1/[N*log(N)] для сеток разного
размера
5.2. Явное указание числа вычислительных узлов, процессоров и ядер
5.3. Явное указание числа тактов сортировки Бетчера и аналитические
выражения для ожидаемого времени, ускорения и эффективности сортировки.
6. Другие требуемые, с вашей точки зрения, материалы
7. Приложение (тексты программ: последовательной и параллельной). Прикладывать в
pdf полезно (тогда на них в отчете ссылаться можно), но не обязательно.
! Обязательно прикладывать тексты программ отдельно в c/cpp формате.