Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 180
Текст из файла (страница 180)
Такое положение дел привело к созданию параллельных илази4орм (сопсштепсу р!а1(онпз), предоставляющих слой программного обеспечения, который координирует ресурсы параллельных вычислений, планирует их и управляет ими. Одни из таких платформ имеют вид библиотек времени выполнения, другие же предоставляют полноценные параллельные языки программирования с компиляторами и поддержкой времени выполнения. Динамическое многопоточное программирование Важным классом параллельных платформ является динамическая многопоточность (бупаш(с пш16!Ьгеаб(пя), которая представляет собой модель, используемую нами в данной главе. Динамическая многопоточность позволяет программисту указывать уровень параллелизма в приложении, не беспокоясь о коммуникационных протоколах, сбалансированности загрузки и других неприятностях программирования со статическими потоками.
Параллельная платформа содержит планировщик, который автоматически обеспечивает баланс загрузки, тем самым существенно упрощая работу программиста. Хотя функциональность сред с динамической многопоточностью продолжает развиваться, почти все они поддерживают две возможности: вложенный параллелизм и параллельные циклы. Вложенный параллелизм обеспечивает параллельный запуск подпрограмм, позволяя вызывающей программе продолжать работу, пока запущенная подпрограмма выполняет свои вычисления. Параллельный цикл подобен обычному циклу аког, с тем отличием, что его итерации могут выполняться одновременно.
В7З Глава 22 Многоаоточиые алгоритмы Эти две возможности образуют базис модели динамической многопоточности, которую мы изучим в данной главе. Ключевым моментом этой модели является то, что программист должен указывать только логическую параллельность вычислений, потоки параллельной платформы и распределение вычислений между ними. Мы будем изучать многопоточные алгоритмы, написанные для этой модели, и то, каким образом параллельная платформа может эффективно планировать выполняемые вычисления. Наша модель динамической многопоточности имеет несколько важных преимуществ. Она является простым расширением нашей последовательной модели.
Мы можем описать многопоточный алгоритм, добавив в псевдокод только три юпочевых слова: рагаИе1, араэвп и яупс. Кроме того, если мы удалим эти слова из многопоточного псевдокода, то получим текст последовательного псевдокода для решения той же задачи, который мы будем называть сериализацией (зепа11хаг)оп) многопоточного алгоритма. Она обеспечивает теоретически ясный способ количественного описания па- раллелизма на основе понятий работы (ч ог)г) и интервала (арап). Многие многопоточные алгоритмы включают вложенный параллелизм, естественным образом вытекающий из парадигмы "разделяй и властвуй'*. Кроме того, многопоточные алгоритмы, как и последовательные, могут быть проанализированы путем решения рекуррентных соотношений.
Модель соответствует развитию практики параллельных вычислений. Все большее количество параллельных платформ поддерживают тот или иной вариант динамической многопоточности, включая С1йс [50, 117), С)йс-ь+ [70], ОрепМР [58), Таз(с Рата!!е! (.йзгагу [229) и ТЪгеаг)ш8 Вш1йп8 В!осЫз [290). В разделе 27.1 введена модель динамической многопоточности и представлены метрики работы, интервала и параллелизма, которые будут использоваться нами для анализа многопоточных алгоритмов. В разделе 27.2 изучается многопоточное умножение матриц, а раздел 27.3 посвяшен сложной задаче многопоточной сортировки слиянием.
27.1. Основы динамической многопоточности Начнем изучение динамической многопоточности с примера рекурсивного вычисления чисел Фибоначчи. Вспомним, что числа Фибоначчи определены рекуррентным соотношением (3.22): К =0, Г,=1, ав = а1 — 1 + ев — 2 для 1 > 2 Часть ГЯ.
Иэбраиные тены ',улял12 !Йфф.~ Рг"Цф,' / -~" / Ьет ~!: акк и', ~~ мир йжеч еем е~ь~~ ~~ ~щ ШВ ~~Я'.~ б(тулье),1 Рис. 27.1. Дерево экземпллроа рекурсивной процедуры при вычислении Вв(б). Каждый зкземшир рзв с одннамземм аргуммтпзм лыполнает одниааоиузо работу и вознрылает одинаковый результат, так по этот способ аычислеинл чисел Фибоначчи очень неэффектилен, но поучителен. Вот простой, рекурсивный последовательный алгоритм вычисления п-го числа Фибоначчи. Р1в(п) 1 !Гп< 1 2 гетвгп п 3 е1зе х = Р1в(п — 1) 4 р = Р1в(п — 2) 5 гезнгп х+ у На практике вы не должны вычислять числа Фибоначчи таким способом, поскольку при ташм вычислении имеется очень много повторяющейся работы. На рис.
27.1 показано дерево экземпляров рекурсивной процедуры, создаваемых при вычислении Ее. Например, вызов Р1в(6) рекурсивно вызывает сначала Р1в(б), а затем — Р1в(4). Но вызов Р1в(б) также вызывает Р1в(4). Оба экземпляра Рш(4) возвращают один и тот же результат (Е~ = 3). Поскольку процедура Ррв не использует технологию запоминания (шетпоиайоп), второй вызов Р1в(4) вновь выполняет всю работу, уже выполненную периым вызовом. Обозначим через Т(п) время работы процедуры Р1в(п). Поскольку Р1в(п) содержит два рекурсивных вызова плюс константное количество дополнительной работы, мы получим рекуррентное соотношение Т(п) = Т(п — 1) +Т(п — 2) + 9(1) . Это рекуррентное соотношение имеет решение Т(п) = Н(Г„), что можно показать с помощью метода подстановки. В качестве гипотезы индукции примем, что Т(п) < аń— Ь, где а > 1 и Ь > 0 представляют собой константы.
При о!5 Глиео 77. Миогопотоииые алгоритмы подстановке получим Т(п) < (аЕ„ ! — Ь) + (айаг„ З вЂ” Ь) + сг(1) = а(Р„! + Е„з) — 2Ь + сг(1) = ахи — 6 — (Ь вЂ” ез(1)) < аń— Ь, если выберем Ь достаточно большйм для доминирования над константой в ег(1). Затем мы можем выбрать а достаточно большйм для удовлетворения начальному условию. Аналитическая граница Т(п) = сг(ф"), (27.1) где ф = (1 + ъ'5)/2 представляет собой золотое сечение, теперь следует из уравнения (3.25).
Поскольку Р'„растет с ростом и экспоненциально, зта процедура представляет собой очень медленный способ вычисления чисел Фибоначчи. (См. гораздо более быстрые способы в задаче 31.3.) Хотя процедура Р!и — не лучший, если не худший способ вычисления чисел Фибоначчи, она представляет собой хороший пример для иллюстрации ключевых концепций анализа многопоточных алгоритмов. Заметим, что в Р!в(п) два рекурсивных вызова, Рш(п — 1) и Р!п(п — 2), в строках 3 и 4 являются независимыми один от другого: они могут быть вызваны в любом порядке, и вычисления одной процедуры никак не влияют на вычисления другой. Таким образом, эти два рекурсивных вызова могут работать параллельно. Расширим используемый в книге псевдокод, добавив новые ключевые слова, а именно — аразгп и яупс, Вот как можно переписать процедуру Рш с использованием динамической многопоточности.
Р-Р!В(п) 1 Ып<1 2 гегпгп и 3 е1ае х = аразтп Р-Р!в(п — 1) 4 у = Р-Р!в(п — 2) 5 яупс б гезпгп х+ у Обратите внимание, что если мы уберем ключевые слова аразгп и ауле из псевдокода Р-Р!и, то полученный в результате псевдокод будет идентичен Р!и (не считая другого имени процедуры и двух рекурсивных вызовов). Определим серналнзанню (зепа1!хайоп) многопоточного алгоритма как последовательный алгоритм, получаемый при удалении многопоточных ключевых слов аразгп и зупс (а когда мы изучим параллельные циклы, еще и рагайе1).
Фактически наш псевдокод обладает тем приятным свойством, что сериализация всегда представляет собой обычный последовательный код, решающий ту же самую задачу. Вложенный параллелизм осуществляется, когда ключевое слово кражи предшествует вызову процедуры, как в строке 3. Семантика запуска (ара!нп) отличает- 8!б Часть ГИ. Избранные тты ся от обычного вызова процедуры тем, что экземпляр процедуры, выполняющий запуск (родительская процедура), может продолжать работать параллельно с запущенной дочерней подпрограммой, вместо того чтобы ожидать завершения ее работы, как это обычно делается при последовательном выполнении.
В нашем случае, пока запущенная дочерняя подпрограмма вычисляет Р-Р!в(п — 1), родительская процедура может продолжать вычисление Р-Р!н(п — 2) в строке 4 параллельно с запущенной дочерней подпрограммой. Поскольку процедура РРщ рекурсивна, зти два вызова сами создают вложенный параллелизм, как и их дочерние подпрограммы, тем самым создавая потенциально огромное дерево параллельно выполняемых подвычислений. Однако ключевое слово яразгп не требует от процедуры обязательного параллельного с запущенной дочерней подпрограммой выполнения; оно лишь разрешает таковое. Ключевые слова для параллельных вычислений выражают логический параллелизм (1оя(са! рага11ейып) вычислений, указывая, какие части вычислений могут выполняться параллельно.
Во время выполнения программы планирови4ик (зс!зедц!ег) определяет, какие подвычисления в действительности могут выполняться параллельно, назначал их доступным процессорам. Немного позже мы рассмотрим теоретические основы работы планировщиков. Процедура не может безопасно использовать значения, возвращаемые запущенными дочерними подпрограммами, кроме как после выполнения команды вупс, как в строке 5. Ключевое слово вупс указывает, что для того, чтобы перейти к следующей за вуас команде, процедура должна дождаться окончания всех запуШенных дочерних подпрограмм. В процедуре Р-Г1В ключевое слово аупс необходимо перед ключевым словом ге!нгп в строке б для того, чтобы избежать некорректного суммирования х и у до того, как будет вычислено значение х.
В дополнение к явной синхронизации, обеспечиваемой ключевым словом яупс, каждая процедура выполняет вупс перед возвратом неявно, таким образом гарантируя, что все дочерние подпрограммы будут завершены до окончания родительской процедуры. Модель многопоточного выполнения Облегчить понимание многопоточного вычисления (ти!11бпеадед сошрп1а1юп), которое является ни чем иным, как множеством команд, выполняемых процессором от имени многопоточной программы, может его представление в виде ориентированного ациклического графа С = (г', Е), именуемого графом вычислений. В качестве примера на рис. 27.2 показан граф вычислений Р-Р1н(4). Концептуально вершинами в К являются команды, а ребра в Е представляют зависимости между командами, где (и, и) ~ Е означает, что команда и должна выполняться до команды ш Для удобства, однако, если цепочка команд не содержит параллельных управляющих инструкций (вразчп, яупс или ге!пгп, где последняя инструкция представляет собой возврат из запушенной подпрограммы — как явный, с применением ключевого слова гетпгп, так и неявный возврат по достижении конца процедуры), их можно группировать в единый фрагмент (за апд), каждый из которых представляет одну или несколько команд.
Команды управления 817 Глава 77. Многопоточные аягоршлмы Рнп 27.2. Ориентированный ацнклнческнй граф, предстшшяюшнй вычисление Р-Вв(4). Каждый круг предсгааляет алин фрагмент аычнслення, причем черные круги представляют либо базоаый случай, лнбо часть процедуры (зюемпляр) до запуска Р-Вв(п — 1) а строке 3, серые круги предсгааляют часть процедуры, ншорая вызывает Р-рзв(п — 2) а строке 4 перед ключеаым словом аупс а строке 5, где процелура приостанавливается а ожнланнн аозарата зазушенной процедуры Р-р|в(п — 1), а белые крути представляют часть процедуры после ключевого слова зупс, а которой аыполнястся сложенне значения з н у перед точкой, а которой пронсходнт возврат полученного результата.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
