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

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

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

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

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

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

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

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

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

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

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

11 Пусть f(N)

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

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

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

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

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

17 Меньше элементов – пирамидальная, иначе – (пирамидальная над фрагментами + слияние упорядоченных фрагментов) Москва, 2011 г. 17 Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

55 Оценка числа последовательно расположенных групп компараторов Москва, 2011 г. 55 Параллельные алгоритмы: Сортировка данных с точки зрения МВС © Якобовский М.В. 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)=

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

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

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

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

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

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

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

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

64 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]

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

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

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

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

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

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