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

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

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

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

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

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

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

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

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

? Конструирование наилучшего последовательного алгоритма Москва, 2010 г. 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) Сравнение алгоритмов сортировки Москва, 2010 г. 11 Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

Пусть f(N)

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

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

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

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

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

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

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

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

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

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

Слияние упорядоченных фрагментов 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]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Слияние упорядоченных фрагментов // объединить два упорядоченных массива 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--]; } Слияние упорядоченных фрагментов Москва, 2010 г. rank1 rank2 46 Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

// взаимодействие процессоров 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; Реализация компаратора слияния Москва, 2010 г. 47 Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

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

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

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

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