ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ —
УДК 004.92+004.94
АВТО-РАСПАРАЛЛЕЛИВАТЕЛЬ ПРОГРАММ, РЕАЛИЗОВАННЫЙ НА ОСНОВЕ КОМПОНЕНТНОЙ ТЕХНОЛОГИИ ПОСТРОЕНИЯ ОПТИМИЗИРУЮЩИХ КОМПИЛЯТОРОВ
© 2009 г. А. Ю. Дроздов, С. В. Новиков
ИТМиВТ им. СЛ. Лебедева РАН 119991 Москва, Ленинский просп., 51 E-mail: ajudrozdov@ipmce.ru, svnovikov@ipmce.ru Поступила в редакцию 10.06.2008 г.
В данной работе описывается автоматический распараллеливатель программ, созданный на базе компонентного подхода к построению оптимизирующих компиляторов и встроенный в технологическую цепочку gcc. В работе рассмотриваются детали использования аналитических и оптимизационных компонент для построения авто-распараллеливателя и алгоритм распараллеливания с использованием библиотеки OpenMP. В заключении приведены результаты работы авто-распараллеливателя по производительности на подмножестве задач из пакетов Spec2006 и NAS parallel benchmarks.
1. ВВЕДЕНИЕ
Ключевую роль в эффективном использовании архитектур с явной параллельностью (многоядерных, кластерных и т.д.) играют системы программирования, предназначенные для создания параллельных программ. Такие системы включают в себя как языковые средства задания параллельности в программе (системы явного параллельного программирования, например, стандарт OpenMP [1], платформу RapidMind [2] и т.д.), так и автоматические средства поиска параллельных вычислений (компиляторы фирм Intel [3], Portland Group [4] и т.д.) и последующего представления их с использованием существующих библиотек поддержки параллельности (MPI [5], libgomp [6] и т.д).
Явное параллельное программирование и автоматическое программирование, взятые независимо друг от друга, обладают серьезными недостатками. Компромиссное решение, описанное в работе [7], состоит в создании системы неявного параллельного программирования. С одной стороны, программист на традиционных языках программирования (С, С++, Fortran) создает
программу с параллельными вычислениями. Автоматическими средствами эти параллельные вычисления должны быть распознаны. В случае проблем с анализом программист может добавить подсказки в программу, разрешив какой-либо конфликт, мешающий определению параллельности. Затем найденные параллельные вычисления автоматически представляются в параллельных терминах конкретной архитектуры. По сути, это некоторая интерактивная среда разработки параллельных программ, в которой сбалансированы усилия человека и автоматических средств. В такой системе основную работу по анализу, оптимизациям и инструментированию параллельного кода выполняет автомат, а человек лишь точечно прагмами разрешает конфликты, с которыми статический анализатор не справляется. Невозможность автоматически разрешить конфликт возникает по двум причинам: из-за несовершенства статического анализа и в силу динамической природы конфликтов. Несмотря на то, что первый фактор со временем будет нивелироваться, разрешение динамических конфликтов потребует подсказок.
Ключевую роль в автоматическом распараллеливании играет статический анализ программ. От точности анализа сильно зависит качество распараллеливания. Основным результатом применения алгоритмов статического анализа являются распознанные параллельные вычисления в программе. Именно параллельные вычисления можно затем автоматически инструментировать командами или вызовами системных библиотек, позволяющими запускать параллельные вычисления на многопоточных системах. Современные алгоритмы статического анализа далеки от совершенства. Чаще всего есть возможность эти алгоритмы усовершенствовать и получать более точные результаты. Для решения некоторых задач иногда приходится разрабатывать новые подходы к проведению анализа. В данной статье описаны некоторые усовершенствования классических алгоритмов анализа, которые улучшили качество автоматического распараллеливания.
В предыдущей работе Дроздова А.Ю. [8] был предложен компонентный подход к построению оптимизирующих компиляторов [9] и была разработана технология портирования компонент в контекст любой существующей технологии оптимизирующей компиляции.
В данной статье описывается автоматический распараллеливатель программ, созданный на базе компонентного подхода, описанного в работе [8], и встроенный в технологическую цепочку gcc [6]. В разделе 2 кратко освещено текущее состояние в области алгоритмов статического анализа и оптимизаций. Раздел 3 посвящен деталям реализации автоматического распарал-леливателя, в нем описан алгоритм распараллеливания. Кроме этого, описаны подходы, улучшающие классические алгоритмы статического анализа программ. Экспериментальные результаты представлены в разделе 4.
2. ОБЗОР КЛАССИЧЕСКИХ СРЕДСТВ АНАЛИЗА И ОПТИМИЗАЦИЙ
2.1. Статический анализ программ
Основная задача, которую решают методы статического анализа программ в оптимизирующих компиляторах - это определение отношения зависимости по данным и управлению между
различными группами вычислений программы [8-15]. Эффективное (точное) вычисление этих отношений имеет решающее значение при проведении оптимизирующих преобразований программы.
Поэтому в современных оптимизирующих компиляторах важнейшую роль играют аналитические фазы компиляции. На фазах анализа определяются избыточные вычисления, зависимости между операциями доступа в память, зависимости по управлению, достижимость по управлению и т. п. В рамках этих фаз анализируется поток управления в программе, поток данных, решаются системы линейных диофан-товых уравнений и неравенств с целью определения зависимостей в цикловых регионах программы.
После того, как компилятор вычислил результаты анализа потоков данных и управления, он может использовать их для получения ответов на вопросы о зависимостях между любыми парами вычислений программы [9, 12, 16-18]. Под вычислениями здесь понимаются такие элементы факторизаций любого уровня, как операции, линейные участки, циклы, процедуры. Любой запрос на отношение зависимости имеет два измерения сложности, которые определяют структуру построения ответа. Одно из них рассматривает сложность вычислений, для которых определяется отношение зависимости, с точки зрения факторизации по управлению, а второе определяет уровень сложности объектов программы, которые участвуют в анализируемых вычислениях.
Если объекты элементарные, то для ответа достаточно результатов внутрипроцедурного потокового анализа управления и данных. По мере того, как увеличивается сложность объектов, увеличивается и сложность алгоритмов анализа, результаты которых необходимы для получения наименее консервативного ответа на вопрос о зависимости. Для объектов - массивов часто бывает необходимо применить анализ зависимостей в гнездах циклов, а для объектов, на которые брался указатель, будут востребованы результаты межпроцедурного анализа потока данных.
Ниже в этом разделе будет дано определение отношения зависимости по данным и управлению и рассмотрены различные методы статического анализа, позволяющие эффективно вычис-
лять это отношение. Особенно важное значение методы статического анализа программ имеют при построении анализатора и автоматического распараллеливателя, для обнаружения независимых участков программы (при построении анализатора) и их дальнейшего оформления в виде параллельных блоков (при построении распа-раллеливателя).
2.1.1. Основные понятия и определения
Обычно принято различать 2 типа зависимостей: зависимости по данным и зависимости по управлению [9-15]. Зависимости по управлению определяются управляющей структурой программы, которая, в свою очередь, определяется операциями передачи управления в программе. Как правило, управляющая структура представляется в виде графа управления, дуги которого отражают возможную передачу управления непосредственно от одной операции к другой. Зависимости по данным определяются информационной структурой программы и отражают свойство операций обращаться к одним и тем же данным в процессе исполнения программы, при наличии пути в графе управления, реализующего возможность их одновременного исполнения на этом пути.
Анализ зависимостей по управлению подразумевает исследование потока управления программы, а анализ зависимостей по данным, помимо анализа потока управления, требует анализа потока данных программы. И хотя в реальности эти виды анализа сильно взаимосвязаны, потому что поток управления зависит от потока предикатных данных, а поток данных зависит от потока управления, их принято рассматривать отдельно друг от друга.
2.1.2. Анализ потока управления
Внутрипроцедурный анализ потока управления
На основе анализа потока управления строятся различные факторизации программы. Факторизации, как правило, преследуют одну из двух целей: либо выделение интересных с точки зрения оптимизации регионов программы, либо выделение крупных блоков программы, независимых друг от друга по управлению.
Рис. 1. Управляющий граф с SESE регионами.
Рис. 2. Дерево структуры программы.
К первым относится такая известная факторизация, как дерево циклов [9, 15], ко вторым можно отнести такие факторизации, как дерево структуры программы (Program Structure Tree, PST) [19] и иерархический граф заданий (Hierarchical Task Graph) [20].
Некоторые из факторизаций (например, Program Structure Tree) оказываются также крайне полезными при проведении анализа потока данных.
На рис. 1 показаны участки управляющего графа с одним входом и одним выходом (Single Entry Single Exit (SESE)). Каждый из них представлен узлом в дереве PST, которое показано на рис. 2.
В контексте автоматического распараллеливателя программ PST может эффективно использоваться для определения так называемого сек-
ционного параллелизма, то есть параллелизма между последовательностями операций, независимых друг от друга по управлению. Например, секции В, С, Б, Е могут исполняться независимо друг от друга, если между вычислениями в этих секциях нет зависимостей по данным.
Межпроцедурный анализ потока управления
Изначально все понятия, связанные с анализом потока управления, вводились и развивались в контексте анализа управляющего графа процедуры, но по мере того,
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.