Собственно доклад ПОСТРОЕНИЕ ПЛАНОВ ПАРАЛЛЕЛЬНОГО ВЫПОЛНЕНИЯ ПРОГРАММ ДЛЯ ПРОЦЕССОРОВ СО СВЕРХДЛИННЫМ МАШИННЫМ СЛОВОМ был предста́влен на ХX конференции разработчиков свободных программ 04÷06 октября 2024 года, «Институт программных систем имени А.К.Айламазяна РАН» г. Переславль-Залесский.
Процессоры архитектуры сверхдлинного машинного слова (VLIW - Very Long Instruction Word) относятся к специфическим классам архитектур, прямо нацеленным на использование внутреннего параллелизма в алгоритмах (программах), причём параллелизм этот анализируется и планируется к рациональному использованию при вычислениях на программном уровне (используется идеологема EPIC - Explicitly Parallel Instruction Computing, явный параллелизм уровня машинных команд); при этом собственно аппаратная часть процессора освобождается от процедур распараллеливания (и поэтому потенциально должна стать проще и экономичнее применяющих внутреннее распараллеливание), а степень реализации потенциала параллелизма благодаря использованию (более богатых) программных ресурсов должна повыситься. В определённой степени VLIW-процессоры явились известной реакцией на ста́вший безобразно длинным конвейер в x86-серии процессорной архитектуры (хотя сам VLIW-подход конвейеризацию не отрицает).
VLIW-подход основан на идее загрузки во входной буфер процессора одновременно набора (bundle) допускающих параллельное выполнение машинных команд и исполнения этого ряда команд аналогично единой команде в процессорах классической архитектуры. VLIW-процессоры реализуют параллелизм уровня ILP (Instruction-Level Parallelizm, параллелизм уровня машинных инструкций) и SMP (Symmetric MultiProcessing, системы с общей памятью) идеологему работы с оперативной памятью. В рамках обеспечения импортонезависимости России разрабатываются процессоры ЭЛЬБРУС c VLIW-архитектурой (http://www.elbrus.ru/elbrus_arch), области применения которых - государственные и оборонные структуры, высокопроизводительные вычислительные системы (суперкомпьютеры).
Несмотря на выпуклое преимущество (программным путём дешевле реализовать сложные процедуры параллелизации), работа VLIW-процессоров сопряжена с известными проблемами. Среди них выделяют:
статичность полученных планов параллельного выполнения (с точки зрения автора недостатком не является, ибо преимущества в качестве программного распараллеливания с лихвой компенсируют эту особенность),
проблемы с излишней неравномерностью времени до́ступа к оперативной памяти разных вычислительных ядер (временна́я антиплотность кода, следствием является резкое снижение производительности из-за неизбежности определения время выполнения всей связки команд сверхдлинного слова по продолжительности наиболее продолжительной из них), для компенсации этого предусматривается использование процессора в режиме DSP (Digital Signal Processor) при расположении обрабатываемых данных в одноуровневой оперативной памяти.
Первыми истинными VLIW-компьютерами стали мини-суперкомпьютеры, выпущенные в начале 1980 г. компаниями MultiFlow, Culler и Cydrome (США). К первым VLIW-процессорам относят TriMedia (Нидерланды) и DSP C6000 (США), такую архитектуру имеют многоядерные процессоры фирмы Tilera Corp. Известны VLIW-процессоры Сrusoe, Efficeon (США), Itanium (США), Эльбрус (Россия). В настоящее время VLIW-подход широко применяется в рыночном сегменте устройств класса DSP (Digital Signal Processor) для смартфонов, систем управления автомобилями, носи́мых устройствах иных мобильных систем и в компонентах сетей сотовой связи (напр., процессоры Snapgragon Hexagon QDSP6 компании Qualcomm, Inc.).
Т.к. аппаратно во VLIW-архитектуре уже заложена линейка отдельных вычислительных ядер соответственно каждому слоту сверхдлинного слова, важным требованием является задача максимальной загрузки вычислительной аппаратуры (этих ядер). Есть данные, что одной из серьёзных проблем Itanium'а явилась как раз неприемлемо малая загрузка аппаратуры при некоторых типах алгоритмов.
Автор считает важнейшим для совершения вычислительных практик изучение свойств алгоритмов; влияние аппаратных реализаций вычислительных систем на развитие методов обработки данных при этом признаётся, но расценивается подчинённым. В данной работе главе́нствующим принято направления изучения свойств алгоритмов [1] и исследуются пределы использования свойства внутреннего (скрытого) их параллелизма, которые реально получить в ходе разработки планов параллельного выполнения алгоритмов (программ) согласно предлагаемой методике. Данные базируются на основе экспериментов, проведённых лично автором публикации и изложенными в книге [2].
Исследовательским инструментом являлась программная ПЛАТФОРМА DF-SPF [3], специально разработанная для данных целей и схематично показанная на рис. 1.
На вход программной системы поступает описание анализируемого алгоритма в императивном виде в форме ассемблероподобного языка или формального его описания в виде ориентированного ациклического Информационного Графа Алгоритма (далее ИГА) - зависимость вида “операторы → операнды”, при этом вершины графа ассоциируются с операторами (группами операторов) программы, а дуги – с линиями передачи данных, определяющими причинно-следственные зависимости между операторами.
Исходной информацией для анализа является алгоритм, описанный в императивном стиле на ассемблероподобном языке и с отсутствием явных указаний последовательности выполнения операторов; архитектурная модель SMP (Symmetric Multi Processing). Фактически модель D-F представляет симулятор граф-машины с сохранением принципа единократного присваивания и возможностью контроля интенсивностью вычислений путём управления дисциплиной выборки готовых к выполнению команд на поле параллельных вычислителей.
Выявление и анализ внутреннего логического параллелизма в алгоритмах реализовано с использованием агентной модели (модуль D-F) и универсального анализатора/преобразователя алгоритмов в форме информационных графов (модуль SPF@home). Неотъемлемой частью функционала модуля SPF@home является блок построения специальных сечений ИГА в виде его Ярусно-Параллельной Формы (далее ЯПФ), хотя реализованный языковыми средствами API (Application Programing Interface, интерфейс программирования приложения) потенциально дает возможность осуществить любой произвольный метод анализа и преобразований алгоритмов (напр., представляет интерес анализ частоты возникновения в конкретных алгоритмах пресловутых цу́гов (цепочек команд) Бабаяна-Волконского, [4]).
Оба упомянутых модуля разработаны с использованием языка C/C++ в стиле GUI для модели Win’32, являются полностью OpenSource и могут быть выгружены для свободного использования (формат инсталляционных файлов; http://vbakanov.ru/dataflow/content/install_df.exe , http://vbakanov.ru/spf@home/content/install_spf.exe, зеркала́ https://cloud.mail.ru/public/EdpR/1ghUN568p и https://cloud.mail.ru/public/9tKJ/YFnPni4aU соответственно). Вычислительные эксперименты проводились над набором оформленных в виде библиотеки программ (алгоритмов), реализующих наиболее часто применяющиеся алгоритмы (напр., линейной алгебры; библиотека может неограниченно расширяться усилиями участников исследований). Условность выполнения операторов реализуется предика́тным методом (что позволяет избежать мультивариантности ЯПФ), программные циклы перед выполнением разворачивались (“unrolling”) с использованием макросов.
При этом совершенно естественным является метод представления каждого слота сверхдлинного командного слова соответствующим сечением ИГА с выполнением последовательно по ярусам с начала до конца программы. Для получения рациональных (разумных, стремящихся к оптимальным вследствие NP-полноты задачи, [5]) являются целенаправленные эквивалентные (не нарушающие информационных связей в алгоритме) преобразования ЯПФ, описываемые с использованием скриптового языка Lua [6]. Основой создания этих сценариев является эвристический подход совместно с итерационным методом движения в сторону повышения качества разрабатываемых планов параллельного выполнения программ.
Предложено большое количество подходов к проблеме построения рациональных планов (расписаний) параллельного выполнения алгоритмов (и созданных на их основе программ); часть из них являются теоретическими и вряд ли когда-либо будут реализованы. Методологически автор данного исследования считает важным выбор соотношения между достаточно быстрой вычислительной процедурой (трудоёмкостью O(N2), где N - число вершин в ИГА) специального деле́ния графа и ювелирно выполняющейся основанной на использовании Lua-эвристик частью общей задачи. С точки зрения автора, при таком разделении труда (суперпозиция формальной и эвристической компонент) достигается бо́льшая эффективность по сравнению с приёмом, когда выборка каждого оператора начинается с “чистого листа”. Определённым недостатком конкретной реализации метода является ограниченность величин исследуемых данных (т.к. ИГА является параметризованным по размеру данных).
Дополнительным преимуществом подхода с использование ЯПФ является возможность поэтапного (с разбиением полного ИГА данного приложения на последовательные блоки) анализа (хотя и с некоторой потерей общей действенности метода). При этом первыми претендентами на локальное распараллеливание являются библиотечные процедуры.
Усреднённая степень использования параллельных вычислительных ресурсов оценивалась пространственной плотностью кода (рис. 2).
Для практического применения характеристику плотность кода (один из близких аналогов - коэффициент полезного действия) удобно оценивать коэффициентом использования параллельных вычислителей (считая общее число таких вычислителей равным ширине ЯПФ); незагру́женные полезными действиями вычислители обычно выполняют “команду-пустышку” NOP (нет операции) :
kи = ∑Wi / (W×H) = M / (W×H) ,
где Wi – ширина i-того яруса ЯПФ (здесь ∑Wi=M - число операций в рассматриваемом алгоритме, W=max(Wi), H – число ярусов ЯПФ). При полной загрузке всех вычислителей в течение всего времени выполнения алгоритма (программы) имеем kи≡1 (напр., вариант полностью последовательного выполнения); неслучайному достижению kи=1 в случае параллельного выполнения активно препятствуют информационные (причинно-следственные) связи типа “операторы → операнды”. Здесь плотность кода вычисляется упрощённо – как среднее по операциям; более точным был бы этот показатель по отношению к процессорным тактам, но анализ информационной структуры алгоритмов не подразумевает учёт количества тактов на операцию.
Основными характеристиками эффективности полученных планов считались следующие:
пространственная плотность кода - уровень загрузки вычислительных ядер VLIW-процессора (аналогично коэффициенту полезного действия в термомеханических системах) - коэффициент использования параллельных вычислителей kи,
вычислительная сложность целенаправленного преобразования ЯПФ – число элементарных шагов преобразования (в качестве меры выбрано число перемещений операторов с яруса на ярус ЯПФ).
Дополнительно анализировалась полученная в результате преобразования высота ЯПФ (параллельная вычислительная сложность) – оценка времени выполнения алгоритма (программы). Также (в первом приближении) не рассматривались вопросы размещения данных в многоуровневой памяти (определение параметров временно́й плотности кода - ближайшая задача исследования).
Как сказано, неявно ставилась задача определения максимальных степеней распараллеливания, реализуемых для VLIW-процессоров (памяту́я об одной из упомянутых проблем Itanium’а). Результаты вычислительных экспериментов по целенаправленному преобразованию ЯПФ представлены на риc. 3÷5.
a) – параллельная вычислительная сложность (высота ЯПФ), b) – вычислительная сложность преобразования ЯПФ (в единицах перемещений операторов с яруса на ярус), с) – плотность кода (в единицах kи);
1 – эвристика (метод преобразования) WithByWith, 2 – эвристика Dithotomy, 3 – аппаратное распараллеливание в симуляторе пото́кового (Data-Flow) вычислителя (приводится для сравнения)
В ходе исследований были предложены две эвристики преобразования ЯПФ (WithByWith и Dichotomy), обладающие - одна повышенным качеством получаемых планов при повышенной же вычислительной трудоёмкости реализации, другая – наоборот (потенциальные кандидаты на разную степень оптимизации). В целом показано, что для VLIW-процессоров с размером слота сверхдлинного слова в 4÷16 команд плотность кода изменяется в достаточно широком диапазоне (может доходить до 0,6÷1,0 с продолжающимся падением при дальнейшим росте слота) и повышается с увеличением размеров обрабатываемых данных (исследовались алгоритмы линейной алгебры с порядком матриц 10 и один искусственно сгенерированный алгоритм). При этом в случае применения эвристики WithByWith высота ЯПФ (параллельная вычислительная сложность) всё же незначительно меньше, чем в случае применения Dichotomy. Причудливая форма кривых в начальной части рис. 3 c) являются следствием противоречивых процессов, происходящих при целенаправленном изменения ЯПФ.
В целом стартующие от 0,8 значения плотности кода нельзя признать полностью удовлетворительным (вследствие его ма́лости). “Светом в конце тоннеля” может являться:
факт улучшения качества получаемых планов параллельного выполнения программ с возрастанием размеров обрабатываемых данных (с ростом порядка матриц резко возрастает число степеней свободы в расположении операторов по ярусам ЯПФ),
улучшение качества эвристик (автор ни в коей степени не считает, что достигнут оптимум при движении в этом направлении).
На рис. 6 приведены линейчатые т.н. TLD (Temporary Local Data) диаграммы распределения размеров временных локальных данных. Размер данных определяется в единицах некоторых обобщённых величин, для определения реальных размеров данных (напр., в байтах) используется информация из пула мер линий передачи данных.
матриц 10-го порядка классическим методом, b) - решения системы линейных
алгебраических уравнений 10-го порядка классическим безитерационным
методом последовательного исключения Гаусса, c) - построенная по
искусственно сгенерированному ИГА алгоритма e17039_o9853_t199.gv
На рис. 6 три слева направо в ряд расположенных тройки линейчатых диаграмм) фиксируют исходное состояние (напр., W=1000), некоторое промежуточное состояние (W=64 или W=32) и режим последовательного выполнения (W=1) для конкретного алгоритма; через HTLD и WTLD обозначены высота и ширина TLD по ярусам ЯПФ. Видно большое разнообразие в распределении TLD-данных по ходу выполнения алгоритма (для упрощения сравнения высо́ты графиков одинаково масштабированы).
матриц, 0 – огибающая, результирующая зависимость)
На рис. 7 представлен размер TLD-данных для различных степеней “ужа́тия” по ширине (ось абсцисс) ленточной диаграммы алгоритма умножения квадратных матриц 10-го порядка с иллюстрацией расположения максимума TLD-диаграмм вдоль этой оси (можно утверждать, что экстремумы практически постоянны).
Дополнительным полезным свойством системы SPF@home является возможность выявления претендентов на расположение в процессорном кэше (насколько правомочно говорить об этом в применении к схеме единократного выполнения операторов).
Обладающее перспективой является замеченное явление разницы между “верхним” и “нижним” ЯПФ. Оба варианта получения ЯПФ (в первом случае все операторы максимально "прижа́ты" к началу программы, во втором - к концу оной; назовём их ЯПФ(в) и ЯПФ(н) соответственно) требуют одинаковой вычислительной сложности при получении, но параметры их сильно отличаются (рис. 8÷9).
Как видно из рис. 8÷9, характер диаграмм интенсивности вычислений для ЯПФ(в) сохраняется; в случае использования ЯПФ(н) имеется явная тенденция к смещению максимума диаграмм ЯПФ к конечной части диаграммы (да и собственно неравномерности распределения – что хорошо видно по расположению пунктирной прямой, показывающей среднеарифметическое значение ординат кривой интенсивности вычислений). А раз вычислительная трудоёмкость получения ЯПФ(в) и ЯПФ(н) одинакова, есть резон начинать процесс целенаправленной модификации с состояния именно ЯПФ(н), при этом основным направлением переноса операторов будет “снизу вверх”.
N безитерационным методом последовательного исключения Гаусса
Обосновать (возможные) преимущества использования ЯПФ(н) при построении рациональных планов выполнения параллельных программ – задача Исследователя (возможно, из лица Читателей)..! В дальнейшем ничто не препятствует Исследователю обратиться к более изощрённым методам построения планов параллельного выполнения программ (см., напр., здесь: https://www.ispras.ru/dcouncil/docs/diss/2021/chernyh/chernyh.php?sphrase_id=5604670).
Нельзя считать невозможными дальнейшие усовершенствования эвристических методов целенаправленного преобразования ЯПФ как каркасов планов параллельного выполнения алгоритмов (программ).
Факт, что требование синхронизации по моменту старта одновременного всех операторов сверхдлинного слова для VLIW-архитектуры сильно ограничивает степени свободы при попытках достижения максимальной временно́й плотности кода. Вопрос о достижимости указанных показателей (в первую очередь плотности кода) вследствие труднопредсказуемых ограничений при схемотехнической реализации не может быть решен однозначно, однако на приведенные величины можно опираться. Эксплуатирующиеся во многих учебных заведениях системы симуляции вычислений (SIMICS, сети Петри) имеют дело не с алгоритмом, а с исполняемым кодом программы (что ценно, но избыточно и трудно варьируемо на этапе анализа именно алгоритмов как истинного “топлива для вычислений”).
Дальнейшие методы повышения степени использования поля параллельных вычислителей в случае выполнения алгоритмов с ограниченным потенциалом параллелизма (напр., разделение параллельного вычислительного поля несколькими приложениями одновременно) не анализировались вследствие требуемого излишнего усложнения планировщика задач местной операционной системы.
В принципе, отдельные параллельно функционирующие вычислительные ядра (соответствующие конкретному слоту в сверхдлинном слове), не обязательно должны быть гомогенными. Для этого случая в API системы SPF предусмотрен вариант создания в пределах каждого яруса ЯПФ нескольких подъярусов, соответствующих заданным мерам вершин и дуг (принципиально сходного эффекта можно ожидать от применения дополнительных фильтров при сечении ИГА на ярусы).
Целевыми потребителями разработанных методов генерации расписаний параллельного выполнения программ в первую очередь являются разработчики трансляторов и виртуальных машин, исследователи свойств алгоритмов (в направлении нахождения и рационального использования потенциала скрытого их параллелизма). Информационный граф алгоритма без труда восстанавливается на основе анализа причинно-следственных связей в программе после завершения работы компилятора; при этом логично библиотечные процедуры обрабатывать (компоновать) отдельно, используя имеющиеся наработки.
Лично мне по душе изречение автора "ereinion" от 24.07.2021 г. https://habr.com/ru/companies/selectel/articles/568862/ “При использовании в качестве процессоров общего назначения, VLIW пока не смогли преодолеть свой главный недостаток — высокие требования к культуре разработки и сложность создания компиляторов. Но кто знает, быть может эту проблему решат стремительно развивающиеся технологии машинного обучения — машинная оптимизация позволит, наконец, воспользоваться всеми преимуществами архитектуры и получить высочайшую производительность? Оставим этот вопрос открытым!”.
Если учитывать последнюю фразу - автор данной статьи фактически проводит подготовительную работу - строит (в форме итеративно стремящихся к некоему оптимуму последовательность “эвристик”) модель предметной области (концептуальную модель, учитывающую как поведение объекта, так и обрабатываемые данные).
Список литературы
1. AlgoWiki. Открытая энциклопедия свойств алгоритмов. Под ред.: Воеводин В., Донгарра Дж. URL: http://algowiki-project.org (дата обращения: 10.02.2024).
2. Баканов В.М. Практический анализ алгоритмов и эффективность параллельных вычислений. — М.: Пробел-2000, 2023. — 198 с. (https://www.litres.ru/book/v-m-bakanov/prakticheskiy-analiz-algoritmov-i-effektivnost-parallelnyh-vyc-70184365/).
3. V.M.Bakanov. Software complex for modeling and optimization of program implementation on parallel calculation systems. Open Computer Science, 2018, 8, Issue 1, Pages 228÷234, DOI: https://www.degruyter.com/document/doi/10.1515/comp-2018-0019/html
4. Железо на службе у алгоритма (продолжение). Борис Бабаян о прошлом, настоящем и будущем вычислительной техники. URL: https://habr.com/ru/articles/214377/ (дата обращения: 30.03.2024).
5. М.Гэри, Д.Джонсон. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982. — 416 с.
6. Иерузалимски Роберту. Программирование на языке Lua. — М.: ДМК Пресс, 2014. — 382 c.
Предыдущие публикации на тему исследования параметров функционирования вычислительных систем методами математического моделирования:
Есть ли параллелизм в произвольном алгоритме и как его использовать лучшим образом (https://habr.com/ru/post/530078/, 26.11.2020)
Такие важные короткоживущие данные (https://habr.com/ru/post/534722/, 24.12.2020)
Это непростое условное выполнение (https://habr.com/ru/post/535926/, 03.01.2021)
Динамика потокового вычислителя (https://habr.com/ru/post/540122/, 01.02.2021)
Параллелизм и плотность кода (https://habr.com/ru/post/545498/, 05.03.2021)
Сколько стоит расписание (https://habr.com/ru/post/551688/, 10.04.2021)
Параллелизм в алгоритмах - выявле́ние и рациональное его использование. Возможности компьютерного моделирования (https://habr.com/ru/articles/688196/ , 14.09.2022)
Построение планов параллельного выполнения программ для процессоров со сверхдлинным машинным словом (проект) (https://habr.com/ru/articles/792744/, 10.02.2024) - текущая
DZEN: Vector_Magistratum - https://dzen.ru/a/Zha6b_Rh8i5m8TMW
