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