Русский
Русский
English
Статистика
Реклама

Скрытый параллелизм

Есть ли параллелизм в произвольном алгоритме и как его использовать лучшим образом

26.11.2020 16:14:32 | Автор: admin

Параллелизации обработки данных в настоящее время применяется в основном для сокращения времени вычислений путем одновременной обработки данных по частям на множестве различных вычислительных устройств с последующим объединением полученных результатов. Параллельное выполнение позволяет обойти сформулированный лордом Рэлеем в 1871 г. фундаментальный закон, согласно которому (в применимости к тепловыделению процессоров) мощность их тепловыделения пропорциональна четвертой степени тактовой частоты процессора (увеличение частоты вдвое повышает тепловыделение в 16 раз) и фактически заменить его линейным от числа параллельных вычислителей при сохранении тактовой частоты). Ничто не дается даром задача выявления (обычно скрытого для непосвящённого наблюдателя, [1]) потенциала параллелизма в алгоритмах не является лежащей на поверхности, а уж эффективность его (параллелизма) использования тем более.

Ниже приведена иллюстрация процесса выявления параллелизма для простейшего случая вычисления выражения axb+a/c (a, b, c входные данные).

а) облако операторов (последовательность выполнения не определена), б) полностью последовательное выполнение, не определена), б) полностью последовательное выполнение, в) параллельное исполнение

Даже в таком примитивном алгоритме параллельное выполнение ускорило вычисления в полтора раза, но потребовало двух вычислителей вместо одного. Обычно с увеличением числа операторов (усложнением алгоритма) ускорение вычислений возрастает (хотя имеются и полностью нераспараллеливаемые на уровне арифметических действий алгоритмы напр., вычисление чисел Фибоначчи). Для приведенного на рис.1 алгоритма все выкладки легко выполняются в уме, но для реальных (много более сложных алгоритмов) требуется машинная обработка.

Параллельная вычислительная система включает несколько вычислителей (арифметико-логических устройств), объединённых общей или локальной оперативной памятями и кэшами. Современные параллельные системы часто имеют не только гомогенное, но и гетерогенное вычислительное поле. Задача распределения вычислений между отдельными вычислителями приводит к разработке расписания (плана) вычислений. Проблемой является многозначность расписаний параллельного выполнения алгоритма в общем случае это NP-полная задача [2], точное решение (при заданных оптимизационных требованиях) которой можно получить только методом полного перебора (что нереально при числе операторов уже более сотен-тысяч). Выходом является использование эвристических методов, исходя из сложности данную область знания можно обоснованно отнести к наиболее сложным случаям Науки о данных (Data Science).

Параметрам выполнения распространенных алгоритмов в параллельном варианте посвящен известный ресурс AlgoWiki [3].

Особенно интересен, с точки зрения автора, вариант параллелизации для языков программирования высокого уровня без явного указания распараллеливания и в системах c концепцией ILP (Instruction-Level Parallelism, параллелизм на уровне команд, с реализацией посредством вычислительной архитектуры EPIC (Explicitly Parallel Instruction Computing, явный параллелизм выполнения команд). При этом аппаратное обеспечение вычислительных систем сильно упрощается и все проблемы выявления параллелизма и построение собственно расписания выполнения программы для заданной конфигурации параллельной вычислительной системы ложатся на компилятор, что ведет к его усложнению и снижению скорости компиляции.

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

Одной из важных процедур выявления параллелизма по заданному ИГА является получения его исходной (обладающей свойством каноничности) Ярусно-Параллельной Формы (ЯПФ), [4]. При этом условием расположением операторов на едином ярусе является независимость их друг от друга по информационным связям (необходимое условие их параллельного выполнения).

Получение такой (без условия ограниченности количества операторов на ярусах) ЯПФ требует O(N2) действий, где N число операторов (вершин графа), ее высота (общее число ярусов) равна увеличенной на единицу длине критического пути в ИГА. Напрямую использовать такую ЯПФ в качестве основы для построения расписания выполнения параллельной программы обычно затруднительно (ширина некоторых ярусов часто сильно превышает число имеющихся параллельных вычислителей). Но т.к. вычисление такой ЯПФ вычислительно малозатратно, во многих случаях целесообразно начинать анализ именно с ее получения и в дальнейшем проводить модификацию этой ЯПФ с учетом конкретных задач. При этом при каждой модификации ЯПФ получаем новую форму, полностью соответствующую исходному ИГА.

Определенным недостатком использования метода построения ЯПФ для получения расписания является невозможность учета времени исполнения операторов, однако для современных микроархитектур характерно всемерное стремление к одинаковости времен выполнения всех операторов, что как раз повышает удобство использования ЯПФ.

На рис. ниже приведен несложный случай алгоритма вычисления вещественных корней полного квадратного уравнения ax2+bx+c=0.

На рисунке -ярусно-параллельная форма алгоритма решения полного квадратного уравнения в вещественных числах в канонической форме (номера ярусов ЯПФ расположены справа)На рисунке -ярусно-параллельная форма алгоритма решения полного квадратного уравнения в вещественных числах в канонической форме (номера ярусов ЯПФ расположены справа)

Показанная ЯПФ уже является расписание выполнения параллельной программы (выполнение начинается сверху вниз, требует 6 относительных единиц времени и 4-х параллельных вычислителей). При этом число задействованных вычислителей по ярусам крайне неравномерно (важно при однозадачном режиме работы вычислительной системы) на 1-м ярусе задействованы все 4, на 2,3,4 - только один и по два на 5- и 6 ярусах. Однако легко видеть, что простейшее преобразование (показанные красным пунктиром допустимые перестановки операторов с яруса на ярус) позволяют выполнить тот же алгоритм за то же (минимальное из возможных) время всего на двух вычислителях! Не для любого алгоритма получается столь идеально часто для снижения требуемого числа параллельных вычислителей единственным путем является увеличение времени выполнения алгоритма (возрастание числа ярусов ЯПФ).

Для решения задач определения рационального (на основе заданных критериев) расписания выполнения произвольных алгоритмов создан инструментальный программный комплекс, включающая два модуля - D-F и SPF@home. Свободная выгрузка инсталляционных файлов доступна с ресурсов http://vbakanov.ru/dataflow/content/installdf.exe и http://vbakanov.ru/spf@home/content/installspf.exe соответственно (дополнительная информация по теме - http://vbakanov.ru/dataflow/dataflow.htm и http://vbakanov.ru/spf@home/spf@home.htm).

 На рисунке - схема инструментального комплекса (*.set и *.gv программный файл и файл информационного графа анализируемой программы соответственно, *.mvr, *.med файлы метрик вершин и дуг графа алгоритма соответственно, *.cls, *.ops файлы параметров вычислителей и операторов программы соответственно, *.lua текстовый файл на языке Lua, содержащий методы реорганизации На рисунке - схема инструментального комплекса (*.set и *.gv программный файл и файл информационного графа анализируемой программы соответственно, *.mvr, *.med файлы метрик вершин и дуг графа алгоритма соответственно, *.cls, *.ops файлы параметров вычислителей и операторов программы соответственно, *.lua текстовый файл на языке Lua, содержащий методы реорганизации

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

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

Для управления созданием расписания используется встроенный скриптовый язык Lua (Lua написан на ANSIC, обеспечивает неявную динамическую типизацию, поддерживает прототипную модель объектно-ориентированного программирования и был выбран на основе свойств его компактности, полной открытости исходных кодов и близости синтаксиса к распространенному С).

Родительское приложение создано с использованием языка программирования С++, является GUI Win32-программой и доступно для свободной выгрузки и использования (как и исходные тексты) через GIT-репозиторий. Вывод данных осуществляется на экран в текстовом и графическом форматах и в файлы (также в структурированной текстовой форме).

Сочетание компилируемой родительской программы и встроенного интерпретатора скриптового языка позволило обеспечить высокую производительность и гибкость (Lua-вызовы фактически являются обертками для API-функций модуля SPF@home).

Копии экранов обсуждаемого комплекса приведены на изображениях ниже (программные модули D-F и SPF@home соответственно).

Модуль D-F (Data-Flow) является фактически универсальным вычислителем, выполняющим программу на ассемблероподобном языке на заданном числе параллельных вычислителей. При их числе большем 1 вычисления ведутся по принципу Data-Flow (реализуется статическая потоковая архитектура), операторы выполняются по условию готовности их к выполнению (ГКВ), что является следствием присвоенности значений все операндам данного оператора; при единичном вычислителе реализуется обычное последовательное выполнение. В случае превышения числа ГКВ-операторов числа свободных вычислители используется задаваемая система приоритетов их выполнения, условное выполнение реализуется предикатным выполнением, для реализации циклов используется система макросов, разворачивающая циклические структуры. Модуль D-F имеет встроенную систему проверку корректности ИГА, для контроля выполнения используется динамическая цветовая индикация выполненности операторов.

Программы для D-F составляются в императивном стиле, каждый оператор по уровню сложности сопоставим с уровнем ассемблера, порядок расположения операторов в программе несущественен. Нижеприведен пример записи программы вычисления вещественных корней полного квадратного уравнения (входной set-файл для модуля D-F, механизм предикатов в приведенном варианте не используется):

Такая программа может рассматриваться как результат компиляции с языков программирования высокого уровня, не содержащих явных указаний на параллелизацию вычислений. В модуле D-F программа отлаживается, результат выдается в файл ИГА-формата для обработки в модуле SPF@home. В модуле SPF@home для получения ЯПФ из gv-файла (стандартный формат текстовых файлов описаний графов), запоминания его во внутреннем представлении системы, создание ЯПФ и запоминание его в Lua-массиве для дальнейшей обработки может быть выполнен следующий код (наклоном выделены API-вызовы системы, двойной дефис означает начало комментария до конца строки):

CreateTiersByEdges("EdgesData.gv")  -- создать ЯПФ по файлу EdgesData.gv -- с подтянутостью операторов вверх-- CreateTiersByEdges_Bottom("EdgesData.gv")  -- создать ЯПФ по файлу EdgesData.gv -- с подтянутостью операторов вниз--OpsOnTiers={} -- создаём пустой 1D-массив OpsOnTiers for iTier=1,GetCountTiers() do -- по ярусам ЯПФ   OpsOnTiers[iTier]={} -- создаём iTier-тую строку 2D-массива OpsOnTiers   for nOp=1,GetCountOpsOnTier(iTier) do -- по порядковым номерам операторов на ярусе iTier        OpsOnTiers[iTier][nOp]=GetOpByNumbOnTier(nOp,iTier) -- взять номер оператора nOpend end -- конец циклов for по iTier и for по nOp

Для удобства данные метрик операторов и дуг графа выведены из gv-файлов и расположены в текстовых mvr и med-файлах, для моделирования выполнения программ на гетерогенном поле параллельных вычислителей служат cls и ops-файлы сопоставления возможностей выполнения определенных операторов на конкретных вычислителях. Преимуществом такого подхода является возможность задания нужных параметров целой группе объектов (списком типа от-до, причем список может быть и вырожденным) одной строкой файла. Задавать параметры можно по практически неограниченному количеству тегов, определяемых разработчиком.

Модуль SPF@home также позволяет определять время жизни данных между ярусами ЯПФ, что необходимо для определения/оптимизации параметров устройств временного хранения данных (обычно регистров процессора). Собственно размер данных при этом берется из med-файлов.

Система нацелена в основном на анализ программ, созданных с использованием языков программирования высокого уровня без явного указания распараллеливания и в системах c концепцией ILP (Instruction-LevelParallelism, параллелизм на уровне команд), хотя возможности модуля SPF@home позволяют использовать в качестве неделимых блоков последовательности команд любого размера.

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

I. Балансировка числа операторов по всем ярусам заданной ЯПФ без увеличения ее высоты (минимизируется требуемое для решения задачи число параллельных вычислителей).

II. Получение расписания выполнения программы на заданном числе параллельных вычислителей с возможным увеличением высоты ЯПФ (фактически временем выполнения программы).

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

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

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

Собственно последовательность получения рационального расписания выполнения параллельной задачи будут следующей:

1) Получение исходной (не имеющей ограничений по ширине ярусов) ЯПФ.

2) Модификация этой ЯПФ в нужном направлении путем целенаправленной перестановки операторов с яруса на ярус при сохранении исходных связей в информационном графе алгоритма.

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

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

Методы достижения цели могут быть собственно разработанными эристиками (обычно ограниченной сложности для возможности использования в режиме реального времени) или стандартными - метод ветвей и границ, генетические, муравьиные и др. (чаще используются при исследовательской работе). Возможности системы включают использование оберток многофункциональных системных Windows-вызовов WinExec, ShellExecute и CreateProcess, так что исследователь имеет возможность вызова и управления любыми внешними программами (например, использовать тот же METIS в качестве процесса-потомка), файловое обслуживание при этом осуществляется средствами Lua.

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

На рис. показаны линейчатые диаграммы ширин ярусов реальных ЯПФ из копий экранов при работе системы SPF@home (средне-арифметическое значение ширин показано пунктиром, a) и символическая схема действия метода Bulldozer - б)На рис. показаны линейчатые диаграммы ширин ярусов реальных ЯПФ из копий экранов при работе системы SPF@home (средне-арифметическое значение ширин показано пунктиром, a) и символическая схема действия метода Bulldozer - б)

Многочисленные вычислительные эксперименты показывают, что во многих случаях удается значительно (до 1,5-2 раз) снизить ширину ЯПФ без увеличения высоты, но почти никогда до минимальной величины (средне-арифметическое значение ширин ярусов).

Т.о. истинной ценностью данного исследования являются именно эвристические методы (реализованные на языке Lua) создания расписаний выполнения параллельных программ при определённых ограничениях (напр., c учетом заданного поля параллельных вычислителей, максимума скорости выполнения, минимизации или ограничения размеров временного хранения данных и др.).

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

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

Список литературы

1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-етербург, 2002. 608 c.

2. Гери М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. : Мир, Книга по Требованию, 2012. 420 c.

3. AlgoWiki. Открытая энциклопедия свойств алгоритмов. URL: http://algowiki-project.org (дата обращения 31.07.2020).

4. ФедотовИ.Е.Параллельное программирование. Модели и приёмы. М.: СОЛОН-Пресс, 2018. 390 с.

5. Roberto Ierusalimschy. Programming in Lua. Third Edition. PUC-Rio, Brasil, Rio de Janeiro, 2013. 348 p.

Подробнее..

Такие важные короткоживущие данные

24.12.2020 22:23:19 | Автор: admin

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

В публикации на Habrе Есть ли параллелизм в произвольном алгоритме и как его использовать лучшим образом от 26.11.2020 г. (http://personeltest.ru/aways/habr.com/ru/post/530078/) описан исследовательский программный комплекс для анализа произвольного алгоритма на наличие скрытого потенциала параллелизма и инструментарий для построения рационального каркаса расписания параллельной программы.

Комплекс включает модуль программного симулятора универсального вычислителя, реализующий Data-Flow (далее D-F) подход к управлению последовательностью вычислений [1] с использованием архитектуры SMP (Symmetric MultiProcessing, симметричная мультипроцессорность), позволяющий выполнять произвольную программу, разработанную на языке программирования уровня Ассемблера [2], причем порядок операндов соответствует стилю AT&T. Программная модель использует трёхадресные команды, условность выполнения осуществляется предикатным методом, [3]). D-F симулятор позволяет гибко управлять параметрами потокового выполнения программ в соответствии с концепцией ILP (Instruction-LevelParallelism, параллелизм уровня машинных команд) и автоматически (в физической реализации на аппаратном уровне) генерировать план выполнения параллельной программы [4].

В вычислителях потоковой архитектуры процесс выбора операторов для исполнения удобно представить результатом взаимодействия некоторых сущностей, асинхронно выполняющих определенные действия актёров [5], при этом естественным образом моделируются связанные с характеристиками времени параметры обработки операторов.

Второй модуль комплекса (SPF@home, далее SPF) служит для выявления в Информационном Графе Алгоритма (далее ИГА) скрытого параллелизма методом построения Ярусно-параллельной Формы (далее ЯПФ) алгоритма [5] c последующей реорганизацией ЯПФ путём последовательных целенаправленных изменений без нарушения информационных связей [6] для составления рационального каркаса расписания выполнения параллельной программы. Одной из важных целей реорганизации ЯПФ является повышение плотности кода (формально определяемой в данном случае равномерностью заполнения ярусов ЯПФ операторами). Т.к. задачи составления расписаний относят к классу NP-полных [7], в данной работе использован метод разработки, основанный на создании и итерационном улучшении основанных на эвристическом подходе сценариев реорганизации ЯПФ [8] (собственно сценарии разрабатываются с использованием скриптового языка Lua [9]).

Исходными данными для модуля SPF служат ИГА-файлы стандартного формата, которые могут быть получены путём импорта из системы D-F или любым иным (в общем случае уровень операторов может быть любым необязательно соответствующим концепции ILP).

Исходя из сложности алгоритмов обработки данную область исследований можно обоснованно отнести к наиболее сложным областям Науки о данных (Data Science).

Все вышеописанные программные модули полностью Open Source, свободная выгрузка инсталляционных файлов доступна с ресурсов http://vbakanov.ru/dataflow/content/install_df.exe и http://vbakanov.ru/spf@home/content/install_spf.exe соответственно (дополнительная информация - http://vbakanov.ru/dataflow/dataflow.htm и http://vbakanov.ru/spf@home/spf@home.htm).

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

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

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

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

Набор API-вызовов системы SPF позволяет получить информацию о требуемых при выполнении заданного алгоритма параметрах (времени жизни данных, далее ВЖД). Эти данные появляются следствием выполнения отдельных операторов и, в свою очередь, служат входными операндами для иных операторов (метафорически можно сказать, это такие ВЖД живут между ярусами ЯПФ).

Система SPF формально выдаёт информацию о временных данных в форме некоторых обобщённых величин, реальный размер данных должен быть определён в med-файлах. Информация о временных данных может быть выдана в известном формате текстового файла для анализа внешней программой.

На рис.1 и 2 показаны расписания выполнения в форме ЯПФ (причём, как и было принято ранее, выполнение осуществляется в направлении увеличения номеров ярусов) алгоритма решения полного квадратного уравнения в вещественных числах (аналогично рис.2 предыдущей статьи для исходной и модифицированной ЯПФ соответственно; при этом номера операторов в овалах (111-116) соответствуют операциям присвоения (или передачи из внешних модулей) начальных значений для расчёта. Диаграммы ВЖД приведены в форме отдельных блоков, включающих циклы генерация использование уничтожение данных, поэтому некоторые номера операторов дублируются.

Рисунок1Исходная ЯПФ алгоритма (слева) и соответствующая диаграмма ВЖД (справа, формула одновременно существующих данных 6-5-4-3-3-3-2)

Рисунок2Модифицированная (один из вариантов) ЯПФ рис.1 и соответствующая ВЖД данных (формула 6-7-5-3-3-3-2)

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

Анализ ВЖД в случае полностью последовательного характера выполнения показанного на рис.3 алгоритма (линейчатые графики распределения количества данных отрисовываются непосредственно системой SPF@home). Собственно ЯПФ здесь вырождена, имеет ширину 1 и содержит 11 исполняемых операторов (плюс уровни исходных и выходных данных).

Рисунок3Количество одновременно существующих данных для трёх (слева направо) вариантов последовательного выполнения алгоритма рис. 1 (слева от диаграммы промежуток ярусов с указанием номеров операторов в формате предыдущий / последующий; in и out входные и выходные данные соответственно, в прямоугольниках диаграммы количество данных)

Первыми (не единственными!) претендентами на линейность исполнения являются находящиеся на ярусах 1,5,6 (рис. 1) операторы, причем вследствие ортогональности по данным они могут быть выполнены в любой последовательности. При этом достигаются разные качества распределения ВЖЛД (на рис. 3 варианта, локальным оптимумом из которых является последний, характеризующийся максимумом числа данных 6 единиц). В данном случае вычислительная сложность процедуры реорганизации ЯПФ явилась незначительной - оказалось достаточным всего двух перестановок операторов (изменения в положении коснулись операторов 101,102,103. Даже в таком простом примере результат оптимизации стоит свеч, для более сложных случаев качество оптимизации будет более значительным.

Следующим этапом определения параметров устройства временного хранения данных является определение необходимых объемов (данные поочередно используют одни и те же области памяти) этого устройства (например, числа регистров общего назначения); для этого применяются известные приемы (напр., метод раскраски графов, [10]). Такие возможности не поддерживаются API модуля SPF@home и могут быть реализованы средствами встроенного языка Lua или внешними модулями.

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

Список литературы

1. J.B.Dennis, D.P.Misunas. A Preliminary Architecture for a Basic Data-Flow Processor. In Proc. Second Annual Symp. Computer Architecture, pр. 126-132, Houston, Texas, January, 1975.

2. БакановВ.М.Параллелизация обработки данных на вычислителях потоковой (Data-Flow) архитектуры. //Журнал Суперкомпьютеры, M.: 2011, 5, с.54-58.

3. Э.Таненбаум, Т.Остин. Архитектура компьютера. СПб.: Изд. Питер, 2019. 816 c.

4. БакановВ.М.Управление динамикой вычислений в процессорах потоковой архитектуры для различных типов алгоритмов. //Журнал Программная инженерия", М.: 2015, 9, c. 20-24.

5. ФедотовИ.Е.Параллельное программирование. Модели и приёмы. М.: СОЛОН-Пресс, 2018. 390 с.

6. БакановВ.М. Программный комплекс для разработки методов построения оптимального каркаса параллельных программ. //Журнал Программная инженерия", М.: 2017, том 8,2, c. 58-65.

7. M.R.Gary, D.S.Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H.Freeman and Company, San Francisco, 1979. 338 pp.

8. V.M.Bakanov. Software complex for modeling and optimization of program implementation on parallel calculation systems. Open Computer Science, Volume 8, Issue 1, Pages 228234, ISSN (Online) 2299-1093, DOI: https://doi.org/10.1515/comp-2018-0019.

9. Roberto Ierusalimschy. Programming in Lua. Third Edition. PUC-Rio, Brasil, Rio de Janeiro, 2013. 348 p.

10. Карпов В.Э. Теория компиляторов. Часть 2. Двоичная трансляция. URL: http://www.rema44.ru/resurs/study/compiler2/Compiler2.pdf (дата обращения 15.12.2020).

Подробнее..

Это непростое условное выполнение

02.01.2021 18:15:24 | Автор: admin
Некоторое время назад я рассказывал о программном комплексе для выявления скрытого параллелизма в произвольном алгоритме и технологиях его, параллелизма, рационального использовании (http://personeltest.ru/aways/habr.com/ru/post/530078/). Одним из компонентов этого комплекса является т.н. универсальный вычислитель, выполненный в соответствии с архитектурой Data-Flow (далее DF, потоковый вычислитель, описание здесь habr.com/ru/post/534722).
Подробнее..

Динамика потокового вычислителя

31.01.2021 14:19:04 | Автор: admin
В публикации habr.com/ru/post/530078 я рассказывал о возможностях потокового (архитектуры Data-Flow, далее DF) параллельного вычислителя. Особенности выполнения программ на нём столь необычны и интересны, что о них следует сказать два слова. Эксперименты проводились на компьютерном симуляторе DF-машины, входящем в исследовательский комплекс для выявления параллелизма в произвольном алгоритме и выработке рационального расписания выполнения этого алгоритма на гомогенном или гетерогенном поле параллельных вычислителей (та же публикация).
Подробнее..

Параллелизм и плотность кода

05.03.2021 14:13:31 | Автор: admin

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

Естественным перед началом анализа будет указание ограничений на ширину и глубину исследований. Принимаем, что многозадачность в рассматриваемых параллельных системах осуществляется простейшим путём - перегрузкой всего блока (связки) выполняющихся операторов (одновременное выполнение операторов разных программ не предполагается) или же система работает в однозадачном режиме; в противном случае высказанное в предыдущей фразе утверждение может быть неверным. Минимизация объёма устройств временного хранения данных (описано здесь http://personeltest.ru/aways/habr.com/ru/post/534722/) проводиться не будет. На этом этапе исследований также не учитываются задержки времени на обработку операторов и пересылку данных между ними (для системы SPF@home формально эти параметры могут быть заданы в файлах с расширениями med и mvr).

В предыдущей публикации http://personeltest.ru/aways/habr.com/ru/post/540122/ была описана технология получения ПВПП на основе модели потокового (Data-Flow) вычислителя. Обычно считают, что правила выбора операторов для выполнения в такой машине подчиняются логике действия некоторых сущностей, совместно выполняющих определённые действия актёров (actors); при этом естественным образом моделируются связанные с характеристиками времени параметры обработки операторов. В общем случае при этом отдельные операторы выполняются асинхронно. В публикации показано, что описанный принцип получения ПВПП приемлем (при выполнении несложных условий) и для машин архитектуры VLIW (Very Long Instruction Word, сверхдлинное машинное слово), отличающихся требованием одновременности начала выполнения всех операторов в связке. В расчётах использовали модель ILP (Instruction-LevelParallelism, параллелизм уровня машинных команд).

В рассматриваемый программный комплекс http://personeltest.ru/aways/habr.com/ru/post/530078/ включен модуль SPF@home, позволяющей работать с гранулами параллелизма любого размера (оператор любой сложности). Основным инструментом этого модуля является метод получения ярусно-параллельной формы (ЯПФ) графа алгоритма (здесь используется информационный граф, в котором вершинами являются узлы преобразования информации, а дугами её передачи).

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

Метод обработки ЯПФ в целом более теоретичен и от многих особенностей абстрагирован, однако он может ещё до выполнения программы (DesignTime) показать ПВПП сверху (учитывая не только параллельный фронт выполнения операторов, но и всю карту боевых действий). Следствием большего абстрагирования ЯПФ-метода является субъективность интерпретации связи моментов обработки операторов с собственно ярусом ЯПФ. В самом деле, можно рассмотреть несколько укрупнённых подходов к таким интерпретациям; см. рис. ниже слева варианты a) и б) соответственно. На этом рисунке операторы показаны красными прямоугольниками, а яруса (в целях большей выразительности сказанного) - горизонтальными линиями:

  • выполнение всех принадлежащих конкретному ярусу операторов начинается одновременно (тогда это фактически VLIW-идеологема и ПВПП изначально обладает ограниченностью, связанной с потерями времени на ожидание выполнения наиболее длительного оператора на ярусе; точное решение получается лишь при одинаковости времён выполнения всех операторов на ярусе);

  • промежуток времени выполнения операторов может плавать относительно связанного с ярусом момента времени (возможна даже ограниченная асинхронность выполнения операторов).

При использовании ЯПФ в своих изысканиях Исследователь должен сам выбрать определённую модель и далее ей следовать. В рамках системы SPF@home, например, имеется возможность целевой реорганизации ЯПФ с конечной целью собрать на ярусах операторы с наиболее близкими длительностями обработки. Именно использование ЯПФ как нельзя лучше отвечает идеологеме EPIC (Explicitly Parallel Instruction Computing, явный параллелизм выполнения команд), позволяющей параллельной вычислительной системе выполнять инструкции согласно плану, заранее сформированному компилятором. Не следует игнорировать и субъективный фактор - бесспорным преимуществом ЯПФ является возможность простой и недвусмысленной визуализации собственно ПВПП.

Исходными данными для модуля SPF@home служат описания информационных графов алгоритма (программы) в стандартной DOT-форме (расширения файлов gv, могущие быть полученными импортом из модуля Data-Flow или иными путями). Допустимые (не нарушающие информационные связи в алгоритме) преобразования ЯПФ управляются программой на языке Lua, реализующей разработанные методы реструктуризации ЯПФ (дополнительная информация приведена в публикации http://personeltest.ru/aways/habr.com/ru/post/530078/). Эти методы неизбежно будут являться эвристическими вследствие невозможности прямого решения поставленных (относящихся к классу NP-полных) задач.

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

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

В качестве пациентов использовались имеющиеся в наличии информационные графы алгоритмов, в основном класса линейной алгебры (как одни из наиболее часто встречающиеся в современных задачах обработки данных). По понятным причинам исследования проводились на данных небольшого объёма в предположении сохранения корректности полученных результатов при обработке данных большего размера. Описанные в данной публикации исследования имеют цель продемонстрировать возможности имеющегося инструментария при решении поставленных задач. При желании возможно исследовать произвольный алгоритм, описав и отладив его в модуле Data-Flow (http://personeltest.ru/aways/habr.com/ru/post/535926/) с последующим импортом в форме информационного графа в модуль SPF@home.

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

Ниже приведены результаты моделирования трёх наиболее часто встречающихся типов задач (в реальном случае обычно требуется выполнение нескольких из них одновременно):

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

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

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

Эмпирический метод 1-01_bulldozer имеет целью получение наиболее равномерного распределения операторов по ярусам ЯПФ без возрастания её высоты (сохранение времени выполнения программы); операторы переносятся только вниз (первоначально ЯПФ строится в верхнем варианте). Для этого метод старается перенести операторы с ярусов шириной выше среднего на яруса с наименьшей шириной. На каждом ярусе операторы перебираются в порядке очередности слева направо.

Метод 1-02_bulldozer является модификацией предыдущего с адаптацией. Для оператора с максимумом вариативности (назовём так диапазон возможного размещения операторов по ярусам ЯПФ без изменения информационных связей в графе алгоритма) в пределах яруса вычисляются верхний и нижний пределы его возможного расположения по ярусам.

В результирующей табл.1 рассматриваются: mnk_N программа аппроксимации методом наименьших квадратов N точек прямой, mnk_2_N то же, но квадратичной функцией, korr_N вычисление коэффициента парной корреляции по N точкам, slau_N решение системы линейных алгебраических уравнений порядка N прямым (не итерационным) методом Гаусса, m_matr_N - программа умножения квадратных матриц порядка N традиционным способом, m_matr_vec_N умножение квадратной матрицы на вектор, squa_equ_2 решение полного квадратного уравнения в вещественных числах, squa_equ_2.pred то же, но с возможностью получения вещественных и мнимых корней при использовании метода предикатов для реализации условного выполнения операторов, e17_o11_t6, e313_o206_t32, e2367_o1397_t137, e451_o271_t30, e916_o624_t89, e17039_o9853_t199 сгенерированные специальной программой по заданным параметрам информационного графа. Вычислительную трудность преобразования будем характеризовать числом перемещений операторов с яруса на ярус. Неравномерность распределения числа операторов по ярусам ЯПФ характеризуется коэффициентом неравномерности (отношение числа операторов на наиболее и наименее нагруженных ярусов соответственно).

Для удобства анализа в таблице цветом выделены ячейки, соответствующие случаю достижению снижения ширины без возрастания высоты ЯПФ, а жирным начертанием цифр величины для сравнения.

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

Интересно, что для некоторых алгоритмов (напр., slau_N) ни один из предложенных методов не дал результата. Сложность балансировки ЯПФ связана с естественным стремлением разработчиков алгоритмов создавать максимально плотные записи последовательности действий.

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

Практический интерес представляют методы с увеличением высоты ЯПФ (см. табл.2, в которой дано сравнение двух методов с метафорическими названиями Dichotomy и WidthByWidth); при этом приходится смириться с увеличение времени выполнения программы. В ходе вычислительных экспериментов задавалась конечная ширина преобразованной ЯПФ (отдельные столбцы в правой части табл.2). Количественные параметры преобразований выдавались в форме частного, где числитель и знаменатель показывают число перемещений (первая строка), высоту ЯПФ (вторая) и коэффициент ковариации CV (третья строка) для каждого исследованного графа. Характеризующий неравномерность распределения ширин ярусов коэффициент ковариации рассчитывался как CV=/W, где - среднеквадратичное отклонение числа операторов по всем ярусам ЯПФ, W - среднеарифметическое числа операторов по ярусам.

Эвристика Dichotomy предполагает для разгрузки излишне широких ярусов перенос половины операторов на вновь созданный ярус под текущим, эвристика WidthByWidth реализует постепенный перенос операторов на вновь создаваемые яруса ЯПФ. Из табл.2 видно, что метод WidthByWidth в большинстве случаев приводит к лучшим результатам, нежели Dichotomy (например, высота преобразованной ЯПФ существенно меньше что соответствует снижению времени выполнения параллельной программы притом за меньшее число перемещений операторов).

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

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

Модуль SPF@home поддерживает эту возможность путём сопоставления информации из двух файлов для операторов и вычислителей (*.ops и *.cls соответственно). Имеется возможность задавать совпадение по множеству свободно назначаемых признаков для любого диапазона операторов/вычислителей. Условием выполнимости данного оператора на заданном вычислителе является minVal_1Val_1maxVal_1 для одинакового параметра (Val_1, minVal_1, maxVal_1 числовые значения данного параметра для оператора и вычислителя соответственно).

Разработка расписания для выполнения программы на гетерогенном поле параллельных вычислителей является более сложной процедурой относительно вышеописанных и здесь упор делается на программирование на Lua (API-функции системы SPF@home обеспечивают минимально необходимую поддержку). Т.к. на одном ярусе ЯПФ могут находиться операторы, требующие для выполнения различных вычислителей, полезным может служить концепция расцепления ярусов ЯПФ на семейства подъярусов, каждое из которых соответствует блоку вычислителей c определёнными возможностями (т.к. все данного операторы яруса обладают ГКВ-свойством, последовательность выполнения их в пределах яруса/подъяруса в первом приближении произвольна). На схеме ниже слева показано расщепление операторов на одном из ярусов ЯПФ в случае наличия 6 параллельных вычислителей 3-х типов.

Пример плана выполнения программы на поле из 3-х типов параллельно работающих вычислителей (c количествоv 5,3,4 штук соответственно и номерами 1-5, 6-8, 9-12 по типам, всего 12 штук) приведён в табл.3. При расчёте в качестве исходной использовался конкретный алгоритм, характеризующийся ЯПФ с числом операторов 206 и дуг 323, ярусов 32 (после расчета подъярусов получилось 48). Первый столбец таблицы показывает (разделитель символ прямого слеша) номер яруса/подъяруса; в ячейках таблицы приведены номера операторов, сумма их числа по подъярусам равно числу операторов на соответствующем ярусе ЯПФ.

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

В самом деле, в рассматриваемом случае общее время T решения задачи определяется суммой по всем ярусам максимальных значений времён выполнения операторов на подъярусах данного яруса, т.к. группы операторов на подъярусах выполняются последовательно (первая сумма берётся по j, вторая по i, максимум по kj):

T=(maxtik),

где j - число ярусов ЯПФ, i - число подъярусов на данном ярусе, kj - типы вычислителей на j-том ярусе, tik - время выполнения оператора типа i на вычислителе типа k. Если ставится задача достижения максимальной производительности, вполне возможно определить число вычислителей конкретного типа, минимизирующее T (напр., для показанного табл.3 случая количество вычислителей типа II полезно увеличить в пику вычислителяv типа I).

Задача минимизации общего времени решения T усложняется в случае возможности выполнения каждого оператора на нескольких вычислителях вследствие неоднозначности tik в вышеприведённом выражении; здесь необходима дополнительная балансировка по подъярусам.

Описание параметров операторов располагается в файлах с расширением ops, параметров вычислителей cls; соответствующая API-функция (обёрнутая Lua-вызовом) возвращает значение, разрешающее или запрещающее выполнение данного оператора на заданном вычислителе. Описанные файлы являются текстовыми (формат данных определён в документации), что даёт возможность разработки внешних программ для генерации требуемого плана эксперимента с использованием модуля SPF@home в режиме командной строки.


В порядке обсуждения небезынтересно будет рассмотреть вариант ЯПФ в нижней форме (при этом все операторы перемещены максимально в сторону окончания выполнения программы). Такая ЯПФ может быть получена из верхней перемещениями операторов по ярусам как можно ниже или проще построением ЯПФ в направлении от конца программы к её началу. Ниже проиллюстрировано сравнение распределения ширин ЯПФ в верхней и нижней формах (изображения в строке слева и справа соответственно в 4-х рядах) для алгоритма умножения матриц традиционным способом при порядках матриц N=3,5,7,10. Здесь H, W и W высота, ширина и среднеарифметическая ширина ЯПФ (последняя показана на рисунках пунктиром; символ прямого слеша разделяет параметры для верхней и нижней ЯПФ (фиолетовый цвет ярус максимальной ширины, красный минимальной).

Соответствующие иллюстрации для процедуры решения систем линейных алгебраических уравнения порядков N=3,5,7,10 безытерационным методом Гаусса представлены ниже.

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

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


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

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

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

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

Итак, программная система SPF@home выполняет практическую задачу по составлению расписаний выполнения заданных алгоритмов (программ) на заданном поле параллельных вычислителей и дает возможность проводить различного типа исследования свойств алгоритмов (в данном случае оценивать вычислительную сложность методов составления расписаний). Система нацелена в основном на анализ программ, созданных с использованием языков программирования высокого уровня без явного указания распараллеливания и в системах c концепцией ILP (Instruction-LevelParallelism, параллелизм на уровне команд), хотя возможности модуля SPF@home позволяют использовать в качестве неделимых блоков последовательности команд любого размера.

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

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


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

Подробнее..

Сколько стоит расписание

10.04.2021 22:12:11 | Автор: admin

Основные данные вычислительных экспериментов по реорганизации ярусно-параллельной формы (ЯПФ) информационных графов алгоритмов (ТГА) приведены в предыдущей публикации (http://personeltest.ru/aways/habr.com/ru/post/545498/). Цель текущей публикации показать окончательные результаты исследований разработки расписаний выполнения параллельных программ в показателях вычислительной трудоёмкости собственно преобразования и качества полученных расписаний. Данная работа является итогом вполне определённого цикла исследований в рассматриваемой области.

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

Т.к. в принятой модели ЯПФ фактически определяет порядок выполнения операторов параллельной программы (операторы выполняются группами по ярусам поочерёдно), в целях сокращения будем иногда использовать саму аббревиатуру ЯПФ в качестве синонима понятия плана (расписания) выполнения параллельной программы. По понятным причинам исследования проводились на данных относительно небольшого объёма в предположении сохранения корректности полученных результатов при обработке данных большего размера. Описанные в данной публикации исследования имеют цель продемонстрировать возможности имеющегося инструментария при решении поставленных задач. При желании возможно исследовать произвольный алгоритм, описав и отладив его в модуле Data-Flow (http://personeltest.ru/aways/habr.com/ru/post/535926/) с последующим импортом в формате информационного графа в модуль SPF@home для дальнейшей обработки.

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

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

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

Полученные результаты предназначаются для улучшения качества разработки расписаний выполнения параллельных программ в распараллеливающих компиляторах будущих поколений. При этом внутренняя реализация данных конечно, совсем не обязана предусматривать явного построения ЯПФ в виде двумерного массива, как для большей выпуклости показано на рис.2 в публикации http://personeltest.ru/aways/habr.com/ru/post/530078/ и выдаётся программным модулем SPF@home (http://vbakanov.ru/spf@home/content/install_spf.exe). Она может быть любой удобной для компьютерной реализации например, в наивном случае устанавливающей однозначное соответствие между формой ИГА в виде множества направленных дуг {k,l} (матрица смежности) и двоек номеров вершин ik,jk и il,jl, где 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. Параметры плана параллельного выполнения при сохранении высоты ЯПФ для алгоритма умножения квадратных матриц 2,3,5,7,10-го порядков (соответствует нумерации по осям абсцисс) классическим методомРисунок 1. Параметры плана параллельного выполнения при сохранении высоты ЯПФ для алгоритма умножения квадратных матриц 2,3,5,7,10-го порядков (соответствует нумерации по осям абсцисс) классическим методомРисунок 2. Параметры плана параллельного выполнения при сохранении высоты ЯПФ для алгоритма вычисления коэффициента парной корреляции по 5,10,15,20-ти точкам (соответствует нумерации по осям абсцисс)Рисунок 2. Параметры плана параллельного выполнения при сохранении высоты ЯПФ для алгоритма вычисления коэффициента парной корреляции по 5,10,15,20-ти точкам (соответствует нумерации по осям абсцисс)Рисунок 3. Параметры плана параллельного выполнения при сохранении высоты ЯПФ для алгоритма решения системы линейных алгебраических уравнений (СЛАУ) для 2,3,4,5,7,10-того порядка (соответствует нумерации по осям абсцисс) прямым (неитерационным) методом ГауссаРисунок 3. Параметры плана параллельного выполнения при сохранении высоты ЯПФ для алгоритма решения системы линейных алгебраических уравнений (СЛАУ) для 2,3,4,5,7,10-того порядка (соответствует нумерации по осям абсцисс) прямым (неитерационным) методом Гаусса

Данные рис. 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=W0 до W=1, где W0 ширина ЯПФ, а нижняя граница соответствует полностью последовательному выполнению). Сравниваем два метода реорганизации ЯПФ Dichotomy и WidthByWidtn:

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

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

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

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

Рисунок 4. Возрастание высоты (ординаты) при ограничении ширины ЯПФ (абсциссы), разы; алгоритм умножения квадратных матриц классическим методом 5 и 10-го порядков рис. a) и b) соответственноРисунок 4. Возрастание высоты (ординаты) при ограничении ширины ЯПФ (абсциссы), разы; алгоритм умножения квадратных матриц классическим методом 5 и 10-го порядков рис. a) и b) соответственноРисунок 5. Возрастание высоты (ординаты) при ограничении ширины ЯПФ (абсциссы), разы; алгоритм решения системы линейных алгебраических уравнений прямым (неитерационным) методом Гаусса 5 и 10-го порядков рис. a) и b) соответственноРисунок 5. Возрастание высоты (ординаты) при ограничении ширины ЯПФ (абсциссы), разы; алгоритм решения системы линейных алгебраических уравнений прямым (неитерационным) методом Гаусса 5 и 10-го порядков рис. a) и b) соответственно

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

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

Рисунок 6. Число перемещений операторов между ярусами - a) и коэффициент вариации CV - b) при снижении ширины ЯПФ для алгоритма умножения квадратных матриц 10-го порядка классическим методом (ось абсцисс ширина ЯПФ после реформирования)Рисунок 6. Число перемещений операторов между ярусами - a) и коэффициент вариации CV - b) при снижении ширины ЯПФ для алгоритма умножения квадратных матриц 10-го порядка классическим методом (ось абсцисс ширина ЯПФ после реформирования)Рисунок 7. Число перемещений операторов между ярусами - a) и коэффициент вариации CV - b) при снижении ширины ЯПФ для алгоритма решения системы линейных алгебраических уравнений 10-го порядка прямым (неитерационным) методом Гаусса (ось абсцисс ширина ЯПФ после реформирования)Рисунок 7. Число перемещений операторов между ярусами - a) и коэффициент вариации CV - b) при снижении ширины ЯПФ для алгоритма решения системы линейных алгебраических уравнений 10-го порядка прямым (неитерационным) методом Гаусса (ось абсцисс ширина ЯПФ после реформирования)

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

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

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

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


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

Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru