Время жизни локальных данных

Параллелизации обработки данных в настоящее время применяется в основном для сокращения времени вычислений путем одновременной обработки данных по частям на множестве различных вычислительных устройств с последующим объединением полученных результатов. Параллельное выполнение позволяет обойти сформулированный лордом Рэлеем в 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-файов (зависимость вида операторы - операнды, при этом вершины графа ассоциируются с операторами (группами операторов) программы, а дуги с линиями передачи (хранения) данных). ИГА обладает свойствами направленности, ацикличности и параметризован по размеру обрабатываемых данных (из-за последнего приходится исследовать один и тот же алгоритм с конкретным набором исходных данных).

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

Для управления созданием расписания используется встроенный скриптовый язык 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 - б)

Многочисленные вычислительные эксперименты показывают, что во многих случаях удается значительно (до 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.

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

В публикации на 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).