Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 183
Текст из файла (страница 183)
Многопоточные алгоритчы МАт-Чес(А,х) 1 п = А. гоп в 2 у — вновь созданный вектор длиной и 3 рагайе! !ог г = 1 го и 4 у,=О 5 рагайе! Гог1 = 1!оп 6 Гог5'=1!оп 7 у, = у,+а,х. 8 геецгп у В этом коде ключевые слова рагайе! Гог в строках 3 н 5 указывают, что итерации соответствующих циклов могут выполняться одновременно. Компилятор может реализовать каждый цикл рагайе! !ог как подпрограмму с вложенным параллелизмом. Например, цикл рагаПе! !пг в строках 5-7 может быть реализован с помощью вызова Мат-Чес-Ма!н-1.00Р(А, х, у, и, 1, и) в стиле "разделяй и властвуй"; при этом компилятор генерирует вспомогательную подпрограмму Мат-Чес-Мин-Г.ООР следующим образом. МАТ-Чес-МА!х-(.ООР(А, х, у, п, 1, у) 1 !Г1== 1~ 2 !ог 5' = 1 1о п 3 у;=у,+а,х, 4 е!зе тЫ = ((1+ 1')/2) 5 зразгп Мат-Чес-Мл1н-(.ООР(А, х, у, и,1, гпЫ) 6 МАт-Чес-МА!х-(.ООР(А, х, у, и, елЫ + 1, г') 7 аупс Этот код рекурсивно запускает первую половину итераций цикла параллельно со второй половиной, а затем выполняет команду зупс, тем самым создавая бинарное дерево выполнения, листья которого представляют отдельные итерации цикла, как показано на рис.
27.4. Для вычисления работы Т1 (п) процедуры Мат-Чес в случае матрицы размером п х и мы просто вычисляем время работы сериализации этого алгоритма, получаемой простой заменой циклов рагайе1 Гог обычными циклами Гог. Таким образом, мы имеем Т1 (и) = 63(пз) из-за доминирующего квадратичного времени работы дважды вложенных циклов в строках 5-7. Этот анализ, однако, игнорирует накладные расходы, связанные с рекурсивным запуском в реализации с параллельными циклами.
В действительности накладные расходы увеличивают работу параллельного цикла по сравнению с его сериализацией, но не асимптотически. Чтобы понять, почему это так, заметим, что поскольку дерево экземпляров рекурсивной процедуры является полным бинарным деревом, количество внутренних узлов на 1 меньше количества листьев (см. упр. Б.5.3). Каждый внутренний узел выполняет константную работу по разделению диапазона итераций, а каждый лист соответствует итерации цикла, которая требует как минимум константного времени (чЭ(п) в данном случае), Таким образом, можно амортизировать наклад- об Часть П!.
Избранные мены Рнс. 27.4. Ориентированный ациклический граф, представляющий вычисление Млт-Чпс-Ммн(.оог(А, к, р, 8, 1, 8). Два числа внутри каждого скругленного прямоугольника указывают значения двух последних параметров (з и з' в заголовке процедуры) при запуске или вызове процедуры.
Черные круги представляют фрагменты, соответствующие либо базовому случаю, либо части процедуры до запуска Мат-Чкс-ммн-).оог в строке 5; серые круги представляют фрагменты, соответствующие части процедуры, которая вызывает Млт-Чпс-Ммм-(.оог в строке 6 ло ключевого слова аупс в строке 7, где выполнение приостанавливается до тех пор, пока не будет осуществлен возврат полпрограммы, запущенной в строке 5; белые же круги представюпот фрагменты. соответствующие (незначительной) части процедуры после ключевого слова зувс и до тачал возврата из ПРОЦЮ1УРЫ.
ные расходы рекурсивного запуска, получая вклад, соответствующий не более чем добавлению постоянного множителя к общей работе. С практической точки зрения динамически многопоточные параллельные платформы иногда пгрубляюпг (соагаеп) листья рекурсии, выполняя несколько итераций в пределах одного листа, либо автоматически, либо по команде программиста, тем самым снижая накладные расходы рекурсивного запуска. Правда, зто снижение достигается ценой уменьшения уровня параллелизма, но если вычисление имеет достаточный зазор параллельности, близкое к идеальному линейное усюрение при этом в жертву не приносится.
Мы также должны учесть накладные расходы на рекурсивные запуски в ходе анализа интервала конструкции параллельного цикла. Поскольку глубина рекурсивных вызовов логарифмически зависит от количества итераций, в случае параллельного цикла с и итерациями, в котором з-я итерация имеет интервал з(ег,о(з), интервал цикла равен Т (и) = й(1би) + гпах 1(ег (г) 1<1<и Например, для процедуры Мдт-Чес в случае матрицы размером и х и параллельный цикл инициализации в строках 3 и 4 имеет интервал 9(1б и), поскольку рекурсивный запуск доминирует над юнстантной работой в каждой итерации. Интервал дважды вложенных циклов в строках 5-7 составляет Н(и), поскольку каждая итерация внешнего цикла рагайе! 1ог содержит и итераций внутрен- Л77 Глаоо 27.
Ммогоооточоые аегоритмы него (последовательного) цикла !пг. Интервал остального кода процедуры имеет константное значение, и, таким образом, доминирует интервал дважды вложенных циклов, что дает общий интервал всей процедуры 9(п). Поскольку работа равна Й(ез ), уровень параллелизма имеет значение Й(п )/Й(п) = Й(п). (В упр. 27.1.6 предлагается построить реализацию с еще большим уровнем параллелизма.) Условии гонки Многопоточный алгоритм является детермииированньим (де1еппппз11с), если он всегда приводит к одним и тем же результатам при одних и тех же входных данных, независимо от того, как именно планируются команды в многоядерном компьютере.
Алгоритм является иедетерминированным, если его поведение может меняться от выполнения к выполнению. Зачастую многопоточные алгоритмы, каторые должны быть детерминированными, таковыми не являются, поскольку содержат "гонку детерминированности" (де1епп1пасу гасе). Гонка является проклятием параллельных вычислений. Среди знаменитых ошибок, связанных с ней, — прибор радиационной терапии ТЬегас-25, убивший трех пациентов и серьезно навредивший еще нескольким, и североамериканское затмение 2003 года, когда без злектричества остались более 50 миллионов человек.
Эти пагубные ошибки очень трудно найти. Можно проводить различные многодневные тесты и так н не обнаружить спорадически проявляющиеся неполадки. Гонка детерминированности осуществляется в том случае, когда две логически параллельные команды обращаются к одной и той же ячейке памяти и как минимум одна из них выполняет запись.
Приведенная далее процедура иллюстрирует условие гонки. клсе-ЕхлмРье( ) 1 х=О 2 рагайе! !ог е' = 1 то 2 3 х=х+1 4 рпп1 х После инициализации переменной х значением 0 в строке ! процедура КАсеЕхлмРье создает два параллельных фрагмента, каждый из которых увеличивает х в строке 3. Хотя, на первый взгляд, процедура клсе-ЕхАмРье должна всегда выводить значение 2 (ее сернализация так и делает), может оказаться выведенным и значение 1. Давайте разберемся, как это может случиться.
Когда процессор увеличивает значение переменной х, эта операция не является неделимой, а состоит из последовательности команд. 1. Чтение х из памяти в один из регистров процессора. 2. Увеличение значения в регистре. 3. Запись значения из регистра обратно в переменную х в памяти. Часть Гтй Избранные теин В1В ! ! Л 7О.! Ж, . зг 2 ) я):=; х.,' 4 .гЗ вЂ”, х ~ 3 ~ (нсгг; ) 5 ) 1)псе ге ! К 7 !'.тэчг), б ', .т=гз ! 8 ~рг)нй.гг ~ Шаг х г! гз ! О 2 О О 3 О 1 4 О ! О 5 О ! 1 6 1 ! ! 7 ! ! 1 (б) (а) Рип 27.5. Иллюстрация гонки детерминированности в процедуре Каса-Ехамгьа.
(в) Ориентированный ациклический граф вычисления указывает зависимости между огдельнымн юмаиламн. гг и гз представляют собой регистры процессора. Команды, не относшциеся к гонке, такие как реализация управления циклом, опущены. (б) Последовательность выполнения, приводящая к ошибке, с указанием значения х в памяти и значений регистров гз и гт для каждого шага последовательности выполнения. На рис. 27.5, (а) показан ориентированный ациклический граф вычисления, представляющий выполнение гтдсе-Ехдырье, с фрагментами, разбитыми на отдельные команды.
Вспомним, что, поскольку идеальный параллельный компьютер поддерживает последовательную согласованность, параллельное выполнение многопоточного алгоритма можно рассматривать как чередование команд с учетом зависимостей в ориентированном ациклическом графе. В части (б) рисунка показаны значения при выполнении вычисления, вызывающем аномалию. Значение х хранится в памяти, а г! и г.й представляют собой регистры процессора. На первом шаге один из процессоров устанавливает значение х равным О. На шагах 2 и 3 процессор 1 считывает значение х из памяти в свой регистр г! и увеличивает его, в результате чего в регистре г; хранится значение, равное 1. В этот момент в игру вступает процессор 2, выполняющий команды 4-6.
Процессор 2 считывает значение х из памяти в свой регистр гз и увеличивает его, в результате чего в регистре гз хранится значение„равное 1; затем он сохраняет полученное значение в переменной х, присваивая ей значение 1. Теперь процессор 1 продолжает работу с шага 7, сохраняя значение 1 из регистра г! в переменную х„что оставляет значение х неизменным. Следовательно, на шаге 8 выводится значение 1, а не 2, как в случае сериализованной процедуры. Мы видим, что получается.
Если при параллельном выполнении процессор ! выполняет свои команды до процессора 2, выводится значение 2. Если при параллельном выполнении, напротив, процессор 2 выполняет свои команды до процессора 1, выводится то же значение 2. Если же команды двух процессоров выполняются одновременно, то может случиться так, как в приведенном примере, когда одно из изменений значения х оказывается потерянным. Конечно, множество выполнений не приводит к ошибке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
