Конвейерные схемы, вычисляющие несколько выражений

SECR 2018
Борис Штейнберг
заведующий кафедрой, ЮФУ

Данная статья относится к области высокоуровневого синтеза. Работа посвящена предварительным преобразованиям программ языка Си, до их автоматического преобразования компилятором в HDL-описание соответствующей электронной схемы. Рассматриваемые преобразования направлены на поиск такой конвейерной схемы, которая способна вычислять несколько различных программных циклов. Создание такого конвейерного вычислителя может привести к экономии ресурсов ПЛИС при генерации схемы и может сэкономить время, необходимое для перепрограммирования ПЛИС-ускорителя. Реализация таких преобразований предполагается на основе ОРС (оптимизирующей распараллеливающей системы). Задача поиска оптимального конвейера оказывается вычислительно сложной, но, в некоторых частных случаях, сводится к известной задаче выравнивания строк.

Transcript

1. Конвейерные схемы, вычисляющие несколько выражений  Южный федеральный университет, мехмат   Б.Я. Штейнберг, А.П. Баглий, Ж.М. Петрова, О.Б. Штейнберг
2. Ускорители на ПЛИС • Система Maxwell фирмы FHPCA (FPGA High Performance Computing Alliance) состоит из 32 «Блэйд-серверов», (один процессор Xeon и две PCI-E карты на ПЛИС Virtex4) для ряда задач, например решения дифференциальных уравнений методом Монте-Карло, показала 250-1000-кратный прирост производительности по сравнению с аналогичной системой, не применяющей ПЛИС. • Карта XILINX ALVEO предназначена для увеличения производительности дата центров, суперкомпьютеров и демонстрирует производительность в 90 раз большую по сравнению с CPU и в 4 раза по сравнению с GPU.
3. Развитие новых архитектур сдерживается отсутствием инструментального ПО • ПЛИСы уже несколько десятилетий демонстрируют конкурентные преимущества в производительности и энергопотреблении, но занимают значительно меньшую часть рынка микросхем, чем могли бы, поскольку не имеют хорошего инструментального программного обеспечения.
4. КЭШ ЦПУ Контроллер t1 t2 tn ... Потоки: Входной менеджер потоков Выходной менеджер потоков СнК ОЗУ Особенности компилятора: 1)содержит конвертор C2HDL; 2) содержит генератор драйверов; 3) ПЛИС поддерживает только часть кода; 4) специальные высокоуровневые оптимизации. Низкое энергопотребление Высокая производительность Высокая скорость обмена ЦПУ и ПЛИС. Не требуется сложный протокол обмена данными. Масштабируемость ограничена логическими ресурсами кристалла. ОСОБЕННОСТИ КОМПИЛЯТОРА НА ПРОГРАММИРУЕМУЮ АРХИТЕКТУРУ (Ю. МИХАЙЛУЦ & К0)
5. Вычислительный конвейер 
6. Вычисление одинаковых выражений 
7. Реконфигурируемый конвейер 
8. Перепрограммирование конвейера • Программируемые архитектуры (ПЛИС) быстро вычисляют, но долго перепрограммируются • И.И. Левин (НИИ МВС ЮФУ) перепрограммирует только связи между вычислительными устройствами (сумматорами, умножителями,…) • K. Bondalapati & V. Prasana предлагают алгоритм минимизации перепрограммирований конвейера для вычисления кода.
9. Конвейер, покрывающий несколько других конвейеров • В данной работе предлагается строить конвейер, на котором можно вычислять несколько исходных выражений. • Предлагаемый конвейер может оказаться сложнее, чем каждый конвейер, построенный в соответствии с каждым входным выражением. Но необходимые ресурсы ПЛИС для построения предлагаемого конвейера меньше, чем совокупные ресурсы для конвейеров всех входных выражений.
10. Конвейер, покрывающий несколько других конвейеров 
11. Граф вычислений – промежуточное представление реконфигурируемого конвейера в компиляторе  Граф вычислений, построенный автоматически в Оптимизирующей распараллеливающей системе (ОРС)
12. Выражения, у которых граф вычислений – простой путь • Граф вычислений цепной дроби – простой путь. • Граф вычислений схемы Горнера можно рассматривать, как простой путь.
13. Применение алгоритмов выравнивания последовательностей  Если исходные выражения представляют собой простой путь, для построения покрывающего выражения можно использовать известные алгоритмы выравнивания строк. • Такие алгоритмы используются в биоинформатике для выравнивания нуклеотидных последовательностей. • Для парного выравнивания можно использовать алгоритм Нидлмана-Вунша. Множественные выравнивания имеют очень высокую алгоритмическую сложность и могут строится на основе парных. • Для общего случая (в процессе) алгоритмы имеют сложный переборный характер, причем перебор деревьев ожидается не простым..
14. Большое тело конвейеризуемого цикла • Может случиться, что на ПЛИС недостаточно ресурсов для создания конвейера одного исходного конвейеризуемого цикла. • Скриншот преобразования «разбиение циклов» в ОРС. • Можно применить преобразование «разбиение цикла» и из одного большого исходного цикла получить несколько более мелких циклов, для которых искать покрывающий цикл.
15. Фотонный компьютер (рисунки С.А. Степаненко): основа программы как и для программируемого конвейера – граф вычислений
16. Сингулярные гнезда циклов для передачи на ускорители • Поскольку доступ к данным в оперативной памяти на современных компьютерах намного дольше вычислительных операций, на ускорители передаются части программы, у которых много вычислений с небольших объемом данных (которые должны поместиться на локальной памяти микросхемы ускорителя, в данном случае, ПЛИС). Такими фрагментами кода могут быть такие гнезда циклов, у которых количество циклов гнезда больше размерности любого входящего в гнездо массива. Такие гнезда можно называть сингулярными (вырожденными). Такими являются гнезда циклов алгоритма перемножения матриц, алгоритма Флойда-Уоршала и др. В ОРС реализован поиск таких участков кода .
18. Преимущества высокоуровневого ВП компилятора по сравнению с регистровым 1. При диалоговом анализе программы пользователь лучше узнает свой код, который ему возвращается преобразованным из высокоуровневого ВП, чем из регистрового. 2. Легче анализировать код для блочного размещения данных в общей памяти. 3. Легче анализировать код для блочно-аффинных размещений данных с перекрытиями в распределенной памяти. 4. Легче генерировать HDL-описание конвейерного вычислителя
19. Low/High Level IR Comparison low-level IR high-level IR small number of source languages high-level IR large number of target computer architectures large number of source languages low-level IR small number of target computer architectures
20. Нестандартные функции компилятора  Поиск сингулярных гнезд циклов (много вычислений с малым числом данных)  Диалоговое преобразование программ к блочным вычислениям (тайлинг)  Минимизация перенастроек конвейера (поиск покрывающего дерева для нескольких деревьев)  Retming для оптимизации буферной памяти для синхронизации конвейера  Распараллеливание рекуррентных вычислений  Диалоговый режим оптимизирующей компиляции с символьным анализом и уточнением зависимостей, с рекомендациями по оптимизации.  Блочные размещения массивов в оперативной памяти  Блочно-аффинные размещения массивов в распределенной памяти
21. http://ops.rsu.ru