Целенаправленные преобразования ЯПФ без увеличения высоты ея
Как говорилось ранее, продолжаем рассматривать ЯПФ в качестве плана (расписания) выполнения программ на поле параллельных вычислителей (пока неопределённой размерности – размер поля будет соответствовать заявленным целям).
- Предварительно вспомним рис. 10 в публикации #009 и сопровождающие его сентенции о степени примени́мости метода использования ЯПФ для анализа параллелизма в алгоритмах – она ограничена!..
Начнём исследования с самого простейшего - изучим с помощью инструмента SPF зависимости пространственной и временно́й сложности алгоритмов (фактически ширины и высоты ЯПФ) от величины обрабатываемых данных (порядка матриц для задач класса линейной алгебры).
На рис. 24 приведены параметры двух алгоритмов при разных размерах обрабатываемых данных (умножение квадратной матрицы на вектор и МНК- аппроксимации методом наименьших квадратов экспериментальных точек), программы из файлов M_MATR_VEC_N.GV и MNK-2_N.GV, где N – порядок системы и число экспериментальных точек соответственно); кривые 1 - высота ЯПФ (параллельная сложность), 2 – ширина ЯПФ, 3 – ускорение вычислений согласно (1).
Полученные данные благоприятны для вычислительной практики – при возрастании размеров обрабатываемых данных параллельная сложность и ускорение вычислений возрастают линейно, однако ширина ЯПФ для случая умножения матриц растёт сильнее линейной зависимости.
Приведённые данные в общем подтверждают полученные с помощью инструмента DF (рис. 19 и соответствуют условиям неограниченного параллелизма).
Метафора BULLDOZER целенаправленного преобразования ЯПФ
Проблема логики действий целенаправленного преобразования ЯПФ вполне реальна. Автор предлагает (красивую) метафору BULLDOZER (не имеет ничего общего с широкоизвестной микроархитектурой фирмы Advanced Micro Devices, Inc.) для визуализации эвристического подхода к построению соответствующих Lua-методик (см. миниатюру ниже). Здесь осуществляются аналогии действий Lua-эвристики с отва́лом бульдозера, осуществляющим сдвиг почвы с возвышенностей во впадины (аналог распределения ширин ярусов ЯПФ). Целевым параметром (к которому нужно стремиться) для эвристических методов является среднеарифметическая величина ширин ярусов ЯПФ (просветлённые вспомнят теорему о среднем значении определённого интеграла) - и точка нулевого СV, кстати..! Отва́л ("нож") бульдозера при "сглаживании" ЯПФ может перемещаться как “сверху вниз” так и “снизу вверх” – как удобнее в каждом конкретном случае (иногда полезно считать, что у бульдозера два отва́ла - спереди и сзади - и он может работать при движении в обоих направлениях).
Критерием окончания процесса перестановки операторов служит исчерпа́ние возможностей передвижения любых операторов между ярусами ЯПФ (определяется выбранной стратегией целенаправленных перемещений).
- Очень интересный психологический момент “огово́рки по Фрейду” – в своё время автор занимался конструированием оборудования для пластической деформации металлов (см. здесь, тут и здесь), поэтому метафора процесса “раска́тки (выра́внивания) поверхности почвы бульдозером” для него вполне органи́чна.
К слову говоря, не вызовет особых сложностей динамическое изменение заданной ширины ярусов ЯПФ (фактически числа заде́йствованных параллельных вычислителей) подходящим способом (напр., используя кусочно-линейную интерполяцию) согласно определённым правилам. Но это уже вторже́ние в область планирования вычислений в условиях многозада́чности – а автор в данный момент не готов решать такие проблемы..!
До сих пор мы считали равноприоритетными перестано́вки с яруса на ярус ЯПФ любых операторов. Однако при “перемеще́нии грунта” можно (и полезно!) использовать дополнительные фильтры по параметрам перемещ́аемых операторов (а средства для зада́ния этих параметров в системе SPF имеются – см. публикацию #019); в некоторых случаях при этом удаётся добиться повышения результирующей плотности кода. // PS. Вопрос на “силу ума́” – подумайте (и подве́ргните внутренней критике!) – фильтр по какому параметру рационально использовать в целях повышения плотности кода..?
Чуть отвлечёмся на принципиальный момент. Вопрос – как Читатель представляет себе рожде́ние формальных методов (в данном случае неважно чего – тут ключевое слово именно формальных)? Не кажется ли ему, что всегда изнача́льно у исследователей (“в де́брях ума своего”) рождаются именно эвристические методы и только потом (далеко не сразу, а после множества прове́рок на де́йственность) эти “эври́стики” переходят в разряд “формали́стик”?..
● Подели́тесь своими соображениями на этот счёт! А может, Вы являетесь приве́рженцем “врождённых знаний”? Не было ли у Вас мгновения, когда происходил “момент внезапного озаре́ния” (неожиданно оказывается, что Вы трудно и давно обдумываемый предмет определённо давно знали, но вспомнили только сейчас)..? Автор не зря спрашивает про тако́е – пару раз пришлось столкнуться с подо́бным…
Итак, продолжаем рассматривать случай невозраста́ния высоты ЯПФ. Этот случай соответствует приближённому условию P≈Ŵ (число параллельных вычислителей P сопостави́мо с Ŵ - средней шириной ЯПФ).
Как обычно, приоритетом является скорость выполнения алгоритма (число ярусов ЯПФ ограничено снизу длиной критического пути в заданном алгоритме); недостатком является большая пространственная сложность (требование огромного числа параллельных вычислителей, подавляющее большинство из которых будут использованы лишь малое время выполнения программы, см. временно́й график интенсивности вычислений – см. рис. 15 и др.).
Однако имеется дополнительная проблема – каким образом оценивать равномерность распределения ширин ЯПФ по высоте оной? Применим стандартную формулу коэффициента вариации CV (где σ - среднеквадратичное отклонение ширин ярусов, Ŵ - среднеарифметическое ширин ярусов, Wi – ширина i-то яруса; суммирование идёт по всем ярусам i):
Интересно, понимает Читатель, с какой целью σ делится на Ŵ ? Поделитесь!..
На рис. 25÷26 показаны результаты применение двух сходных методов (“эвристик”), основанных на метафоре BULLDOZER и реализованных на языке Lua. Скрипт с именем 1_Bulldozer.lua формально следует указанной выше метафоре, скрипт же 2_Bulldozer.lua реализует дополнительные возможности. На рис. 25÷26 кривые 1 (сплошные) – исходные параметры алгоритмов, 2 (пунктир) – результат преобразования согласно эвристики 1_Bulldozer.lua, 3 (штрих-пунктир) – преобразование согласно 2_Bulldozer.lua; a) – ширина ЯПФ, b) – (коэффициент вариации, рассчитанный согласно (5), c) – число перемещений операторов с яруса на ярус ЯПФ (вычислительная трудоёмкость получения плана параллельного выполнения).
Полученные данные информативны. В целом можно сказать, что идея целенаправленного изменения ЯПФ работоспособна – удаётся создать план параллельного выполнения алгоритмов без увеличения времени выполнения (высоты ЯПФ, параллельной сложности) с понижением ширины (ср. пунктир/штрих-пунктир со сплошными линиями) и снижением неравномерности ширин. Получены количественные оценки трудоёмкости преобразований, причём получение планов с лучшими результатами требуют бо́льшей трудоёмкости (особенно выпукло на рис. 26).
В то же время следует признать, что достигнутые результаты ограничены. В первую очередь малоприемлема равномерность распределения ширин ЯПФ (считается, что совокупность данных является однородной только при CV≤0,33; такая величина при анализе результатов сглаживания ширин ярусов ЯПФ встречается нечасто). К тому же разброс параметров для различных алгоритмов слишком вели́к.
В целом надо сказать, что внутренние свойства алгоритмов достаточно успешно “сопротивляются” попыткам сглаживания ширин ярусов ЯПФ, хотя попытки совершенствования эвристик её преобразования дают эффект (ср. кривые 2 и 3 на рис. 25÷26).
- Читатель вправе вы́казать претензии автору в легковесности количества фактического материала (выводы сделаны на основе всего двух серий экспериментов – рис. 25÷26 соответственно). Автор возразит, что на самом деле цикл экспериментов включал значительно бо́льшее их количество, и все они показали схо́дные результаты (как во́дится, в публикацию вошли наиболее вы́пуклые итоги экспериментов).
К счастью, работа в режиме P≈Ŵ соблюдается нечасто (в подавляющем большинстве случаев P≪Ŵ и высоту ЯПФ неизбежно приходится увеличивать).
PS. Полный текст скрипта Bulldozer.lua здесь не приводится, однако подсказку можно дать (см. схему ниже); c целью лучшего понимания вло́женности циклов они выделены разным цветом (см. самые левые столбцы таблицы). Sapienti Sat...
Не зря показанная на вышеприведённой миниатюре эвристика названа наи́вной. На самом деле под понятие эвристики подходят любые творческие методы. Для конкретного случая можно использовать перемещения операторов только в одну сторону (“вверх” или “вниз” относительно ЯПФ), но можно и использовать перемещения в обоих направлениях; можно неоднократно изменять направление движения “отва́ла бульдозера’ etc.
И главное (повтори́м на всякий случай!) – проведённые согласно модели SPF расчёты априори не соответствуют условию достижения максимальной плотности кода (а именно в этом режиме реализуется минимум времени выполнения всей программы – к чему логично стремиться; вторично отсыла́ю к рис. 10 в публикации #009). Ассоциация синхронизации по началу выполнения каждой машинной команды с определённым ярусом ЯПФ в таких условиях неприе́млема. В данном случае логично было бы использовать для расчёта планов параллельного выполнения программ описанный в публикации #010 инструмент DF или же один из методов, приведённых в таблице в публикации #013 (классификация А.А.Прихожего – исключая получение ЯПФ графа алгоритма, естественно).
Читатель понимает, конечно, что вышеприведённый пример предста́влен для иллюстрации формального применения основанной на ЯПФ методике расчёта; способ вполне работоспособен (хотя экстремальной плотности кода при его использовании не достигнуть). При его употреблении для многоядерного процессора, например, размер гранул параллелизма должен быть значительно больше одной машинной инструкции (возможно, даже прибли́жен к режиму макропараллелизма – см. публикацию #018).
Всё ре́ченное остаётся верным и в случае модификации ЯПФ при возможности увеличения её высоты. Публикация #016 относится к особому случаю применения ЯПФ для расчётов планов параллельного выполнения программ для процессоров с VLIW-архитектурой (архитектура со сверхдлинным машинным словом). В этом случае все машинные команды начинают выполняться одновременно (синхронизация по времени); при этом вполне логично ассоциировать начало выполнения сверхдлинного слова с (соответствующим) ярусом ЯПФ.
Резюме - метод анализа (и, соответственно, преобразования) алгоритма следует выбирать с учётом ло́гико-физической реализации выбранной вычислительной системы (её архитектуры).
Авторские ресурсы:
Информация о канале вообще и его оглавление…
- В работе мы будем использовать специализированное авторское программное обеспечение (фактически исследовательские инструменты), предназначенное для выявления в произвольных алгоритмах параллелизма и его рационального использования при вычислениях.
В.М.Баканов. Практический анализ алгоритмов и эффективность параллельных вычислений. ISBN 978-5-98604-911-3. 2023. LitRes.ru