Новым процессорам — новые компиляторы

Начиная с середины прошлого десятилетия ведущие производители микроэлектроники (Intel, AMD, Nvidia, IBM, Tilera и др.) наладили выпуск многоядерных процессоров — параллельные вычисления стали массовыми. Предлагаемые рынку архитектуры отличаются не только количеством ядер, но и способом их соединений, видами параллельных вычислений (SIMD, MIMD, pipeline), организацией используемой памяти и т. п., причем как только на рынок выходит новый высокопроизводительный процессор или ускоритель, тут же появляется соблазн объединить несколько таких устройств и получить еще большую производительность. И вот здесь возникает проблема разработки программного обеспечения, использующего весь потенциал вычислительной системы [1]. Разработка такого ПО требует много ресурсов (программистов высокой квалификации, времени, средств), а планы по переносу прикладных программ на новую систему обычно обречены на провал — перенос программ между архитектурами обычно возможен только в рамках семейств схожих архитектур.

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

Оптимизирующие компиляторы

Распараллеливающий компилятор — частный случай оптимизирующего, который условно можно разделить на блок синтаксического разбора текста, блок оптимизации и генератор кода. До наступления эпохи массового параллелизма проблему разработки эффективных программ решали семейства оптимизирующих компиляторов: GCC, LLVM, Intel С++/Fortran Compiler, Microsoft Visual Studio. В основе каждого семейства компиляторов лежит его внутреннее («промежуточное») представление, и при появлении нового процессора в этих семействах разрабатывался генератор кода из внутреннего представления к архитектуре нового процессора. Для нового процедурного языка программирования создавалась процедура синтаксического разбора с этого языка во внутреннее представление. И в одном и в другом случае иногда приходилось расширять блок оптимизации.

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

Автоматизировать, а значит, ускорить, удешевить и повысить надежность разработки компиляторов стремятся десятилетиями. Автоматизация основана на формальном описании входа и выхода компилятора — например, средствами формы Бэкуса-Наура, на основе которых построены известные «генераторы компиляторов» YACC, BIZON, ANTLER, GoldParser, на самом деле являющиеся генераторами парсеров.

Имеется много компилирующих систем (C-to-Verilog, Catapult C, Impulse CoDeveloper, MathLab и др.), генерирующих код HDL (Hardware Description Language) и ориентированных на автоматизацию проектирования электронных схем. В перспективе такие системы могут быть использованы при разработке компиляторов для вычислительных систем с программируемыми процессорами или ускорителями на ПЛИС. Кроме этого есть еще компилирующие системы для одновременного проектирования вычислительной системы и программ к ней, но они ориентированы на создание встроенных систем.

В целом для создания генератора параллельного кода в компиляторах приемлемых средств автоматизации на данный момент нет.

Все перечисленные семейства компиляторов имеют генераторы параллельного кода OpenMP для работы на системах с общей памятью (многоядерные или SMP-архитектуры), однако само по себе распараллеливание не самоцель.

Развитие инструментов оптимизирующей компиляции отстает от развития вычислительных архитектур, что иллюстрирует пример простейшей программы перемножения матриц:

for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
for (k = 0; k < N; k++)
C[i][j] = C[i][j] + A[i][k]*B[k][j]

На больших размерностях эта программа работает на многоядерном процессоре Intel Core 2 Duo в 60 раз медленнее, чем соответствующая программа библиотеки MKL для традиционной архитектуры. Очевидно, что быстродействие библиотечной программы не сводится к распараллеливанию, поскольку два ядра могут дать ускорение не более, чем вдвое. С другой стороны, следует отметить, что быстрая библиотечная программа могла быть написана программистом весьма высокой квалификации, хорошо знающим и учитывающим архитектуру процессора (несколько видов кэш-памяти, технология SSE и другие особенности).

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

Память против параллельности

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

Можно выделить несколько типов алгоритмов:

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

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

Работа компиляторов с памятью

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

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

Когда время доступа к данным превысило время их обработки, в процессорах появилась кэш-память, более быстрая, чем оперативная. Данные из оперативной памяти в кэш передаются рядом лежащими группами — «кэш-линейками». Актуальными здесь стали задачи такого распределения данных в оперативной памяти, чтобы в подгружаемых кэш-линейках было мало лишних данных. Важным фактором оптимизации работы с памятью является выравнивание массивов (размещение в памяти, начиная с адреса, кратного определенному числу) — при обращении к элементам выравненного массива (в случае, когда адрес массива кратен размеру кэш-линейки) происходит меньше кэш-промахов. Также на некоторых типах процессоров векторные команды работают только с выравненными массивами (когда адрес массива кратен размеру векторного регистра). Автоматическое выравнивание данных реализовано во всех компиляторах, поддерживающих автоматическую векторизацию (GCC, Intel, LLVM, MSVC 2012). В некоторых компиляторах семейства PGI реализованы операции копирования массивов (copyin) на графический ускоритель и выгрузка результатов с ускорителя в оперативную память (copy).

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

Распределение массивов в оперативной памяти

Практически все современные компьютеры имеют аппаратную поддержку виртуальной и кэш-памяти. Трансляция адреса виртуальной памяти в адрес физической может занять значительное время (10–100 тактов), поэтому, чтобы каждый раз не высчитывать физические адреса к одним и тем же виртуальным страницам, некоторые современные процессоры, поддерживающие страничную организацию памяти, включают в себя отдельный кэш (буфер ассоциативной трансляции TLB). Если данные, к которым происходит обращение, находятся в разных виртуальных страницах, то это приводит к большому количеству промахов к TLB-кэшу и, как следствие, простаиванию процессора. Кэш данных предназначен для уменьшения времени обработки запросов к часто используемым данным. Перед тем как данные попадают в процессор, они сохраняются в кэше. Таким образом, повторное обращение к ним не требует участия оперативной памяти.

Считывание данных из оперативной памяти в кэш происходит линейками длинной 32 или 64 байта, что, как правило, превышает длину используемых в программе данных, поэтому вместе с каждым считываемым куском данных в кэш-память попадают и соседние данные. Таким образом, для уменьшения обращений к памяти желательно, чтобы данные, которые используются соседними по времени исполнения операциями, размещались в оперативной памяти по соседству. Одним из способов увеличения производительности является выбор правильного метода хранения данных, но матрицы (массивы) в оперативной памяти распределяются компилятором, как и 50 лет назад, по столбцам (Фортран) либо по строкам (Си, Паскаль), независимо от исполняемого кода, что не всегда приводит к эффективному использованию кэш-памяти. В некоторых случаях логично использовать размещение массивов по блокам, которое в некоторых блочных алгоритмах может дать ускорение до 40%. Следует подчеркнуть, что блочное размещение массивов уместно только для блочных алгоритмов. Хранение матриц по блокам дает преимущество при реализации численных методов линейной алгебры и математической физики, в задачах кодирования и обработки сигналов.

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

Размещение в распределенной памяти

Автоматическое распараллеливание программ выполняется современными распараллеливающими компиляторами в основном для вычислительных систем с общей памятью (векторные, VLIW, многоядерные, SMP), однако для систем с распределенной памятью задача автоматического распараллеливания существенно сложнее — помимо автоматического определения параллельно выполняемых операций следует автоматически разместить данные в распределенной памяти так, чтобы минимизировать межпроцессорные пересылки.

Существуют различные описания порядка размещения данных в распределенной памяти. Как правило, эти описания реализуются в специальных командах параллельных языков программирования, а не при автоматическом распределении данных, которое реализовать технически сложно. Блочно-аффинные размещения реализованы, например, в экспериментальном распараллеливателе ДВОР, однако для описания размещения массивов в иерархической распределенной памяти требуется более общая модель. Кроме того, современные модели автоматического размещения данных в распределенной памяти не учитывают возможности коммуникационной сети.

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

Пересылки данных возникают не только между процессорами, но и между модулями локальной памяти процессорных элементов, расположенных на одном кристалле (типа Tile64 или Cell BE).

Автоматическое распараллеливание на вычислительные системы с распределенной памятью — еще один резерв распараллеливающих компиляторов.

Внутреннее представление

Некоторые компилирующие системы имеют несколько внутренних представлений разного уровня, но нам интересен уровень, на котором производятся оптимизирующие и распараллеливающие преобразования программ (более высокий уровень может использоваться для парсеров, а более низкий — для генераторов кода).

Оптимизация использования памяти не исключает традиционной оптимизации. Например, если за счет оптимизации последовательных вычислений на одном ядре можно получить ускорение, это означает, что можно использовать меньше процессорных ядер и, следовательно, при проектировании увеличить на кристалле процессора объем памяти. В этом смысле основа оптимизирующих преобразований программ — внутреннее представление компилирующей системы.

Большинство известных систем автоматической оптимизации и распараллеливания программ имеют внутреннее представление низкого уровня (GCC, LLVM, Intel С++/Fortran Compiler, Microsoft Visual C++), близкое к ассемблеру и ориентированное на генерацию команд x86. Низкий уровень внутреннего представления удобен для создания оптимизирующих компиляторов с широкого класса языков, даже далеких от Си и Фортрана, — таких как Java и Lisp. Однако эти внутренние представления неудобны для генерации кода для других архитектур, далеких от х86, — например, CUDA, Tile64, Мультиклет и др. Также представления ассемблерного уровня неудобны для генерации HDL-кода.

Низкоуровневая оптимизация ассемблерного кода возможна лишь тогда, когда имеется ассемблер для процессора, но высокоуровневая оптимизация может разрабатываться параллельно с созданием ассемблера процессора, что позволяет сократить сроки реализации распараллеливающих компиляторов. Ввиду этого, интересной представляется задача переноса классических низкоуровневых преобразований программ на высокоуровневое внутреннее представление. Высокоуровневое внутреннее представление имеется в распараллеливающих системах SUIF, ДВОР и проекте Rose Compiler.

Контроль корректности преобразований

Анализ информационных зависимостей в программе — это основа контроля корректности автоматических преобразований программ, однако, несмотря на обилие методов определения информационных зависимостей, эти зависимости во многих случаях определяются неточно или долго. Сложности с реализацией анализа информационных зависимостей имеются в семействе компиляторов компании Portland Group (PGI), где в виде директив (OpenAcc) реализована поддержка вычислений на графическом ускорителе. Данные директивы по своему использованию похожи на директивы OpenMP, в частности, если имеется цикл с независимыми итерациями, то его можно выполнить параллельно, прописав перед ним директиву acc parallel for. Однако анализатор зависимостей не всегда может определить, являются ли итерации цикла независимыми, поэтому разработчики PGI добавили в состав своих компиляторов возможность явно указывать, что конкретный цикл не имеет зависимостей между итерациями (директива acc loop independent).

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

Для хранения решетчатого графа не подходят такие традиционные структуры, как матрица смежности или список дуг графа. Это происходит из-за того, что множество вершин решетчатого графа совпадает с итерационным пространством программы. Затраты памяти на хранение такого количества вершин или дуг для реальных программ неприемлемы. Кроме того, время просмотра такого графа будет сопоставимо со временем исполнения программы, что также недопустимо. Впервые эффективный способ хранения и быстрый алгоритм построения решетчатого графа были предложены В. В. Воеводиным и Полем Фортье [2]. Граф можно описать набором функций, заданных на некоторых подмножествах пространства итераций. Такое описание решетчатого графа позволяет автоматически проводить анализ программ, выявлять распараллеливаемые циклы, расщеплять гнезда циклов, проводить оптимизацию по памяти и уточнять информационные зависимости в программе (см. рисунок).

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

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

Проблемы автоматического распараллеливания

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

Кроме уточнения информационных зависимостей и изменения порядка выполнения ассоциативных операций, диалог системы с пользователем может дать следующие преимущества по сравнению с автоматическим распараллеливанием:

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

Диалоговый режим компиляции имеется у распараллеливающей коммерческой системы Parawise , преобразующей код на языке Фортран в параллельный код с использованием библиотеки MPI или директив OpenMP. Параллельный код может генерироваться также с применением специальной библиотеки коммуникаций CAPLib, которая позволяет использовать библиотеку межпроцессорных коммуникаций SHMEM. Диалог используется для определения значений некоторых переменных в программе. На основе полученной информации компилятор принимает решение о возможности распараллеливания.

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

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

Новое поколение компиляторов

Ручное программирование для современных процессоров и ускорителей — долгий и дорогостоящий процесс, и сегодня требуется новое поколение компиляторов, основные черты которых таковы:

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

***

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

Литература

1. Mycrost A. Programming Language Design and Analysis motivated by Hardware Evolution (invited Presentation)
2. Feautrier Paul. Parametric Integer Programming. Laboratoire MASI, Institut Blaise Pascal, Universite de Versailles St-Quentin, 1988.

Борис Штейнберг (borsteinb@mail.ru) — профессор, Михаил Юрушкин (m.yurushkin@gmail.com) — аспирант Южного федерального университета (Ростов-на-Дону). Статья подготовлена на основе материалов доклада «Автоматическое отображение высокоуровневых программ на современные параллельные вычислительные системы со сложной архитектурой» (Б. Я. Штейнберг), представленного на III Московском суперкомпьютерном форуме (МСКФ-2012, грант Российского фонда фундаментальных исследований 12-07-06085-г).