Сортировка данных с точки зрения МВС Учебный курс Параллельные алгоритмы Якобовский Михаил Владимирович проф., д.ф.-м.н. Институт прикладной математики им. М.В.Келдыша РАН, Москва 1

Расположить в порядке неубывания N элементов массива чисел, используя p процессоров Москва, 2012 г. 2 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Наилучшем последовательном алгоритме Медленном последовательном алгоритме Высокой степени внутреннего параллелизма К вопросу о Москва, 2012 г. 3 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

A.Объём оперативной памяти одного процессорного узла достаточен для одновременного размещения в ней всех элементов массива B.Объём оперативной памяти одного процессорного узла мал для одновременного размещения в ней всех элементов массива Две задачи сортировки массива чисел Москва, 2012 г. 4 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Расположить N элементов массива a таким образом, чтобы для любого выполнялось неравенство Задача А Москва, 2012 г. 5 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Пусть массив можно разместить на p процессорах. Пусть на процессоре с номером rank размещено элементов массива. Расположить N элементов массивов таким образом, чтобы: –для любых и выполнялось неравенство – для любого –выполнялось неравенство Задача B Москва, 2012 г. 6 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Части массива хранятся на нескольких процессорах –Каждая часть массива должна быть упорядочена –На процессорах с б о льшими номерами должны быть размещены элементы массива с б о льшими значениями Правильно Ошибка Задача B Москва, 2012 г. 7 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Будем рассматривать только процесс упорядочивания элементов: –Перед началом сортировки на каждом из процессоров уже есть часть элементов массива –После окончания сортировки на каждом из процессоров должно остаться столько элементов, сколько их было в начале (но, это уже могут быть другие элементы, расположенные ранее на других процессорах) Задача B Москва, 2012 г. 8 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

–Упорядочивание фрагментов массива на каждом из процессоров ? –Перераспределение элементов массива между процессорами –Упорядочивание фрагментов массива на каждом из процессоров ? Этапы сортировки Москва, 2012 г. 9 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

? Конструирование наилучшего последовательного алгоритма Москва, 2012 г. 10 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Алгоритм сортировки Среднее число операцийМаксимальное число операций Быстрая (qsort)11.7 n log 2 nO(n 2 ) Пирамидальная (hsort) 16 n log 2 n18 n log 2 n+ 38n Слияние списков (lsort) 10 n log 2 nO(n log 2 n) Сравнение алгоритмов сортировки Москва, 2012 г. 11 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Пусть f(N)

Константа времени сортировки T=10 -9 K N log 2 (N) Москва, 2012 г. 13 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

T=10 -9 K n log 2 (n) M=10 -9 R n log 2 (n) Пирамидальная сортировка: константы времени и числа операций Время работы алгоритма определяется : Числом операций сравнения и перестановки элементов массива Временем обращения к оперативной памяти ( чтения и записи элементов массива ) Москва, 2012 г. 14 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Москва, 2012 г. 15 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Москва, 2012 г. 16 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Меньше 10^5 - пирамидальная, больше - слияние Москва, 2012 г. 17 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Меньше 10^5 пирамидальная, больше – пирамидальная, потом слияние упорядоченных фрагментов Москва, 2012 г. 18 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Москва, 2012 г. 19 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Константа времени сортировки наилучшего алгоритма Москва, 2012 г. 20 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

сортировать ( массив mas, число элементов n ) { если (n > 1) { // сортировка первой половины массива сортировать ( mas, n/2); // сортировка второй половины массива сортировать ( mas+n/2, n-n/2); // слияние отсортированных половинок массива слияние ( mas, n/2, mas+n/2,n-n/2); } Изящный Изящный алгоритм сортировки массива слиянием Москва, 2012 г. 21 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Dsort(intsort *array, int n) { a=array;// сортируемый массив b=array_second;// вспомогательный массив for(i=1;i

исходный массив процессоров такта такта тактов тактов Параллельная сортировка слиянием методом сдваивания Требуется тактов (8 процессоров) Москва, 2012 г. 23 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Слияние упорядоченных фрагментов for(ia=0,ib=0,k=0;k=n1) b[j+k]=a[r+ib++]; else if(ib>=n2) b[j+k]=a[j+ia++]; else if(a[j+ia]

… Слияние одним процессором. Требуется 16 тактов Москва, 2012 г. 25 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Слияние двумя процессорами. Требуется 8 тактов Москва, 2012 г. 26 Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Ускорение при методе сдваивания k 1 – сортировка, k 2 – передача данных Москва, 2012 г. 27 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Дерево называют сбалансированным, если потомки любого его корня отличаются по высоте не более чем на 1 Сбалансированное дерево Москва, 2012 г. 28 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Не сбалансированное дерево Москва, 2012 г. 29 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Пирамида – сбалансированное бинарное дерево в котором левый потомок любого узла не ниже правого потомка Пирамиды Москва, 2012 г. 30 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Сбалансированное дерево, но не пирамида Москва, 2012 г. 31 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В

Пирамида Москва, 2012 г. 32 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В i 2i2i+1

В линейном массиве потомки вершины i хранятся в элементах 2i, 2i+1 Хранение пирамиды Москва, 2012 г. 33 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

В упорядоченной пирамиде для любого i выполняется a[i/2] a[i] Пирамида, но не упорядоченная Москва, 2012 г. 34 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В. i_left=index[i][0]; if(i_left>=0) if(a[i]

Упорядоченная пирамида Москва, 2012 г. 35 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Поменять корень местами с последним потомком Москва, 2012 г. 36 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В

Поменять корень местами с последним потомком Москва, 2012 г. 37 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В [ 9

Вернуть остатку пирамиды упорядоченность Москва, 2012 г. 38 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В [ 9

Вернуть остатку пирамиды упорядоченность Москва, 2012 г. 39 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В [ 9 Пирамида стала меньше и перестала быть упорядоченной

Вернуть остатку пирамиды упорядоченность Москва, 2012 г. 40 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В [ 9

Вернуть остатку пирамиды упорядоченность Москва, 2012 г. 41 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В [ 9

Поменять корень местами с последним потомком Москва, 2012 г. 42 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В [ 9

Поменять корень местами с последним потомком Москва, 2012 г. 43 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В [ 9 Пирамида стала меньше и перестала быть упорядоченной

Вернуть остатку пирамиды упорядоченность Москва, 2012 г. 44 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В [ 8 9

Вернуть остатку пирамиды упорядоченность Москва, 2012 г. 45 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В [ 8 9

Вернуть остатку пирамиды упорядоченность Москва, 2012 г. 46 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В [ 8 9

Вернуть остатку пирамиды упорядоченность Москва, 2012 г. 47 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В [ 8 9

меняем местами вершину пирамиды и последний элемент пирамиды [ восстанавливаем упорядоченность пирамиды [ [ 9 меняем местами вершину пирамиды и последний элемент пирамиды [ 9 восстанавливаем упорядоченность пирамиды [ [ [ 8 9 Пирамидальная сортировка – хаотичные обращения к памяти Москва, 2012 г. 48 Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Оптимальный алгоритм последовательной сортировки H алгоритм (пирамидальная сортировка) при n от 10 до DH алгоритм (пирамидальная сортировка блоков размером до и их последующее слияние) при n больше пирамидальная слияние Москва, 2012 г. 49 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Константа времени сортировки наилучшего алгоритма Москва, 2012 г. 50 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Сети сортировки Параллельные алгоритмы сортировки Москва, 2012 г. 51 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Сеть сортировки (пузырёк) n=6 s=2n-3=9 Москва, 2012 г. 52 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Сеть сортировки четно-нечетные перестановки n=6 s=n=6 Москва, 2012 г. 53 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Сеть сортировки n=6 s=6 Москва, 2012 г. 54 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Минимальная сеть сортировки n=6 s=5 Москва, 2012 г. 55 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Минимальные сети сортировки [Кнут] n=6 s=5 n=10 s=7 n=9 s=8 n=12 s=8 n=16 s=9 Москва, 2012 г. 56 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Четно-нечетное слияние Бэтчера – масштабируемая сеть Москва, 2012 г. 57 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Сортировка массива из 15 элементов на основе четно-нечетного слияния Бэтчера Москва, 2012 г. 58 Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В. - сеть четно-нечетного слияния Бетчера упорядоченные фрагменты

B(n) Оценка числа тактов Москва, 2012 г. 59 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В. S(n/2) B(n/2) S(n/2) Выполняются одновременно B(n)=B(n/2)+S(n) S(n) S(n)=S(n/2)+1

Оценка числа последовательно расположенных компараторов Москва, 2012 г. 60 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В. B(n)=B(n/2)+S(n) S(n)=S(n/2)+1 S(n)=log 2 (n) B(n)=B(n/2)+log 2 (n) B(n)= log 2 (n) (log 2 (n)+1) / 2 B(p)=

Сортировка восьми элементов или n элементов восемью процессорами Москва, 2012 г. 61 Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В. - сеть четно-нечетного слияния Бетчера

Нечетно-четное слияние Бетчера Сортировка 8ми элементов Москва, 2012 г. 62 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Разбить массив размера n на части размера n/p На каждом из p процессоров отсортировать часть массива размером n/p с помощью последовательного алгоритма Выполнить общую сортировку с помощью сети сортировки Общая схема алгоритма Москва, 2012 г. 63 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Пример работы алгоритма Начало, массив распределен по процессорам Москва, 2012 г. 64 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Сортируем фрагменты Москва, 2012 г. 65 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Первые два компаратора слияния перестановки Москва, 2012 г. 66 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Вторая пара компараторов слияния перестановки Москва, 2012 г. 67 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Массив упорядочен Последний компаратор слияния перестановки Москва, 2012 г. 68 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Сортировка блоков – ОДИНАКОВОГО РАЗМЕРА Москва, 2012 г. 69 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Слияние упорядоченных фрагментов // объединить два упорядоченных массива a,b for(ia=0,ib=0,k=0;k=n1) c[k]=b[ib++]; else if(ib>=n2) c[k]=a[ia++]; else if(a[ia]

for(ia=0,ib=0,k=0; k=n1) c[k]=b[ib++]; else if(ib>=n2) c[k]=a[ia++]; else if(a[ia]

Join(int *a, int *b, int *c, int n,rank1,rank2) { if(rank==rank1) for(ia=0,ib=0,k=0;kb[ib]) c[k--]=a[ia--]; else c[k--]=b[ib--]; } Слияние упорядоченных фрагментов Москва, 2012 г. rank1 rank2 72 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

// взаимодействие процессоров rank и rankC int *a,*b,*c,*tmp; ASend(a,n,rankC); ARecv(b,n,rankC); ASync(); Join(a,b,c,n, rank, rankC); tmp=a; a=c; c=tmp; Реализация компаратора слияния Москва, 2012 г. 73 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

P T,сек ESE max S max spsp % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % n=10 8 Москва, 2012 г. 74 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Рассмотрен ряд методов сортировки массивов Проиллюстрирована разница между зависимостью от объема данных времени сортировки и числа выполняемых операций Построен «наилучший» последовательный алгоритм сортировки Рассмотрены сети сортировки Построен параллельный масштабируемый алгоритм сортировки Заключение Москва, 2012 г. 75 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

В чем причина различия характера зависимости времени сортировки и числа выполняемых операций от числа элементов сортируемого массива? Какие еще можно предложить варианты сортировки, улучшающие использование кеш- памяти? Что можно предложить для уменьшения объемов передаваемых при сортировке данных? Вопросы для обсуждения Москва, 2012 г. 76 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Якобовский М.В. проф., д.ф.-м.н., зав. сектором «Программного обеспечения многопроцессорных систем и вычислительных сетей» Института прикладной математики им. М.В.Келдыша Российской академии наук mail: web: Контакты Москва, 2012 г. 77 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.