Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 184
Текст из файла (страница 184)
Например, если порядок выполнения будет (1,2,3,7,4,6,6,8) или (1,4,6,6,2,3,7,8), мы получим корректный результат. В этом и заключается основная проблема гонки детерми- о29 Глава 27. Многопоточные алгоритмы нированности. В общем случае большинство порядков выполнения дают корректный результат — как в нашем случае, когда команды слева выполняются до команд справа или наоборот. Но некоторые порядки выполнения чередующихся команд приводят к неверным результатам. Из-за этого гонки крайне трудно тестировать.
Можно выполнять тесты сутки напролет и нн разу не столкнуться с ошибкой, а затем получить катастрофические последствия при эксплуатации готового программного обеспечения. Хотя справиться с проблемой гонки можно разными способами, включая применение взаимоисключающих блокировок и иных методов синхронизации, для наших целей мы просто будем гарантировать, что параллельно выполняемые фрагменты независимы: между ними не может возникнуть гонка детерминированности. Таким образом, в конструкции рагайе! Гог все итерации должны быть независимыми.
Между яразгп и соответствующим ему яупс запускаемый дочерний код должен быть независимым от кода родителя, включая код, выполняемый дополнительными запускаемыми или вызываемыми дочерними подпрограммами. Обратите внимание, что аргументы для запускаемой дочерней подпрограммы вычисляются родителем до того, как будет выполнен реальный запуск, так что вычисление этих аргументов происходит последовательно с любыми обращениями к ним после запуска.
В качестве примера того, насколько просто сгенерировать код с гонкой, приведем некорректную реализацию многопоточного умножения матрицы на вектор, интервал которой достигает значения го(18 и) путем распараллеливания внутреннего цикла 1ог. МАт-Чес-%кОтгл(А, к) 1 п = А.гоюв 2 у — вновь созданный вектор длиной п 3 рагайе! Гоге = 1!оп 4 у;=О 5 рвгайе! Гог ! = 1 го п 6 рагайе! Гог 2' = 1 го п 7 РЛ = У,+опхэ 8 гегвгп у К сожалению, эта процедура некорректна из-за гонки при обновлении Гп в строке 7, выполняемой параллельно для всех и значений 21 В упр.
27.1.6 предлагается разработать корректную реализацию алгоритма с интервалом В(18 п). Многопоточный алгоритм с гонкой иногда может оказаться корректным. Например, два параллельных потока могут сохранять одно и то же значение в совместно используемой переменной, и при этом не важно, какое значение будет сохранено первым. Однако в общем случае мы должны рассматривать код с гонкой как неверный.
830 Часть $Ж Избранные темы Урок шахмат Мы завершим этот раздел реальной историей, случившейся в процессе разработки многопоточной шахматной программы мирового уровня *8осга1ез (79), хотя конкретные данные немного упрощены для ясности. Прототип программы отрабатывался на 32-процессорном компьютере, но окончательная работа предполагалась на суперкомпьютере с 512 процессорами. В некотором месте разработчики применили оптимизацию, которая позволила снизить время работы при тестировании на 32-процессорной машине с Тзз = 65 до Тзз —— 40 секунд.
Затем разработчики использовали измерения работы и интервала и заключили, что эта оптимизированная версия, работающая быстрее на 32 процессорах, на самом деле окажется медленнее исходной версии при работе на машине с 512 процессорами. В результате такая "оптимизация" была отвергнута. Вот как выглядел их анализ. Исходная версия программы имела работу Т1 —— 2048 секунд и интервал Т = 1 секунда. Если рассматривать неравенство (27.4) как равенство, Тр = Т1/Р + Т, и использовать его как приближение времени работы на Р процессорах, то можно увидеть, что на самом деле Тю = 2048/32 + 1 = 65. При оптимизации работа становится равной Т, '= 1024 секунды, а интервал — Т' = 8 секунд.
Вновь используя наше приближение, получаем Т г = 1024/32 + 8 = 40. Однако относительные скорости этих двух версий меняются, когда мы вычисляем время работы на 512 процессорах. В частности, мы имеем Тыз 2048/512 + 1 = 5 секунд, а Тбш = 1024/512 + 8 = 10 секунд. Оптимизация, которая ускоряет программу при работе на 32 процессорах, делает ее в два раза более медленной на 512 процессорах! Оптимизированная версия интервала равна 8, и недоминирующий член в формуле времени работы на 32 процессорах становится доминирующим в случае 512 процессоров, полностью сводя на нег преимущества использования большего количества процессоров.
Мораль этой истории в том, что работа и интервал могут предоставить лучшее средство экстраполяции производительности, чем время работы. Упражнения гй1Л Предположим, что мы запускаем процедуру Р-Гш(п — 2) в строке 4 процедуры Р-Г~в, а не вызываем ее, как это делается на самом деле. Как это повлияет на асимптотические работу, интервал и параллелизм? гул.г Начертите ориентированный ациклический граф вычислений, получаемый при выполнении Р-Ргв(5). Считая, что каждый фрагмент вычисления выполняется за единичное время, вычислите работу, интервал и параллелизм данного вычисления. Покажите, как распределить полученный ориентированный ациклический граф по трем процессорам с использованием жадного планирования, пометив каждый фрагмент временным шагом, на котором он должен выполняться.
аЗ! Гаава гл Многоноаочные аагоритны 27.1.3 Докажите, что жадный планировщик обеспечивает следующую временную границу, несколько более строгую, чем доказанная в теореме 27.1: (27.5) Тр< +Т 27.1.4 Постройте ориентированный ациклический граф вычислений, для которого одно выполнение жадным планировщиком может потребовать почти в два раза больше времени, чем другое выполнение жадным планировщиком на том же количес'гве процессоров. Опишите работу этих двух разных выполнений вычисления. 27.1.5 Профессор выполняет измерения своего детерминированного многопоточного алгоритма на идеальном параллельном компьютере с жадным планировщиком на 4, 10 и 64 процессорах.
Он утверждает, что получил следующие величины: Те — — 80 секунд, Тес = 42 секунды и Та4 = 10 секунд. Докажите, что профессор либо врет, либо некомпетентен. (Укаэаниег воспользуйтесь правилом работы (27.2), правилом интервала (27.3) и неравенством (27.5) из упр. 27.1.3.) 27.1. 6 Разработайте многопоточный алгоритм для умножения матрицы размером п х п на и-вектор, который достигает уровня параллелизма 9(из/ 1к и) при работе ез(пз).
27.1.7 Рассмотрим следующий многопоточный псевдокод для транспонирования матри- цы А размером п х п "на месте", без привлечения дополнительной памяти. Р-Талия'озв(А) 1 и = А.гоген 2 рагайе! !ог 1' = 2 то и 3 рагайе! Тог ! = 1 то з — 1 4 обменять и; с ом Проанализируйте работу, интервал и уровень параллелизма этого алгоритма. 27.1.В Предположим, что мы заменили цикл рагайе! 1ог в строке 3 процедуры РТклхзгозе (см. упр.
27.1.7) обычным циклом Гог. Проанализируйте работу, интервал и уровень параллелизма полученного алгоритма. 27.1.9 Для какого количества процессоров две версии описанной выше шахматной программы будут иметь одинаковую скорость работы в предположении, что Тр = ввз Часть Г11. Иэбранные темы 27.2. Многопоточное умножение матриц В этом разделе рассматривается многопоточное умножение матриц, сериализованное время работы которого изучалось в разделе 4.2.
Мы изучим как многопоточные алгоритмы, основанные на стандартном тройном вложенном цикле, так и алгоритмы "разделяй и властвуй". Многопоточное умножение матриц вложенными циклами Первый алгоритм, который мы рассмотрим, — простейший алгоритм, основанный на распараллеливании циклов процедуры 8011лкп-Млтк1Х-Ми.т1г1лэ, приведенной на с. 100. Р-Б(ЯСАКЕ-МАТК1Х-М1ЛТ1Р1Х(А, В) 1 п = А.гоэлз 2 С вЂ” вновь созданная матрица размером и х и 3 рагайе! гог г' = 1 1о п 4 рагайе1 !ог 1' = 1 го и 5 св б $огlс = !гоп 7 с; = с,. + аеь . бьв 8 гегцгп С Для того чтобы проанализировать этот алгоритм, заметим, что поскольку его сериализацией является алгоритм 8011лкк-Млтк1Х-Ми1т1гьу, работа данного алгоритма представляет собой просто Т1 (п) = сэ(пз) — время работы алгоритма Боилкн-Млтк1Х-Миьт1гьу.
Интервал Т (п) = сэ(п), поскольку алгоритм следует вниз по пути в дереве рекурсии для цикла рагайе! !ог, начинающегося в строке 3, затем вниз по дереву рекурсии для цикла рагайе! !ог, начинаюшегося в строке 4, после чего выполняет все и итераций обычного цикла !ог, начинающегося в строке б, что в результате приводит к интервалу сэ(18 п) + 9(18 и) + 9(п) = 9(и). Таким образом, уровень параллелизма равен В(пз)1ех(п) = 6(пз).
В упр. 27.2.3 предлагается распараллелить внутренний цикл для получения уровня параллелизма, равного 9(из/18 п), чего нельзя добиться простым использованием рагайе! !ог, поскольку при этом создаются гонки. Многопоточный алгоритм "разделяй и властвуй" для умножения матриц Как мы знаем из раздела 4.2, матрицы размером п х п можно перемножить последовательно за время сэ(п~я ) = О(и~ ш), воспользовавшись стратегией "разделяй и властвуй" Штрассена. Естественным образом возникает вопрос о многопоточной версии этого алгоритма.
Начнем, как и в разделе 4.2, с многопоточной версии более простого алгоритма "разделяй и властвуй". Вспомним (с. 102), что процедура 80илкн-Млтк1Х-М11ьтпчх-кнсцкз1чн, которая умножает две матрицы, А и В, размером и х и и дает в результате матрицу С того же размера, основывается на разбиении каждой из трех матриц на Глава ах Мноеовоточлые алгоритмы ЗЗЗ четыре подматрицы размером п/2 х и/2: Ам Агг В Вы В12 С Сы Сгг После этого мы можем переписать умножение матриц следующим образом: С я Сгг Агл Агг Вм А11Вы АмВгг АггВы АжВгг / й) А12В21 АггВгг АггВш АггВгг / Р-МАтк!х-М1л.т1Р1х-нес1зкз1че(С, А, В) 1 и = А.гашз 2 !!и==1 3 с11 = аггбг1 4 е!зе пусть Т представляет собой новую матрицу размером и х и 5 Разбиение А, В, С и Т на подматрицы размером и/2 х п/2 А11,АппАм,Агг; Вы,В12,В21 Вгг' Сы Сгг С21~Сгг,' и Тп, Тпп Тгп Тгг', соответственно б зразчп Р-МАтк1Х-М1зет1Реч-Кес1зкз1че(С„, Аы, Вм) 7 зразтп Р-МАтк1Х-М1л.т1ич-йесикяче(С,г, А11, Вгг) 8 зраип Р-МАтк1Х-Мштпчх-йесикяче(С21,АгмВы) 9 зражп Р-МАтк1Х-М1зет1Р1ч-йес1зкз1че(Сгг, Ая, Вгг) 10 зраип Р-МАтк1х-Мш.т1Рьч-кес1зкз1че(Т11, А12, В21) !1 зраип Р-МАтк1х-М1зьт1Реч-нес1зкз1че(Т12, Агг, Вгг) 12 зразгп Р-МАтк1Х-М1з1т1Р1ч-йесцкз1че(Тг„Агг, В21) 13 Р-МАтк1Х-Миет1Реч-кес1зкз!че(Тгг, А2г, Вгг) 14 зупс 15 рига!!е! гог г' = 1 !о п 16 рагайе! !ог З = 1 !пи 17 ст = с3+!0 В строке 3 обрабатывается базовый случай умножения матриц размером 1 х 1.
Рекурсивный случай обрабатывается в строках 4-17. Память для временной матрицы Т выделяется в строке 4, а в строке 5 выполняется разбиение каждой из матриц А, В, С и Т на подматрицы размером п/2 х и/2. (Как и в процедуре Б0иАке-МАтк1х-М1зет1Р1ч-Кес1зкяче на с. 102, мы обошли молчанием гг эвк гпв Итак, для умножения двух матриц размером и х п мы выполняем восемь умножений матриц размером п/2 х п/2 и одно сложение матриц размером и х и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
