Основные данные вычислительных экспериментов по реорганизации ярусно-параллельной формы  (ЯПФ) информационных графов алгоритмов (ТГА) приведены в предыдущей публикации. Цель текущей публикации – показать окончательные результаты исследований разработки расписаний выполнения параллельных программ  в показателях вычислительной трудоёмкости собственно преобразования  и качества полученных расписаний. Данная работа является итогом вполне определённого цикла исследований в рассматриваемой области.

Как и было сказано ранее, вычислительную трудоёмкости (ВТ) в данном случае будем вычислять в единицах перемещения операторов с яруса на ярус в процессе реорганизации ЯПФ. Этот подход близок классической методике определения ВТ операций упорядочивания (сортировки) числовых массивов, недостатком является неучёт трудоёмкости  процедур определения элементов для перестановки.

Т.к. в принятой модели ЯПФ  фактически определяет порядок выполнения операторов параллельной программы (операторы выполняются группами по ярусам поочерёдно), в целях сокращения будем иногда использовать саму аббревиатуру “ЯПФ” в качестве синонима понятия плана (расписания) выполнения параллельной программы. По понятным причинам исследования  проводились на данных относительно небольшого объёма в предположении сохранения корректности полученных результатов при обработке данных большего размера.  Описанные в данной публикации исследования имеют цель продемонстрировать возможности имеющегося инструментария при решении поставленных задач.  При желании возможно исследовать произвольный алгоритм, описав и отладив его в модуле Data-Flow с последующим импортом в формате информационного графа в модуль SPF@home для дальнейшей обработки.

Основной целью преобразований ЯПФ продолжаем считать получение максимальной плотности кода (фактически максимальная загрузка имеющихся в наличии отдельных вычислителей параллельной вычислительной системы). Кстати, именно с этими понятиями связано известное зло-ироничное  высказывание об излишнем количестве NOP-инструкций в “связках” сверхдлинного машинного слова в вычислителях VLIW-архитектуры (даже при наличии участков полностью последовательного кода лакуны в сверхдлинном слове формально должны быть заполнены некоей операцией-“пустышкой”).

В наличии NOP-операторов во VLIW-связке нет ничего постыдного – в алгоритмах встречаются чисто последовательные участки. Плохо, когда VLIW-связка малозаполнена  реально изменяющими данные операторами  постоянно (одна из причин краха проекта Itanium)…

Как и ранее, будем ссылаться на разработанные эвристические методы (иногда сокращённо именуемые просто  эвристиками), реализованные на языке Lua и управляющие преобразованиями ЯПФ. Также не учитываем возможности одновременного выполнения команд нескольких процессов на параллельном поле вычислителей (хотя теоретически это может привести к повышению плотности кода).

В приводимых исследованиях не учитывалось ограничение на  реальный объём памяти для временного хранения данных между ярусами операторов (обычно регистров общего назначения), это ограничение может ухудшить полученное  решение (а использование оперативной памяти для декларируемой цели - снизить быстродействие). С другой стороны, моделирование даёт возможность оценить разумный размер регистрового файла.   

Полученные результаты предназначаются для улучшения качества  разработки расписаний выполнения параллельных программ  в распараллеливающих компиляторах будущих поколений. При этом внутренняя реализация данных конечно, совсем  не обязана предусматривать явного построения ЯПФ в виде двумерного массива, как для большей выпуклости показано на рис.2 в этой публикации и выдаётся программным модулем SPF@home (http://vbakanov.ru/spf@home/content/install_spf.exe). Она может быть любой удобной для компьютерной реализации – например, в наивном случае устанавливающей однозначное соответствие между формой ИГА в виде множества направленных дуг {k,l} (матрица смежности) и двоек номеров вершин i_k,j_k и i_l,j_l, где i,j – номера строк и столбцов в ЯПФ (процедуру преобразования ИГА в начальную ЯПФ провести всё равно придётся, ибо в данном случае именно она выявляет параллелизм в заданном ИГА алгоритме; только после этого можно начинать любые преобразования ЯПФ).

Учитывая давно известный факт о продвижении активной (там, где в данный период времени происходит энергичное выполнение машинных команд) области операторов вдоль фронта выполняемой программы, при нехватке памяти обработку можно проводить блоками последовательно от начала выполнения программы к её концу – при этом выходные вершины предыдущего блока являются входными для последующего.

Для каждой из группы рассматриваемых задач (преобразования с сохранением высоты исходной ЯПФ или при возможности увеличения высоты оной) рассмотрим по две методики (эвристики, ибо так согласились именовать разработки) – для перового  случая это “1-01_bulldozer” vs “1-02_bulldozer”, для второго - “WidthByWidtn” vs “Dichotomy”. Мне стыдно повторять это, но высота ЯПФ определяет время выполнения программы…

1. Получение расписания параллельного выполнения программ при сохранении высоты ЯПФ

Сохранение высоты исходной  ЯПФ равносильно выполнению алгоритма (программы) за минимально возможное время. Наиболее равномерная нагрузка на все вычислители параллельной системы будет при одинаковой ширине всех ярусов ЯПФ (среднеарифметическое значение). В ЯПФ реальных алгоритмов и размерности обрабатываемых данных среднеарифметическое значение является довольно большим (практически всегда много большим числа отдельных вычислителей в параллельной системе). Т.о. рассматриваемый случай не часто встречается в практике, но всё же должен быть разобран.

Для сравнения выберем часто анализируемые ранее алгоритмы и два эвристических метода целенаправленного преобразования их ЯПФ – эвристики “1-01_bulldozer” и “1-02_bulldozer”.

Результаты применения этих эвристик приведены на рис. 1-3; обозначения на этих рисунках (по осям абсцисс отложены показатели размерности обрабатываемых данных):

• графики a), b) и с) – ширина ЯПФ, коэффициент вариации (CV ширин ярусов ЯПФ),  число перемещений (характеристика вычислительной трудоёмкости) операторов соответственно;

• сплошные (красная), пунктирные (синяя) и штрих-пунктирные (зелёная) линии – исходные данные, результат применения эвристик “1-01_bulldozer” и  “1-02_bulldozer” cответственно.

Данные рис. 1-3 показывают, что во многих случаях удаётся приблизиться к указанной цели. Напр., рис. 1a) иллюстрирует снижение ширины ЯПФ до 1,7 раз (метод “1-01_bulldozer”) и до 3 раз (метод “1-02_bulldozer”) при умножении матриц 10-го порядка.

Коэффициент вариации ширин ярусов ЯПФ (рис. 1b) приближается к 0,3 (граница однородности набора данных) при использовании эмпирики “1-02_bulldozer” и, что немаловажно, достаточно стабилен на всём диапазоне размерности данных.

Трудоёмкость достижения результата (рис. 1c) при использовании метода “1-02_bulldozer” значительно ниже (до 3,7 раз при порядке матриц 10) метода “1-01_bulldozer”.

Важно, что эффективность метода возрастает с ростом размерности обрабатываемых данных.

Не менее эффективным показал себя метод  “1-02_bulldozer” на алгоритме вычисления коэффициента парной корреляции (рис. 2).

Попытка реорганизации ЯПФ алгоритма решения системы линейных алгебраических уравнений (СЛАУ) порядка до 10 обоими методами (рис. 3) оказалась малополезной. Ширину ЯПФ снизить не удалось вообще (рис. 3a), снижение CV очень мало (рис. 3b), однако метод “1-02_bulldozer” немного выигрывает в трудоёмкости (рис. 3c).

Для большей полноты выводов объём исследований должен быть  расширен, однако уже сейчас ясно, далеко не каждый метод реорганизации ЯПФ одинаково эффективен для преобразования (в смысле построения рационального  расписания параллельного выполнения) различных алгоритмов. Т.к. принятый в данной работе общий подход предполагает итеративное приближение к наилучшему решению поставленной задачи, надлежит продолжить разработку новых эвристик (с учётом достигнутого).

2. Получение расписания параллельного выполнения программ на фиксированном числе параллельных вычислителей

Эта постановка задачи максимально близка к реальному случаю составления расписания для VLIW-машины с заданным числом процессорных команд в машинном слове (размер “связки”, “бандла” сверхдлинного машинного слова). При этом достигается и повышение плотности кода.

Ниже рассматривается распространенный случай выполнения программы на заданном гомогенном поле из  W параллельных вычислителей (от W=W₀ до W=1, где W₀ – ширина ЯПФ, а нижняя граница соответствует полностью последовательному выполнению). Сравниваем два метода реорганизации ЯПФ – “Dichotomy” и “WidthByWidtn”:

• “Dichotomy”. Цель – получить вариант ЯПФ с c шириной не более заданного W c увеличением высоты   методом перенесения операторов с яруса на вновь создаваемый ярус ниже данного. Если ширина яруса выше W, ровно половина операторов с него переносится на вновь создаваемый снизу ярус и так далее, пока ширина  станет не выше заданной W. Метод работает очень быстро, но “грубо” (высота ЯПФ получается явно излишней и неравномерность ширин ярусов высока).

• “WidthByWidtn”. Подлежат переносу только операторы яруса с числом операторов выше заданного N>W путём создания под таким  ярусом число ярусов М, равное:

Особенностью этой  эвристики является правило выбора конкретных операторов,  подлежащих переносу на вновь создаваемые ярусы.

На рис. 4,5  показаны результаты выполнения указанных эвристик в применении к двум распространенным алгоритмам линейной алгебры - умножение квадратных  матриц классическим методом  и решение системы линейных алгебраических уравнений прямым (неитерационным) методом Гаусса; красные и синие линии на этих и последующих рисунках соответствуют эвристикам “WidthByWidtn” и “Dichotomy” соответственно. Не забываем, что ширина реформированной ЯПФ  здесь соответствует числу команд в “связке” сверхдлинного машинного слова.

Как видно из рис. 4 и 5, оба метода на указанных алгоритмах приводят к близким результатам (из соображений представления ЯПФ плоской таблицей и инвариантности общего числа операторов в алгоритме это, конечно,  гипербола!). При большей высоте ЯПФ увеличивается время жизни данных, но само их количество в каждый момент времени снижается.

Однако “при всех равно-входящих” соответствующие методу “WidthByWidtn” кривые расположены ниже, нежели по методу “Dichotomy”; это соответствует несколько большему быстродействию. Полученные методом “WidthByWidtn” результаты практически совпадают с идеалом высоты ЯПФ, равным N_сумм./W_средн. , где N_сумм. – общее число операторов, W_средн. – среднеарифметическое числа операторов по ярусам ЯПФ при заданной ширине ея.

Анализ результатов, приведённый на рис. 6 и 7, более интересен (хотя бы потому, что имеет чисто практический интерес – вычислительную трудоёмкость преобразования ЯПФ). Как видно  из рис. 6 и 7, для рассмотренных случаев метод  “WidthByWidtn” имеет меньшую (приблизительно в 3-4 раза) вычислительную трудоёмкость (в единицах числа перестановок операторов с яруса на ярус) относительно метода “Dichotomy” (хотя на первый взгляд ожидается обратное). Правда, при этом метод (эвристика) “WidthByWidtn” обладает более сложной внутренней логикой по сравнению с “Dichotomy” (в последнем случае она примитивна). ). Логично использовать в распараллеливающих компиляторах  метод “Dichotomy” для быстрого (но достаточно “грубого”) построения планов выполнения параллельных программ, а метод “WidthByWidtn” – для построения этих планов в режиме  оптимизации.

Т.о. проведено сравнение методов реорганизации (преобразования) ЯПФ конкретных алгоритмов с целью их параллельного выполнения на заданном числе вычислителей. Сравнение проведено по критериям вычислительной трудоёмкости преобразований и неравномерности загрузки параллельной вычислительной системы.

Используя разработанное программное обеспечение, возможно анализировать любые алгоритмы по указанным критериям с целью выбора наиболее эффективных (минимально простых и максимально результативных) методов определения рациональных расписаний выполнения параллельных программ.

В соответствие  с присущим эвристическому подходу итерационному принципу постепенного приближения к наилучшему решению рассматриваемой задачи автор уверен в возможности количественного улучшения (относительно вышеприведённым параметрам) методик определения расписаний выполнения программ на заданном поле параллельных вычислителей.

Предыдущие публикации на тему исследования параметров функционирования вычислительных систем методами математического моделирования:

• Есть ли параллелизм в произвольном алгоритме и как его использовать лучшим образом (https://habr.com/ru/post/530078/, 26.11.2021)

• Такие важные  короткоживущие данные (https://habr.com/ru/post/534722/, 24.12.2021)

• Это непростое условное выполнение (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) - текущая