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

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

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

 

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

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

 

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Результат.

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

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