Читать книгу Технологии автоматического дедуктивного распараллеливания в языке Planning C - Владимир Викторович Фомин, Владимир Викторович, Владимир Викторович Таболин - Страница 4

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

Анализ кода обычно сводится к обнаружению параллелизма циклов (обычно это параллелизм по данным и, реже, по процессам) и параллелизма подзадач в линейном или ветвящемся коде. Решение данных задач [1, 4] подразумевает явное или неявное построение графа взаимосвязей отдельных высоко- или низкоуровневых команд программы с выявлением в нем параллельных ветвей и определением точек слияния (барьерной синхронизации) этих ветвей. Такой граф может быть построен с помощью, в простейшем случае, статического, а в более общем случае – динамического анализа программного кода. Следует заметить, что в наиболее сложных случаях (например, при наличии сложной рекурсии с ветвлением), когда полноценный динамический анализ затруднен, приходится применять уже не автоматическое, а полуавтоматическое распараллеливание, переходя в диалоговый режим с пользователем с целью выяснения, например, зависимости или независимости отдельных фрагментов программы. После обнаружения параллелизма применяются те или иные адекватные средства распараллеливания: векторные инструкции и/или порождение потоков (зависимых, с согласованием, например, с применением транзакционной памяти, или независимых).

По уровню анализа/переработки исходного кода программы можно выделить три градации:

1. В наиболее простом случае (преимущественно параллелизм по данным), распараллеливание может производиться непосредственно компилятором (при этом исходный код, с формальной точки зрения, практически не меняется), который, в частности, может применить векторные инструкции. К таким компиляторам относятся, например, GNU C/C++ Compiler и Intel C++ Compiler. Несколько условно можно отнести к этой градации плагин-компилятор VAST1, который работает с промежуточными представлениями компилируемой программы и может встраиваться в иные компиляторы, выполняя ряд распараллеливающих оптимизаций циклов и векторизаций.

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

2. В более сложных случаях выполняется полноценный анализ (специализированной системой) с последующей частичной переработкой кода исходной программы, в который вставляются те или иные директивы распараллеливания, соответствующие одному из стандартных интерфейсов распараллеливания (DVM [9], MPI, OpenMP [4, 27]). Это достаточно «быстрый» и «дружелюбный» по отношению к программисту (поскольку структура кода, в целом, не претерпевает существенных изменений и может быть легко проанализирована, например, в целях обучения) вариант. Кроме того, здесь:

а) не предъявляются повышенные требования к компилятору;

б) более широк диапазон выявляемых паттернов параллелизма (в частности, параллелизма по задачам);

в) возможна оперативная адаптация параллелизатора под конкретную ЭВМ с целью более правдоподобного анализа перспективности выделения параллелизма по задачам.

В качестве примеров можно назвать системы распараллеливания YUCCA, PLUTO [32] и AutoPar [37], использующие для распараллеливания директивы OpenMP, S2P [40], использующую OpenMP и pThreads, а также PIPS [29], в которой используются MPI и OpenMP.

3. В наиболее сложном случае возможна глубокая проработка исходного кода параллелизатором с достаточно активным диалогом с программистом, что, вероятно, позволяет в наибольшей степени выявить потенциально параллельные фрагменты и дать наиболее эффективный выходной код. Однако это, фактически, уже полуавтоматическое распараллеливание. Здесь можно назвать, например, системы ParaWise [23], Tournavitis [32] и САПФОР/ПАРФОР [3, 8].

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