Параллельные вычисления. Баканов В.М. - 78 стр.

                                   - 78 -


можно определенным способом распределить разным процессорам для па-
раллельного исполнения).
  Циклы, все итерации которых информационно независимы, принято назы-
вать ParDO циклами, из условия независимости следует, что возможно их
выполнять в любом порядке (в т.ч. параллельно). Этот вид параллелизма ва-
жен на практике благодаря частой встречаемости и простоты использования.
Нахождение циклов ParDO производится с помощью анализа информацион-
ной структуры программы (основанный на графовом представлении алго-
ритмов критерий определения цикла ParDO приведен, напр., в работе [1]).
Причем найденное по графу алгоритма свойство ParDO говорит лишь о
принципиальной возможности независимого выполнения итераций (для реа-
лизации возможности необходимо произвести определенные преобразования
цикла), полностью готовые к распараллеливанию циклы обозначаются как
TrueParDO.
  Одними из первых программных средств, обеспечивающих некоторую ав-
томатизацию распараллеливания, явились как раз системы выявления парал-
лелизма в циклах. Обычно используют два типа таких систем:

  • Специализированные компиляторы (компиляторы с традиционных язы-
   ков программирования – обычно Fortran), функциональность которых
   расширена средствами выявления параллелизма, эквивалентными преоб-
   разованиями цикла и созданием соответствующего исполняемого кода
   (обычно рассчитанного на векторную архитектуру вычислителя).
  • Препроцессоры, осуществляющие анализ и отбор циклов на векториза-
   цию или распараллеливание, выявленные блоки часто конвертируются в
   допускающее параллельную обработку расширение языка (напр., MPI, см.
   подраздел 4.1); в дальнейшем (преобразованный) исходный текст обраба-
   тывается стандартным компилятором.

  Многие такие системы допускают диалоговый режим работы – при этом
автоматически выявляются блоки-кандидаты на распараллеливание, а окон-
чательное решение о необходимости и способе преобразования в параллель-
ную форму принимает разработчик.
  Одним из известных и мощных препроцессоров-векторизаторов, каждый
член которого настроен на конкретную объектную машину, является KAP.
Система KAP использует для оптимизации коллапс циклов, разбиение цикла,
переупорядочение операторов и разрушение контуров зависимостей по дан-
ным, сегментацию цикла (преобразование исходного цикла в гнездо из не-
скольких циклов при соблюдении условия непереполнения кэш-памяти).
  Известными системами являются PFC (и основанная на ней инструмен-
тальная диалоговая система анализа программ PTOOL), ParaScope, BERT 77,