- Ваши половые предпочтения? - Гетеро! // “Вспомнить всё”, режиссёр Пол Верховен, 1990
Современные многоядерные процессоры все чаще разрабатываются с вычислительными ядрами различных возможностей. Поэтому практически полезно уметь строить расписание выполнения параллельных программ для подобных систем (с гетерогенным полем параллельных вычислителей).
В случае гетерогенности поля параллельных вычислителей большая часть работы выполнятся Lua-скриптами (поддержка в виде API-функций системы позволяет производить любые манипуляции с ЯПФ), при этом общий стиль работы скорее напоминает аге́нтный подход (программный агент из “облака операторов” последовательно по ярусам ЯПФ распределяет операторы по “подходящим” вычислителям. При этом положительным является возможность активного использования информации из пула данных метрик вершин (операторов) и дуг (линий передачи данных). Имена всех Lua-вызовов даются согласно файлу-справке API_User.pdf.
Построение планов (расписаний) параллельного вычисления на системах с гетерогенным вычислительным полем
Информация о возможности выполнения конкретного оператора на конкретном вычислителе задаётся в файлах ХYZ.OPS и XYZ.CLS (OPS, CLS являются рекомендуемыми расширениями файлов, причём XYZ - обычно имя проекта, при отсутствии таких файлов используются имена файлов по умолчанию OPERATORS.OPS и CALCULATORS.CLS). Файлы типов OPS и CLS используются всегда вместе и служат для определения, на каких вычислителях (Calcs) может быть выполнен данный оператор (Ops) в случае гетерогенного поля параллельных вычислителей.
Формат файлов *.OPS параметров операторов следующий (допускаются переносы со строки на строк, после символа ‘;’ может следовать комментарий до конца строки):
˄=n1/n2: ˄-nameParam1˄Val1˄-nameParam2˄Val2˄ ... ; комментарий
где ˄ - один или несколько пробелов,
n1, n2 - диапазон ("от/до" включительно) номеров операторов, для которых задаются далее следующие параметры (n1,n2 - целые числа, символы равенства, прямого слэша и двоеточия обязательны),
nameParam1, nameParam2… - имя параметра, начинается с символа дефиса, первый символ после дефиса обязательно буква на латинице, далее любые символы (кроме пробела), имя параметра регистрозави́симо; после =n1/n2: должен следовать хотя бы один параметр,
Val1, Val2… - значение данного параметра (интерпретируется как вещественное, разделитель целой и дробной частей - точка).
Формат файлов *.CLS параметров для вычислителей следующий:
˄=n1/n2:˄-nameParam1˄minVal1˄maxVal1˄-nameParam2˄minVal2˄maxVal2˄ ... ; комментарий
где n1,n2 - диапазон ("от/до" включительно) номеров вычислителей, для которых задаются далее следующие параметры (n1, n2 - целые числа, символы равенства, прямого слэша и двоеточия обязательны,
nameParam1,nameParam2 - имя параметра, начинается с символа дефиса, первый символ после дефиса обязательно буква на латинице, далее любые символы (кроме пробела), имя параметра регистрозави́симо; после =n1/n2: должен следовать хотя бы один параметр,
minVal1 и maxVal1, minVal2 и maxVal2 - минимум и максимум значений данного параметра (интерпретируются как вещественные, разделитель целой и дробной частей - точка).
Условием выполни́мости данного оператора на заданном вычислителе является minVal_i≤Val_i≤maxVal_i для одинакового i (где Val_i, minVal_i, maxVal_i – числовые значения данного параметра для оператора и вычислителя соответственно).
- Напр., Lua-вызов GetParamsByOp(Op) возвращает полную строку параметров оператора Op, вызов CanExecOpCalc(Op,Calc) определяет возможность выполнения оператора Op на вычислителе Сalc. Для проверки корректности зада́ния параметров служит вы́зов PutParamsAll(), выводящий в текстовый фрейм исходные и откорректированные (синтаксически неверные подстроки удаляются) строки параметров (эти строки заключены в вертикальные черты). Если строка пустая (выводится символ ‘||’), то параметры не загружались или файлы параметров пустые.
При проверке возможности выполнения данного оператора Op на заданном вычислителе Calc с помощью вызова CanExecOpCalc(Op,Calc) именно оператор фактически является клиентом, который запрашивает возможность обслуживания (выполнение) у сервера (вычислителя). В соответствии с этим условие выполнимости заключается в удовлетворении всех запросов клиента Op данным сервером Calc (фактически список параметров оператора связан логическим ‘И’). Если численное значение n каждого из запросов клиента попадает в диапазон (включая границы) n1÷n2 численных значений сервера (с тем же именем параметра, естественно), вызов CanExecOpCalc(Op,Calc) возвращает число больше нуля (число удовлетворяющих условию выбора параметров - оно равно, конечно, GetCountParamsByOp(Op) для данного оператора); в противном случае возвращается (для информации) значение меньше нуля, равное числу совпадений (оно по модулю меньше GetCountParamsByOp(Op). Если строка параметров оператора Op пустая - он может выполняться на любом вычислителе; если строка параметров вычислителя Сalc пустая - на нём не может выполняться ни один оператор.
- Предварительно параметры должны быть загружены в систему посредством вызовов LoadFileNameParamsCalcs(FileName) и LoadFileNameParamsOps(FileName), где FileName – файлы параметров.
Общее число вычислителей от 1 до max(n1,n2) по всем диапазонам (определяется вызовом GetCountCalcs()); вариантом является описание =n1/n2: с последующим (заве́домо уникальным) именем параметра вычислителя (вычислителей), не совпадающим ни с одним из параметров операторов. В случае перекры́тия имён параметров в разных строках в расчёт принимается первое вхожде́ние (в порядке чтения CLS, OPS).
- Весьма практически-полезный сервис предоставляет API-функция TestCanExecAllOpsCalcs(), которая при нулевом значении параметра возвращает true, если каждый оператор может быть выполнен хотя бы на одном вычислителе и false, ежели хоть один оператор не может быть выполнен ни на одном вычислителе. При ненулевом входном параметре выдаётся (для каждого оператора) список вычислителей, на которых данный оператор может быть выполнен. В (проблемном) случае возвра́та false полезно вызвать также PutParamsAll() для уточнения проблемы.
Дополнительно системой SPF поддерживаются файлы задания метрик вершин (операторов) *.mvr и дуг (информационных связей) *.med; принципы их организации и обработки сходны ранее описанным (подробнее см. ранее упомянутый файл API_User.pdf). В mvr-файлах могут быть описаны, напр., длительности выполнения отдельных операторов, в med-файлах – закономерности определения латентности при обмене данными (напр., в виде ре́перных точек при описании зависимости кусочно-линейной функцией).
- Из сказанного видно, что разработка расписания для выполнения программы на гетерогенном поле параллельных вычислителей является более сложной процедурой относительно ранее описанных и здесь упор делается на Lua-программирование. Т.к. на одном ярусе ЯПФ могут находиться операторы, требующие для выполнения различных вычислителей, полезной может служить метафора расщепления ярусов ЯПФ на семейства подъярусов, каждое из которых соответствует блоку вычислителей c определёнными возможностями (т.к. все операторы данного яруса обладают одинаковыми возможностями выполнения, последовательность обработки их в пределах яруса/подъяруса в первом приближении произвольна).
На схеме рис. 39 а) показана схема расщепления операторов на одном из ярусов ЯПФ в случае наличия 3 параллельных вычислителей 2-х типов, на рис. 39 b) - результат расчёта реального плана выполнения параллельной программы на гетерогенном поле параллельных вычислителей (3 типа вычислителей по 5, 3 и 4 штук соответственно, номера исполняемых операторов скрыты).
В этом случае общее время T решения задачи определяется суммой по всем ярусам максимальных значений времён выполнения операторов на подъярусах данного яруса:
где j - число ярусов, i- число подъярусов на данном ярусе, kj - типы вычислителей на j-том ярусе, tik - время выполнения оператора типа i на вычислителе типа k.
Если ставится задача достижения максимальной производительности, возможно определить число вычислителей конкретного типа, минимизирующее T (решение обратной задачи оптимизации по соотношению числа вычислителей разных типов, при такой постановке плотность кода максимизируется автоматически). Задача минимизации общего времени решения T согласно формуле (7) усложняется в случае возможности выполнения каждого оператора на нескольких вычислителях вследствие неоднозначности tik в вышеприведённом выражении; здесь необходима дополнительная “балансировка” по подъярусам.
В общем случае здесь решается обратная задача для каждого алгоритма (группы алгоритмов), где неизвестными, минимизирующими функцию цели (плотность кода) является количество вычислителей каждого типа, входящих в границы гетерогенного вычислительного поля.
- Идея подъярусов “шевелилась в извилинах” у автора давно. Он понимал, что можно при генерации ЯПФ “усилить фильтр” относительно однофакторного по причинно-следственным (информационным) параметрам; напр., реализовать фильтрацию дополнительно по времени выполнения операторов etc. Но (согласно высказыванию автора по методологическим вопросам в публикации #016) было ясно, что ЯПФ в таком случае превратится в хаос (“блюдо макарон”) из сотен/тысяч ярусов и даже проанализировать такое спагетти будет практически невозможно. Именно поэтому автор отошёл от мысли усиления фильтра и решил прибегнуть к ювелирному использования эвристических методов при организации подъярусов. Надо признаться – это ему (автору, конечно!) удалось далеко неидеально – плотность кода получилось невысокой…
А как Вы, Читатели, относитесь к идее “подъярусов”?.. Можете ли Вы предложить нечто лучшее?
Авторские ресурсы:
- Cloud Mail.ru: https://vk.com/valery_bakanov?w=wall647639183_101
