DataFlow_Компилятор с ЯВУ в ориентированный ациклический граф(2)Версия2

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

© Балыбердин Андрей Леонидович 2019 Rutel@Mail.ru

 

DataFlow Компилятор с языков высокого уровня в ориентированный ациклический граф

(Преобразование в единый для всех Data Set граф)

 

Ориентированный ациклический граф — орграф, в котором отсутствуют направленные циклы, но могут быть «параллельные» пути, выходящие из одного узла и разными путями приходящие в конечный узел.

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

В качестве промежуточного языка предполагается использовать LLVM.

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

Разворачивание циклов.

В DataFlow нет командной последовательности, а в ациклическом графе нет циклических зависимостей данных. Для ликвидации циклов необходимо произвести поиск и разворачивание циклов, создание бесконечной конструкции из отдельных итераций цикла в теле программы. Циклы превратятся развернутую, бесконечную часть программы.

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

Для оптимальной записи можно циклические части программы пометить значком бесконечного повторения.

Выделение команд преобразования данных.

В начале данного параграфа нужно обратить внимание на отличие концепции данных для DataFlow от данных для фон Неймана. Для DataFlow данные не просто число, а символ. Символ характеризуется множеством свойств, самое главное свойство это уникальный идентификатор (аналог адреса для фон Неймана), тип переменной, значение и прочее. Для вычислительной системы (АЛУ) символ появляется только в момент назначения ему идентификатора. Любая команда может быть исполнена только когда все ее операнды имеют идентификатор. Кроме того символ это не только цифровое значение значение, но и тип. Получается что АЛУ в DataFlow должно реагировать и на тип обрабатываемых данных. С физической точки зрения отсутствие идентификатора обозначает, то что вычислительный процесс еще не дошел до вычисления значения конкретной переменной. Теоретически можно обходиться и без данной сущности, но это сильно и самое главное бесполезно увеличивает затраты на вычислительный процесс.

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

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

В результате должен получиться ациклический направленный граф преобразующий любой исходный Data Set в результирующий Data Set.

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

Особенности вычисления циклов.

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

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

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

Для простоты понимания: Результатом преобразования будет схема цифровой логики не имеющая в своем составе элементов памяти (регистров и тд). Компилятор (применяется в FPGA) может выполнить автоматическое добавление регистров преобразующих такую схему в конвейер (по вертикальной составляющей) или добавление регистров по горизонтальной составляющей. Добавление регистров по горизонтальной составляющей позволит контролировать степень параллельности (число параллельных команд). Разворачивание циклов образует периодические структуры и разбиение на секции с данным периодом по горизонтали позволяет повторно использовать логику предыдущей секции для вычисления результата следующей. Программа разбивается на две части : Логика, вычисления ациклической части и логика вычисления циклической части. Необходимо доказать, что все циклы в конечном итоге преобразуются в одну логическую схему.

Результат.

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

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