Генерация кода для архитектур с переконфигурируемым трактом обработки данных при помощи LLVM

30 октября 2017

Мы продолжаем изучать возможности и особенности компиляторов LLVM. Предлагаем вам перевод очередной статьи, посвященной LLVM.

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

Авторы: Михаэл Адриансен, Марк Вейтвлит, Рул Йорданс, Люк Ваейен, Хенк Корпорал. Кафедра электротехники, Эйндховенский технологический университет, Эйндховен, Нидерланды.

Хороший инструментарий крайне важен для вычислительных платформ, так как он упрощает программирование платформы. Особенно это касается реконфигурируемых архитектур, для которых необходимо адаптировать прикладные программы под каждую конфигурацию аппаратного обеспечения. Данная статья описывает способы применения фреймворка LLVM в генерации кода для крупнозернистых реконфигурируемых массивов (англ. Coarse Grained Reconfigurable Array, CGRA). Поддержка всех возможных конфигураций архитектуры требует от компилятора CGRA адаптивности. Необходимо использовать особенности аппаратуры и заложенный в них метод явного обхода. При этом от компилятора требуется поддержка программных конвейеров, множества регистровых файлов и операционного планирования. Статья оценивает потенциал фреймворка LLVM и определяет недостающий функционал, необходимый для поддержки архитектур с переконфигурируемым трактом обработки данных.

---

Введение

Встраиваемые мобильные устройства ограничены емкостью батареи. Для обычного мобильного телефона мощность, доступная приложениям, составляет около 1 Ватт [1]. Энергоэффективность такой платформы ограничивает количество вычислений, которые могут выполнять приложения. Несмотря на то, что для высокой производительности и энергоэффективности можно использовать интегральные схемы специального назначения (англ. Application Specific Integrated Circuits, ASIC), такой выбор не всегда целесообразен из-за недостаточной гибкости. Чем меньше времени на разработку, тем важнее становится скорость создания программ. Процессоры общего назначения предоставляют высокий уровень гибкости и программируемости, но им не хватает вычислительной мощности и/или энергоэффективности. В таких процессорах значительная часть вычислительных ресурсов идет на выборку и декодирование команд, а еще больше — на перемещение данных между памятью, кэшами и регистровыми файлами [2]. Программируемая логическая интегральная схема (англ. Field-Programmable Gate Array, FPGA) позволяет избежать существенной части затрат вычислительных ресурсов за счет пространственного маппинга приложений, но ее излишняя реконфигурируемость также приводит к высоким затратам. Для большинства приложений обработки сигналов FPGA предоставляет чрезмерную реконфигурируемость. CGRA благодаря своим более крупным модулям требует меньше бит для конфигурирования, что позволяет снизить потребление энергии без потери пространственного маппинга приложений [3].

В целом, программируемость устройства зависит от инструментов, с помощью которых для него пишется код. Большинство CGRA можно рассматривать как реконфигурируемые процессоры. Для программиста это является положительным моментом, так как он уже знаком с подобными архитектурами. Преимущество перед процессорами общего назначения заключается возможности адаптироваться под приложение после изготовления. Следовательно, поиск энергоэффективной конфигурации архитектуры можно выполнять на самой аппаратной платформе. Однако ручной маппинг приложения для каждой платформы – долгий и трудоемкий процесс. Чтобы программист мог эффективно использовать сконфигурированную архитектуру, нам необходим компилятор, преобразующий высокоуровневый язык (например, C) в высокопараллельные инструкции CGRA. Для такой архитектуры требуется очень гибкий компилятор, способный делать несколько допущений об архитектуре конфигурируемого процессора. Две архитектурные особенности CGRA, направленные на снижение энергопотребления, уже обнаружили крайнюю затруднённость их эффективного применения в высокоуровневом компиляторе. Эти особенности – явный обход регистрового файла и распределенные регистровые файлы. Явный обход регистрового файла значительно уменьшает потребление энергии архитектурой процессора за счет передачи промежуточных результатов вычислений напрямую из одного функционального блока в другой, избегая тем самым энергозатрат на запись и чтение в/из регистрового файла. Распределенные регистровые файлы позволяют архитектуре процессора использовать множество мелких файлов, требующих меньших затрат энергии и меньше места на жестком диске по сравнению с одним большим. Однако такие файлы могут стать проблемой для компилятора, если не все функциональные блоки имеют доступ ко всем регистровым файлам.

Статья описывает компилятор для архитектур CGRA, разрабатываемый при помощи фреймворка LLVM [4]. Однако мы нашли несколько ключевых особенностей шаблонов архитектур CGRA, которые сложно реализовать при помощи этого фреймворка. LLVM, в основном, предоставляет поддержку обычных скалярных (суперскалярных) процессоров, но со временем был расширен для поддержки архитектур длинных машинных команд (англ. Very Long Instruction Word, VLIW) (таких, как Qualcomm Hexagon [5]) и архитектур графических процессоров AMD Radeon [6]. Таким образом, поддержка высокопараллельных архитектур VLIW на данный момент присутствует как таковая, однако, LLVM все еще не поддерживает более продвинутые особенности архитектуры (например, явный обход регистрового файла и распределенные регистровые файлы). В этой работе мы концентрируемся на этих особенностях и определяем компоненты LLVM, которые можно считать достаточно зрелыми, и компоненты, которые требуют значительной доработки, касающейся поддержки архитектур с реконфигурируемым трактом обработки данных (например, CGRA). Глава «Архитектура» описывает архитектуру CGRA. Глава «Пример программирования CGRA» показывает особенности этой архитектуры на ядре-примере и демонстрирует сложности, возникающие при генерации кода. Глава «Компилятор» предлагает подходы к использованию особенностей генерации кода CGRA при помощи LLVM и рассматривает различные специфичные для целевых архитектур оптимизации. Глава «Текущее состояние CGRA» описывает текущее состояние компилятора, а также целесообразность использования LLVM для платформы CGRA с практической точки зрения.

Другие материалы по теме

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

Например, архитектуры TTA (англ. Transport Triggered Architecture) очень похожи на архитектуру CGRA тем, каким образом компилятор генерирует код. В частности, TTA тоже предоставляет явный путь данных, поэтому задача компилятора — сопоставить операции с функциональными блоками и найти пути между функциональными блоками (которые могут как проходить, так и не проходить через регистровый файл) для маршрутизации операндов. Информация о TTA представлена в источнике [7], компилятор описан в [8] и [9]. Новые версии архитектуры TTA включены во фреймворк TCE [10], [11], который с недавних пор поддерживает генерацию кода при помощи LLVM.

Архитектура синхронного переноса (англ. Synchronous Transfer Architecture, STA) описана в [12] и похожа на TTA, но триггеры в ней реализованы при помощи VLIW-подобной машинной команды. Архитектура состоит из нескольких функциональных блоков, которые имеют входные и выходные порты для передачи данных. Входные порты выбираются при помощи мультиплексоров. Машинные команды разделены на сегменты. Каждый сегмент отвечает за функциональный блок и содержит триггер, информацию для мультиплексоров и, опционально, непосредственное значение. Компиляторный подход описан в [13]. Компилятор использует целочисленное линейное программирование для планирования команд.

Другим процессором с заданным трактом обработки данных является процессор для обработки множества данных за раз (англ. Single Instruction, Multiple Data, SIMD) [14]. Путь данных вычислительных элементов SIMD похож на путь данных в RISC, но в нем конвейерные регистры, при помощи архитектуры набора команд (англ. Instruction Set Architecture, ISA), выступают для компилятора в качестве источников операндов. За счет явного обхода переменных с коротким сроком существования внутри конвейерных регистров можно избежать большого количества обращений к регистровому файлу, что приведет к снижению энергопотребления. Компилятор, поддерживающий OpenCL [15], использует LLVM в качестве фронтенда. Бэкенд, в свою очередь, абсолютно индивидуальный и использует метод планирования «снизу-вверх». Несмотря на то, что применение индивидуального бэкенда более консервативно, чем в TTA, оно говорит о том, что поддержка архитектур заданного тракта обработки данных в стандартном фреймворке LLVM является сложной задачей.

Архитектура

CGRA состоит из хост-процессора и реконфигурируемой логики, как показано на рисунке 1. Хост-процессор отвечает за конфигурацию CGRA. Данные приложений можно переносить между двумя процессорами при помощи общей глобальной памяти. Загрузка данных конфигурации и инструкций CGRA также выполняется хост-процессором. Данные конфигурации содержат bit-файл, похожий на bit-файл FPGA, который конфигурирует сети управления и сети данных, а также поведение функциональных блоков. Основой CGRA являются следующие функциональные блоки:

• блоки накопления ветвей (англ. Accumulate Branch Units, ABU), которые используются как для потока управления, так и в качестве дополнительного накапливающего регистра;
• арифметико-логические устройства (англ. Arithmetic Logic Units, ALU), способные выполнять простейшие арифметические и логические операции;
• блоки непосредственных значений (англ. Immediate Units, IMM), используемые для создания констант, необходимых программе;
• блоки загрузки/хранения (англ. Load Store Units, LSU), способные загружать и хранить значения в локальных банках памяти или глобальной памяти;
• блоки умножения (англ. Multiplier Units, MUL), используемые для выполнения операций умножения;
• регистровый файл, используемый для хранения промежуточных результатов.

Рисунок 1. Архитектура [3].

Функциональные блоки управляются блоками загрузки (англ. Instruction Fetch, IF) и декодирования (англ. Instruction Decode, ID) команд. Каждому блоку IF/ID назначается участок памяти команд, из которого он производит чтение инструкций по одной за такт. Связь между блоком IF/ID и одним или несколькими функциональными блоками устанавливается во время конфигурирования. Множество групп IF/ID-функциональных блоков составляют процессор VLIW. Конфигурация SIMD создается за счет формирования связи между одним блоком IF/ID и несколькими функциональными блоками. При помощи реконфигурируемой сети данных каждый вход и выход функционального блока может быть задействован. Это позволяет архитектуре адаптировать путь прохождения данных приложения, а также осуществлять пространственный маппинг приложения на устройство. Результаты, полученные функциональными блоками, не требуют хранения в регистровом файле, их можно напрямую передавать другим функциональными блокам, что создает заданный тракт обработки данных. Несмотря на то, что это может быть очень энергоэффективным процессом, компиляция для таких архитектур – нетривиальная задача.

Рисунок 2 показывает экземпляр простейшего процессора. Он содержит IMM для генерации значений, которые ALU могут использовать в вычислениях. Регистровый файл может быть использован для хранения текущих значений, которые не могут храниться внутри регистров явного пути данных. LSU могут загружать и хранить данные в локальной или глобальной памяти, а ABU используется для вычислений, связанных с указателем на инструкции и ветвлением. Можно заметить, что допускается пропуск данными некоторых функциональных блоков, например, данные из LSU могут напрямую приниматься блоком ALU без необходимости проходить через регистровый файл. Для компиляции это значит, что может существовать несколько путей между производящими и принимающими функциональными блоками.

Рисунок 2. Конфигурация простейшей архитектуры.

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

Пример программирования CGRA

Алгоритм бинаризации показывает, как может быть выполнен код CGRA. Псевдокод примера показан в алгоритме 1. Бинаризация может использоваться для создания черно-белой версии изображения при помощи сравнения информации об элементах изображения с предельным значением и записи единицы или нуля вместо элемента изображения в зависимости от результата сравнения. В алгоритме 1, каждый пиксель массива A сравнивается с предельным значением TH. Результат этого сравнения записывается в соответствующий массив B. По окончанию работы алгоритма, массив B будет содержать черно-белую версию изображения в массиве А.

Алгоритм 1. Алгоритм бинаризации.

Input: Массив A, содержащий изображение, предельное значение TH.
Output: Массив B, содержащий двоичное изображение.
1: procedure BINARIZATION(A[ ], B[ ], TH, Count) 
2:       for int I = Count; I != Count;I=I-1do 
3:            B[I] < (A[I] >= TH) 
4:       end for 
5: end procedure

Для выполнения алгоритма бинаризации была создана пользовательская конфигурация CGRA (см. рисунок 3). Архитектура конфигурации показана на рисунке 3а, заданное вручную планирование изображено на рисунке 3b. Несмотря на то, что каждый алгоритм может быть вычислен при помощи минимальной конфигурации архитектуры, показанной на рисунке 2, эта конфигурация использует больше функциональных блоков для уменьшения количества циклов. В конфигурации бинаризации используются два ALU: один для операций сравнения, требуемых самой бинаризацией; а второй для управления счетчиком циклов.

Цикл for был программно поставлен на конвейер, чтобы показать полный потенциал архитектуры. Тело цикла находится внутри красных линий. Блоки IMM и регистровые файлы содержат информацию о переменных и блоках, которые их произвели. Блоки LSU, ALU и ABU показывают, какие операции выполняет каждый функциональный блок. Три функциональных блока слева используются для обработки данных. Два значения массива A сравниваются с предельными значениями на каждой итерации цикла. Результат сравнения записывается в массив B. Вычисление адреса выполняется косвенно в LSU. Четыре функциональных блока справа используются для потока управления циклом. Переменная I уменьшается на 1 на каждой итерации. Когда I станет равно нулю, цикл завершится.

(a) Архитектурная конфигурация.

(b) Планирование программных инструкций.

Рисунок 3. Фрагмент кода бинаризации CGRA.

Из этого примера, хорошо виден используемый в архитектуре CGRA параллелизм на уровне команд (англ. Instruction Level Parallelism, ILP) и то, как он влияет на программную конвейеризацию и обход. Пример можно наблюдать на критическом пути (LSU-ALU-LSU) фрагмента кода, покрывающем расстояние большее, чем между границами циклов. Явный обход также можно наблюдать благодаря тому факту, что только итератор I хранится в файле регистров, а все другие программные значения передаются напрямую между функциональными блоками.

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

Компилятор, позволяющий планировать команды, как показано на рисунке 3b, должен обладать следующими свойствами:

• он должен быть адаптируемым, чтобы выполнять планирование для всех возможных конфигураций;
• планировщик должен поддерживать явный обход файла регистра;
• планировщик должен быть операционно-ориентированным;
• для эффективного планирования должна поддерживаться программная конвейеризация;
• для планирования под все конфигурации требуется поддержка множества регистровых файлов.

Компилятор

Реализация поддержки новых архитектур в рамках LLVM требует добавления зависимого от целевой архитектуры бэкенда. Этот бэкенд преобразует независимое от целевой архитектуры промежуточное представление LLVM в зависимые от целевой архитектуры инструкции, определяет где хранить промежуточные данные программы и генерирует финальную сборку или бинарный код, который может быть запущен на целевой архитектуре. Обычно этот процесс разделен на несколько шагов, как показано на рисунке 4. Сначала операции промежуточного представления преобразуются в операции целевой архитектуры в процессе выбора инструкций. Затем происходит планирование выбранных инструкций и распределение регистров для хранения промежуточных результатов. Порядок, в котором происходит планирование и распределение регистров, может оказывать значительное влияние на качество конечного кода. Таким образом, внутри фреймворка можно выбрать, какой порядок будет использоваться для новой целевой архитектуры, и для реализации ранее упущенных возможностей могут быть добавлены итерации перед распределением или после планирования. Наконец, пролог и эпилог добавляются для обработки входных и выходных точек компилируемой функции. Обычно такие команды можно вставлять в начало или конец генерируемого кода. Однако в CGRA это более сложная процедура, требующая дополнительного шага планирования. После этого генерация кода завершена, и машинный код может быть записан в выходной файл.

Рисунок 4. Порядок проходов планирования в компиляторе.

Адаптация фреймворка компилятора

Обычно LLVM использует инструкции, работающие с регистрами, адресами в памяти и непосредственными значениями. Инструкции CGRA же содержат информацию о том, из какого порта-источника поступают операнды, и в какой порт-адресат необходимо направить результаты. Выделенный класс регистра можно использовать для моделирования входных и выходных портов функционального блока таким образом, чтобы архитектура была совместимой с ожидаемой моделью. Выбор инструкций преобразует стандартные инструкции LLVM в псевдо-инструкции, которые также работают с регистрами и непосредственными значениями. Затем специальный проход планировщика преобразовывает их в настоящие инструкции и устанавливает корректные порты-источники и адресаты.

Так как проход пролога/эпилога добавляет новую псевдо-инструкцию в существующее расписание, после этого необходим новый проход планировщика. Оба прохода планировщика используют один и тот же код. На данный момент бэкенд использует существующий распределитель регистров LLVM. Однако для поддержки множества файлов регистра может понадобиться другой распределитель регистров. Подробнее об этом см. ниже.

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

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

Поддержка явного обхода

Традиционный планировщик сможет планировать архитектуры явного обхода после внесения некоторых изменений. Один из подходов — использование планировщика совместно с дополнительным проходом, который проверяет наличие возможностей для явного обхода, например, в [16]. Этот подход лучше всего работает с планировщиком на базе циклов, так как он всегда может направить результаты обратно в регистровый файл. А применение в архитектуре CGRA затруднено, так как пропускная способность регистрового файла ограничена, что приводит к повторным планированиям после выбора обхода. Другой подход — разместить регистры обхода до планирования инструкций, как это сделано в [10]. Преимущество такого подхода заключается в том, что нормальный алгоритм планирования способен заранее учитывать пути обходов и имеет больше шансов на оптимальное планирование. Наконец, третьим подходом является использование планировщика, который способен автоматически назначить регистры в процессе планирования команд. После этого файлы регистра эффективно используют обход, но все еще требуют размещения.

Был выбран планировщик, реализующий третий подход, так как он может выполнять планирование за приемлемое время. Этот планировщик использует граф ресурсов, чтобы определить доступность функциональных блоков и регистров обхода во время процесса планирования. Граф ресурсов построен исходя из описания конфигурации в XML-файле. Описание конфигурации содержит список функциональных блоков и связей между ними. Загрузка этого графа ресурсов в нашем бэкенде индивидуальная, так как LLVM обычно не предоставляет такой детальной адаптивности бэкендов. Обычно один бэкенд поддерживает фиксированный набор вариантов архитектур, что предоставляет гораздо меньше гибкости, чем шаблон CGRA.

Операционно-ориентированный алгоритм планирования

На данный момент проходы планирования инструкций LLVM предоставляют только алгоритмы, основанные на циклах и их нельзя применять к архитектурам c заданным трактом обработки данных, для которых больше подходит операционно-ориентированный алгоритм. Такой подход требует более тщательного учета системных ресурсов по сравнению с существующими планировщиками. Современные планировщики, основанные на циклах, ограничены, так как не имеют возможности добавлять новые операции в существующие или будущие циклы. Планировщик архитектуры с заданным трактом обработки данных должен уметь добавлять дополнительные операции, чтобы поддерживать значения активными, если они потребуются позже. Конечное назначение операнда не известно на текущий момент, потому что планировщик не знает, где и когда произойдет выполнение операции. Операционно-ориентированный планировщик способен отложить маршрутизацию созданного операнда или перенаправить операнд, пока его назначение неизвестно. Это приводит к более оптимальному использованию ресурсов.

Адаптированный алгоритм планирования показан в алгоритме 2. Пути операндов можно найти при помощи алгоритма кратчайших путей Дейкстры, как это сделано в [17]. В дополнение, алгоритм кратчайшего пути используется для выбора функционального блока. Для каждого операнда вычисляется кратчайший путь от его создателя до функционального блока. Таким образом, для первого операнда алгоритм кратчайшего пути необходимо запустить один раз. Для выполнения операции выбирается функциональный блок с наименьшей стоимостью. Стоимость пути вычисляется при помощи веса на ребрах графа ресурсов. Промежуточные операнды отличаются от операндов регистров, так как они могут быть созданы в любом месте расписания команд до тех пор, пока существует путь к функциональному блоку, для которого они необходимы. Расположение непосредственных значений находится за счет нахождения кратчайшего пути от функционального блока, который их обрабатывал до блока IMM. Это значит, что пути промежуточных операндов используются, когда вычислительный функциональный блок уже был выбран. Другим подходом будет ручной выбор блока IMM и поиск пути к вычислительному функциональному блоку. Однако это может привести к увеличению потребления энергии.

Алгоритм 2. Основанный на операциях алгоритм планирования.

Input: DDG D базового блока B и граф ресурсов RG 
Output: расписание команд базового блока MB 
1: procedure SCHEDULE(D,M) 
2: 	R ←initialize_ready_list(D) 
3: 	while R  = ∅ do 	 //расписание базового блока 
4: 	   o ←select_next_operation(R,D) 
5: 	   F ←find_available_FUs(o,RG) 
6: 	   while true do 		 //поиск функционального блока 
7: 		f ←select_FU(F) 
8: 		if o can be scheduled on f then 
9: 		claim_resources(RG) 
10: 		R ← R\{o} 
11: 		New_ops = add_ready_ops(o,D) 
12: 		R ← R∪New ops 
13:			 //добавить операцию в список готовых 
14: 		break 
15: 	      else 
16: 	   	   F ← F \f 
17: 	      end if 
18: 	   end while 
19: 	end while 
20: end procedure

Когда операция производит результат, который должен быть использован другой операцией, необходимо убедиться, чтобы этот результат был доступен на момент выполнения последней операции. Планировщик должен либо гарантировать доступность результата, либо быть способен перепланировать операцию, производящую этот результат. В противном случае планировщик составит недопустимое частичное расписание команд. Самый простой способ гарантировать доступность результата — направлять все результаты в регистровый файл, чтобы его можно было прочитать позже. Этот подход не позволит планировщику ошибиться, однако, спровоцирует перерасход ресурсов, что, в свою очередь, сместит исполнение других операций с той стадии цикла, когда ресурсы была свободны. Другой вариант — использование графов максимального потока, как описано в [17]. Он гарантирует достаточность ресурсов для направления всех активных переменных в регистровый файл без необходимости распределять ресурсы. Такой подход повысит качество планирования, но увеличит время отработки алгоритма, так как для каждой операции необходимо строить и обрабатывать граф. В некоторых случаях результат не может быть направлен в файл регистра, но его все еще можно использовать, например, в качестве входных данных для LSU. Применение графа максимального потока не позволит запланировать производящую инструкцию, что делает этот подход немного пессимистичным. Для восстановления недопустимых неполных расписаний команд также можно использовать планировщик с механизмом возврата, так как он всегда может отменить операцию, результат которой не может быть доставлен по назначению. Однако делать это нужно аккуратно, так как в случае ненахождения подходящего варианта планировщик откажет.

Программная конвейеризация в LLVM

Как показано в приложении-примере, программная конвейеризация — основной метод оптимизации архитектур, использующих ILP. Реализация программной конвейеризации в LLVM может быть выполнена на различных этапах компиляции, что имеет свои преимущества и недостатки. Изначально LLVM использовала планирование на основе свободных модулей [18] (англ. Swing Modulo Scheduling, SMS) для суперскалярной архитектуры Ultra Sparc IIIi [19] как часть этапа общего планирования. Однако эта реализация исчезла в результате тщательной переработки всей инфраструктуры планировщика LLVM. Недавно была предложена альтернативная реализация на независимом от целевой архитектуры уровне промежуточного представления кода, прямо перед планированием команд [20]. Преимущество такой реализации в том, что его можно использовать для других архитектур, включая архитектуры с пользовательским бэкендом, которые отличаются от таких фреймворков, как [15].

Наконец, было предложено новое дополнение к LLVM [21], которое реализует похожий подход для архитектуры процессора Hexagon сразу после этапа выбора команд, перед этапами планирования и распределения регистров. Преимущество этого подхода в том, что известны конкретные операции, которые будет выполнять процессор [21]. Этот подход схож с подходом, используемым на уровне промежуточного представления кода тем, что он преобразует вложенные циклы за счет перераспределения операций в соответствии с расписанием команд, но оставляет само планирование для нормального алгоритма планирования. Это приводит не только к достаточно прямолинейной реализации, которую можно портировать на другие архитектуры, но и к значительному увеличению производительности.

Поддержка множественных (распределенных) файлов регистра

Архитектура CGRA позволяет строить конфигурации с множественными регистровыми файлами. При текущем планировщике поддержка множественных файлов регистра является не тривиальной задачей. Рисунок 5 показывает граф потоков управления приложения, в котором один и тот же виртуальный регистр существует в нескольких базовых блоках и используется в другом базовом блоке. Рано или поздно vreg1 нужно будет распределить в физический регистр. Так как планировщик назначает пути операндов, он распределит vreg1 в файл регистра. Планировщик должен записать vreg1 в тот же файл регистра в блоке “if then”, что и в блоке “if else”. Затем он должен прочитать vreg1 из блока “Tail” того же регистрового файла. Этот метод можно назвать совмещенным планированием и распределением регистрового файла. После этого прохода распределитель регистров все еще должен назначить виртуальным регистрам физические. Этот проход должен иметь информацию о множественных регистровых файлах.

Рисунок 5. Граф потоков управления с кодом, который сложно распределить конфигурациям со
множественными регистровыми файлами.

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

Оптимизации энергоэффективности целевой архитектуры

Веса на ребрах между узлами графа ресурсов определяют, какие решения будет принимать планировщик. Это можно использовать для влияния на алгоритм планировщика, чтобы он генерировал энергоэффективные расписания команд. Многие операнды используются лишь несколько раз. Чтение операнда из регистрового файла дважды может расходовать больше энергии, чем однократное чтение и использование ALU для хранения значения до востребования. При использовании нескольких ALU для передачи операнда можно сохранить энергию за счет использования одного ALU для нескольких циклов вместо передачи значения на другой ALU на каждом цикле. При использовании одного ALU изменяется меньше бит-команд. При выборе между функциональными блоками, предпочтение отдается функциональному блоку с кратчайшей выходной связью, так как передача выходного операнда на другие функциональные блоки потребует меньше энергии. Помимо улучшения энергоэффективности, вес на ребрах позволяет улучшить качество расписания команд. Веса на концах регистрового файла могут совпадать с обратным числом регистров, которые содержит этот файл. Если в конфигурации несколько регистровых файлов, то механизм оптимизации автоматически балансирует количество регистров между файлами, если это позволяют взаимосвязи внутри конфигурации.

Текущий планировщик назначает коды операции, источники операндов и направляет операнды на функциональные блоки, которые должны выполнить какое-либо задание. По умолчанию, неиспользуемые функциональные блоки выполняют пустую команду. Сохранение команд из предыдущего цикла может быть более удачным подходом к снижению энергопотребления. Если команда не меняется на протяжении нескольких циклов, меньше бит меняется на этапе вызова и декодирования инструкций. Нужно быть аккуратным, чтобы эффект этой оптимизации энергопотреблении не был потерян на этапе выполнения. При выполнении пустой команды вывод функционального блока не меняется. Если вместо этого выполняется команда, меняющая вывод, используется больше энергии, чем при выполнении пустой команды. Рисунок 6 показывает два расписания команд, которые предоставляют один и тот же функционал. Для сохранения энергии расписание на рисунке 6а можно преобразовать в расписание, изображенное на рисунке 6b. В таком случае вся операция сложения, включая создание непосредственного значения и загрузки регистра, может быть скопирована на следующий цикл. Если данные записывались в R1 на цикле 2, выбор был бы менее тривиальным за счет дополнительного использования ALU. Необходимо найти эвристический алгоритм, который позволит получить золотую середину.

(a) Начальное расписание команд.

(b)Оптимизированное расписание команд.

Рисунок 6. Оптимизация энергоэффективности.

Текущее состояние CGRA

Компилятор CGRA на данный момент находится на ранней стадии своего развития. Он поддерживает большинство операций, необходимых для компиляции тестов производительности. Реализовано соглашение о вызовах, которое позволяет компилятору предоставлять базовую поддержку вызова функций. Можно генерировать код для архитектур, которые содержат множественные регистровые файлы, однако, хранить код в базовых блоках невозможно в силу ограничений распределителя регистров. Во время тестирования компилятора стало ясно, что необходимо тщательно выбирать веса на ребрах графа ресурсов при реализации операционного планировщика. В некоторых случаях планирование первого операнда операции делает невозможным планирование второго, т. к. путь первого блокирует путь второго. На данный момент планировщик представляет из себя отдельный проход LLVM, который заменяет собственный алгоритм планирования LLVM.

Чтобы в будущем полностью поддерживать множественные регистровые файлы и улучшать явный путь данных в расписании команд, мы считаем, что распределитель регистров должен быть включен в проход планировщика. Это позволит выполнять повторное планирование при ошибке распределения регистров, пока информация операционного планировщика еще доступна. Добавление комбинированного фреймворка планирования команд и распределения ресурсов (например, Unison [22]) в LLVM должно значительно упростить планирование команд для архитектуры CGRA, а также улучшить ее производительность.

Дальнейшие недавние дополнения LLVM (такие как поддержка программной конвейеризации) также выглядят многообещающими. Предложенная реализация [21] для архитектуры Hexagon в значительной мере соответствует текущей организации бэкенда CGRA, и мы ожидаем, что она может быть интегрирована без значительных трудностей. Главными дополнениями, необходимыми бэкенду CGRA, являются несколько средств целевых архитектур для предоставления информации о доступных блоках параллельных функций в конфигурируемых архитектурах.

Заключение

Разработка компилятора для реконфигурируемой архитектуры, основанного на LLVM, возможна, однако фреймворк нацелен на другие архитектуры. Пользовательский планировщик необходим, так как уже существующие поддерживают только циклическое планирование. Необходимо внимательно следить, чтобы такой планировщик не создавал недопустимое расписание команд, однако, этого можно избежать при помощи соответствующих эвристических алгоритмов. Мы также выяснили, что распределение регистров должно быть интегрировано с планировщиком для поддержки вытесняющего кода и множественных регистровых файлов. Глядя на текущие разработки в сфере LLVM, мы считаем, что программная конвейеризация для архитектуры Hexagon выглядит многообещающей и должна быть интегрирована в набор инструментов CGRA.

Список литературы

1. C. Van Berkel, “Multi-core for mobile phones,” in Design, Automation Test in Europe Conference Exhibition, 2009. DATE ’09., 2009.
2. R. Hameed, W. Qadeer, M. Wachs, O. Azizi, A. Solomatnikov, B. C. Lee, S. Richardson, C. Kozyrakis, and M. Horowitz, “Understanding sources of inefficiency in general-purpose chips,” SIGARCH Comput. Archit. News, vol. 38, no. 3, Jun. 2010.
3. M. Wijtvliet, L. Waeijen, M. Adriaansen, and H. Corporaal, “Position paper: Reaching intrinsic compute efficiency requires adaptable microarchitectures,” 2016.
4. C. Lattner and V. Adve, “LLVM:ACompilationFrameworkforLifelong Program Analysis & Transformation,” in Proceedings of the 2004 International Symposium on Code Generation and Optimization (CGO’04), Palo Alto, California, Mar 2004.
5. L. Codrescu, “Qualcomm hexagon DSP: An architecture optimized for mobile multimedia and communications,” in HotChips, 2013.
6. M. Mantor and M. Houston, “AMD graphic core next: Low power high performance graphics & parallel compute,” in AMD Fusion’11 developer summit, 2013.
7. H. Corporaal and H. J. Mulder, “Move: A framework for highperformance processor design,” in Proceedings of the 1991 ACM/IEEE conference on Supercomputing. ACM, 1991, pp. 692–701.
8. J. Hoogerbrugge, Code generation for transport triggered architectures. TU Delft, Delft University of Technology, 1996.
9. J. Janssen, Compiler strategies for transport triggered architectures. TU Delft, Delft University of Technology, 2001.
10. P. Kellom¨aki, V. Guzma, and J. Takala, “Safe pre-pass software bypassing for transport triggered processors,” Acta Technica Napocensis, vol. 49, no. 3, pp. 5–10, 2008.
11. J. Pekka, K. Heikki, V. Timo, and T. Jarmo, “Code density and energy efficiency of exposed datapath architectures,” Journal of Signal Processing Systems, vol. 80, no. 1, July 2015.
12. G. Cichon, P. Robelly, H. Seidel, E. Mat´ uˇs, M. Bronzel, and G. Fettweis, “Synchronous transfer architecture (sta),” in Computer Systems: Architectures, Modeling, and Simulation. Springer, 2004, pp. 343–352.
13. J. Guo, T. Limberg, E. Mat´us, B. Mennenga, R. Klemm, and G. Fettweis, “Code generation for sta architecture,” in Euro-Par 2006 Parallel Processing. Springer, 2006, pp. 299–310.
14. L. Waeijen, D. She, H. Corporaal, and Y. He, “A low-energy wide simd architecture with explicit datapath,” Journal of Signal Processing Systems, vol. 80, no. 1, pp. 65–86, 2014. [Online]. Available: http://dx.doi.org/10.1007/s11265-014-0950-8
15. D. She, Y. He, L. Waeijen, and H. Corporaal, “A co-design framework with opencl support for low-energy wide simd processor,” Journal of Signal Processing Systems, vol. 80, no. 1, pp. 87–101, 2014. [Online]. Available: http://dx.doi.org/10.1007/s11265-014-0957-1
16. D. D. She, “Energy efficient code generation for streaming applications,” Ph.D. dissertation, Technische Universiteit Eindhoven, 2014.
17. D. She, Y. He, B. Mesman, and H. Corporaal, “Energy efficient code generation for processors with exposed datapath,” in Proc. 9th Workshop on Optimizations for DSP and Embedded Systems (ODES-9), 2011.
18. J. Llosa, A. Gonz´alez, E. Ayguad´e, and M. Valero, “Swing module scheduling: a lifetime-sensitive approach,” in Parallel Architectures and Compilation Techniques, 1996., Proceedings of the 1996 Conference on. IEEE, 1996, pp. 80–86.
19. T. M. Lattner, “An Implementation of Swing Modulo Scheduling with Extensions for Superblocks,” Master’s thesis, Computer Science Dept., University of Illinois at Urbana-Champaign, Urbana, IL, June 2005.
20. R. Jordans and H. Corporaal, “High-level software-pipelining in LLVM,” in SCOPES ’15 - 18th International Workshop on Software and Compilers for Embedded Systems, Sankt Goar, Germany, June 2015, pp. 97–100.
21. B. Cahoon, “An implementation of swing modulo scheduling in a production compiler,” in LLVM developers meeting, October 2015, patch under review: http://reviews.llvm.org/D16829.
22. R. C. Lozano, M. Carlsson, G. H. Blindell, and C. Schulte, “Register allocation and instruction scheduling in unison,” in Proceedings of the 25th International Conference on Compiler Construction, 2016, pp. 263–264.

Теги: LLVM, генерация кода, компиляция, реконфигурируемые архитектуры, CGRA