Временная организация, управление и производительность

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

Таблица занятости:

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

- Инициация таблицы занятости наступает тогда, когда начинается вычисление, которое проследует по определенному ею пути.

- Таким образом, инициация соответствует началу вычисления отдельной функции.

Свойства ТЗ:

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

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

Латентность (Latency):

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

- Латентность может иметь любое неотрицательное значение, включая 0.

1. “Жадная” стратегия. Понятие MAL в теории конвейера. Лемма для статических конвейеров. Введение задержек для увеличения производительности конвейеров.

Жадная стратегия – стратегия, которая всегда между двумя инициациями вводит минимальную из латентностей, возможных в текущий момент времени.

Загружаем конвейер так:
- сразу, как только такая возможность появилась
- и это не приведёт к заторам на конвейере.

В нулевом такте начинает выполняться первая операция (Б1). Этот момент отмечен первой стрелкой снизу. Теперь ждём, когда можно будет загрузить вторую операцию (Б2).В нулевом и первом такте не можем, т.к. первая ступень уже занята операцией Б1, а во втором не можем потому, что это приведёт к затору на второй ступени в четвёртом такте (там выполняется ещё первая команда, а уже должна начинать вторая). Итак, загружаем Б2 в третьем такте. Эта операция отмечена второй стрелкой под таблицей. Теперь на конвейере выполняются Б1 и Б2.

А когда мы можем загрузить следующую, Б3? Как видим, только на 11 такте, конвейер при этом уже будет полностью пустой, и всё повторится.

Латентность: сколько времени нам надо ждать, прежде чем запихнуть на конвейер следующую команду? Ответ - 3 такта для второй команды (после загрузки первой), и 8 тактов - для загрузки третьей (после второй). Далее - циклично, для 4-й команды 3 такта, для 5-й команды 8 тактов... Поэтому записываем в угловых скобках: L=<3,8>. Среднее значение, можно получить как (3+8)/2.

«Терпеливая» стратегия для В

В соответствии с "Терпеливой" стратегией мы не загружаем следующую операцию сразу, как только можем, а немного ждём. На рисунке видим, что полного освобождения конвейера (как в случае "жадной") не происходит, ресурсы конвейера распределяются оптимальнее и латентность (средняя) оказывается меньше, несмотря на то, что вторая команда загружается не через 2, а через 4 такта.