Владимир Пекунов - Технологии автоматического дедуктивного распараллеливания в языке Planning C

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]).

Как уже упоминалось выше, большинство известных систем автоматического распараллеливания использует OpenMP и/или MPI, что вероятно, во многом объясняется их широкой поддержкой или непосредственно в компиляторах (OpenMP) или в специализированных библиотеках (MPI). Это существенный аргумент и мы, несомненно, в данной работе рассмотрим возможность применения некоторых, базирующихся на применении OpenMP технологий автоматического распараллеливания, подразумевающих, например, применение сверхоптимистичных вычислений [16], использующих предицирующие каналы, построенные на базе OpenMP. Данная задача является новой.

Отметим, что существует еще один, достаточно интересный вариант средств распараллеливания – расширение Cilk++ 2 2 См., например, https://www.cilkplus.org [32], для которого известны как независимые реализации, так и реализации в ряде версий GNU C++ Compiler. Его серьезным достоинством является предельная простота базовых средств, включающих всего три ключевых слова: cilk_spawn(запуск параллельного процесса), cilk_sync(ожидание завершения порожденных процессов), cilk_for(распараллеливание циклов). Такая простота, во многом, объясняется тем, что гранулой параллелизма по задачам является обычная C-функция, что в значительной степени перекликается с идеями, реализованными в T-системе [4].

Автору не удалось найти сведений о реализации систем автоматического распараллеливания с применением Cilk++, поэтому разработка средств такого распараллеливания представляет не только потенциальный практический, но и определенный теоретический интерес. При этом задача автоматического распараллеливания будет сведена к адекватной расстановке директив cilk_sync, cilk_spawnи cilk_for.

Далее, следует отметить, что в последние десятилетия в практике параллельных вычислений достаточно широко используются векторные расширители (обычные процессоры с векторными инструкциями или многоядерные видеокарты с потоковыми процессорами SIMT-архитектуры). В данной работе мы можем попытаться разработать, например, такие средства автоматического распараллеливания циклов для работы на векторных расширителях, которые (что является достаточно новой задачей) в значительной степени нивелируют (автоматически) фактор замедления исполнения (характерный для SIMT-режима), обусловленный наличием расходящихся трасс потоков различных итераций цикла. Как и в случае машин на обычных процессорах, чтобы добиться максимально возможной многоплатформенности, целесообразно опираться на некие стандартизованные средства распараллеливания, такие как OpenCL [39].