Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 185
Текст из файла (страница 185)
Приведенный ниже псевдокод реализует эту стратегию "разделяй и властвуй" с использованием вложенного параллелизма. В отличие от процедуры ВОиАКЕМАтк1Х-М1зет1Р1Ч-Кесикз1че, на которой она основана, процедура Р-МАтк1хМШ.Т1Р1х-йЕСипяЧЕ получает выходную матрицу в качестве параметра, чтобы избежать излишнего вьгделения памяти для матриц. б34 Часть >тэ' Иэбранные тена небольшой вопрос о том, как использовать вычисления индексов для представления подматричных частей исходной матрицы.) Рекурсивный вызов в строке 6 присваивает подматрице См произведение подматрнц АыВ», так что Сы становится равным первому из двух членов, образующих сумму в (27.6).
Аналогично в строках 7-9 выполняется присваивание подматрицам Спь Сз> и Сзз первого из двух членов соответствующих сумм в (27.6). В строке 10 подматрице Ты присваивается произведение подматриц А>аВзм так что Т» становится равным второму члену в сумме для Сы. В строках 11-13 выполняется аналогичное присванвание вторых членов сумм для Спн Сз> и Сзз подматрицам Тпн Тз> и Таз соответственно. Первые семь рекурсивных вызовов запускаются, а последний выполняется в основном фрагменте.
Инструкция аупс в строке 14 гарантирует, что все произведения подматриц в строках 6-13 будут полностью вычислены, после чего мы добавляем произведения из Т в С с использованием дважды вложенных циклов рагайе! Гог в строках 15-17. Сначала проанализируем работу М>(и) процедуры Р-МАтк>х-Мя.тпчхКес>>кз>че, проводя анапиз времени работы ее последовательного предшественника $<;н»>ке-МАтк>х-М>л.т>Е1у-Вес>>ке>>>е.
В рекурсивном случае разбиение выполняется за время В(1), затем выполняется восемь рекурсивных умножений матриц размером п/2 х п/2, и наконец выполняется работа б>(пз) по сложению двух матриц размером и х п. Таким образом, рекуррентное соотношение для работы М>(п) имеет вид М>(п) = 8М>(п/2) + б>(п~) ~(„з) согласно случаю 1 основной теоремы.
Другими словами, работа нашего многопоточного алгоритма асимптотически та же, что и время выполнения процедуры 3>2>>яке-Млтк>х-М>>ьт>ееу с трижды вложенными циклами из раздела 4.2. Для определения интервала М (и) процедуры Р-Мнтк>х-М>>етпчхКЕс>>кз>ЧЕ сначала заметим, что интервал для разбиения равен б>(1) и над ним доминирует интервал 9(1би) дважды вложенных циклов рагайе1 !ог в строках 15-17. Поскольку восемь параллельных рекурсивных вызовов работают с матрицами одинакового размера, максимальным интервалом кюкдого рекурсивного вызова является интервал любого нз них.
Следовательно, рекуррентное соотношение для интервала М (п) процедуры Р-Млтк>х-Мнет>ги-Кес>>кз>че имеет вид М, (п) = М, (и/2) + В(1яп) . (27.7) Это рекуррентное соотношение не подпадает ни под один из случаев основной теоремы, но соответствует условию упр. 4.6.2. Согласно упр. 4.6.2 решением рекуррентного соотношения (27.7) является М,(п) = 9(!й~ п). Теперь, когда мы знаем работу и интервал процедуры Р-Млтк>х-М>>ьтпчхКес>>кз>че, можно вычислить уровень ее параллелизма как М>(и)/Мьа(п) = 9(п /1к п) и увидеть, что он весьма высок.
В35 Глава ел Многоноточные алгоритмы Многопоточный метод Штрассеиа В случае многопоточного алгоритма Штрассена мы следуем той же общей схеме, что и иа с. 104, только с применением вложенного параллелизма. 1. Разбиваем входные матрицы А и В и выходную матрицу С иа подматрицы размером п/2 х п/2, как в (27.6). Работа и интервал этого шага составляют 9(1) при использовании пересчета индексов. 2. Создаем 10 матриц 51, Яз,..., Яш, каждая из которых имеет размер и/2 х и/2 и представляет собой сумму или разность двух матриц, созданных в и.
1. Все 10 матриц создаются ценой работы еэ(пз) и интервала 9(!йп) с помощью дважды вложенных циклов рагайе1 !ог. 3. Используя созданные в и. 1 подматрицы и 10 матриц, созданных в п. 2, рекурсивио запускаем вычисление семи произведений матриц Р1, Рз,..., Р1 размером п/2 х и/2. 4. Вычисляем искомые подматрицы Сы, Спи Сз1,Сзз результирующей матрицы С путем сложения и вычитания различных комбинаций матриц Р1, вновь используя дважды вложенные циклы рагайе! !ог.
Вычисление всех четырех подматриц имеет работу се(пз) и интервал б1(1к п). Для анализа этого алгоритма сначала заметим, что, поскольку сериализация совпадает с исходным последовательным алгоритмом, работа нашего алгоритма равна времени работы сериализации, а именно — 9(п1Я т). Как и в случае процедуры Р-Млтк1х-М~л.т1рет-Кесцкз1че для интервала можно записать рекурреитиое соотношение. В данном случае параллельно выполняются семь рекурсивных вызовов, но поскольку все они работают с матрицами одного и того же размера, мы получаем такое же рекурреитиое соотношение (27.7), как и в случае процедуры Р-Млтк1х-М15ст1иу-Кес11кз1че, решением которого является В((йз и). Таким образом, уровень параллелизма многопоточного алгоритма Штрассена равен еэ(п1кт/!йз п).
Это высокий параллелизм, хотя и меньший, чем в случае процедуры Р-МАтк1Х-Ми.т!Рех-Кес11кз11ге. Упражнения 27.2.1 Изобразите ориентированный ациклический граф для вычислений для процедуры Р-300лке-МАтк1х-М15стпчх для матриц размером 2 х 2, помечая соответствие вершин иа своей дишрамме фрагментам выполнения алгоритма. Используйте соглашение, согласно которому ребра, соответствующие запускам и вызовам, направлены вниз, ребра продолжения направлены вправо, а ребра возвратов — вверх. Считая, что каждый фрагмент выполняется за единичное время, проанализируйте работу, интервал и параллелизм этого вычисления. 27.2.2 Повторите упр. 27.2.1 для процедуры Р-Млтк1х-М1л.т1ри"-Кес11кз1т е. бзб Часть !71.
Избнанние аемн 27.2.3 Запишите псевдокод многопоточного алгоритма, перемножающего две матрицы размером п х и с работой й(пз), но с интервалом всего лишь 9(1й и). Проанализируйте свой алгоритм. 27.2.4 Запишите псевдокод эффективного многопоточного алгоритма, умножающего матрицу размером р х о иа матрицу размером д х т.
Ваш алгоритм должен быть высокопараллельным, даже когда любые из значений р, о и т равны 1. Проанализируйте свой алгоритм. 27.2.5 Запишите псевдокод эффективного многопоточного алгоритма транспонирования матрицы размером и х и "на месте", без привлечения дополнительной памяти, с использованием для рекурсивного деления матрицы на четыре подматрицы размером п/2 х и/2 метода "разделяй и властвуй" без цикла рагайе! !ог. Проанализируйте свой алгоритм. 27.2сб Запишите псевдокод эффективной многопоточной реализации алгоритма (см. раздел 25.2), который вычисляет кратчайшие пути между всеми парами вершин в графе со взвешенными ребрами.
Проанализируйте свой алгоритм. 27.3. Многопоточная сортировка гпиянием Мы познакомились с сортировкой слиянием в разделе 2.3.1, а в разделе 2.3.2 проанализировали время ее работы и показали, что оно составляет В(п1кп). Поскольку сортировка слиянием сама по себе использует парадигму "разделяй и властвуй", складывается впечатление, что она является прекрасным кандидатом для многопоточности с применением вложенного параллелизма.
Можно легко модифицировать псевдокод так, чтобы первый рекурсивный вызов был запускаемым. Мексе-Бокт'(А, р, т) ! !$р<т 2 о = '((р+т)/2) 3 враэтп Мекое-Бокт'(А,р, о) 4 Мекбе-ЯОкт (А, о + 1, т) 5 вупс 6 Мекке(А, р, о, т) Подобно своему последовательному аналогу, Мекпе-Бокт' сортирует подмассив А(р..
т1 После того как две рекурсивные подпрограммы в строках 3 и 4 ВЗ7 Тлаеа 22 Мнаеолоточные алгоритмы Рэ Ю гэ Рэ дэ гэ зг Рэ дэ гэ рнс. 27.Гь Идея, лежащая в основе многопоточного слияния отсортированных подмассивов Т[рэ .. гэ] и Т[рг .. гз] в подмжсив А[рз .. гз). Пусть х = Т[дэ) предсппшяет собой медиану Т[рэ .. гэ), а дг — место в Т[рэ .. гз], такое, что х попадаег между Т[дз — Ц и Т[дг). Каждый элемент подмассивов Т[рэ .. дэ — Ц и Т[рз ..
дз — Ц (светлая штриховка) не превышает х, а каждый элемент полмассивов Т[дэ + 1 .. гэ) и Т[дз+ 1 .. гз) (темная штризовка) как минимум равен х. Для слияния мы вычисляем индекс дз, где х располагается в А[рз .. гз), копируем х в А[дз], а затем рекурсивно выполняем слияния Т[рэ ..д, — Ц с Т[р, дз — Ц в А[рз,дз — Ц и Т[д, + 1..гэ] с Т [де ..
гз] в А[да + 1 .. э'3). будут завершены, что обеспечивается инструкцией яупс в строке 5, процедура Мекае-Боктэ вызывает такую же процедуру Мекпе, как и приведенная на с. 54. Давайте проанализируем процедуру Мекпе-Бойт'. Для этого сначала проанализируем процедуру МЕКПЕ. Вспомним, что в последовательном случае время ее работы по слиянию п элементов составляет б)(п). Поскольку процедура Мейпе последовательная, и ее работа, и ее интервал равны 9(п). Таким образом, работа МЯ1 (п) процедуры МЕХПЕ-БОКтэ с п элементами характеризуется рекуррентным соотношением МБ1(п) = 2 МЯ1(п/2) + В(п) = й(п1йп) и совпадает со временем работы последовательной сортировки слиянием.
Поскольку два рекурсивных вызова Мекпе-Бойт' могут работать параллельно, интервал МЯ' определяется рекуррентным соотношением МЯ' (п) = МЯ' (п/2) +Н(п) = 9(п) . Таким образом, уровень параллелизма процедуры Мекпе-Бокт' стремится к МБ1 (п)] МБ' (п) = тэ(1Б п), весьма невыразительной величине. Например, чтобы отсортировать 1О миллионов элементов, линейного ускорения можно достичь на нескольких процессорах, но эффективно использовать сотни процессоров не удастся. Вероятно, вы уже догадались, в чем слабое место этой многопоточной реализации сортировки слиянием: в последовательной процедуре Мекай. Хотя слияние изначально может казаться по своей сути последовательным, в действительности можно создать его многопоточную версию с использованием вложенного параллелизма.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
