'

Учебный курс Введение в параллельные алгоритмы

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

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


Слайд 16

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


Слайд 17

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


Слайд 18

Слияние упорядоченных фрагментов // объединить два упорядоченных массива a,b for(ia=0,ib=0,k=0;k<n1+n2;k++) { if(ia>=n1) c[k]=b[ib++]; else if(ib>=n2) c[k]=a[ia++]; else if(a[ia]<b[ib]) c[k]=a[ia++]; else c[k]=b[ib++]; } Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В. Москва, 2009 г. 19 из 29


Слайд 19

for(ia=0,ib=0,k=0;k<n;k++) { if(ia>=n1) c[k]=b[ib++]; else if(ib>=n2) c[k]=a[ia++]; else if(a[ia]<b[ib]) c[k]=a[ia++]; else c[k]=b[ib++]; } // n – число элементов в каждом из массивов a,b Слияние упорядоченных фрагментов Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В. Москва, 2009 г. rank1, a[n] rank2, b[n] 20 из 29


Слайд 20

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++]; else c[k++]=b[ib++]; } else for(ia=n-1,ib=n-1,k=n-1;k>=0;) { if(a[ia]>b[ib]) c[k--]=a[ia--]; else c[k--]=b[ib--]; } } Слияние упорядоченных фрагментов Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В. Москва, 2009 г. rank1 rank2 21 из 29


Слайд 21

// взаимодействие процессоров 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


Слайд 22

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


Слайд 23

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


Слайд 24

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


Слайд 25

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


Слайд 26

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


Слайд 27

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


Слайд 28

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


×

HTML:





Ссылка: