Постановка задачи
Псевдослучайный набор чисел хранится в виде масива. Необходимо
упорядочить элементы массива в порядке возрастания, т.е. так, чтобы каждый
последующий элемент в нем был не меньше предыдущего. При этом реализовать
упорядочивание с помощью быстрой сортировки, реализовать его параллельный
алгоритм для многопроцессорных систем. Сравнить эффективности параллельного
и последовательного алгоритмов.
Метод решения (последовательный алгоритм)
Используем стратегию "разделяй и властвуй". Шаги алгоритма:
-
Выбираем в массиве некоторый элемент, который будем называть
опорным элементом. С точки зрения
корректности алгоритма выбор опорного элемента безразличен. С точки зрения
повышения эффективности алгоритма выбираться должна медиана, но без
дополнительных сведений о сортируемых данных её обычно невозможно получить.
Известные стратегии: выбирать постоянно один и тот же элемент, например,
средний или последний по положению; выбирать элемент со случайно выбранным
индексом.
- Операция разделения
массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или
равные опорному элементу, оказались слева от него, а все элементы, большие
опорного — справа от него. Обычный алгоритм операции:
- Два индекса — l и r, приравниваются к минимальному и максимальному
индексу разделяемого массива соответственно.
- Вычисляется индекс опорного элемента m.
- Индекс l последовательно увеличивается до m до тех пор, пока l-й элемент
не превысит опорный.
- Индекс r последовательно уменьшается до m до тех пор, пока r-й элемент
не окажется меньше либо равен опорному.
- Если r = l — найдена середина массива — операция разделения закончена,
оба индекса указывают на опорный элемент.
- Если l < r — найденную пару элементов нужно обменять местами и
продолжить операцию разделения с тех значений l и r, которые были
достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до
опорного элемента, то при обмене значение m изменяется на r-й или l-й
элемент соответственно.
- Рекурсивно упорядочиваем подмассивы, лежащие слева и
справа от опорного элемента.
- Базой рекурсии являются наборы, состоящие из одного или двух элементов.
Первый возвращается в исходном виде, во втором, при необходимости, сортировка
сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в
процессе разделения.
Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина
обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу,
терминальная ветвь рекурсии будет достигнута всегда и обработка гарантированно
завершится.
Реализация:
void division(long* arr, long left, long right, long
&t){
long x = arr[left];
long tmp = 0;
t =
left;
for(long i = left + 1; i < = right; i++)
{
if(arr[i]
<
x)
{
t++;
tmp =
arr[t];
arr[t] = arr[i];
arr[i] =
tmp;
}
}
tmp = arr[left];
arr[left] =
arr[t];
arr[t] = tmp;
}
void qs(long* arr, long left, long right) {
if(left < right)
{
long t = 0;
division(arr, left, right,
t);
qs(arr, left, t);
qs(arr, t + 1,
right);
}
}
Метод решения (параллельный алгоритм)
Существует множество параллельных обобщений алгоритма быстрой
сортировки. Рассмотрим наиболее простой способ, но тем не менее
дающий хорошее ускорение последовательного алгоритма на многопроцессорных
системах.
Пусть, исходный набор данных расположен на первом процессоре, с него
начинается работа алгоритма:
- Процессор выбирает ведущий элемент, сортирует остальные элементы
относительно него (большие - в правую сторону, меньшие - в левую);
- Меньшую часть он отдает другому свободному процессору;
- После этого процессор продолжает работать с большей частью одновременно, в
то время как другой процессор работает с меньшей по принципу начиная с 1го
пункта;
- Когда все процессоры получат свою часть, ускорение алгоритма будет
максимальным.
В ходе работы алгоритма исходный набор окажется разделенным на две части
(случайно), меньшая из которых передастся другому свободному процессору, большая
останется на исходном для дальнейшей обработки. Далее обе части опять будут
разделены и опять на двух исходных останутся большие части (на первом процессоре
всё равно большая), а меньшие отправятся другим процессорам. В этом заключается
ускорение алгоритма. При задействовании всех процессов, все части параллельно
будут сортироваться последовательным алгоритмом.
Реаизация:
long length = 0;
long* Array;
double time;
int
size = 0, rank = 0;
MPI_Init(&argc,
&argv);
MPI_Comm_size(MPI_COMM_WORLD,
&size);
MPI_Comm_rank(MPI_COMM_WORLD,
&rank);
MPI_Status status;
long first = 0;
long plength = length;
long* part =
Array;
long fproc = rank;
long lproc = size -
1;
if(rank != 0) {
MPI_Recv(&first, 1, MPI_LONG,
MPI_ANY_SOURCE, 0, MPI_COMM_WORLD,
&status);
MPI_Recv(&plength, 1, MPI_LONG, MPI_ANY_SOURCE,
0, MPI_COMM_WORLD, &status);
part = new
long[plength];
MPI_Recv(part, plength, MPI_LONG, MPI_ANY_SOURCE,
0, MPI_COMM_WORLD, &status);
MPI_Recv(&lproc, 1,
MPI_LONG, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD,
&status);
}
long l = 0;
long r = plength -
1;
long m;
long x = fproc + (lproc - fproc +
1)/2;
long y = lproc;
while (x > fproc)
{
division(part, l, r, m);
long pos =
0;
long count = 0;
if(m - l + 1 < = r - m)
{
pos = l;
count = m - l +
1;
l = m + 1;
} else
{
pos = m + 1;
count = r -
m;
r =
m;
}
MPI_Send(&pos, 1, MPI_LONG, x, 0,
MPI_COMM_WORLD);
MPI_Send(&count, 1, MPI_LONG, x, 0,
MPI_COMM_WORLD);
MPI_Send(part + pos, count, MPI_LONG, x, 0,
MPI_COMM_WORLD);
MPI_Send(&y, 1, MPI_LONG, x, 0,
MPI_COMM_WORLD);
y = x - 1;
x = fproc + (y - fproc
+ 1)/2;
}
qs(part, l, r);
x = fproc + (lproc - fproc
+ 1)/2;
while (x > fproc) {
long
pos;
long count;
MPI_Recv(&pos, 1, MPI_LONG,
x, 0, MPI_COMM_WORLD, NULL);
MPI_Recv(&count, 1, MPI_LONG, x,
0, MPI_COMM_WORLD, NULL);
MPI_Recv(part + pos, count, MPI_LONG,
x, 0, MPI_COMM_WORLD, NULL);
x = fproc + (x -
fproc)/2;
}
if (rank != 0)
{
MPI_Send(&first, 1, MPI_LONG, status.MPI_SOURCE, 0,
MPI_COMM_WORLD);
MPI_Send(&plength, 1, MPI_LONG,
status.MPI_SOURCE, 0, MPI_COMM_WORLD);
MPI_Send(part, plength,
MPI_LONG, status.MPI_SOURCE, 0, MPI_COMM_WORLD);
delete[]
part;
} else {
time = (clock() -
time)/CLOCKS_PER_SEC;
//print(Array, length);
cout << "Sorting time by "
<< size << ": "
<< time <<
"
sec" <<
endl;
delete[] Array;
}
MPI_Finalize();
Анализ эфективности параллельного алгоритма
Временные затраты на ускорение алгоритма:
Каждую итерацию массив делится случайно. На первой итерации при делении на 2
части с меньшими и большими элеменами с разделяющим ведущем пусть длина меньшей
части n1. Алгоритм отправляет её на другой процессор сортироваться параллельно,
а так как она короче, то и досортируется быстрее, значит время её сортировки не
учитывается. Длина большей части N-n1, с этой частью мы проделываем точно такую
же итерацию с разделителем n2. И так далее до момента, когда число свободных
процессоров закончится, то есть до разделителя nk. Где p=2^k.
T1=[N+(N-n1)+(N-n1-n2)+...+(N-n1-...-nk)]*t, где t - время перестановки.
Временные затраты на работу алгоритма при максимальном ускорении:
После достижения максимального ускорения алгоритм будет работать в режиме
стандартной быстрой сортировки. Последняя большая, и поэтому учитываемая, часть
будет иметь длину (N-n1-...-nk).
T2=[(N-n1-...-nk)log₂(N-n1-...-nk)]*t, где t - время перестановки.
Временные затраты на работу алгоритма при максимальном
ускорении:
T3=(α+w/β)(log₂(p))^2 + (α+w(N/2p)/β)(log₂(p)), где α - латентность, β -
пропускная способность сети, а w – размер элемента набора в байтах.
В итоге, общие затраты:
T=T1+T2+T3 *В качестве B берется среднее число, которым может быть
разбиение. То есть (из теории вероятности) - 3/4.
Результаты вычислительных эксперментов
Параметры оборудования:
процессор: Pentium Dual-Core Т4300, 2.10 GHz (2 CPUs)
память: 3072MB RAM
OS: Win Seven Home Premium
компилятор: С++ встроенный в Visual Studio 2005
компилятор: С++ встроенный в Visual Studio 2005
параметры теоретических зависимостей в данной вычислительной системе имеют значения: латентность a – 43 мкс; пропускная способность b – 39,13 Мбайт/с и величина w равна 8 байт
Результаты тестов (2 процесса)
| Размер массива |
Последовательный алгоритм |
Параллельный (2 процесса) |
Ускорение |
Теоретическая оценка |
| 1000000 |
0.155 |
0.129 |
1.201 |
0.119 |
| 5000000 |
1.223 |
1.113 |
1.098 |
0.109 |
| 10000000 |
3.564 |
3.165 |
1.126 |
3.095 |
| 15000000 |
7.008 |
4.401 |
1.592 |
4.552 |
| 20000000 |
11.536 |
6.713 |
1.718 |
6.888 |
| 40000000 |
40.571 |
27.245 |
1.489 |
28.001 |
| 80000000 |
151.998 |
81.492 |
1.865 |
83.650 |
Результаты тестов (4 процесса)
| Размер массива |
Последовательный алгоритм |
Параллельный (4 процесса) |
Ускорение |
Теоретическая оценка |
| 1000000 |
0.156 |
0.102 |
1.529 |
0.112 |
| 5000000 |
1.223 |
0.752 |
1.626 |
0.926 |
| 10000000 |
3.52 |
2.332 |
1.509 |
2.519 |
| 15000000 |
6.937 |
4.04 |
1.717 |
3.918 |
| 20000000 |
11.885 |
7.279 |
1.632 |
7.532 |
| 40000000 |
40.73 |
21.666 |
1.879 |
20.999 |
| 80000000 |
151.813 |
94.922 |
1.599 |
94.387 |
На данной конфигурации оборудования оптимальные показатели эффективности
будут при запуске на 2 процессах, т.к. у процессора всего два физических ядра.
Для не особо больших размерностей массива программа, работающая на 4 роцессорах
показала лучшее время чем на 2х, однако с ростом числа ортируемых элементов
2-хпроцессорная программа показывает все более лучшие результаты по сравнению с
4х. По сравнению с последовательным алгоритмом, паралельный показывает заметно
лучшие результаты тестов.
Автор
Студент группы 8410 Коршак Александр.
