Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 181
Текст из файла (страница 181)
Каждая группа фрагментов, прнналлежашнх одной н той же процедуре, ограничена скругленным прямоугольннком, слабо заштрнхоаанным для запускаемых процедур н сильно — для вызываемых. Ребра запуска н вызова напраалены вниз, продолжения выполнения — по горизонтали апраао, а ребра аозарата — вверх. Полыая, что каждый фрагмент требует единицы времени, ася работа составляет 17 единиц, поскольку нмеется 17 фрагментов, а интервал раасн 8 единицам, поаашьку критический путь (указанный выделенными штриховкой ребрами) содержит 8 фрагментоа. параллельными вычислениями в фрагменты не входят, но представлены в структуре ориентированного ациклического графа.
Например, если фрагмент имеет два преемника, один из них должен быть запушен параллельно, а для предшественника указывают, что этн предшественники обьединяются инструкцией луис. Таким образом, в общем случае множество )г образует множество фрагментов, а множество ориентированных ребер Е представляет зависимости между фрагментами, порожденными управлением параллельными вычислениями. Если в С имеется ориентированный путь от фрагмента и к фрагменту е, мы говорим, что эти два фрагмента ~логически) ппследпаагппчаиы.
В противном случае фрагменты и и и (лпгически7 параллельны, Многопоточное вычисление можно изобразить как ориентированный ациклический граф фрагментов, встроенный в дерево экземпляров процедур. Например, на рис. 27.1 показано дерево экземпляров процедур для вычисления Р-Рги(6) (без детализированной структуры показанных фрагментов). На рис. 27.2 показана в увеличенном виде одна из частей этого дерева, с демонстрацией фрагментов, составляющих каждую процедуру. Все ориентированные ребра, соединяюшие фрагменты, проходят либо в пределах процедуры, либо вдоль неориентированных ребер дерева процедуры.
Часть УП. Избраниые теми Чтобы иметь возможность указывать различные зависимости между фрагментами, ребра ориентированного ациклического графа вычислений можно классифицировать. Ребро нродвлження (сопбпиабоп едйе) (и,и'), на рис. 27.2 направленное горизонтально, соединяет фрагмент и с его преемником и' в пределах одного и того же экземпляра процедуры. Когда фрагмент и запускает фрагмент и, ориентированный ациклический граф содержит ребро запуска (араььп едяе) (и, и), которое на рисунке направлено вниз. Ребра вызовов (са11 едяеа), представляя обычные вызовы процедур, также направлены вниз. Фрагмент и, запускающий фрагмент и, отличается от фрагмента и, вызывающего фрагмент и тем, что запуск приводит к наличию горизонтального ребра продолжения от фрагмента и к фрагменту и', следующему в процедуре за и и указывающему, что и' можно выполнять одновременно с о, в то время как выюв не приводит к появлению такого ребра.
Когда фрагмент и выполняет возврат в вызвавшую процедуру, а г представляет собой фрагмент, непосредственно следующий за следующим аупс в вызывающей процедуре, ориентированный ациклический граф вычислений содержит ребро возврата (генно едйе) (и, г), направленное вверх. Вычисление начинается с одного начального фрагмента ()ш6а! азгапб) — черной вершины в процедуре, помеченной как Р-Г1в(4) на рис.
27.2 — и заканчивается единственным конечным фрагменнюм (Йпа! а!гапб) — белой вершиной в процедуре, помеченной как Р-г1В(4). Мы будем изучать выполнение многопоточных алгоритмов на идеальном нараллельнан комньююере (16еа! рагайе! сошризег), состоящем из множества процессоров и носледовазнельно согласованной (аейиепба11у сопгйа1еп!) совместно используемой памяти.
Последовательная согласованность означает, что совместно используемая память, в которую в действительности процессорами одновременно может выполняться много как загрузок, так и чтений, дает одни и те же результаты, как и в случае, если на каждом шаге будет выполняться только одна команда одного процессора. Иначе говоря, память ведет себя так, как если бы команды выполнялись последовательно в некотором глобааьном линейном порядке, сохраняющем индивидуальный порядок выполнения команд каждым процессором. В случае динамических многопоточных вычислений, автоматически распределяемых по процессорам параллельной платформой, совместно используемая память ведет себя так, как если бы команды многопоточных вычислений чередовались таким образом, что образовывали бы линейный порядок, сохраняющий частичный порядок ориентированного ациклического графа вычислений.
В зависимости от планировщика упорядочение может отличаться при разных запусках одной и той же программы, но поведение любого выполнения программы может быть понято в предположении, что команды выполняются в некотором линейном порядке, согласованном с ориентированным ациклическим графом вычислений.
В дополнение к сделанным семантическим предположениям модель идеального параллельного компьютера делает также некоторые предположения, связанные с производительностью. В частности, предполагается, что каждый процессор машины обладает одной и той же вычислительной мощностью, а стоимость планирования игнорируется.
Хотя зто последнее предположение может казаться слишком оптимистичным, оказывается, что для алгоритмов с достаточной степе- я!9 Глава 2Х Маогоаоточные тгооааемы нью "параллелизма" (термин, который вскоре будет точно определен) на практике накладные расходы планирования обычно минимальны. Меры производительности Измерять теоретическую эффективность многопоточного алгоритма можно с использованием двух метрик; "работы" (звог)г) и "интервала" (зрап).
Работа многопоточного вычисления представляет собой общее время выполнения всего вычисления на одном процессоре. Другими словами, работа представляет собой сумму времен, взятую по всем фрагментам. В ориентированном ациклическом графе вычислений, в котором каждый фрагмент требует единичного времени, работа равна просто количеству вершин ориентированного ациклического графа. Интервал представляет собой наибольшее время выполнения фрагментов вдоль произвольного пути в ориентированном ациклическом графе, Опять же, в случае ориентированного ациклического графа, в котором каждый фрагмент требует единичного времени, интервал равен количеству вершин на наидлиннейшем, или критинескаи, пути (спбса! ра1п) в ориентированном ациклическом графе.
(Вспомним из раздела 24.2, что критический путь в ориентированном ациклическом графе С = ()г, Е) можно найти за время ев()г + Е).) Например, ориентированный ациклический граф вычислений на рис.27.2 всею имеет 17 вершин, а в критическом пути у него 8 вершин, так что если каждый фрагмент требует единичного времени, то работа равна 17 единицам времени, а интервал— 8 единицам. Фактическое время выполнения многопоточного вычисления зависит не только от его работы и интервала, но и от количества доступных процессоров и от того, как планировщик распределяет фрагменты по процессорам. Обозначая время выполнения многопоточного вычисления на Р процессорах, мы будем использовать Р в качестве нижнего индекса.
Например, время выполнения алгоритма на Р процессорах может быть обозначено как То. Работа представляет собой время выполнения алгоритма на одном процессоре, т.е. Ть Интервал является временем работы при выполнении каждого фрагмента на своем собственном процессоре— другими словами, если у нас имеется неограниченное количество процессоров,— так что интервал мы обозначаем как Т„. Работа и интервал предоставляют нам нижнюю границу времени выполнения Тр многопоточного вычисления на Р процессорах.
За один шаг идеальный параллельный компьютер с Р процессорами может выполнить не более Р единиц работы; таким образом, за время Тр он может выполнить работу, не превышающую РТр. Поскольку общая работа составляет Ть имеем РТр ) Ть Деление на Р дает правило работы: Та > Т1(Р . (27.2) Идеальный параллельный компьютер с Р процессорами не может работать быстрее машины с неограниченным количеством процессоров. Так что машина с неограниченным количеством процессоров может эмулировать Р-процессорную машину, используя только Р из своих процессоров. Таким образом, Часть е71. Избранные тены В7О можно сформулировать следующее правило интервалов: Тр>Т (27.3) Определим ускорение (зреес)цр) вычислений иа Р процессорах как отношение Тз(Тр, говорящее о том, во сколько раз вычисления на Р процессорах быстрее, чем на 1 процессоре. Согласно правилу работы имеем Тр > Т1 (Р, откуда вытекает, что Тз7Тр < Р.
Таким образом, ускорение на Р процессорах не может превышать Р. Когда ускорение линейно зависит от количества процессоров, т.е. когда Тз )Тр = 'ез(Р), вычисления демонстрируют линейное ускорение, а когда Т1 (Т> = Р, мы имеем идеальное линейное ускорение. Отношение Тз(Т работы к интервалу дает параллелизм (рата!!е!Вш) многопоточного вычисления. Параллелизм можно рассматривать с трех точек зрения.
Как отношение параллелизм определяет среднее количество работы, которая может быть выполнена параллельно на каждом шаге вдоль критического пути. Как верхняя граница параллелизм дает максимально возможное ускорение, которое может быть достигнуто с помощью произвольного количества процессоров. Наконец, что, вероятно, наиболее важно, параллелизм указывает предел возможности достичь идеального линейного ускорения. В частности, когда количество процессоров превышает уровень параллелизма, вычисления не могут достичь идеального линейного ускорения.
Чтобы понять это утверждение, предположим, что Р > Тз7Т, и в этом случае из правила интервалов вытекает, что ускорение удовлетворяет условию Т1)Тр < Т1)Т < Р. Кроме того, если число процессоров Р в идеальном параллельном компьютере существенно превышает параллелизм — т.е. если Р » Т1 )Т, — то Тз )Тр « Р, так что ускорение гораздо меньше, чем количество процессоров. Другими словами, чем больше процессоров мы используем сверх параллелизма, тем менее идеальным становится ускорение. В качестве примера рассмотрим вычисление Р-Е!в(4) на рис.27.2 и будем считать, что каждый фрагмент требует единичного времени. Поскольку работа Т1 — — 17, а интервал Т = 8, параллелизм равен Т17Т = 17/8 = 2.125. Следовательно, достигнуть более чем удвоенного ускорения невозможно, сколько бы процессоров не использовалось для проведения вычислений.
Мы увидим, что в случае ббльших входных размеров Р-Гпз(ц) демонстрирует существенную степень параллелизма. Определим зазор параллельноспзи (раийе! з!ас)пзезз) многопоточного вычисления на идеальном параллельном компьютере с Р процессорами как отношение (Т1)Т )!Р = Т1 ((РТ ), которое представляет собой множитель, на который параллелизм вычисления превосходит количество процессоров в машине. Таким образом, если зазор меньше 1, мы не можем надеяться достичь идеального линейного ускорения, поскольку Т17(РТ ) < 1 и из правила интервалов вытекает, что ускорение на Р процессорах удовлетворяет условию Тз~Тр < Тз)Т < Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
