Построение планов параллельного выполнения программ для процессоров со сверхдлинным машинным словом (проект)
Процессоры архитектуры сверхдлинного машинного слова (VLIW — Very Long Instruction Word) относятся к специфическим классам архитектур, прямо нацеленным на использование внутреннего параллелизма в алгоритмах (программах), причём параллелизм этот анализируется и планируется к рациональному использованию при вычислениях на программном уровне; собственно аппаратная часть освобождается от процедур распараллеливания (и поэтому должна стать проще и экономичнее использующих внутреннее распараллеливание).
VLIW-подход основан на идее загрузки во входной буфер процессора одновременно набора (bundle) допускающих параллельное выполнение машинных команд и исполнения этого ряда команд аналогично единой команде в процессорах классической архитектуры. VLIW-процессоры реализуют параллелизм уровня ILP (Instruction-Level Parallelizm, параллелизм уровня машинных инструкций) и SMP (Symmetric MultiProcessing, системы с общей памятью) идеологему работы с оперативной памятью. Несмотря на выпуклое преимущество (программным путём дешевле реализовать сложные процедуры параллелизации), работа VLIW-процессоров сопряжена с известными проблемами. Среди них называют статичность полученных планов параллельного выполнения и проблемы с излишней неравномерностью времени доступа к оперативной памяти разных вычислительных ядер (временна́я антиплотность кода, следствием является резкое снижение производительности из-за неизбежности определять время выполнения всей связки команд сверхдлинного слова по продолжительности наиболее длинной из них).
Первыми истинными 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] и исследуются пределы использования свойства внутреннего (скрытого) их параллелизма, которые реально получить в ходе разработки планов параллельного выполнения алгоритмов (программ). Данные базируются на основе экспериментов, проведённых автором публикации в период 2018÷2023 г.г. при работе со студентами РТУ МИРЭА и НИУ ВШЭ (занятия с бакалаврами, магистрами, научно-исследовательский семинар студентов) и изложенными в книге [2].
Исследовательским инструментом являлась программная ПЛАТФОРМА DF-SPF, специально разработанная для данных целей и схематично показанная на рис. 1 [3].
Рисунок 1. Общая схема взаимодействия компонентов инструментального программного комплекса для исследования внутреннего параллелизма в алгоритмах (программах) и построения рациональных планов параллельного выполнения программ
На вход программной системы поступает описание анализируемого алгоритма в императивном виде в форме ассемблероподобного языка или формального его описания в виде ориентированного ациклического Информационного Графа Алгоритма (далее ИГА) — зависимость вида «операторы → операнды», при этом вершины графа ассоциируются с операторами (группами операторов) программы, а дуги — с линиями передачи данных.
Исходной информацией для анализа является алгоритм, описанный в императивном стиле на ассемблероподобном языке и с отсутствием явных указаний последовательности выполнения операторов; архитектурная модель SMP (Symmetric Multi Processing). Фактически модель D-F представляет симулятор граф-машины с сохранением принципа единократного присваивания и возможностью контроля интенсивностью вычислений путём управления дисциплиной выборки готовых к выполнению команд на поле параллельных вычислителей. Условность выполнения операторов реализуется предикатным методом, программные циклы перед выполнением разворачивались (»unrolling») с использованием макросов.
Выявление и анализ внутреннего логического параллелизма в алгоритмах реализовано с использованием агентной модели (модуль D-F) и построения специальных сечений ИГА в виде его Ярусно-Параллельной Формы (далее ЯПФ, модуль SPF@home). Оба упомянутых модуля разработаны с использованием языка C/C++ в стиле GUI для модели Win»32, являются полностью OpenSource и могут быть выгружены для свободного использования (формат инсталляционных файлов; http://vbakanov.ru/dataflow/content/install_df.exe, http://vbakanov.ru/spf@home/content/install_spf.exe). Вычислительные эксперименты проводились над набором оформленных в виде библиотеки программ (алгоритмов), реализующих наиболее часто применяющиеся алгоритмы (напр., линейной алгебры; библиотека может неограниченно расширяться усилиями участников исследований).
Методом получения рациональных (разумных, стремящихся оптимальным вследствие NP-полноты задачи, [4]) являются целенаправленные эквивалентные (не нарушающие информационных связей в алгоритме) преобразования ЯПФ, описываемые с использованием скриптового языка Lua [5]. Основой создания этих сценариев является эвристический подход совместно с итерационным методом движения в сторону повышения качества разрабатываемых планов параллельного выполнения программ.
Можно считать, что при этом не менее 50% всей работы выполняется (достаточно быстрой) процедурой создания ЯПФ по ИГА вычислительной трудоёмкостью O (N2), где N — число вершин в ИГА; остальная часть реализуется ювелирным использованием Lua-эвристик. С точки зрения автора исследования, при таком разделении труда (суперпозиция формальной и эвристической компонент) достигается большая эффективность по сравнению с приёмом, когда выборка каждого оператора начинается с «чистого листа». Дополнительным преимуществом подхода с использование ЯПФ является возможность поэтапного (с разбиением полного ИГА данного приложения на последовательные блоки) анализа (хотя и с некоторой потерей общей действенности метода).
Усреднённая степень использования параллельных вычислительных ресурсов оценивалась пространственной плотностью кода (рис. 2).
Рисунок 2. К определению пространственной плотности кода
Для практического применения характеристику плотность кода (один из близких аналогов — коэффициент полезного действия) удобно оценивать коэффициентом использования параллельных вычислителей (считая общее число таких вычислителей равным ширине ЯПФ); незагру́женные полезными действиями вычислители обычно выполняют «команду-пустышку» NOP (нет операций) :
kи= ∑Wi / (W*H) = M / (W*H) ,
где Wi — ширина i-того яруса ЯПФ (здесь ∑Wi=M — число операций в рассматриваемом алгоритме, W=max(Wi), H — число ярусов ЯПФ). При полной загрузке всех вычислителей в течение всего времени выполнения алгоритма (программы) имеем kи≡1 (напр., вариант полностью последовательного выполнения); неслучайному достижению kи=1 в случае параллельного выполнения активно препятствуют информационные (причинно-следственные) связи типа «операторы → операнды».
Основными характеристиками эффективности полученных планов считались следующие:
пространственная плотность кода — уровень загрузки вычислительных ядер VLIW-процессора (аналогично коэффициенту полезного действия в термомеханических системах) — коэффициент использования параллельных вычислителей kи,
вычислительная сложность целенаправленного преобразования ЯПФ — число элементарных шагов преобразования (в качестве меры выбрано число перемещений операторов с яруса на ярус ЯПФ).
Дополнительно анализировалась полученная в результате преобразования высота ЯПФ (параллельная вычислительная сложность) — оценка времени выполнения алгоритма (программы).
В ходе исследований было обращено внимание на возможность снижения вычислительной сложности преобразований ЯПФ при первоначальном оной построении в «нижнем» варианте (все операторы находятся на максимально приближенных к концу программы ярусах, при этом преобладающим направлением миграции операторов является направленность в сторону начала программы).
Результаты вычислительных экспериментов по целенаправленному преобразованию ЯПФ представлены на риc. 3÷5.
Рисунок 3. Алгоритм m_matr_10.set умножения квадратных матриц 10 порядка классическим методом, оси абсцисс — ширина ЯПФ после оной преобразования:
a) — параллельная вычислительная сложность (высота ЯПФ), b) — вычислительная сложность преобразования ЯПФ (в единицах перемещений операторов с яруса на ярус), с) — плотность кода (в единицах kи);
1 — эвристика (метод преобразования) WithByWith, 2 — эвристика Dithotomy, 3 — аппаратное распараллеливание в симуляторе пото́кового (Data-Flow) вычислителя (приводится для сравнения)
Рисунок 4. Алгоритм slau_10.set решения системы линейных алгебраических уравнений 10 порядка классическим безитерационным методом последовательного исключения Гаусса
Рисунок 5. Искусственно сгенерированный ИГА алгоритма e17039_o9853_t199.gv
В ходе исследований предложены две эвристики преобразования ЯПФ (WithByWith и Dichotomy), обладающие — одна повышенным качеством получаемых планов при повышенной же вычислительной трудоёмкости реализации, другая — наоборот (потенциальные кандидаты на разную степень оптимизации). В целом показано, что для VLIW-процессоров с размером слота сверхдлинного слова в 4÷16 команд плотность кода изменяется в достаточно широком диапазоне (может доходить до 0,6÷1,0 с продолжающимся падением при дальнейшим росте слота) и повышается с увеличением размеров обрабатываемых данных (исследовались алгоритмы линейной алгебры с порядком матриц не выше 10).
Нельзя считать невозможными дальнейшие усовершенствования эвристических методов целенаправленного преобразования ЯПФ как каркасов планов параллельного выполнения алгоритмов (программ). В действительности указанные показатели могут оказаться не полностью достижимыми (вследствие труднопредсказуемых ограничений при реализации), однако это величины, на которые можно опираться.
Дальнейшие методы повышения степени использования поля параллельных вычислителей в случае выполнения алгоритмов с ограниченным потенциалом параллелизма (напр., разделение параллельного вычислительного поля несколькими приложениями одновременно) не анализировались вследствие требуемого излишнего усложнения планировщика задач местной операционной системы.
Целевыми потребителями разработанных методов генерации расписаний параллельного выполнения программ в первую очередь являются разработчики трансляторов и виртуальных машин, исследователи свойств алгоритмов (в направлении нахождения и рационального использования потенциала скрытого их параллелизма).
Исследовательская ПЛАТФОРМА DF-SPF и разработанные с её помощью методики (приёмы выявления скрытого параллелизма и его параметров в произвольных алгоритмах, способы построения рациональных планов выполнения параллельных программ на заданном поле вычислителей) ряд лет применяются при обучении студентов в указанных университетах России и позволили повысить компетенции учащихся в области теории и практики параллельной обработки данных.
Список литературы
1. AlgoWiki. Открытая энциклопедия свойств алгоритмов. Под ред.: Воеводин В., Донгарра Дж. URL: http://algowiki-project.org (дата обращения: 15.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. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, Книга по Требованию, 2012. — 420 c.
5. Иерузалимски Роберту. Программирование на языке Lua. — М.: ДМК Пресс, 2014. — 382 c.
