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

Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (начало) © Якобовский М.В. Ц Е Л Ь О С Н О В Н А Я Расположить в порядке неубывания N элементов массива чисел, используя p процессоров Москва, 2009 г. 2 из 34

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

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

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

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

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

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

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

Алгоритм сортировки Среднее число операцийМаксимальное число операций Быстрая (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) Сравнение алгоритмов сортировки Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (начало) © Якобовский М.В. Москва, 2009 г. 10

Пусть f(N)

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

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

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

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

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 процессоров) Сортировка слиянием методом сдваивания Москва, 2009 г. Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (начало) © Якобовский М.В. 18 из 34 Для просмотра анимации возможно требуется установить свободно распространяемый Swiff Point Player:

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

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

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

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

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

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

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

Пирамида называется упорядоченной если для любого (если такие элементы в массиве есть ) Пирамидальная сортировка Москва, 2009 г. Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (начало) © Якобовский М.В. 26 из 34

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

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

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

Оптимальный алгоритм Оптимальна комбинация H алгоритма (пирамидальная ) в диапазоне – D алгоритма (слияние) в диапазоне – Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (начало) © Якобовский М.В. Москва, 2009 г. 30 из 34

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

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

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

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