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

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

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

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

Разобрать

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

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

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

График

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

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

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

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

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

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

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

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

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

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

Пример

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

   делать я = 1, п     z(я) = Икс(я) + у(я)   Enddo

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

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

   делать я = 2, п     z(я) = z(я - 1)*2   Enddo

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

   делать я = 2, п     z(я) = z(1)*2**(я - 1)   Enddo

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

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

Основная статья: конвейерная обработка программного обеспечения

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

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

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

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

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

Трудности

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

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

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

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

  • Разрешить программистам добавлять в свои программы "подсказки" для управления распараллеливанием компилятора, например HPF за распределенная память системы и OpenMP или же OpenHMPP за Общая память системы.
  • Создайте интерактивную систему между программистами и инструментами / компиляторами распараллеливания. Известные примеры: Векторные Ткани 'Пареон, СУИФ Explorer (компилятор промежуточного формата Стэнфордского университета), компилятор Polaris и ParaWise (формально CAPTools).
  • С аппаратной поддержкой спекулятивная многопоточность.

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

Смотрите также: Инструмент автоматического распараллеливания

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

  • Компилятор парадигмы
  • Компилятор Polaris
  • Компилятор Rice Fortran D
  • СУИФ компилятор
  • Компилятор Венского Фортрана

Рекомендации

  1. ^ "Иехезкаэль, Рафаэль (2000). «Эксперименты по отделению вычислительного алгоритма от распространения программ и коммуникации». Конспект лекций по информатике компании Springer Verlag. Конспект лекций по информатике. 1947: 268–278. Дои: [// doi.org/10.1007%2F3-540-70734-4_32 10.1007 / 3-540-70734-4_32. ISBN  978-3-540-41729-3."]
  2. ^ Фокс, Джеффри; Рой Уильямс; Поль Мессина (1994). Параллельные вычисления работают!. Морган Кауфманн. С. 575, 593. ISBN  978-1-55860-253-3.
  3. ^ Симоне Кампанони, Тимоти Джонс, Гленн Холлоуэй, Гу-Ён Вэй, Дэвид Брукс.«Проект HELIX: обзор и направления».2012.
  4. ^ Дж. Анантпур, Р. Говиндараджан, Вычисление зависимости от времени выполнения и выполнение циклов в гетерогенных системах «Архивная копия» (PDF). Архивировано из оригинал (PDF) на 2015-10-06. Получено 2015-10-05.CS1 maint: заархивированная копия как заголовок (связь)
  5. ^ X. Zhuang, A. E. Eichenberger, Y. Luo, Kevin O’Brien, Kathryn, Использование параллелизма с планированием с учетом зависимостей
  6. ^ «Автоматический параллелизм и зависимость данных». Архивировано из оригинал на 2014-07-14.
  7. ^ Рюнгер, Гудула (2006). «Модели параллельного программирования для нерегулярных алгоритмов». Параллельные алгоритмы и кластерные вычисления. Конспект лекций по вычислительным наукам и технике. 52: 3–23. Дои:10.1007/3-540-33541-2_1. ISBN  978-3-540-33539-9.

Смотрите также