Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 188
Текст из файла (страница 188)
Например, замена цикла !ог циклом рагайе1 дог создаст гонки, поскольку каждая итерация тела цикла зависит от предыдущей. Приведенная далее процедура Р-Яслгс-1 выполняет параллельное вычисление Э-префикса, хотя и очень неэффективно. Р"Яслгч'-1(х) 1 п = х.1епдсп 2 у[1 .. п] — вновь созданный массив 3 Р-Бслгг-!-Аггх(х,у,1,п) 4 гецггп у Р-Зслгг-1-Аггх(х, у, г,2) 1 рагайе! дог 1 = г го 2 2 у[1] = Р-йеггггсе(х, 1,1) б. Проанализируйте работу, интервал и уровень параллелизма процедуры Р-Бслн-1. Используя вложенный параллелизм, можно добиться более эффективного вычисления З-префикса.
Р-Бслгс-2(х) 1 п = х.1епд1Ь 2 у[1 ..п] — вновь созданный массив 3 Р-Бслгг-2-Аггх(х, у, 1, п) 4 гецгги у Р-Ясли-2-Аггх(х, у, г 2) 1 !1г ==2 2 у[г] = х[г] 3 е1ае lс = [[с+2)/2] 4 ярагчп Р-Бслгч-2-Аг2х(х, у, г', л) 5 Р-Бслгч-2-Аих[х, у, й + 1, 7) 6 зупс 7 рагайе1$ог1= к+1 го2 8 у[1] = у[/с] Э у[1] а Докажите, что процедура Р-Бслгс-2 жгрректна, и проанализируйте ее работу, интервал и уровень параллелизма. Можно усовершенствовать как процедуру Р-бслы-1, так и процедуру Р-Яслгс-2, выполняя вычисление З-префикса в два разных прохода по данным.
При первом проходе мы собираем члены различных последовательных подмассивов х во временный массив 1, а на втором проходе используем члены в 1 для вычисления окончательного результата у. Эта стратегия реализуется приведенным далее псевдокодом, в котором опущены некоторые выражения. В4В Часть РИ. Избранные темы Р-ЯСАХ-3(х) 1 и = х.1еидй 2 у[1 .. и] и 1[1 .. и] — вновь созданные массивы 3 у[Ц = х[Ц 4 1ти>1 5 Р-ЯСАХ-ПР(х,1,2, и) 6 Р-ЯСАХ-Потух(х[Ц, х, $, у, 2, и) 7 гегнгп у Р-ЯСАХ-1)Р (х, 1, з, 5) 1 И1== 5 2 геен гп х[1] 3 е1ве 4 )с = [(1+5)/2] 5 1[)с] = врача Р-ЯСАХ-БР(х,г, з, )с) 6 зтдбг = Р-ЯСАХ-1)Р(х,1,)с+1,т) 7 вупс 8 геен гп // Заполните пустое место Р-ЯСАХ-гз0ззХ(о, х, 1, у, з,5) 1 1з1==5 2 у[з] = зз®х[з] 3 е1ве 4 )с = [(з+5')/2) // В двух следующих строках заполните пустые места 5 вразгп Р-ЯСАХ-00чгх(,х,г,у,з',)с) 6 Р-ЯсАх-130%х(, х, 1, у, к + 1,7) 7 вупс а Заполните три пропущенные выражения в строке 8 процедуры Р-ЯСАХ-И' и в строках 5 и 6 процедуры Р-ЯСАХ-Почх.
Докажите корректность процедуры Р-ЯсАх-3 со своими выражениями. (Указаниес докажите, что значение зз, переданное в процедуру Р-ЯСАХ-П0ЧзХ(ю, х, 1, у,1,5), удовлетворяет условию о = х[Ц З х[2] З Э х[з — Ц.) д. Проанализируйте работу, интервал и уровень параллелизма процедуры РЯСАХ-3. 27.5. Многопоточное простое шаблонное вычисление Информатика переполнена алгоритмами, требующими заполнения элементов массива значениями, зависящими от уже вычисленных соседних значений, а также от другой информации, не изменяющейся в процессе вычислений. Структура соседних элементов не изменяется в процессе вычислений и называется шаблоном (в1епсй). Например, в разделе 15.4 представлен шаблонный алгоритм для 849 глава 27.
Миаюпаточнме алаоритмм вычисления наидлиннейшей общей подпоследовательности, где значение элемента с[з,2] зависит только от значений элементов с[( — 1,2], с[1,2 — 1] и с[1 — 1,2 — 1], а также от элементов яч и у в двух входных последовательностях. Входные последовательности фиксированы, но алгоритм заполняет двумерный массив с таким образом, что элемент с[(,2] вычисляется после вычисления трех элементов: с[1 — 1,2], с[1,2 — 1] и с[1 — 1,2 — 1]. В данной задаче мы рассмотрим использование вложенного параллелизма для многопоточного шаблонного вычисления в массиве А размером и х п, при котором значение, помещаемое в элемент А[з,2], зависит толью от значений А[г',2ч], где ю' < 1 и 2х < 2 (и юнечно, г' ф 1 или 2ч?Ь 2).
Другими словами, значение элемента зависит толью от значений элементов, находящихся выше или левее него, а также от статической информации, находящейся вне этого массива. Кроме того, в этой задаче мы полагаем, что если заполнены все элементы, от которых зависит элемент А[з,2], то сам элемент А[г,2] мвкно заполнить за время тз(1) (как в процедуре (.СЯ-(.нмотн из раздела 15А). Можно разбить массив А размером и х п на четыре подмассива размером и/2 х п/2 следующим образом: А= Аы Аш (27. 11) Теперь заметим, что подмассив Аы можно заполнить рекурсивно, посюльку он не зависит от элементов остальных трех подмассивов. После заполнения подмассива Аы можно продолжить рекурсивное заполнение подмассивов Аш и Азы поскольку хотя онн оба и зависят от Аы, но не зависят один от другого.
В юнце мы можем рекурсивно заполнить подмассив Азз. а Запишите многопоточный псевдоюд $1м91.е-бтемс11., выполняющий зто простое шаблонное вычисление с использованием алгоритма "разделяй н властвуй", основанного на разбиении (27.11) и рассмотренного выше.
(Не беспокойтесь о деталях базового случая, которые зависят от конкретного шаблона.) Запишите и решите рекуррентное соотношение для работы и интервала этого алгоритма в терминах п. Каков уровень его параллелизма? 6. Модифицируйте свое решение и. (а), разделив массив размером п х п на девять подмасснвов размером и/3 х п/Ъ и выполнив рекурсивные вычисления с максимально возможным параллелизмом. Проанализируйте свой алгоритм. Насколько увеличился нли уменьшился уровень параллелизма по сравнению с алгоритмом из части (а)? а Обобщите свое решение пп.
(а) и (б) следующим образом. Выберите целочисленное значение Ь ) 2. Разделите массив размером и х и на Ьз подмассивов, каждый размером п/Ь х и/Ь, с максимально возможной параллельностью рекурсивных вычислений. Чему равны работа, интервал и уровень параллелизма вашего алгоритма, выраженные через и и Ь? Докажите, что при использовании этого подхода уровень параллелизма должен составлять о(п) при любом я50 Часть ГГЕ Иебрааные немы выборе Ь > 2. (Указание: для последнего доказательства покажите, что степень и в выражении для уровня параллелизма строго меньше 1 при любом выборе Ь > 2.) а Запишите псевдокод многопоточного алгоритма для данного простого шаблонного вычисления, который достигает уровня параллелизма, равного сз(п/18 и).
Докажите с помощью понятий работы и интервала, что данная задача фактически имеет присущий ей уровень параллелизма ез(п). Как оказывается, достичь этого максимального уровня параллелизма нашему многопоточному псевдокоду не позволяет его природа "разделяй и властвуй". 27.6. Рандомнзнрованные многопоточные алгоритмы Как и в случае обычных последовательных алгоритмов, иногда требуется реализовать рандомизированные многопоточные алгоритмы.
В данной задаче рассматривается, как адаптировать различные меры производительности для работы с ожидаемым поведением таких алгоритмов. В ней также требуется разработать и проанализировать многопоточный алгоритм рандомизированной быстрой сортировки. а Поясните, как изменить закон работы (27.2), закон интервала (27.3) и границы жадного планировщика (27.4) для работы с математическими ожиданиями случайных величин Тр, Т1 и Т б. Рассмотрим рандомизированный многопоточный алгоритм, в котором 1% времени мы имеем Т1 = 104 и Тюссо = 1, но в течение 99% времени Т1 —— Тю сов = 10з.
Докажите, что УскоРение РандомизиРованного многопоточного алгоритма следует определять как Е [Т1] /Е [Тр], а не как Е [Т1/Тр]. в. Докажите, что параллелизм рандомизированного многопоточного алгоритма следует определять как отношение Е [Т5] /Е [Т ]. а Превратите алгоритм КАг4помиеп-()01скзокт, приведенный на с.
208, в многопоточный с применением вложенного параллелизма. (Не распараллелнвайте КАмпом1ееО-РАкт1т1Ом.) Запишите псевдокод своего алгоритма РКАХООМ1ЕЕО-( ИЛСКБОКТ. ех Проанализируйте свой многопоточный алгоритм рандомизированной быстрой сортировки. (Укаэаннес обратитесь к анализу алгоритма КАнпОМ1ЕЕОБееест на с. 246.) Заключительные замечания Параллельные компьютеры, их модели и алгоритмические модели параллельного программирования в процессе развития принимали различные формы. Предыдущие издания этой книги включали материал о сортирующих сетях и мо- Глава 27. Многопоточные алгоритмы 857 дели РВАМ (Рагайе! Капскою-Ассезз МасЬ)пе, — параллельная машина с произвольным доступом). Модель параллельных данных [47, 167) является еще одной популярной алгоритмической моделью программирования, использующей в качестве примитивов векторы и матрицы.
Грэхэм (ПгаЬагп) [148] и Брент (Вгеп!) [54) показали, что существуют планировтцики, достигающие границы из теоремы 27.1. Игер (Еайег), Захорян (е.аЬог]ап) и Лазовска (Ьахоюз(га) [97] показали, что любой жадный планировщик достигает этой границы, и предложили методологию использования работы и интервала (хотя и с другими терминами) для анализа параллельных алгоритмов. Блеллох (В!ейосЬ) [46] разработал алгоритмическую модель программирования, основанную на работе и интервале (который он называя "глубиной" вычисления) для программирования с параллельными данными. Блюмоф (В!шпоГе) и Лейзерсон (Ьейегзоп) [51] разработали распределенный алгоритм планирования для динамической многопоточности, основанный иа рандомизированном "хищении работы" (ног)с-згеа!шй), и показал, что он достигает границы Е [Тр] < Тг(Р + 0(Т ).
Арора (Агога), Блюмоф (В1шпоГе) и Плакстон (Р!ах!оп) [19], а также Блеллох (В1ейосЬ), Гиббонс (П)ЬЬопз) и Матиас (Майаз) [48] также нашли доказуемо хорошие алгоритмы для планирования вычислений с динамической многопоточностью. На многопоточный псевдокод и модель программирования большое влияние оказали проект Сйй [50,117] из М1Т и расширения Сйй++ [70) для языка программирования С++ от Сйй Аггз, 1пс. Многие многопоточные алгоритмы из этой главы взяты из неопубликованных лекций Ч.Э. Лейзерсона (С.Е. 1.еыегзоп) и Г. Прокопа (Н.
Рго1сор) и были реализованы иа С)Пг или С)йг++. Многопоточный алгоритм сортировки слиянием разработан под влиянием алгоритма Акла (АЬ)) [12]. Понятие последовательной согласованности предложено Лампортом (Ьашрогг) [222]. Глава 28. Работа с матрицами Поскольку операции над матрицами являются сердцем научных расчетов, эффективные алгоритмы для работы с матрицами представляют значительный практический интерес.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
