Конвейерная обработка программного обеспечения
В информатике оптимизации программная конвейерная обработка — это метод, используемый для циклов , аналогичный аппаратной конвейерной обработке . Конвейерная обработка программного обеспечения — это тип выполнения вне порядка , за исключением того, что переупорядочение выполняется компилятором ( или, в случае рукописного ассемблерного кода , программистом), а не процессором . Некоторые компьютерные архитектуры имеют явную поддержку программной конвейерной обработки, особенно архитектура Intel IA -64 .
Важно отличать программную конвейерную обработку , которая является методом целевого кода для перекрывающихся итераций цикла, от планирования по модулю , наиболее эффективного в настоящее время известного метода компилятора для создания программных конвейерных циклов. Конвейерная обработка программного обеспечения известна программистам на языке ассемблера машин с параллелизмом на уровне команд с тех пор, как такие архитектуры существовали. Эффективная генерация такого кода компилятором началась с изобретения планирования по модулю Рау и Глейзером. [1] Лам показал, что для эффективного планирования по модулю нет необходимости в специальном оборудовании. Ее метод разложения по модулю переменной широко используется на практике. [2] Гао и др. сформулировал оптимальную конвейерную обработку программного обеспечения в области целочисленного линейного программирования, кульминацией которой стала проверка расширенных эвристик в оценочной статье. [3] В этой статье есть хороший набор ссылок по теме.
Пример
[ редактировать ]Рассмотрим следующий цикл:
for i = 1 to bignumber A(i) B(i) C(i) end
В этом примере пусть A(i), B(i), C(i) быть инструкциями, каждая из которых оперирует данными i, которые зависят друг от друга. Другими словами, A(i) должен завершиться раньше B(i) можно начать. Например, A мог загружать данные из памяти в регистр , B может выполнить некоторую арифметическую операцию с данными, и C мог сохранить данные обратно в память. Однако пусть не существует зависимости между операциями для разных значений i. Другими словами, A(2) может начаться раньше A(1) заканчивается.
Без программной конвейерной обработки операции выполняются в следующей последовательности:
A(1) B(1) C(1) A(2) B(2) C(2) A(3) B(3) C(3) ...
Предположим, что каждая инструкция выполняется за 3 такта (на данный момент игнорируем стоимость цикла управления). Также предположим (как и в большинстве современных систем), что инструкция может выполняться в каждом цикле, если она не зависит от уже выполняемой инструкции. Таким образом, в неконвейерном случае каждая итерация занимает 9 тактов: 3 такта для A(1), 3 такта для B(1)и 3 тактовых цикла для C(1).
Теперь рассмотрим следующую последовательность инструкций с программной конвейерной обработкой :
A(1) A(2) A(3) B(1) B(2) B(3) C(1) C(2) C(3) ...
Можно легко проверить, что инструкция может отправляться в каждом цикле, а это означает, что одни и те же 3 итерации могут быть выполнены в общей сложности за 9 тактов, что дает в среднем 3 такта на итерацию.
Выполнение
[ редактировать ]Программная конвейеризация часто используется в сочетании с развертыванием цикла , и эта комбинация методов часто является гораздо лучшей оптимизацией, чем развертывание цикла отдельно. В приведенном выше примере мы могли бы написать код следующим образом (предположим на данный момент, что bignumber делится на 3):
for i = 1 to (bignumber - 2) step 3 A(i) A(i+1) A(i+2) B(i) B(i+1) B(i+2) C(i) C(i+1) C(i+2) end
Конечно, дело усложняется, если (как это обычно бывает) мы не можем гарантировать, что общее количество итераций будет делиться на количество итераций, которые мы разворачиваем. Дополнительные сведения о решениях этой проблемы см. в статье о развертывании цикла , но учтите, что программная конвейерная обработка не позволяет использовать устройство Даффа . [ нужна ссылка ]
В общем случае развертывание цикла может оказаться не лучшим способом реализации программной конвейерной обработки. Рассмотрим цикл, содержащий инструкции с высокой задержкой . Например, следующий код:
for i = 1 to bignumber A(i) ; 3 cycle latency B(i) ; 3 C(i) ; 12(perhaps a floating point operation) D(i) ; 3 E(i) ; 3 F(i) ; 3 end
потребуется развернуть 12 итераций цикла, чтобы избежать узкого места в инструкциях C. Это означает, что код цикла увеличится в 12 раз (что не только влияет на использование памяти, но и может повлиять на кэша производительность , см. раздувание кода ). Хуже того, пролог (код перед циклом для обработки случая bignumber не делится на 12), скорее всего, будет даже больше, чем код цикла, и, весьма вероятно, неэффективен, поскольку в этом коде нельзя использовать программную конвейерную обработку (по крайней мере, без значительного дальнейшего раздувания кода). Кроме того, если bignumber ожидается, что размер будет умеренным по сравнению с количеством развернутых итераций (скажем, 10-20), тогда выполнение будет проводить большую часть времени в этом неэффективном коде пролога, что делает оптимизацию программной конвейерной обработки неэффективной.
Для сравнения, вот программная конвейерная обработка нашего примера ( пролог и эпилог будут объяснены позже):
prologue for i = 1 to (bignumber - 6) A(i+6) B(i+5) C(i+4) D(i+2) ; note that we skip i+3 E(i+1) F(i) end epilogue
Прежде чем перейти к прологу и эпилогу, которые обрабатывают итерации в начале и конце цикла, давайте проверим, что этот код делает то же самое, что и исходный код, для итераций в середине цикла. В частности, рассмотрим итерацию 7 исходного цикла. Первой итерацией конвейерного цикла будет первая итерация, включающая инструкцию из итерации 7 исходного цикла. Последовательность инструкций следующая:
- Итерация 1:
A(7) B(6) C(5) D(3) E(2) F(1) - Итерация 2:
A(8) B(7) C(6) D(4) E(3) F(2) - Итерация 3:
A(9) B(8) C(7) D(5) E(4) F(3) - Итерация 4:
A(10) B(9) C(8) D(6) E(5) F(4) - Итерация 5:
A(11) B(10) C(9) D(7) E(6) F(5) - Итерация 6:
A(12) B(11) C(10) D(8) E(7) F(6) - Итерация 7:
A(13) B(12) C(11) D(9) E(8) F(7)
Однако, в отличие от исходного цикла, конвейерная версия позволяет избежать узкого места в инструкции. C. Обратите внимание, что между ними имеется 12 инструкций. C(7) и зависимая инструкция D(7), что означает, что латентные циклы инструкции C(7) используются для других инструкций, а не тратятся впустую.
Пролог и эпилог обрабатывают итерации в начале и конце цикла. Вот возможный пролог к нашему примеру выше:
; loop prologue (arranged on lines for clarity) A(1) A(2), B(1) A(3), B(2), C(1) A(4), B(3), C(2) ; cannot start D(1) yet A(5), B(4), C(3), D(1) A(6), B(5), C(4), D(2), E(1)
Каждая строка выше соответствует итерации основного конвейерного цикла, но без инструкций для итераций, которые еще не начались. Аналогичным образом, эпилог постепенно удаляет инструкции для завершенных итераций:
; loop epilogue (arranged on lines for clarity) B(bignumber), C(bignumber-1), D(bignumber-3), E(bignumber-4), F(bignumber-5) C(bignumber), D(bignumber-2), E(bignumber-3), F(bignumber-4) D(bignumber-1), E(bignumber-2), F(bignumber-3) D(bignumber), E(bignumber-1), F(bignumber-2) E(bignumber), F(bignumber-1) F(bignumber)
Трудности реализации
[ редактировать ]Требование пролога и эпилога — одна из основных трудностей реализации конвейерной обработки программного обеспечения. Обратите внимание, что пролог в этом примере состоит из 18 инструкций, что в 3 раза больше, чем сам цикл. В эпилоге также будет 18 инструкций. Другими словами, пролог и эпилог вместе взятые в 6 раз больше самого цикла . Хотя для этого примера программная конвейерная обработка все же лучше, чем попытка развертывания цикла, она требует компромисса между скоростью и использованием памяти. Также имейте в виду, что если раздувание кода слишком велико, это в любом случае повлияет на скорость из-за снижения производительности кэша.
Еще одна трудность заключается в том, что во многих архитектурах большинство инструкций используют регистр в качестве аргумента и что конкретный используемый регистр должен быть жестко запрограммирован в инструкции. Другими словами, на многих архитектурах невозможно закодировать такую инструкцию, как «перемножить содержимое регистра». X и зарегистрируйтесь Y и поместите результат в регистр Z", где X, Y, и Z - это числа, взятые из других регистров или памяти. Это часто называют причиной того, что конвейерную обработку программного обеспечения невозможно эффективно реализовать на традиционных архитектурах.
Фактически, Моника Лам представляет элегантное решение этой проблемы в своей диссертации « Компилятор, оптимизирующий систолическую матрицу» (1989) ( ISBN 0-89838-300-5 ). Она называет это расширением по модулю переменной . Хитрость заключается в том, чтобы реплицировать тело цикла после того, как он был запланирован, позволяя использовать разные регистры для разных значений одной и той же переменной, когда они должны работать одновременно. Для простейшего примера предположим, что A(i) и B(i) могут выдаваться параллельно и что задержка первого составляет 2 цикла. Тогда конвейерное тело может быть:
A(i+2); B(i)
При распределении регистров тела этого цикла возникает проблема, заключающаяся в том, что результат A(i+2) должен оставаться активным в течение двух итераций. Используя тот же регистр для результата A(i+2) и ввод B(i) приведет к неверным результатам.
Однако, если мы реплицируем тело запланированного цикла, проблема будет решена:
A(i+2); B(i) A(i+3); B(i+1)
Теперь под результаты можно выделить отдельный регистр. A(i+2) и A(i+3). Если быть более конкретным:
r1 = A(i+2); B(i) = r1 r2 = A(i+3); B(i+1) = r2 i = i + 2 // Just to be clear
Если предположить, что каждый набор команд считывает свои входные регистры перед записью в выходные регистры, этот код верен. В начале реплицируемого тела цикла r1 имеет значение A(i+2) из предыдущей реплицируемой итерации цикла. С i было увеличено на 2, на самом деле это значение A(i) в этой повторяющейся итерации цикла.
Конечно, репликация кода увеличивает размер кода и нагрузку на кэш точно так же, как это делают пролог и эпилог. Тем не менее, для циклов с большим количеством срабатываний на архитектурах с достаточным параллелизмом на уровне команд этот метод легко работает достаточно хорошо, чтобы оправдать любое увеличение размера кода.
реализация IA-64
[ редактировать ]Архитектура Intel IA-64 представляет собой пример архитектуры, разработанной с учетом трудностей конвейерной обработки программного обеспечения. Некоторая архитектурная поддержка конвейерной обработки программного обеспечения включает в себя:
- «Вращающийся» банк регистров; инструкции могут ссылаться на номер регистра, который перенаправляется в другой регистр на каждой итерации цикла (в конечном итоге возвращаясь к началу). Это делает дополнительные инструкции [ указать ] вставленный в предыдущий пример ненужный.
- Предикаты (используются для «предикативных» инструкций; см. «Предикат ветвления »), которые получают значения из специальных инструкций цикла. Эти предикаты включают или выключают определенные инструкции в цикле, делая ненужными отдельные пролог и эпилог.
Ссылки
[ редактировать ]- ^ BR Рау и CD Glaeser, «Некоторые методы планирования и легко планируемая горизонтальная архитектура для высокопроизводительных научных вычислений», В материалах четырнадцатого ежегодного семинара по микропрограммированию (MICRO-14), декабрь 1981 г., страницы 183-198
- ^ М. Лам, «Конвейерная обработка программного обеспечения: эффективный метод планирования для машин VLIW», в материалах конференции ACM SIGPLAN 88 по проектированию и реализации языков программирования (PLDI 88) , июль 1988 г., страницы 318-328. Также опубликовано как Уведомления ACM SIGPLAN 23(7).
- ^ Дж. Руттенберг, Г. Р. Гао, А. Стаутчинин и В. Лихтенштейн, «Вскрытие конвейерной обработки программного обеспечения: оптимальные и эвристические методы в производственном компиляторе», в материалах конференции ACM SIGPLAN 1996 г. по проектированию и реализации языков программирования, июнь 1996 г. , страницы 1–11. Также опубликовано как Уведомления ACM SIGPLAN 31(5).