Все идеи и алгоритмы, описываемые в данной статье, являются результатом моей независимой и полностью самостоятельной интеллектуальной деятельности. Как автор, разрешаю свободно использовать, изменять, дополнять все идеи и алгоритмы любому человеку или организации в любых типах проектов при обязательном указании моего авторства.
© Балыбердин Андрей Леонидович 2019 Rutel@Mail.ru
DataFlow Компилятор с языков высокого уровня в ориентированный ациклический граф
(Доказательство возможности такого преобразования)
.
Ориентированный ациклический граф — орграф, в котором отсутствуют направленные циклы, но могут быть «параллельные» пути, выходящие из одного узла и разными путями приходящие в конечный узел.
Основой устройства DataFlow компьютера является принцип, согласно которому исполнение команд происходит в момент готовности всех необходимых данных, без привязки к последовательности команд в памяти.
Для такой вычислительной архитектуры ациклический ориентированный граф является идеальным представлением программы.
В настоящее время развитие вычислительной техники идет по пути конвейеризации (позволяет поднимать тактовую частоту), внеочередного исполнения (позволяет исполнять несколько команд одновременно), векторизации (позволяет одной командой обрабатывать много данных при этом максимально полно использовать преимущества конвейера) спекулятивного исполнения, многопроцессорности (позволяет иметь много нитей исполнения) и включения различных аппаратных ускорителей часто применяемых функций (распаковка видео и тд). Графовое представление ПО в полной мере отвечает всем этим тенденциям. В современных процессорах все эти тенденции нашли свое отражение, но в относительно небольшой степени. Например, внеочередное или параллельное исполнение не задействует больше чем 10-20 смежных команд и так по всем направлениям.
Вывод: Необходимо обновить вычислительную парадигму.
Думаю что «выстрелят» системы основанные на DataFlow, но только в том случае если будут гарантировать одновременную и максимальную загрузку большого числа исполнительных устройств, исполнение десятков тысяч команд за такт. Следует отметить что процесс миниатюризации давно подошел к своему пределу. В одном кристалле удалось реализовать всю вычислительную систему, но при этом очень мало уделяется внимания межчиповому взаимодействию.
Для того что бы достичь большого числа одновременно исполняемых команд, необходимо отказаться от последовательного исполнения команд (в нем нельзя достичь уровня больше чем 10 первичных команд за такт). Иными словами необходимо окончательно «похоронить» фон-Неймана. Наиболее оптимальной является парадигма DataFlow, но для того что бы она заработала необходимо «выбросить из головы» многое из что было наработано предыдущей. Любая технология или устройство представляет собой компромисс многих требований и если в новую технологию «тащить» части предыдущей только потому что «мы привыкли и так все делают» получится ущербный и не жизнеспособный гибрид.
Есть большая проблема, которую нельзя просто так оставить в прошлом - это человеческий фактор. Логическое мышление человека последовательно и не позволяет одновременно оперировать более чем 5-7 сущностями, что делает крайне не эффективным (даже невозможным) непосредственное создание параллельных и распределенных программ для DataFlow вычислительных систем. На начальном этапе необходим алгоритм (инструмент) преобразующий программы на языках высокого уровня в «программу» для DataFlow (потом этим займется сильный ИИ). Будем считать что исходными данными для алгоритма преобразования будет промежуточный язык компиляторов с технологией LLVM.
Почему именно LLVM:
-
любая переменная присваивается только один раз
-
метки достаточно далеки от концепции адресного пространства (с ними невозможны арифметические операции)
-
сущности считаются в «штуках»
-
есть специальный оператор выбора значения в зависимости ветки исполнения
-
осталось только убрать условные переходы и можно преобразовывать в ациклический ориентированный граф.
-
для большинства ЯВУ (если не для всех) есть возможность преобразование в LLVM.
Базовые утверждения для DataFlow вычислителя:
-
DataFlow программа представляет собой ациклический граф, в узлах которого находятся различные устройства (команды) преобразования данных.
-
Единственной функцией программы является преобразование исходных данных в результат (часть данных могут быть состоянием программы). Промежуточное состояние для конечного пользователя не имеет значения. Аналогом из схемотехники являются цифровые автоматы.
-
Если две или более программы при одинаковом наборе входящих данных всегда порождают одинаковые новые данные, то такие программы являются эквивалентными.
-
Последовательность исполнения задается готовностью комплекта данных (Data Set) на входе конкретного устройства обработки.
-
Функцию передачи и формирования Data Set исполняет сеть ССИ.
-
В момент обработки данных они исчезают (расходуются), при необходимости порождая новые данные на выходе устройства обработки. Примерно как в LLVM с однократным присваиванием, а тут однократное использование.
-
Граф программы не должен иметь циклов, будем интерпретировать такие конструкции (различные циклы) как «спирали» во времени.
-
Памятью (состоянием) программы являются не обработанные или не полные Data Set.
-
Единой памяти и вообще адресного пространства нет, есть понятие уникального идентификатора (пока этого будет достаточно).
На первый взгляд программы для языков высокого уровня и DataFlow систем принципиально между собой различаются и не могут быть преобразованы друг в друга, но это только на первый взгляд.
Если посмотреть на процесс исполнения программ со стороны процессора. Проведем эксперимент, запишем «трассу» (последовательность исполняемых команд) для какого то конкретного Data Set. Потом отбросим команды не влияющие на результат исполнения (различные MOV, CMP, CALL, PUSH и тд), оставим только команды выполняющие какие то действия над данными. Поскольку команды ветвления реализовались, то получится линейная последовательность из команд преобразования данных. Можно еще отбросить команды не влияющие на результат, большинство из них выполняют функцию установки флагов. Останется относительно немного (около 20%) команд и их отсортировать по «слоям». Первый слой это команды которые могут быть выполнены с использованием только исходных, второй слой с использованием данных полученных в результате исполнения команд первого слоя и исходных данных. Продолжая до тех пор пока не будет вычислены все результаты исполнения программы, по факту получим ациклический (нет направленных циклов) направленный (направление от исходных данных к результату исполнения программы) граф (есть много параллельных путей для вычисления). Данный граф можно оптимизировать, самый очевидный способ это представить каждую операцию как логическую схему (состоит из битовых «И», «ИЛИ», «НЕ») и вычислить для схемы целиком СКНФ или СДНФ представление. Данная математика хорошо проработана в применении к FPGA, но для реального применения данный подход не оптимален. Какой бы набор данных (Data Set) не использовался, результатам будет ациклический граф. Программа может еще и «зависнуть», но это показатель того что программа написана с ошибкой.
Что нам дает данный эксперимент:
Можно утверждать, что на момент начала написания программы, программист уже представляет (возможно неосознанно) нечто (обычно это называют алгоритмом), являющееся в своей основе набором ациклических направленных графов. В процессе написания программы, он просто пишет распаковщик требуемого графа (сопоставляет каждому Data Set свой граф).
Создает суммарную программу которая содержит последовательность команд распаковки ациклического графа и последовательность команд обработки данных соответствующую конкретному «графу».
Можно считать, что любая программа с ЯВУ может быть превращена в конечное число ациклических направленных графов.
Оптимизация программ.
В настоящее время оптимизируют суммарную программу, а это сложно и не всегда приводит к нужным результатам. Предлагаю при оптимизации учитывать двойственность программы и производить оптимизацию в три этапа :
-
распаковать набор ациклических графов.
-
оптимизировать вычислительную часть задачи.
-
запаковать вычислительную часть наиболее оптимальным для конкретного процессора образом.
В следующей статье будут рассмотрены принципы быстрого составления набора графов, перебор всех возможных Data Set не является правильным подходом к решению данной проблемы и компактного его представления.
Комментарии
Не понял, почему команда CMP не влияет на результат? Установка флагов - это изменение состояния. А внутреннее состояние, сами же сказали, это такие же данные.
Вслед за командой CMP идет же команда типа JZ. Она как раз и зависит от флагов. Её куда деваете??? В простейших алгоритмах типа умножения матриц фиксированного размера друг на друга без ветвлений, да, обойтись можно. А в общем случае?
Для записи трека она уже реализовалась (приняла участие) в формирование конкретной последовательности вычислений.
Представьте, что число графов относительно небольшое и какой из них применить понятно из анализа Data Set.
Вычислительный процесс будет прост :
1. Анализируем входные данные
2. Выполняем нужный граф.
Все команды, которые я указал как отбрасываемые, они не занимаются непосредственным вычислением результата, они участвуют в "распаковке" требуемого графа.
А запись трека это и есть реализация одного конкретного сченария вычислений - одного конкретного графа.
Вопрос философский. Как до начала вычислений предугадать, по какому сценарию пойдет вычисление? В общем случае - никак. Иначе, если можно было бы предугадать, то вычислять уже нет никакого смысла - и так всё ясно.
Если число возможных сценариев невелико, то всё понятно. Я и сам могу привести класс задач, где это так. Но что Вы будете делать, если число возможных сценариев очень велико? 2n, где n - число точек ветвления с ростом n растет ОЧЕНЬ быстро. Мы же не школьники, которым надо быстро повторить решение, к которому уже есть готовый ответ...
В данной статье я показываю, что какой либо сценарий не выбрать, он приведет к ациклическому графу.
Во второй статье я покажу как преобразовать программу к двум графам
Первый (один) ациклический, направленный, имеет конечные размеры для любой программы и выполняется один раз.
При этом он позволяет производить преобразование (формировать ярусы или слои исполняемых команд) аналогичное преобразованию для трека в первой статье.
Второй граф отличается только тем что его нужно исполнять в цикле (нет ветвлений и тд), до тех пор пока для первого графа не будут получены результаты исполнения программы.
В качестве специализированного вычислителя для решения конкретных задач - подойдёт. Но не более того.
Почему же - если можно преобразовать любую прогу, а значит вычислитель универсальный.
Теоретически - да. Практически - только ограниченное число путей вычислений. Что бы будете делать, если число точек ветвления, например, 128?
Ещё раз внимательно перечитайте этот комментарий.
Этот вопрос будет рассмотрен следующей статье будет
Гладко было на бумаге...
И чего Вам не хватает для проверки/реализации Вашей идеи?
идеи
Вот вопрос:
Стараюсь описывать самые простые вещи, самыми простыми словами, так что бы было понятно школьнику.
Вы понимаете о чем я написал?
Или все настолько печально, что вы не можете мне "оппонировать" по причине полного непонимания того о чем я пишу ?
Что то типа слова все знакомые, но ничего непонятно.
Сначала выложу на «обозрение» все вплоть до алгоритмов сильного ИИ и только потом начну проверять сам.
Есть надежда, что найдутся любопытные и сами проверят и используют в своих работах.
Проект большой и самому все проверить неподъемная задача.
Да и смычл — ну вот скажу я что все проверил.
а мне в ответ — да это же тривиально, проверяется на бумажке в клеточку — а ты вот это следующее проверяй.
И что я так все сам сделать должен ?
Да мне банально жизни не хватит — а я хочу реализовать весь проект в пределах своей биологической жизни и стать полностью бессмертным.
А зачем становиться бессмертным? Чтобы что?
Для того что бы эволюционировать.
Вы задумывались, а что будет после человека в плане эволюции ?
Биология (физическая биология) жестко ограничивает размер, силу, интеллект биологического существа.
С некоторой вероятностью (если главным параметром считать интеллект), можно считать что биологический чаловек достиг максимума.
Если даже потом появится другой разумный вид, он не будет на порядок умнее человека. Он не сможет "кушать" с такой скорость с какой мозг потребляет, да и время жизни должно быть очень большим (нужно передать зания).
Считаю, что человек (как биологический вид) дошел до уровня развития, когда появилась насущная необходимость разорвать жесткую связь между биологическим телом и информационной сущностью (личностью человека).
Для себя сформуровал цель (направления движения) :
Хочу быть всем,
Хочу что бы все было мной,
Хочу быть всегда.
)
Вы предлагаете каждый раз оптимизировать исполнение для конкретного набора данных? Потому что для произвольного набора данных, например, ввода извне (в т.ч. от пользователя, в т.ч. real-time), а также для скриптов или похожих данных управляющих данными, в общем случае, подобная оптимизация не представляется эффективной. Для частных случаев это возможно, можно даже оптимизировать для N коренных подвариантов. И даже иерархически, однако это уже будет требовать много предварительного времени и памяти. Чем больше свободы для набора данных при той же полноте оптимизации, тем больше времени и памяти.
Спасибо за толковый комментарий.
В данной статье я показал, что любая программа для любого Data Set превращается в направленный граф.
В следующей статье покажу ка преобразовывать в один граф, но без потери возможности оптимизации и параллельного исполнения.
В третьей статье будет показано, как произвести обратное преобразование ("сжатие") графа в программу предельно оптимальную для конкретной вычислительной архитектуры.