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

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

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

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

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

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

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

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

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

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

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

11 Пусть f(N)

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

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

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

15 сортировать ( массив 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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