Автоматическое распараллеливание

Автоматическое распараллеливание , также автоматическое распараллеливание или автопараллелизация относятся к преобразованию последовательного кода в многопоточный и/или векторизованный код для одновременного использования нескольких процессоров в многопроцессорной машине с общей памятью ( SMP ). ^{[ 1 ]} Полностью автоматическое распараллеливание последовательных программ является сложной задачей, поскольку требует сложного анализа программы , и лучший подход может зависеть от значений параметров, которые неизвестны во время компиляции. ^{[ 2 ]}

Структурами управления программированием, которым автопараллелизация уделяет наибольшее внимание, являются циклы , поскольку, как правило, большая часть времени выполнения программы происходит внутри той или иной формы цикла. Существует два основных подхода к распараллеливанию циклов: конвейерная многопоточность и циклическая многопоточность. ^{[ 3 ]} Например, рассмотрим цикл, который на каждой итерации выполняет сотню операций и выполняется тысячу итераций. Это можно представить как сетку из 100 столбцов и 1000 строк, всего 100 000 операций. Циклическая многопоточность присваивает каждую строку отдельному потоку. Конвейерная многопоточность назначает каждый столбец отдельному потоку.

Метод автоматического распараллеливания

Разобрать

Это первый этап, на котором сканер считывает входные исходные файлы, чтобы идентифицировать все статические и внешние варианты использования. Каждая строка в файле будет проверена на соответствие заранее определенным шаблонам для разделения на токены . Эти токены будут сохранены в файле, который позже будет использоваться грамматический движок. Грамматический движок будет проверять шаблоны токенов, соответствующие заранее определенным правилам, для идентификации переменных, циклов, управления операторы, функции и т. д. в коде.

Анализировать

Анализатор . используется для определения участков кода, которые могут выполняться одновременно Анализатор использует статическую информацию, предоставляемую сканером-парсером. Анализатор сначала найдет все полностью независимые функции и отметит их как отдельные задачи. Затем анализатор определяет, какие задачи имеют зависимости.

Расписание

Планировщик . перечислит все задачи и их зависимости друг от друга с точки зрения времени выполнения и начала Планировщик составит оптимальное расписание с точки зрения количества используемых процессоров или общего времени выполнения приложения.

Генерация кода

Планировщик . сгенерирует список всех задач и подробную информацию о ядрах, на которых они будут выполняться, а также время, в течение которого они будут выполняться Генератор кода будет вставлять в код специальные конструкции, которые будут считываться планировщиком во время выполнения. Эти конструкции будут указывать планировщику, на каком ядре будет выполняться конкретная задача, а также время начала и окончания.

Циклическая многопоточность

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

Анализ распараллеливания компилятора

Компилятор обычно проводит два прохода анализа перед фактическим распараллеливанием , чтобы определить следующее:

Безопасно ли распараллеливать цикл? Ответ на этот вопрос требует точного анализа зависимостей и анализа псевдонимов.
Стоит ли его распараллеливать? Этот ответ требует достоверной оценки (моделирования) рабочей нагрузки программы и мощности параллельной системы.

Первый проход компилятора выполняет анализ зависимости данных цикла, чтобы определить, может ли каждая итерация цикла выполняться независимо от других. Иногда с зависимостью от данных можно справиться, но это может повлечь за собой дополнительные накладные расходы в виде передачи сообщений , синхронизации разделяемой памяти или какого-либо другого метода взаимодействия процессора.

Второй проход пытается оправдать усилия по распараллеливанию путем сравнения теоретического времени выполнения кода после распараллеливания со временем последовательного выполнения кода. Как ни странно, код не всегда выигрывает от параллельного выполнения. Дополнительные накладные расходы, которые могут быть связаны с использованием нескольких процессоров, могут снизить потенциальное ускорение распараллеленного кода.

Пример

Цикл называется DOALL, если все его итерации в любом вызове могут выполняться одновременно.

Приведенный ниже код Фортрана — DOALL, и его можно автоматически распараллелить компилятором, поскольку каждая итерация не зависит от других, а конечный результат массива z будет правильным независимо от порядка выполнения других итераций.

   do i = 1, n
     z(i) = x(i) + y(i)
   enddo

Есть много приятных параллельных задач, в которых есть такие циклы DOALL. Например, при рендеринге фильма с трассировкой лучей каждый кадр фильма может визуализироваться независимо, и каждый пиксель одного кадра может визуализироваться независимо.

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

   do i = 2, n
     z(i) = z(i - 1)*2
   enddo

Это не означает, что код нельзя распараллелить. Действительно, это эквивалентно циклу DOALL.

   do i = 2, n
     z(i) = z(1)*2**(i - 1)
   enddo

Однако современные распараллеливающие компиляторы обычно не способны автоматически выявить этот параллелизм, и сомнительно, выиграет ли этот код от распараллеливания вообще.

Конвейерная многопоточность

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

Существует множество приятных параллельных задач, которые имеют такие относительно независимые блоки кода, в частности системы, использующие каналы и фильтры .

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

Считайте кадр необработанных данных пикселей с датчика изображения,
MPEG Выполните компенсацию движения для необработанных данных,
Энтропия сжимает векторы движения и другие данные,
Разбейте сжатые данные на пакеты,
Добавьте соответствующее исправление ошибок и выполните БПФ для преобразования пакетов данных в сигналы COFDM и
Отправьте сигналы COFDM на телевизионную антенну.

Конвейерный многопоточный распараллеливающий компилятор может назначить каждую из этих шести операций другому процессору, возможно, расположенному в систолическом массиве , вставляя соответствующий код для пересылки вывода одного процессора на следующий процессор.

Недавние исследования посвящены использованию мощности графического процессора. ^{[ 4 ]} и многоядерные системы ^{[ 5 ]} для вычисления таких независимых блоков кода (или просто независимых итераций цикла) во время выполнения. Доступ к памяти (прямой или косвенный) можно просто пометить для разных итераций цикла и сравнить для обнаружения зависимостей. Используя эту информацию, итерации группируются по уровням таким образом, что итерации, принадлежащие одному уровню, независимы друг от друга и могут выполняться параллельно.

Трудности

Автоматическое распараллеливание компиляторами или инструментами очень затруднено по следующим причинам: ^{[ 6 ]}

анализ зависимостей затруднен для кода, который использует косвенную адресацию, указатели, рекурсию или косвенные вызовы функций, поскольку такие зависимости трудно обнаружить во время компиляции;
циклы имеют неизвестное количество итераций;
доступ к глобальным ресурсам сложно координировать с точки зрения распределения памяти, ввода-вывода и общих переменных;
нерегулярные алгоритмы , использующие косвенность, зависящую от ввода, мешают анализу и оптимизации во время компиляции. ^{[ 7 ]}

Обходной путь

Из-за трудностей, присущих полностью автоматическому распараллеливанию, существует несколько более простых подходов для получения параллельной программы более высокого качества. Один из них — позволить программистам добавлять «подсказки» в свои программы для управления распараллеливанием компилятора, например HPF для систем с распределенной памятью и OpenMP или OpenHMPP для систем с общей памятью . Другой подход заключается в создании интерактивной системы между программистами и инструментами/компиляторами распараллеливания. Яркими примерами являются Vector Fabrics Pareon , SUIF Explorer (компилятор промежуточного формата Стэнфордского университета), компилятор Polaris и ParaWise (формально CAPTools). с аппаратной поддержкой Наконец, еще один подход — спекулятивная многопоточность .

Распараллеливание компиляторов и инструментов

Большинство составителей исследований для автоматического распараллеливания рассматривают на Фортране . программы ^{[ нужна ссылка ]} потому что Фортран дает более строгие гарантии в отношении псевдонимов, чем такие языки, как C . Типичные примеры:

См. также

Оптимизация гнезда циклов
Контракт на распараллеливание
Модель многогранника, также известная как модель многогранника.
Масштабируемый параллелизм
БМДФМ
Векторизация
ПоследовательностьL

Ссылки

^ Йехезкаэль, Рафаэль (2000). «Эксперименты по отделению вычислительного алгоритма от распространения и коммуникации программ» (PDF) . Прикладные параллельные вычисления. Новые парадигмы высокопроизводительных вычислений в промышленности и научных кругах . Конспекты лекций по информатике . Том. 1947. Спрингер Верлаг . стр. 268–278. дои : 10.1007/3-540-70734-4_32 . ISBN 978-3-540-41729-3 .
^ Фокс, Джеффри; Уильямс, Рой; Мессина, Пол (1994). Параллельные вычисления работают! . Морган Кауфманн . стр. 575, 593. ISBN. 978-1-55860-253-3 .
^ Кампанони, Симоне; Джонс, Тимоти; Холлоуэй, Гленн; Вэй, Гу Ён; Брукс, Дэвид (2012). Проект HELIX: обзор и направления .
^ Анантпур, Дж.; Говиндараджан, Р. «Вычисление зависимостей во время выполнения и выполнение циклов в гетерогенных системах» (PDF) . Архивировано из оригинала (PDF) 6 октября 2015 года . Проверено 5 октября 2015 г.
^ Чжуан, X.; Эйхенбергер, А.Е.; Луо, Ю.; О'Брайен, Кэтрин Кевин, Использование параллелизма с планированием с учетом зависимостей
^ «Автоматический параллелизм и зависимость данных» . Архивировано из оригинала 14 июля 2014 года.
^ Рюнгер, Гудула (2006). «Модели параллельного программирования для нерегулярных алгоритмов». Параллельные алгоритмы и кластерные вычисления . Конспекты лекций по вычислительной технике и технике. 52 : 3–23. дои : 10.1007/3-540-33541-2_1 . ISBN 978-3-540-33539-9 .

Дальнейшее чтение

Паунтейн, Дик (декабрь 1989 г.). «Настройка параллельных программ, часть 1: Occam Transpiler, находящийся в стадии разработки, упростит написание программного обеспечения для параллельной обработки» . БАЙТ . Том. 14, нет. 13. McGraw-Hill, Inc., стр. 349–352. ISSN 0360-5280 . ковчег:/13960/t34188734 . Проверено 6 января 2022 г. (Примечание. Использует термин «транспилятор Occam» как синоним компилятора «источник-источник», работающего в качестве препроцессора , который принимает обычную программу occam в качестве входных данных и получает новый исходный код occam в качестве выходных данных с присвоением ссылок на каналы и т. д.). . добавил к нему, тем самым настроив его для параллельной обработки для максимально эффективной работы в сети транспьютеров .)

[Yehezkael_2000-1] Йехезкаэль, Рафаэль (2000). «Эксперименты по отделению вычислительного алгоритма от распространения и коммуникации программ» (PDF) . Прикладные параллельные вычисления. Новые парадигмы высокопроизводительных вычислений в промышленности и научных кругах . Конспекты лекций по информатике . Том. 1947. Спрингер Верлаг . стр. 268–278. дои : 10.1007/3-540-70734-4_32 . ISBN 978-3-540-41729-3 .

[Fox-Williams_Messina_1994-2] Фокс, Джеффри; Уильямс, Рой; Мессина, Пол (1994). Параллельные вычисления работают! . Морган Кауфманн . стр. 575, 593. ISBN. 978-1-55860-253-3 .

[Campanoni-Jones-Holloway-Wei-Brooks_2012-3] Кампанони, Симоне; Джонс, Тимоти; Холлоуэй, Гленн; Вэй, Гу Ён; Брукс, Дэвид (2012). Проект HELIX: обзор и направления .

[Anantpur-Govindarajan_2013-4] Анантпур, Дж.; Говиндараджан, Р. «Вычисление зависимостей во время выполнения и выполнение циклов в гетерогенных системах» (PDF) . Архивировано из оригинала (PDF) 6 октября 2015 года . Проверено 5 октября 2015 г.

[Zhuang-Eichenberger-Luo-OBrien-5] Чжуан, X.; Эйхенбергер, А.Е.; Луо, Ю.; О'Брайен, Кэтрин Кевин, Использование параллелизма с планированием с учетом зависимостей

[Blitzprog-6] «Автоматический параллелизм и зависимость данных» . Архивировано из оригинала 14 июля 2014 года.

[Rünger_2006-7] Рюнгер, Гудула (2006). «Модели параллельного программирования для нерегулярных алгоритмов». Параллельные алгоритмы и кластерные вычисления . Конспекты лекций по вычислительной технике и технике. 52 : 3–23. дои : 10.1007/3-540-33541-2_1 . ISBN 978-3-540-33539-9 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

v т и Оптимизация компилятора
Базовый блок	Оптимизация глазка Нумерация локальных значений
Петля	Автоматическое распараллеливание Автоматическая векторизация Индукционная переменная Петля слияния Движение кода, инвариантное к циклу Инверсия цикла Перестановка петель Оптимизация гнезда циклов Разделение цикла Развертывание цикла Выключение петли Конвейерная обработка программного обеспечения Снижение прочности
Поток данных анализ	Доступное выражение Удаление общего подвыражения Постоянное складывание мертвого магазина Устранение Распознавание и устранение индукционных переменных Анализ переменных в реальном времени Использовать-определить цепочку
SSA на основе	Глобальная нумерация значений Разреженное условное постоянное распространение
Генерация кода	Планирование инструкций Выбор инструкции Распределение регистров Рематериализация
Функциональный	Вырубка лесов Устранение хвостового вызова
Глобальный	Межпроцедурная оптимизация
Другой	Устранение проверки границ Выполнение функции во время компиляции Устранение мертвого кода Шаблоны выражений Встроенное расширение Перейти к потоку Частичная оценка Оптимизация на основе профиля
Статический анализ	Анализ псевдонимов Анализ доступа к массиву Анализ потока управления Анализ потока данных Анализ зависимостей Анализ побега Анализ указателя Анализ формы Анализ диапазона значений