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

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

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

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

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

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

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

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

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

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

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

Минимальные сети сортировки [Дональд Э.Кнут] n=6 s=5 n=10 s=7 n=9 s=8 n=12 s=8 n=16 s=9 12

Объединение двух упорядоченных массивов размера m и n: и. a) Если m=0 или n=0, то сеть пуста b) m=n=1, то нужен один компаратор. с) Если mn>1, то сольём нечетные элементы последовательностей и, и получим Сольём четные элементы последовательностей и, и получим Применим операции сравнения перестановки к элементам (w1,v2), (w2,v3), (w3,v4), … И получим отсортированный массив Четно-нечетное слияние Бэтчера Москва, 2009 г. Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В. 13 из 29

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

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

Обменная сортировка со слиянием [Бэтчер] 16

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

Алгоритм сортировкиСреднее число операций ПирамидальнаяO(n log 2 n) СлияниеO(n log 2 n) Параллельная сортировка методом сдваивания. Объём данных ограничен оперативной памятью вычислительного узла Параллельная четно-нечетная сортировка Объём данных ограничен общей оперативной памятью Параллельная «обменная сортировка со слиянием» Сравнение алгоритмов сортировки Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В. Москва, 2009 г. 18

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

// взаимодействие процессоров rank и rankC int *a,*b,*c,*tmp; ASend(a,n,rankC); ARecv(b,n,rankC); ASync(); Join(a,b,c,n,min(rank,rankC),max(rank,rankC)); tmp=a; a=c; c=tmp; Реализация компаратора слияния Москва, 2009 г. Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В. 22 из 29

Каждое выполнение компаратора слияния требует передачи n элементов, даже если элементы уже расположены правильно На процессоре с меньшим номером подготовим массив, содержащий r+1 элемент массива a с номерами и передадим его на процессор с большим номером Сокращение объема передаваемых данных Москва, 2009 г. Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В. i aiai b n-i-1 i aiai i*i* n 23 из 29

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

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

ABCD (A+D )% ABCD D=C C=B B=A A=(A+D)mod2 Генерация псевдослучайных чисел Москва, 2009 г. Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В. 26 из 29

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

1. Дональд Э.Кнут. Искусство программирования, т.3. Сортировка и поиск 2-е изд.: Пер. с английского – М.: Издательский дом «Вильямс», Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", с. 3. Якобовский М.В. Параллельные алгоритмы сортировки больших объемов данных. Москва, 2008, Список литературы Москва, 2009 г. Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В. 28 из 29

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