Якобовский М.В., д.ф.-м.н.
Институт математического моделирования РАН, Москва
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Учебный курс Введение в параллельные алгоритмы презентация
Содержание
- 1. Учебный курс Введение в параллельные алгоритмы
- 2. Введение в параллельные алгоритмы: Сортировка
- 3. Объём оперативной памяти одного процессорного узла достаточен
- 4. Части массива хранятся на нескольких процессорах Каждая
- 5. Будем рассматривать только процесс упорядочивания элементов: Перед
- 6. Упорядочивание фрагментов массива на каждом из
- 7. ? Стратегия перераспределения данных между процессорами Введение
- 8. Сеть сортировки (пузырёк) n=6 s=2n-3=9
- 9. Сеть сортировки четно-нечетные перестановки n=6 s=n=6
- 10. Сеть сортировки n=6 s=?=5 Москва, 2009
- 11. Минимальная сеть сортировки n=6 s=?=5
- 12. Минимальные сети сортировки [Дональд Э.Кнут] n=6 s=5 n=10 s=7 n=9 s=8 n=12 s=8 n=16 s=9
- 13. Объединение двух упорядоченных массивов размера m и
- 14. Доказать правильность можно на основе принципа нулей
- 15. Сортировка 8ми элементов Москва, 2009 г.
- 16. Обменная сортировка со слиянием [Бэтчер]
- 17. Сортировка блоков – ОДИНАКОВОГО РАЗМЕРА
- 18. Сравнение алгоритмов
- 19. Слияние упорядоченных фрагментов // объединить два упорядоченных
- 20. 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]
- 21. Join(int *a, int *b, int *c, int
- 22. // взаимодействие процессоров rank и rankC int
- 23. Каждое выполнение компаратора слияния требует передачи n
- 24. n=108 Москва, 2009 г. Введение в параллельные
- 25. Генерация псевдослучайных чисел Москва, 2009 г.
- 26. ABCD D=C C=B B=A
- 27. Рассмотрен ряд, основанных на сетях методов параллельной
- 28. Дональд Э.Кнут. Искусство программирования, т.3. Сортировка и
- 29. Якобовский М.В. д.ф.-м.н., зав. сектором
Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В. Ц Е Л Ь О С Н О В Н А Я Расположить в порядке
Слайд 1Лекция 4
Сортировка данных с точки зрения МВС
(окончание)
Учебный курс
Введение в параллельные
алгоритмы
Слайд 2
Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание)
© Якобовский М.В.
Ц Е Л Ь
О С Н О В Н А Я
Расположить в порядке
неубывания
N элементов массива чисел,
используя p процессоров
Москва, 2009 г.
из 29
Слайд 3Объём оперативной памяти одного процессорного узла достаточен для одновременного размещения в
ней всех элементов массива
Объём оперативной памяти одного процессорного узла мал для одновременного размещения в ней всех элементов массива
Объём оперативной памяти одного процессорного узла мал для одновременного размещения в ней всех элементов массива
Две задачи сортировки массива чисел
Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В.
Москва, 2009 г.
из 29
Слайд 4Части массива хранятся на нескольких процессорах
Каждая часть массива должна быть упорядочена
На
процессорах с большими номерами должны быть размещены элементы массива с большими значениями
Правильно
Ошибка
Ошибка
Правильно
Ошибка
Ошибка
Задача B
Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В.
Москва, 2009 г.
из 29
Слайд 5Будем рассматривать только процесс упорядочивания элементов:
Перед началом сортировки на каждом из
процессоров уже есть часть элементов массива
После окончания сортировки на каждом из процессоров должно остаться столько элементов, сколько их было в начале (но, это уже могут быть другие элементы, расположенные ранее на других процессорах)
После окончания сортировки на каждом из процессоров должно остаться столько элементов, сколько их было в начале (но, это уже могут быть другие элементы, расположенные ранее на других процессорах)
Задача B
Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В.
Москва, 2009 г.
из 29
Слайд 6
Упорядочивание фрагментов массива на каждом из процессоров
Перераспределение элементов массива между
процессорами с сохранением упорядоченности массива на каждом отдельном процессоре
Этапы сортировки
Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В.
Москва, 2009 г.
из 29
Слайд 7?
Стратегия перераспределения данных между процессорами
Введение в параллельные алгоритмы: Сортировка данных с
точки зрения МВС (окончание) © Якобовский М.В.
Москва, 2009 г.
из 29
Слайд 8Сеть сортировки (пузырёк) n=6 s=2n-3=9
Москва, 2009 г.
Введение в параллельные алгоритмы: Сортировка
данных с точки зрения МВС (окончание) © Якобовский М.В.
из 29
Слайд 9Сеть сортировки четно-нечетные перестановки n=6 s=n=6
Москва, 2009 г.
Введение в параллельные алгоритмы:
Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В.
из 29
Слайд 10Сеть сортировки n=6 s=?=5
Москва, 2009 г.
Введение в параллельные алгоритмы: Сортировка данных
с точки зрения МВС (окончание) © Якобовский М.В.
из 29
Слайд 11Минимальная сеть сортировки n=6 s=?=5
Москва, 2009 г.
Введение в параллельные алгоритмы: Сортировка
данных с точки зрения МВС (окончание) © Якобовский М.В.
из 29
Слайд 13Объединение двух упорядоченных массивов размера m и n: и
.
a) Если m=0 или n=0, то сеть пуста
b) m=n=1, то нужен один компаратор.
с) Если mn>1, то
сольём нечетные элементы последовательностей
и , и получим
Сольём четные элементы последовательностей
и , и получим
Применим операции сравнения перестановки к элементам (w1,v2), (w2,v3), (w3,v4), …
И получим отсортированный массив
a) Если m=0 или n=0, то сеть пуста
b) m=n=1, то нужен один компаратор.
с) Если mn>1, то
сольём нечетные элементы последовательностей
Сольём четные элементы последовательностей
Применим операции сравнения перестановки к элементам (w1,v2), (w2,v3), (w3,v4), …
И получим отсортированный массив
Четно-нечетное слияние Бэтчера
Москва, 2009 г.
Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В.
из 29
Слайд 14Доказать правильность можно на основе принципа нулей и единиц:
Если сеть с
n входами сортирует в порядке неубывания все 2n последовательности из 0 и 1, то она будет сортировать в том же порядке любую последовательность n чисел.
Правильность сети
Москва, 2009 г.
Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В.
из 29
Слайд 15
Сортировка 8ми элементов
Москва, 2009 г.
Введение в параллельные алгоритмы: Сортировка данных с
точки зрения МВС (окончание) © Якобовский М.В.
из 29
Слайд 17
Сортировка блоков – ОДИНАКОВОГО РАЗМЕРА
Москва, 2009 г.
Введение в параллельные алгоритмы:
Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В.
из 29
Слайд 18
Сравнение алгоритмов сортировки
Введение в параллельные алгоритмы: Сортировка данных с точки зрения
МВС (окончание) © Якобовский М.В.
Москва, 2009 г.
Слайд 19Слияние упорядоченных фрагментов
// объединить два упорядоченных массива 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]
c[k]=a[ia++];
else c[k]=b[ib++];
}
else c[k]=b[ib++];
}
Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В.
Москва, 2009 г.
из 29
Слайд 20 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]
элементов в каждом из массивов a,b
Слияние упорядоченных фрагментов
Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В.
Москва, 2009 г.
rank1, a[n]
rank2, b[n]
из 29
Слайд 21Join(int *a, int *b, int *c, int n,rank1,rank2)
{
if(rank==rank1)
for(ia=0,ib=0,k=0;k
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--];
}
}
}
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
из 29
Слайд 22// взаимодействие процессоров 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 г.
Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В.
из 29
Слайд 23Каждое выполнение компаратора слияния требует передачи n элементов, даже если элементы
уже расположены правильно
На процессоре с меньшим номером подготовим массив, содержащий r+1 элемент массива a с номерами
и передадим его на процессор с большим номером
На процессоре с меньшим номером подготовим массив, содержащий r+1 элемент массива a с номерами
и передадим его на процессор с большим номером
Сокращение объема передаваемых данных
Москва, 2009 г.
Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В.
i
ai
bn-i-1
i
ai
bn-i-1
i*
n
из 29
Слайд 24n=108
Москва, 2009 г.
Введение в параллельные алгоритмы: Сортировка данных с точки зрения
МВС (окончание) © Якобовский М.В.
из 29
Слайд 25Генерация псевдослучайных чисел
Москва, 2009 г.
Введение в параллельные алгоритмы: Сортировка данных с
точки зрения МВС (окончание) © Якобовский М.В.
из 29
Слайд 26
ABCD
D=C
C=B
B=A
A=(A+D)mod2
Генерация псевдослучайных чисел
Москва, 2009 г.
Введение в параллельные алгоритмы: Сортировка данных с
точки зрения МВС (окончание) © Якобовский М.В.
из 29
Слайд 27Рассмотрен ряд, основанных на сетях методов параллельной сортировки массивов
Рассмотрен вопрос
оптимизации выполнения слияния на компараторе слияния
Рассмотрен вопрос сокращения числа шагов и объема передаваемых данных
Рассмотрен вопрос сокращения числа шагов и объема передаваемых данных
Заключение
Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В.
Москва, 2009 г.
из 29
Слайд 28Дональд Э.Кнут. Искусство программирования, т.3. Сортировка и поиск 2-е изд.: Пер.
с английского – М.: Издательский дом «Вильямс», 2001.
Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.
Якобовский М.В. Параллельные алгоритмы сортировки больших объемов данных. Москва, 2008, http://lira.imamod.ru/FondProgramm/Sort/ParallelSort.pdf
Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.
Якобовский М.В. Параллельные алгоритмы сортировки больших объемов данных. Москва, 2008, http://lira.imamod.ru/FondProgramm/Sort/ParallelSort.pdf
Список литературы
Москва, 2009 г.
Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В.
из 29
Слайд 29Якобовский М.В.
д.ф.-м.н.,
зав. сектором
«Программного обеспечения многопроцессорных систем и вычислительных
сетей»
Института математического моделирования
Российской академии наук
mail: mail: lira@imamod.rumail: lira@imamod.ru
web: web: http://lira.imamod.ru
Института математического моделирования
Российской академии наук
mail: mail: lira@imamod.rumail: lira@imamod.ru
web: web: http://lira.imamod.ru
Контакты
Введение в параллельные алгоритмы: Сортировка данных с точки зрения МВС (окончание) © Якобовский М.В.
Москва, 2009 г.
из 29
