DataFlow Архитектура процессора (Введение, модель программирования)

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

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

DataFlow Архитектура процессора

(Введение, модель программирования)

Новосибирск, 2023 г.

Введение:

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

• Считаем что вершинами ациклического графа могут быть только команды исполняемые в рамках обычного процессорного АЛУ и хотя это и не так, но для простоты рассмотрения пусть будет.

• Минимальное время исполнение программы, для случая с бесконечным числом АЛУ, равно числу ярусов умноженного на время исполнения команды плюс затраты времени на коммуникации.

• Для объединения АЛУ в единую структуру используется сеть ССИ, которая является коммуникационной основой процессора и вычислительной системы в целом. ССИ позволяет произвольным образом соединять произвольное число АЛУ в рамках одного или нескольких кристаллов.

• Современные достижения микроэлектроники позволяют получить производительность меж-кристального взаимодействия на уровне 100 ТБит в секунду (интерфейс с 4-6 соседями). Данной скорости хватит для работы универсального процессора средней производительностью в 5 триллионов операций в секунду (один символ данных на пять команд).

• Для оценки числа АЛУ на один кристалл и суммарной производительности реализованного в рамках одного кремниевого кристалла процессора используем параметры современных микросхем GPU (16384 АЛУ с частотой 2.5ГГц, 200МБ памяти в виде FIFO и различных буферов). Пиковая производительность составит 40 триллионов операций в секунду.

• Отдельные АЛУ процессора подключается в «разрыв» FIFO виртуального канала ССИ коммутатора. Процессор (совокупность ALU) забирает данные для обработки из FIFO приемника и помещает результаты обработки в FIFO передатчика сети ССИ. Число таких FIFO на одном кристалле может быть от ста тысяч тысяч до миллиона.

• При компактной упаковке таких процессоров, 2 процессора на литр (кубический дм) в куб со стороной в один метр получаем производительность суперкомпьютера до 10E17 в секунду на кубический метр.

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

Модель программирования:

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

• Результат исполнения вершины используется для вычисления одной или нескольких вершин обязательно находящихся выше ярусом.

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

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

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

• Вся программа может быть представлена несколькими большими «треугольниками». Основание «треугольника» это исходные данные, вершина одно результирующее данное, их можно выполнять независимо друг от друга. Тело «треугольника» представляет собой как бы большую команду команду виртуального АЛУ преобразующую исходные данные программы в результат за один такт и без промежуточных данных. Число больших «треугольников» равно числу результирующих данных.

• Поскольку в реальности такого виртуального АЛУ нет, а программа представляет собой ациклический граф состоящий их отдельных «треугольников» команд АЛУ, то можно сказать что большой «треугольник» состоит из большого числа соединенных между собой маленьких «треугольников» команд реального АЛУ.

• Число реальных физических АЛУ достаточно велико, но все же может быть меньше чем число вершин в графе программы. Решать эту проблему можно двумя путями.

  • Первый способ: Разбить программу на множество «треугольников» меньшего размера и выполнить их последовательно. С запоминанием результатов исполнения каждого как промежуточных данных.

  • Второй способ: Объединить маленькие «треугольники» (команды АЛУ) в конструкции побольше и исполнять их как обычные линейные последовательные куски кода. В реальности можно использовать оба способа одновременно.

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

• Разбиение «большого треугольника» на меньшие может породить пересечение «треугольников», а это одинаковые промежуточные данные и повторное вычисление уже вычисленных результатов в разных частях программы. Решение о повторном вычислении или передачи готовых данных принимается после учета времени на передачу. В случае если повторное вычисление тратит времени и энергии меньше чем передача этих промежуточных данных, то повторно вычисляем, если нет то передаем.

• Программа исполняемая в DataFlow вычислителе, представляет собой совокупность данных хранимых в памяти, списка команд хранимых в АЛУ и сети виртуальных каналов ССИ.

• Для вычисления необходимо передать данных из памяти в соответствующие виртуальные каналы сети ССИ и записать результаты в память. Иными словами, Вычисление результата это передача набора данных по заранее сформированной сети виртуальных каналов, с последующим приемом и сохранением в память результатов исполнения.