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

реализованными в T-системе [4].

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

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

      Перейдем к выбору платформы для подсистемы автоматизации распараллеливания, которая, как уже было решено выше, должна быть реализована в виде некоего пакета языковых расширений для стандартного компилятора. Такой компилятор, как следует из вышеизложенного, как минимум, должен допускать подобные высокоуровневые расширения и иметь стандартные средства распараллеливания, использующие OpenMP и OpenCL, а также позволять генерировать выходной код, выходящий за рамки классического C/C++, чтобы обеспечить возможность вставки директив распараллеливания Cilk++.

      Далее отметим, что задача автоматического распараллеливания подразумевает решение нескольких типовых подзадач:

      а) лексико-синтаксический разбор (парсинг) исходной программы;

      б) распознавание реализованного в программе алгоритма с определением потенциально параллельных фрагментов;

      в) отбор фрагментов, распараллеливание которых дает существенный выигрыш по времени;

      г) реструктуризация алгоритма (вставка директив распараллеливания);

      д) формирование распараллеленного выходного кода.

      Задача лексико-синтаксического разбора, в простейшем случае, может выполняться специальным автоматом, построенным в соответствии с формальной грамматикой входного языка программирования. Здесь обычно применяются программные средства по типу bison/flex (yacc/lex), в значительной степени облегчающие построение указанного автомата.

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