КОНВЕЙЕРИЗАЦИЯ АЛГОРИТМОВ КАК МЕТОДИКА УСКОРЕНИЯ РАСЧЕТОВ

АННОТАЦИЯ

Изучен метод конвейеризации, область его использования, достоинства и недостатки. Приведён пример конвейеризации цикла в программном коде.

ABSTRACT

The method of pipelining, the area of its use, advantages and disadvantages have been studied. An example of pipelining a loop in a program code is given.

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

Keywords: pipeline, pipelining, hardware implementation, software code.

Определение конвейера (конвейеризации)

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

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

Под конвейерным режимом понимают такой вид обработки, при котором интервал времени, требуемый для выполнения процесса в функциональном узле (например, в АЛУ микропроцессора) продолжительнее, чем интервалы, через которые данные могут вводиться в этот узел [1]. Предполагается, что функциональный узел выполняет процесс в несколько этапов, т. е. когда первый этап завершается, результаты передаются на второй этап, на котором используются другие аппаратные средства. Разумеется, что устройство, используемое на первом этапе, оказывается свободным для начала новой обработки данных. Как известно, можно выделить четыре этапа обработки команды микропроцессора: выборка, декодирование, выполнение и запись результата. Иными словами, в ряде случаев, пока первая команда выполняется, вторая может декодироваться, а третья выбираться (рисунок 1).

Рисунок 1. Пример структуры простого цикла и направление переноса операций по обратной дуге

Принцип метода программной конвейеризации

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

В итоге такой подход создает некоторую параллельность, отсутствующую на отдельно взятой итерации. Использование подобного принципа важно для машин, у которых присутствуют несколько функциональных устройств, способных работать одновременно, как в разрабатываемых АО «МЦСТ» микропроцессорах с архитектурами SPARC и «Эльбрус».

Обычно для выполнения каждой инструкции требуется осуществить некоторое количество однотипных операций, например, получение инструкции, раскодирование инструкции и т.п. Каждую из этих операций сопоставляют одной ступени конвейера. Некоторые современные процессоры имеют более 30 ступеней в конвейере, что повышает производительность процессора, но, однако, приводит к увеличению длительности простоя (например, в случае ошибки в предсказании условного перехода). Не существует единого мнения по поводу оптимальной длины конвейера: различные программы могут иметь различные требования. По способу синхронизации работы ступеней конвейеры могут быть синхронными и асинхронными. Для традиционных ВМ характерны синхронные конвейеры. Связано это, прежде всего, с синхронным характером работы процессоров [2]. Ступени конвейеров в процессоре обычно располагаются близко друг от друга, благодаря чему тракты распространения сигналов синхронизации получаются достаточно короткими и фактор «перекоса» сигналов становится не столь существенным. Асинхронные конвейеры оказываются полезными, если связь между ступенями не столь сильна, а длина сигнальных трактов между разными ступенями сильно рознится. Примером асинхронных конвейеров могут служить систолические массивы [2].

Пример распараллеливания цикла методом конвейера

Программная конвейеризация циклов преобразует тело цикла таким образом, что на выполнение могут выдаваться команды из разных итераций исходного цикла, которые выполняются параллельно, подобно конвейеру [3]. Рассмотрим пример:

for i = 1 to N

A(i); B(i); C(i); D(i);

End

В этом примере A(i), B(i), C(i), D(i) обозначают инструкции, которые обрабатывают элемент данных i, зависящие друг от друга. Другими словами, A(i) должно быть выполнено перед тем, как может начать выполняться B(i). Например, A может загружать данные из памяти в регистр, B и C – выполнять арифметические операции над данными, а D – записывать полученный результат обратно в память. Предположим, что не существует зависимости между операциями для различных значений i. То есть, A(2) может начинаться до завершения D(1). Без программной конвейеризации, операции будут выполняться в следующем порядке:

A(1); B(1); C(1); D(1); A(2); B(2); C(2); D(2); A(3);…

Допустим, что на выполнение каждой инструкции уходит один такт процессора (без учета увеличения счетчика цикла). Также допустим, что в процессоре есть одно функциональное устройство, которое выполняет инструкции A и D (в примере – устройство работы с памятью) и одно функциональное устройство, которое выполняет инструкции B и C (в примере – арифметическое устройство). Тогда в рассмотренном случае на выполнение каждой итерации уходит четыре такта (при этом на каждом такте одно из функциональных устройств процессора простаивает, так как нет готовых для выполнения инструкций). Теперь рассмотрим преобразованный цикл, который полностью использует все функциональные устройства процессора:

A(1);

B(1);

for i = 2 to N

A(i), C(i - 1);

B(i), D(i - 1);

end

C(N);

D(N);

Для него порядок выполнения инструкций будет следующим:

A(1); B(1); A(2), C(1); B(2), D(1); A(3), C(2); B(3), D(2); …

Здесь инструкции, разделенные ‘;’, выполняются на разных тактах процессора, а инструкции, разделенные ‘,’, – на одном. При этом можно легко проверить, что в среднем на выполнение каждой итерации тратится по два такта процессора. Из этого примера видно, что при наличии возможности параллельного выполнения большого числа инструкций применение этой оптимизации может оказаться очень выгодным. Однако оно может быть связано с многими трудностями. В частности, для корректного преобразования цикла часто необходимо отдельно обрабатывать часть инструкций с нескольких первых и последних итераций – это ведет к увеличению размера кода (иногда в разы превышая размер тела цикла). Также, время жизни некоторых регистров может превышать длину одной итерации (например, какая-то инструкция использует значение переменной, вычисленное на предыдущей итерации), что означает необходимость использования временных регистров для хранения таких значений и, следовательно, создания новых операций для заполнения этих регистров. Эти дополнительные операции могут свести на нет все преимущества от применения конвейеризации циклов.

Вывод

Метод конвейеризации является удобным и эффективным способом увеличения производительности процессов. Основным принципов конвейера является то, что в одной итерации цикла производится расчет как итерации i, так и i-1, что позволяет распараллелить процесс и не позволяет простаивать вычислительным узлам в ожидании следующей итерации.

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

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

Список литературы:

1. Ким А.К., Перекатов В.И., Ермаков С.Г. Микропроцессоры и вычислительные комплексы семейства Эльбрус // СПб.: Питер – 2013. – 272 с.
2. Альфред Ахо, Моника Лам, Рави Сети, Джеффри Ульман. Компиляторы: принципы, технологии и инструментарий. – Изд. 2-е. – М.: ИД «Вильямс» – 2008. – 184 с.
3. А. Белеванцев, Д. Журихин, Д. Мельник. Компиляция программ для современных архитектур. Труды Института системного программирования РАН – Том 16 – 2009 – 31 с.