Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 182
Текст из файла (страница 182)
В действительности при уменьшении зазора от 1 до 0 ускорение вычисления отклоняется от идеального линейного ускорения все сильнее и сильнее. Однако, если зазор больше 1, ограничением является работа, приходящаяся на один про- Гаева 22 Миогоаоточаые алгоаиоемы цессор. Как мы увидим, при росте зазора от 1 хороший планировщик может все больше и больше приближаться к идеальному линейному ускорению.
Планирование Хорошая производительность зависит не только от минимизации работы и интервала. Должно также выполняться эффективное распределение фрагментов по процессорам параллельной машины. Наша модель многопоточного программирования не предоставляет возможности указать, какие фрагменты должны выполняться тем или иным процессором. Вместо этого в вопросе распределения вычислений по процессорам мы полагаемся на планировщик параллельной платформы.
На практике планировщик распределяет фрагменты по статическим потокам, а операционная система распределяет потоки по процессорам, но этот дополнительный уровень косвенности не является необходимым для нашего понимания процесса планирования. Мы можем просто представить, что планировщик параллельной платформы распределяет фрагменты по процессорам непосредственно. Многопоточный планировщик должен выполнять планирование, ие зная заранее, когда фрагменты будут запущены или когда они завершатся — он должен работать в оператнвнам (оп-11пе) режиме.
Кроме того, хороший планировщик работает распределенно, с учетом баланса загруженности процессоров. Существование хороших оперативных распределенных планировщиков доказано, но их анализ представляет собой сложную задачу. Поэтому для простоты мы будем рассматривать централизованный (сеппа11геб) планировщик, которому в любой момент времени известно глобальное состояние вычисления.
В частности, мы проанализируем жадные планнровнгнкн, назначающие процессорам на каждом временнбм шаге максимально возможное количество фрагментов. Если на очередном шаге к выполнению готовы как минимум Р фрагментов, мы говорим, что этот шаг является полным, и жадный планировщик назначает любые Р готовых фрагментов процессорам. В противном случае для выполнения готово менее Р фрагментов, и мы говорим, что шаг неполон, а планировщик назначает каждый готовый фрагмент своему процессору. Согласно правилу работы наилучшее время выполнения, на которое мы можем надеяться при наличии Р процессоров, составляет Тр = Т~7Р, а согласно правилу интервала лучшее, на что можно надеяться, — Тр = Т .
В приведенной далее теореме показано, что жадный планировщик доказанно хорош в том плане, что достигает в качестве верхней границы суммы этих двух нижних границ. Теорема 27.1 На идеальном параллельном компьютере с Р процессорами жадный планировщик выполняет многопоточное вычисление с работой Т~ и интервалом Т за время Т,<Т(Р+Т (27.4) гТоказатеяьство. Начнем с рассмотрения полных шагов. На каждом полном шаге Р процессоров вместе выполняют общее количество работы, равное Р. Предположим для доказательства от противного, что количество полных шагов Часть $7б Иябраамые темы строго больше, чем ~!Тг(Р). Тогда общее количество работы на полных шагах составляет не менее Р (,Т~(Р~ +1) = Р~Т!(Р~ + Р = Т1 — (Тз эпос! Р) + Р )Т (из уравнения (3.8)) (из неравенства (3.9)) . Таким образом, мы получили противоречие, заключающееся в том, что Р процессоров должны выполнить ббльшую работу, чем требует вычисление, и это позволяет заключить, что количество полных шагов не превышает ~ Т! (Р!.
Рассмотрим теперь неполный шаг. Пусть С является ориентированным ациклическим графом, представляющим все вычисление в целом, и без потери общности предположим, что каждый фрагмент выполняется за единицу времени. (Можно заменить каждый более длинный фрагмент цепочкой фрагментов единичной длины.) Пусть С' представляет собой подграф С, который все еще должен быль выполнен по состоянию на начало неполного шага, и пусть Са — подграф, который останется невыполненным после этого неполного шага.
Наидлиннейший путь в ориентированном ациклическом графе с необходимостью начинается в вершине с нулевой входной степенью. Поскольку неполный шаг жадного планировщика выполняет все фрагменты с нулевой входящей степенью в С', длина наидлиннейшего пути в Са должна быть на 1 меньше, чем длина наидлиннейшего пути в С~. Другими словами, неполный шаг уменьшает интервал невыполненного ориентированного ациклического графа на 1.
Следовательно, количество неполных шагов не превышает Т Поскольку каждый шаг является либо полным, либо неполным, теорема доказана. Приведенное далее следствие из теоремы 27.1 показывает, что жадный планировщик всегда хорошо работает. Следствие 27.2 Время выполнения Тр любого многопоточного вычисления при планировании выполнения жадным планировщиком на идеальном параллельном компьютере с Р процессорами отличается от оптимального не более чем в 2 раза. Тр ( Т1 ( Р + Таа ( 2 шах(Тз(Р,Т ) ( 2Тр Докезвтельство. Обозначим через Тр время выполнения, получаемое путем оптимального планирования на машине с Р процессорами, и пусть Т! и Т обозначают соответственно работу и интервал вычисления. Поскольку правила работы и интервала — неравенства (27.2) и (27.3) — дают нам Тр > шах(Тт7Р, Т, ), из теоремы 27.1 вытекает, что вгз Глава г7.
Многопоточные алгоритмы Очередное следствие показывает, что фактически жадный планировщик с ростом зазора достигает близкого к идеальному линейного ускорения любого многопоточного вычисления. Следствие 27.3 Пусть Тр обозначает время выполнения многопоточного вычисления, полученное жадным планировщиком на идеальном параллельном компьютере с Р процессорами, и пусть Т1 и Т представляют собой соответственно работу и интервал вычисления. Тогда, если Р « Т1)Т, имеем Тр = Т1(Р, или, что эквивалентно, ускорение приблизительно равно Р. Доказательство. Если мы предположим, что Р «Т17Тоа, то мы также имеем Т « Т17Р, а следовательно, теорема 27.1 дает нам Тр < Т~(Р + Т Т17Р. Поскольку правило работы (27.2) гласит, что Тр > Т17Р, мы заключаем, что Тр — Т1)Р, или, что эквивалентно, что ускорение равно Т1(Тр — Р. ° Символ « означает "гораздо меньше", но насколько "гораздо"? На практике зазора, не меньшего 10 (т.е.
когда параллелизм в 10 раз превышает количество процессоров), в общем случае достаточно для достижения хорошего ускорения. При этом член, соответствующий интервалу, в жадной границе (27.4) составляет менее 10% от члена, соответствующего работе, приходящейся на один процессор, что достаточно хорошо для большинства инженерных ситуаций. Например, если вычисление выполняется только на 10 или 100 процессорах, параллелизм, равный, скажем, 1000000, не имеет никакого преимущества над параллелизмом 10000, несмотря на разницу в 100 раз. Как показано в задаче 27.2, иногда снижение чрезвычайно высокого параллелизма дает возможность получить алгоритмы, лучшие с других точек зрения, но при этом в той же степени масштабируемые на разумном количестве процессоров.
Анализ многопоточных алгоритмов Теперь у нас есть все необходимые инструменты для проведения анализа многопоточных алгоритмов и получения точных границ времен их работы на различном количестве процессоров. Анализ работы достаточно прост и прямолинеен, поскольку ее подсчет — ни что иное, как анализ времени работы обычного последовательного алгоритма (а именно — сериализации многопоточного алгоритма), с которым вы уже должны быть хорошо знакомы, ведь именно этому вопросу посвящено большинство материала данной книги! Анализ интервала куда интереснее, но, вообще говоря, не сложнее — отбит только немного в нем разобраться. Основные идеи мы изучим на примере программы Р-Р[в.
Анализ работы Т1 (и) алгоритма Р-Р~в(п) не представляет трудности, поскольку мы уже его проводили. Исходная процедура Р~в, по сути, является сериализацией Р-Р~в, а следовательно, Т1(п) = Т(п) = 9(фп) согласно уравнению (27.1). На рис. 27.3 показано, как выполняется анализ интервала. Если два подвычисления соединены последовательно, интервал их объединения равен сумме их интервалов; если же они соединены параллельно, то интервал их объединения равен 824 Часть )71. Избранные тены А — В Работа: Т,(А О В) = Т,(А) + Т,(В) Интервал: Т (А Ы В) = Т,(А)+ Т, (В) Работа: Т1(А О В) = Т,(А) + Т1(В) Интервал: Т (А 0 В) = тах(Т, (А), Т Л(ВИ (а) (б) Рнс. 27.3. Работа н интервал составных подвычнсленнй. (а) Когда два подвычнслення соединены последовательно, работа нх объединения равна сумме отдельных работ, а интервал — сумме отдельных интервалов.
(б) Когда два подвычнслення соедннсны параллельно, работа нх объедннсння равна сумме отдельных работ, а интервал — максимальному нз отдельных интервалов. максимальному из индивидуальных интервалов. В случае процедуры Р-Р(в(п) запускаемый вызов Р-Р(в(п — 1) в строке 3 выполняется параллельно с вызо- вом Р-Г(в(п — 2) в строке 4. Следовательно, интервал Р-Р(в(п) можно записать в виде рекуррентного соотношения Т (и) = гпах(Т,(п — 1),Т (и. — 2)) + 9(1) = Т,(п — 1) + ез(1), решением которого является Т (п) = )В(тг).
Параллелизм процедуры Р-Г)п(п) равен Т)(п)/Т (п) = (Э(ф"/п), те. быстро растет с ростом п. Таким образом, даже на очень больших параллельных компьютерах средних значений и достаточно для достижения почти идеального линейного ускорения для процедуры Р-Р)в(п), поскольку она обладает значительным зазором параллельности. Параллельные циклы Многие алгоритмы включают циклы, все итерации которых могут выполняться параллельно. Как мы увидим, такие циклы можно распараллелить с помощью ключевых слов вратчп и лупе, но гораздо удобнее явно указать, что итерации в таких циклах могут выполняться одновременно.
В нашем псевдокоде такая функциональность обеспечивается ключевым словом рагайе1, предшествующим ключевому слову (ог в соответствующем цикле. В качестве примера рассмотрим задачу умножения матрицы А = (а, ) размером п х п на и-вектор х = (х ). Полученный в результате п-вектор у = (у,) определяется как уваа~ сих у=) для з = 1, 2....,п. Вычислить произведение матрицы на вектор можно путем параллельного вычисления всех элементов у следующим образом. зг5 Глава 77.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
