Автоматическое распараллеливание
 | Эта статья нуждается в дополнительных ссылок для проверки . ( февраль 2008 г. ) |
Автоматическое распараллеливание , также автоматическое распараллеливание или автопараллелизация относятся к преобразованию последовательного кода в многопоточный и/или векторизованный код для одновременного использования нескольких процессоров в многопроцессорной машине с общей памятью ( SMP ). [1] Полностью автоматическое распараллеливание последовательных программ представляет собой сложную задачу, поскольку требует сложного анализа программы , и лучший подход может зависеть от значений параметров, которые неизвестны во время компиляции. [2]
Структурами управления программированием, которым автопараллелизация уделяет наибольшее внимание, являются циклы , поскольку, как правило, большая часть времени выполнения программы происходит внутри той или иной формы цикла. Существует два основных подхода к распараллеливанию циклов: конвейерная многопоточность и циклическая многопоточность. [3] Например, рассмотрим цикл, который на каждой итерации выполняет сотню операций и выполняется тысячу итераций. Это можно представить как сетку из 100 столбцов и 1000 строк, всего 100 000 операций. Циклическая многопоточность присваивает каждую строку отдельному потоку. Конвейерная многопоточность назначает каждый столбец отдельному потоку.
автоматического Техника распараллеливания
Разобрать [ править ]
Это первый этап, на котором сканер считывает входные исходные файлы, чтобы идентифицировать все статические и внешние варианты использования. Каждая строка в файле будет проверена на соответствие заранее определенным шаблонам для разделения на токены . Эти токены будут сохранены в файле, который позже будет использоваться грамматический движок. Грамматический движок будет проверять шаблоны токенов, соответствующие заранее определенным правилам, для идентификации переменных, циклов, управления операторы, функции и т. д. в коде.
Анализировать [ править ]
Анализатор . используется для определения участков кода, которые могут выполняться одновременно Анализатор использует статическую информацию, предоставляемую сканером-парсером. Анализатор сначала найдет все полностью независимые функции и отметит их как отдельные задачи. Затем анализатор определяет, какие задачи имеют зависимости.
Расписание [ править ]
Планировщик . перечислит все задачи и их зависимости друг от друга с точки зрения времени выполнения и начала Планировщик составит оптимальное расписание с точки зрения количества используемых процессоров или общего времени выполнения приложения.
Генерация кода [ править ]
Планировщик . сгенерирует список всех задач и подробную информацию о ядрах, на которых они будут выполняться, а также время, в течение которого они будут выполняться Генератор кода будет вставлять в код специальные конструкции, которые будут считываться планировщиком во время выполнения. Эти конструкции будут указывать планировщику, на каком ядре будет выполняться конкретная задача, а также время начала и окончания.
Циклическая многопоточность [ править ]
Циклический многопоточный распараллеливающий компилятор пытается разделить цикл так, чтобы каждая итерация могла выполняться на отдельном процессоре одновременно.
Анализ распараллеливания компилятора [ править ]
Компилятор обычно проводит два прохода анализа перед фактическим распараллеливанием , чтобы определить следующее:
- Безопасно ли распараллеливать цикл? Ответ на этот вопрос требует точного анализа зависимостей и анализа псевдонимов.
- Стоит ли его распараллеливать? Этот ответ требует достоверной оценки (моделирования) рабочей нагрузки программы и мощности параллельной системы.
Первый проход компилятора выполняет анализ зависимости данных цикла, чтобы определить, может ли каждая итерация цикла выполняться независимо от других. С зависимостью от данных иногда можно справиться, но это может повлечь за собой дополнительные накладные расходы в виде передачи сообщений , синхронизации разделяемой памяти или какого-либо другого метода взаимодействия процессора.
Второй проход пытается оправдать усилия по распараллеливанию путем сравнения теоретического времени выполнения кода после распараллеливания со временем последовательного выполнения кода. Как ни странно, код не всегда выигрывает от параллельного выполнения. Дополнительные накладные расходы, которые могут быть связаны с использованием нескольких процессоров, могут снизить потенциальное ускорение распараллеленного кода.
Пример [ править ]
Цикл называется DOALL, если все его итерации в любом вызове могут выполняться одновременно.
Приведенный ниже код Фортрана — DOALL, и его можно автоматически распараллелить компилятором, поскольку каждая итерация не зависит от других, а конечный результат массива z будет правильным независимо от порядка выполнения других итераций.
делаю я знак равно 1 , п
z ( я ) знак равно Икс ( я ) + y ( я )
enddo
Есть много приятных параллельных задач, в которых есть такие циклы DOALL. Например, при рендеринге фильма с трассировкой лучей каждый кадр фильма может визуализироваться независимо, и каждый пиксель одного кадра может визуализироваться независимо.
С другой стороны, следующий код не может быть распараллелен автоматически, поскольку значение z(i) зависит от результата предыдущей итерации, z(i - 1).
do я знак равно 2 , n
z ( я ) знак равно z ( я - 1 ) * 2
enddo
Это не означает, что код нельзя распараллелить. Действительно, это эквивалентно циклу DOALL.
делаю я знак равно 2 , п
z ( я ) знак равно z ( 1 ) * 2 ** ( я - 1 )
конецдо
Однако современные распараллеливающие компиляторы обычно не способны автоматически выявить этот параллелизм, и сомнительно, выиграет ли этот код от распараллеливания вообще.
Конвейерная многопоточность [ править ]
Конвейерный многопоточный распараллеливающий компилятор пытается разбить последовательность операций внутри цикла на серию блоков кода так, чтобы каждый блок кода мог выполняться на отдельных процессорах одновременно.
Существует множество приятных параллельных задач, которые имеют такие относительно независимые блоки кода, в частности системы, использующие каналы и фильтры .
Например, при производстве прямого телевещания следующие задачи необходимо выполнять много раз в секунду:
- Считайте кадр необработанных данных пикселей с датчика изображения,
- MPEG Выполните компенсацию движения для необработанных данных,
- Энтропия сжимает векторы движения и другие данные,
- Разбейте сжатые данные на пакеты,
- Добавьте соответствующее исправление ошибок и выполните БПФ для преобразования пакетов данных в сигналы COFDM и
- Отправьте сигналы COFDM на телевизионную антенну.
Конвейерный многопоточный распараллеливающий компилятор может назначить каждую из этих шести операций другому процессору, возможно, расположенному в систолическом массиве , вставляя соответствующий код для пересылки вывода одного процессора на следующий процессор.
Недавние исследования посвящены использованию мощности графического процессора. [4] и многоядерные системы [5] для вычисления таких независимых блоков кода (или просто независимых итераций цикла) во время выполнения. Доступ к памяти (прямой или косвенный) можно просто пометить для разных итераций цикла и сравнить для обнаружения зависимостей. Используя эту информацию, итерации группируются по уровням таким образом, что итерации, принадлежащие одному и тому же уровню, независимы друг от друга и могут выполняться параллельно.
Трудности [ править ]
Автоматическое распараллеливание компиляторами или инструментами очень затруднено по следующим причинам: [6]
- анализ зависимостей затруднен для кода, который использует косвенную адресацию, указатели, рекурсию или косвенные вызовы функций, поскольку такие зависимости трудно обнаружить во время компиляции;
- циклы имеют неизвестное количество итераций;
- доступ к глобальным ресурсам сложно координировать с точки зрения распределения памяти, ввода-вывода и общих переменных;
- нерегулярные алгоритмы , использующие косвенность, зависящую от ввода, мешают анализу и оптимизации во время компиляции. [7]
Обходной путь [ править ]
Из-за трудностей, присущих полностью автоматическому распараллеливанию, существует несколько более простых подходов для получения параллельной программы более высокого качества. Один из них — позволить программистам добавлять «подсказки» в свои программы для управления распараллеливанием компилятора, например HPF для систем с распределенной памятью и OpenMP или OpenHMPP для систем с общей памятью . Другой подход заключается в создании интерактивной системы между программистами и инструментами/компиляторами распараллеливания. Яркими примерами являются Vector Fabrics Pareon , SUIF Explorer (компилятор промежуточного формата Стэнфордского университета), компилятор Polaris и ParaWise (формально CAPTools). Наконец, еще один подход — спекулятивная многопоточность с аппаратной поддержкой .
Распараллеливание компиляторов и инструментов [ править ]
Большинство составителей исследований для автоматического распараллеливания рассматривают на Фортране . программы [ нужна цитата ] потому что Фортран дает более строгие гарантии в отношении псевдонимов , чем такие языки, как C . Типичные примеры:
- Компилятор парадигмы
- Компилятор Полярис
- Рисовый компилятор Fortran D
- SUIF компиляция
- Венский компилятор Фортрана
См. также [ править ]
- Оптимизация гнезда циклов
- Контракт на распараллеливание
- Модель многогранника, также известная как модель многогранника.
- Масштабируемый параллелизм
- БМДФМ
- Векторизация
- Последовательность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 в качестве выходных данных с присвоением ссылок на каналы и т. д.). . добавил к нему, тем самым настроив его на параллельную обработку для максимально эффективной работы в сети транспьютеров .)