Управление и организация конвейеров.

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

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

1. время использования для любых ступеней является кратным некоторому периоду синхронизации;

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

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

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

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

Любая строка таблицы занятости соответствует использованию во времени отдельной ступени конвейера. Другая размерность – время- разбита на сегменты, обычно фиксированные и равные базовому периоду синхронизации. Любой столбец представляет собой диаграмму внутреннего использования конвейера в определенный момент времени. Для упрощения временные сегменты нумеруются целыми числами; первый сегмент обозначается как нулевая единица времени, или как нулевой цикл синхронизации. Метка в графе (i,j) указывает, что для данного конвейера исполнение данной функции требует использование i-ой ступени через j единиц времени после начала вычисления этой функции. Если для одного конвейера, имеется несколько возможных таблиц занятости (обозначаемых различными символами ), то метки в графах таблицы совпадают с обозначением самой таблицы. Общее число единиц времени от момента 0 до последнего сегмента, в которой все еще имеются действия конвейера, называется временем вычисления для данной таблицы занятости. Например, для трехступенчатого конвейера таблица занятости для двух разных вычислений представлена на рисунке 12.11.

 

Время 1 ступень     А   А     2 ступень   А   А   А   3 ступень А   А       А

Время 1 ступень В В         В В 2 ступень     В   В       3 ступень       В   В

 

Время вычисления = 7 Время вычисления = 8

Рисунок 12.11.

В любой таблице занятости представляется в точности одно вычисление данной функции. Статический конвейер – это такой конвейер, в котором все инициации относятся к одной и той же таблице занятости. Динамический конвейер – это конвейер, последовательность инициаций которого содержит различные таблицы занятости. Таблица занятости может содержать несколько меток в одной строке и столбце. Несколько меток в строке – неоднократное использование этой ступени на протяжении вычисления функции, либо, если метки занимаемой смежные графы – ступень, которая работает медленнее других. Несколько меток в столбце означает использование многих ступеней в один момент времени, то есть параллельное вычисление функции. Таблица занятости не определяет однозначно аппаратуру конвейера. Напротив, большое число структур конвейеров может быть представлено одной и той же таблицей занятости. Например, таблице занятости В (рисунок 12.11) могут соответствовать два типа структур конвейера (рисунок 12.12):

 

 

 

Рисунок 12.12.

Для таблицы А конвейер может быть следующим (рисунок 12.13):

 

 

Рисунок 12.13.

Ключевым параметром конвейера, определяющим производительность конвейера, является латентность, то есть число единиц времени, разделяющих инициации одной любой различной таблицы занятости. Латентность может иметь любое неотрицательное значение, включая 0. Например, (рисунок 12.14):

 

Время 1 ступень     А1 А2 А1 А2     2 ступень   А1 А2 А1 А2 А1 А2   3 ступень А1 А2 А1 А2     А1 А2

Время 1 ступень     А1     А2     2 ступень   А1       А2   3 ступень А1     А2   А1   А2

 

А₁А Латентность =1 А₁А Латентность =2

Рисунок 12.14.

Такие таблицы представляют динамическое использование конвейера, когда несколько инициаций действует одновременно. Между двумя инициациями возможно более одной латентности, однако не все латентности допустимы. Например, в статическом конвейере латентность равная нулю недопустима, так как приводит к конфликту ( то есть к использованию одной и той же ступени разными инициациями одновременно). Иными словами такая латентность вызывает столкновение. Поскольку конвейер должен произвести как можно больше вычислений за возможное более короткое время, временной мерой производительности системы является темп инициации или среднее число инициаций за единицу времени. Удобнее использовать величину обратную темпу инициации – среднюю латентность, то есть среднее число времени между двумя инициациями. Чем меньше латентность, тем быстрее работает конвейер. Для статического конвейера нижняя граница средней латентности равна 1, так как латентность 0 всегда приводит к столкновению. Для динамического конвейера возможности латентности равные 0, так как две различные таблицы занятости могут и не перекрываться.

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

Если одновременно задействовать различные таблицы занятости, то показатель использований ступеней будет равен сумме использований, вносимых каждым типом функций. Максимальный показатель использования любой ступени равен 1. Если задан набор из нескольких различных таблиц занятости, то целью стратегии диспетчеризации является выработка последовательности моментов времени, в которые должны выполняться инициации. Иными словами, выработка такой последовательности латентностей между инициациями, которая минимизирует среднюю латентность( максимальный темп инициации).

Выбор латентности между одной парой инициаций, непосредственно влияет на то, какие множества латентностей будут допустимы в последующих парах. Вследствие этого, стратегия, которая всегда между двумя последовательными инициациями вводит минимальную из латентностей, возможных в текущий момент времени, не всегда приводит к максимальной производительности. Такая стратегия называется жадной. Оптимальные стратегии должны это прогнозировать, чтобы определить влияние на производительность любой из возможных последовательностей латентности. Например, стратегия, которая запускает новые инициации таблицы занятости В, чередуя латентности равные 3 с латентностью равной 8, что приводит к средней латентности равной 5,5 [(3+8)/2]- это жадная стратегия, поскольку 3 – наименьшая латентность, не приводящая к столкновениям между двумя инициациями. Более эффективная стратегия откладывает начало второй инициации до четвертого такта, и тогда новые инициации могут осуществляться с интервалом 4. Ясно, что средняя латентность равная четырем, лучше.

 

Жадная последовательность для таблицы занятости В показана на рисунке 12.15:

Время

ступень

В1

В1

В2

В2

В1

В1

В2

В2

В3

В3

В4

В4

В3

В3

В4

В4

В1

В1

В2

В2

В3

В3

В4

В4

В1

В1

В2

В2

В3

В3

В4

В4

 

Цикл повторяется

Последовательность латентности = 3,8,3,8, ….

Средняя латентность = 5,5

Рисунок 12.15.

Оптимальная последовательность инициализации для таблицы занятости В показана на рис. 12.16:

Время

ступень

В1

В1

В2

В2

В1

В1

В3

В3

В2

В2

В4

В4

В3

В3

В5

В5

В1

В1

В2

В2

В3

В3

В4

В4

В1

В1

В2

В2

В3

В3

В4

В4

 

Цикл повторяется

Последовательность латентности = 4,4,4, ….

Средняя латентность = 4

Рисунок 12.16.

Жадная стратегия использует ступень 1 только в течении 73% общего времени работы конвейера, а ступень 2 и 3 – только 36 %. Вторая стратегия достигает почти 100 % использования ступени 1 и 50 % - ступень 2 и 3.

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