20150406_msu06_Sort (Лекции)

МГУ ВМКЛекция 6Сортировка данныхс точки зрения МВСПараллельные алгоритмыЯкобовский Михаил Владимировичпроф., д.ф.-м.н.Институт прикладной математикиим. М.В.Келдыша РАН, Москва1Расположить в порядкенеубыванияN элементов массивачисел,,чиселиспользуя p процессоровМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.2К вопросу оНаилучшем последовательном алгоритме Медленном последовательном алгоритме Высокой степени внутреннего параллелизмаМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.3Две задачи сортировки массива чиселA.

Объём оперативной памяти одного процессорногоузла достаточен для одновременного размещенияв ней всех элементов массиваB. Объём оперативной памяти одного процессорногоузла мал для одновременного размещения в ней всехэлементов массиваМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.4Задача АРасположить N элементов массива a такимобразом, чтобы для любогоi  0,, N  2выполнялось неравенствоai  ai 1Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.5Задача BПусть массив можно разместить на p процессорах. Пусть на процессоре с номером rank размещеноn rank элементов массива a rank.Nrank pranknrank 0Расположить N элементов массивов a rank таким образом,чтобы:rank2– для любых rank  0,,  p  1 и i  0,, nвыполнялось неравенство a rank  a rankii 1– для любого rank  0,,  p  2– выполнялось неравенство a rank  a rank1n rank 1Москва, 2015 г.0Сортировка данных с точки зрения МВС © Якобовский М.В.6Задача BЧасти массива хранятся на несколькихпроцессорах– Каждая часть массива должна быть упорядочена– На процессорах с большими номерами должны бытьразмещены элементы массива с большимизначениями• ПравильноМосква, 2015 г.1,2,3,55,6,7,78,8,9• Ошибка1,2,3,55,7,6,78,8,9• Ошибка1,2,3,55,6,7,87,8,9Сортировка данных с точки зрения МВС © Якобовский М.В.N  11p37Задача BБудем рассматривать только процессупорядочивания элементов:– Перед началом сортировки на каждом из процессоровуже есть часть элементов массива– После окончания сортировки на каждом изпроцессоров должно остаться столько элементов,сколько их было в начале (но, это уже могут бытьдругие элементы, расположенные ранее на другихпроцессорах)Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.8Предлагаемая стратегия: Этапы сортировки– Упорядочивание фрагментов массива на каждом изпроцессоров– Перераспределение элементов массива междупроцессорамиМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.9Конструирование наилучшего последовательногоалгоритмаСравнение последовательных алгоритмов сортировкиM n  Cn 2АлгоритмсортировкиСреднее число операцийМаксимальное числооперацийБыстрая (qsort)11.7 n log2nO(n 2)Пирамидальная(hsort)16 n log2n18 n log2 n+ 38nСлияние списков(lsort)10 n log2nO(n log2n)Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.10Пусть f(N)<C∙g(N), нуи что?g(N)f(N)f(N)g(N)N0NГде тут наши 2 Гигобайта оперативной памяти???Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.11T=10-9Константа времени сортировкиKN log2(N)1409K(n)=10 T(n) / (n log2(n))Исходный массив не упорядоченD sort - слияние130Q sort - библиотечная процедура qsort120L sort - слияние списковH sort - пирамидальная сортировка110W sort - быстрая сортировка100Массив упорядоченWsort - быстраясортировка9080706050403020101001 00010 000100 0001 000 0001E71E8n - Размер массиваМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.12Пирамидальная сортировка: константы времени ичисла операцийисходный массив не упорядочен9K(n)= 10 T(n)/(n log2(n))R(n)= M(n)/(n log2(n))65605550исходный массивупорядочен по убываниюR(n)= M(n)/(n log2(n))45R(n), K(n)40Время работы алгоритмаопределяется:35• Числом операций сравнения иперестановки элементов массива302520T=10-9K1510• Временем обращения коперативной памяти(чтения и записи элементовмассива)n log2(n)M=10-9R n log2(n)501001 00010 000100 0001 000 0001E71E8n - Размер массиваМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.1325232119H17D15q13w119751.E+021.E+03Москва, 2015 г.1.E+041.E+051.E+06Сортировка данных с точки зрения МВС © Якобовский М.В.1.E+071.E+0814252321H_D19H17D15q13DHw119751.E+021.E+03Москва, 2015 г.1.E+041.E+051.E+06Сортировка данных с точки зрения МВС © Якобовский М.В.1.E+071.E+0815Меньше 10^5 - пирамидальная, больше - слияние25232119H_D17H15D13119751.E+021.E+03Москва, 2015 г.1.E+041.E+051.E+06Сортировка данных с точки зрения МВС © Якобовский М.В.1.E+071.E+0816Меньше 100 000 элементов – пирамидальная,иначе – (пирамидальная над фрагментами + слияние упорядоченных фрагментов)25232119H17D15DH13119751.E+021.E+03Москва, 2015 г.1.E+041.E+051.E+06Сортировка данных с точки зрения МВС © Якобовский М.В.1.E+071.E+081725232119q17w15DH13119751.E+021.E+03Москва, 2015 г.1.E+041.E+051.E+06Сортировка данных с точки зрения МВС © Якобовский М.В.1.E+071.E+0818Константа времени сортировки наилучшего алгоритма36Dsort - слияниеHsort - пирамидальнаясортировкаDHsort - оптимизированнаясортировка(слияние+пирамидальная)34302826249K(n)=10 T(n) / (n log2(n))32222018161001 00010 000100 0001 000 0001E71E8n - Размер массиваМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.19Сортировка слиянием методом сдваиванияТребуется 2 + 4 + 8 + 16 = 30 тактов (8 процессоров)5221957334403682исходный массив5221957334403682251259373404362812253759122357903448 процессоров2368023344684 такта8 тактов012223334456789ИТОГОМосква, 2015 г.2 тактаСортировка данных с точки зрения МВС © Якобовский М.В.16 тактов30 тактов20Изящный алгоритм сортировки массива слияниемсортировать ( массив mas, число элементов n ){если (n > 1){// сортировка первой половины массивасортировать ( mas, n/2);// сортировка второй половины массивасортировать ( mas+n/2, n-n/2);// слияние отсортированных половинок массиваслияние ( mas, n/2, mas+n/2,n-n/2);}}Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.21Нерекурсивный алгоритм сортировки массива слияниемDsort(intsort *array, int n){a=array;// сортируемый массивb=array_second;// вспомогательный массивfor(i=1;i<n;i=i*2) // размер объединяемых фрагментов{for(j=0;j<n;j=j+2*i) // начало первого из объединяемых// фрагментов{r=j+i; // начало второго из объединяемых фрагментовn1=max(min(i,n-j), 0);n2=max(min(i,n-r), 0);// слияние упорядоченных фрагментовb = a[r…r+n1] & a[j…j+n2]}c=a;a=b;b=c;}Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.22Слияние упорядоченных фрагментовfor(ia=0,ib=0,k=0;k<n1+n2;k++){if(ia>=n1) b[j+k]=a[r+ib++];elseif(ib>=n2) b[j+k]=a[j+ia++];elseif(a[j+ia]<a[r+ib]) b[j+k]=a[j+ia++];elseb[j+k]=a[r+ib++];}Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.23Слияние одним процессором.

Требуется 16 тактовОбращение к последовательным адресам памяти(1 2 2 3 5 5 7 9)12235579122355791223557912235579122355791223557912235579…Москва, 2015 г.(0 2 3 3 4 4 6 8)023344680233446802334468023344680233446802334468023344680010120122012230122330122333Сортировка данных с точки зрения МВС © Якобовский М.В.24Слияние двумя процессорами. Требуется 8 тактов1223557912235579122355791223557912235579122355791223557912235579Москва, 2015 г.0233446802334468023344680233446802334468023344680233446802334468090189012789012267890122256789012223556789012223345567890122233344556789Сортировка данных с точки зрения МВС © Якобовский М.В.25Ускорение при методе сдваиванияk1 – сортировка, k2 – передача данныхS n, p  T n,1k1n log 2 nT n, p  n  nk1  log 2  2 p  1  k 2 ( p  1)p p99S 10 ,4 41 k21.13 30 k1 3.532S 10 ,32  11k1 k2  3  2 56  31 1k130 k1 Москва, 2015 г.32Сортировка данных с точки зрения МВС © Якобовский М.В.26ПирамидыДерево называют сбалансированным, еслипотомки любого его корня отличаются по высотене более чем на 1 Пирамида – сбалансированное бинарное деревов котором левый потомок любого узла не нижеправого потомкаМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.27Не сбалансированное деревоМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.28Сбалансированное дерево, но не пирамида1248Москва, 2015 г.3569710 11 12 13Сортировка данных с точки зрения МВС © Якобовский М.В.29Пирамидаi1248592i310 1162i+1712Потомки вершины i хранятся в элементах 2i, 2i+1a1 a2 a3 a4 a5 a6 a7 a1 ai a3 a2i a2i 1 a6 a7 Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.30Упорядоченная пирамида9 58Москва, 2015 г.44671203352Сортировка данных с точки зрения МВС © Якобовский М.В.31Поменять корень местами с последним потомком9 58446712033529541Москва, 2015 г.842036572Сортировка данных с точки зрения МВС © Якобовский М.В.32Поменять корень местами с последним потомком2 584467120335[92541Москва, 2015 г.842036579Сортировка данных с точки зрения МВС © Якобовский М.В.33Вернуть остатку пирамиды упорядоченность2 584467120335[92541Москва, 2015 г.842036579Сортировка данных с точки зрения МВС © Якобовский М.В.34Вернуть остатку пирамиды упорядоченность8 524467120335[98541242036579Пирамида стала меньше и перестала быть упорядоченнойМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.35Вернуть остатку пирамиды упорядоченность8 524467120335[98541Москва, 2015 г.242036579Сортировка данных с точки зрения МВС © Якобовский М.В.36Вернуть остатку пирамиды упорядоченность8 574462120335[98541742036259Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.37Поменять корень местами с последним потомком8 574462120335[98541742036259Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.38Поменять корень местами с последним потомком8 574462120335[95541742036289Пирамида стала меньше и перестала быть упорядоченнойМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.39Вернуть остатку пирамиды упорядоченность5 57446212033[89554174206238Москва, 2015 г.9Сортировка данных с точки зрения МВС © Якобовский М.В.40Вернуть остатку пирамиды упорядоченность5 57446212033[89754154206238Москва, 2015 г.9Сортировка данных с точки зрения МВС © Якобовский М.В.41Вернуть остатку пирамиды упорядоченность7 55446212033[89754154206238Москва, 2015 г.9Сортировка данных с точки зрения МВС © Якобовский М.В.42Вернуть остатку пирамиды упорядоченность7 56445212033[89754164205238Москва, 2015 г.9Сортировка данных с точки зрения МВС © Якобовский М.В.43Пирамидальная сортировка – хаотичные обращения к памятименяем местами вершину пирамиды и последний элемент пирамиды9 5844671203352[восстанавливаем упорядоченность пирамиды2 588 5244674467120335[9120335[9меняем местами вершину пирамиды и последний элемент пирамиды8 574462120335[9восстанавливаем упорядоченность пирамиды5 577 557 56Москва, 2015 г.44624462445212033[8912033[8912033[89Сортировка данных с точки зрения МВС © Якобовский М.В.44Оптимальный алгоритмОптимальна комбинация: H алгоритм (пирамидальная сортировка)при n от 10 до 50 000 DH алгоритм (пирамидальная сортировка блоковразмером до 50 000 и их последующее слияние)при n больше 50 000пирамидальнаяпирамидальнаяпирамидальнаяслияниепирамидальнаяслияниеслияниеМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.45Константа времени сортировки наилучшего алгоритма36Dsort - слияниеHsort - пирамидальнаясортировкаDHsort - оптимизированнаясортировка(слияние+пирамидальная)34302826249K(n)=10 T(n) / (n log2(n))32222018161001 00010 000100 0001 000 0001E71E8n - Размер массиваМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.46Сеть сортировки (пузырёк) n=6 s=2n-3=9123456Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.47Сеть сортировки четно-нечетные перестановки n=6 s=n=6123456Шаги: 1Москва, 2015 г.2345Сортировка данных с точки зрения МВС © Якобовский М.В.648Сеть сортировки четно-нечетные перестановки n=6 s=n=6123456Шаги:123456nnnnO log 2  p    O log 2  n   On ppppTp  On Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.49Сеть сортировки n=6 s=6123456Шаги: 1Москва, 2015 г.2345Сортировка данных с точки зрения МВС © Якобовский М.В.650Минимальная сеть сортировки n=6 s=5123456Шаги: 1Москва, 2015 г.2345Сортировка данных с точки зрения МВС © Якобовский М.В.51Минимальные сети сортировкиn=10 s=7n=6 s=5n=12 s=8[Дн.Кнут]n=9 s=8n=16 s=9Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.52Четно-нечетное слияние Бэтчера – масштабируемая сеть2468913213571011121Москва, 2015 г.1146278899111110101112766712453104513532893131312Сортировка данных с точки зрения МВС © Якобовский М.В.1234567891011121353Сортировка массива из 15 элементовна основе четно-нечетного слияния Бэтчера715715782612128812121578346226269105610991091012157811441145139105135131113451112114114131113131433141415упорядоченные фрагменты- сеть четно-нечетного слияния БетчераМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.54Оценка числа тактовB(n)=B(n/2)+S(n)B(n)S(n)B(n/2)S(n/2)ВыполняютсяодновременноS(n)=S(n/2)+1S(n/2)B(n/2)Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.55Оценка числа последовательно расположенных группкомпараторовB(n)=B(n/2)+S(n)S(n)=S(n/2)+1Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.56Оценка числа последовательно расположенных группкомпараторовB(n)=B(n/2)+S(n)S(n)=S(n/2)+1Москва, 2015 г.S(n)=log2(n)Сортировка данных с точки зрения МВС © Якобовский М.В.57Оценка числа последовательно расположенных группкомпараторовB(n)=B(n/2)+S(n)S(n)=S(n/2)+1S(n)=log2(n)B(n)=B(n/2)+log2(n)Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.58Оценка числа последовательно расположенных группкомпараторовB(n)=B(n/2)+S(n)S(n)=S(n/2)+1S(n)=log2(n)B(n)=B(n/2)+log2(n)B(n)= log2(n) (log2(n)+1) / 2Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.59Оценка числа последовательно расположенных группкомпараторовB(n)=B(n/2)+S(n)S(n)=S(n/2)+1S(n)=log2(n)B(n)=B(n/2)+log2(n)B(n)= log2(n) (log2(n)+1) / 2log 2 p  log 2 p   1sp 2Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.60Сортировка восьми элементовили2nnlogp2O log 2 pp2 n элементов восемью процессорами- сеть четно-нечетного слияния БетчераМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.61Пример работы алгоритмаНачало, массив распределен по процессорам874392512406874392512406Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.62Сортируем фрагменты874392512406239125046478239125046478Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.63Первые два компаратора слияния перестановки478239478239125046234Москва, 2015 г.125046234789012456789012456Сортировка данных с точки зрения МВС © Якобовский М.В.64Вторая пара компараторов слияния перестановки234789234789012456012Москва, 2015 г.012456012456234789456234789Сортировка данных с точки зрения МВС © Якобовский М.В.65Последний компаратор слияния перестановки012456234012456234789012789012234456789234456789Массив упорядоченМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.66Ограничение метода:Сортировка блоков – ОДИНАКОВОГО РАЗМЕРА123456Шаги: 1Москва, 2015 г.23456Сортировка данных с точки зрения МВС © Якобовский М.В.67Слияние упорядоченных фрагментов// объединить два упорядоченных массива a,bfor(ia=0,ib=0,k=0;k<n1+n2;k++){if(ia>=n1) c[k]=b[ib++];elseif(ib>=n2) c[k]=a[ia++];elseif(a[ia]<b[ib]) c[k]=a[ia++];elsec[k]=b[ib++];}Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.68Слияние упорядоченных фрагментовfor(ia=0,ib=0,k=0;k<n;k++){if(ia>=n1) c[k]=b[ib++];elseif(ib>=n2) c[k]=a[ia++];elseif(a[ia]<b[ib]) c[k]=a[ia++];elsec[k]=b[ib++];}rank1, a[n]rank2, b[n]// n – число элементов в каждом из массивов a,bМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.69Слияние упорядоченных фрагментовfor(ia=0,ib=0,k=0;k<n;k++){rank1, a[n]rank2, b[n]if(a[ia]<b[ib]) c[k]=a[ia++];elsec[k]=b[ib++];}// n – число элементов в каждом из массивов a,bМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.70Слияние упорядоченных фрагментовJoin(int *a, int *b, int *c, int n,rank1,rank2){if(rank==rank1)for(ia=0,ib=0,k=0;k<n;){if(a[ia]<b[ib]) c[k++]=a[ia++];elsec[k++]=b[ib++];}elsefor(ia=n-1,ib=n-1,k=n-1;k>=0;){if(a[ia]>b[ib]) c[k--]=a[ia--];elsec[k--]=b[ib--];}}Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.rank1rank271Реализация компаратора слияния// взаимодействие процессоров rank и rankCint *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;Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.72Сортировка семи элементовМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.73Разделить на две группыМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.74Снова разделить каждую группуМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.75Сортировать каждый короткий фрагментМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.76Сортировать нечетные строки в каждом из фрагментовМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.77Сортировать четные строки в каждом из фрагментовМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.78Объединить отсортированные четные и нечетные строкив каждом фрагментеМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.79Объединить два отсортированных фрагментаМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.80Объединить четные строки отсортированных фрагментовМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.81Объединить нечетные строки отсортированныхфрагментовМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.82Замыкающая цепочка компараторовМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.83Полная сеть сортировкиМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.84Полная сеть сортировки, такты выполненияМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.85Сортировка восьми элементовили2nnlogp2O log 2 pp2 n элементов восемью процессорами- сеть четно-нечетного слияния БетчераМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.86n=108EP123456781627324864128192256384512640Москва, 2015 г.T,сек83.5146.4035.9329.6824.4522.1621.8219.9512.369.327.856.454.923.192.521.991.631.291.21maxlog 2 n1n, p  log 2 n  s p  log 2 p 1  log n p(log 2 p  1) / 2E100.00%90.00%77.48%70.35%68.33%62.80%54.67%52.32%42.22%33.20%33.24%26.97%26.53%20.47%17.29%16.41%13.33%12.64%10.78%S1.001.802.322.813.423.773.834.196.758.9710.6412.9516.9826.2033.1942.0251.2064.7469.02Emax100%100%95%96%91%92%89%90%82%74%73%66%64%56%51%49%49%42%41%Smax1.02.02.83.94.55.56.27.213.120.023.331.940.971.598.2124.6187.0217.4264.7sp013355661014151921283336414547log 2 p  log 2 p   1sp 2Сортировка данных с точки зрения МВС © Якобовский М.В.87ЗаключениеРассмотрен ряд методов сортировки массивов Проиллюстрирована разница междузависимостью от объема данных временисортировки и числа выполняемых операций Построен «наилучший» последовательныйалгоритм сортировки Рассмотрены сети сортировки Построен параллельный масштабируемыйалгоритм сортировкиМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.88КонтактыЯкобовский М.В.проф., д.ф.-м.н.,зав.

сектором«Программного обеспечения многопроцессорныхсистем и вычислительных сетей»Института прикладной математики им.М.В.Келдыша Российской академии наукmail: lira@imamod.ruweb: http://lira.imamod.ruМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.89.