Лемма для статического конвейера

Для любого конвейера со статической конфигурацией, реализующего некоторую таблицу занятости, величина MAL всегда > или = MAX числу меток в любой строке этой таблицы.

MAL - Минимальное Среднее значение Латентности. Т.е. это количество тактов, которое мы должны подождать, прежде чем загрузим на конвейер следующую инструкцию. Почему оно не меньше числа "крестиков" в каждой ступени конвейера, я думаю, понятно. Если у нас есть операция, которая выполняется за 3 такта, и все 3 такта первая ступень занята, то независимо от всех остальных ступеней мы не сможем загрузить в конвейер ничего другого, пока эти 3 такта не пройдут, иначе будут столкновения.
Почему MAL может оказаться больше - тоже понятно. Может оказаться так, что операция выполняется 10 тактов, а в каждой ступени по 5 действий, но если запустить следующую операцию даже через 5 тактов, всё равно произойдут столкновения.
Это должно быть понятно из того, что я написал выше.
Как средняя латентность может быть минимальной? Для "Жадной" стратегии средняя латентность у операции В оказалась 5,5, а для "Терпеливой" она 4. Вот 4 и есть минимальная средняя латентность.

Введение задержек для увеличения производительности:

Лемма для статического конвейера - student2.ru Лемма для статического конвейера - student2.ru


  1. Теория конвейера: вектор столкновений. Диаграмма переходов. Пример.

В каждом состоянии закодирована информация, называемая вектором столкновений. Такой вектор является d-разрядной двоичной последовательностью, где d — время вычисления для таблицы занятости. При этом d разрядов нумеруются от 0 до d-1 слева направо; 0 в i-й позиции означает, что у инициации, начатой через i единиц времени после текущего момента, не будет столкновений ни с одной из незавершенных в текущий момент инициации, а 1 означает, что столкновения будут и поэтому инициация должна быть запрещена.

Лемма для статического конвейера - student2.ru Диаграмма состояний для операции В: Диаграмма состояний для операции А

Лемма для статического конвейера - student2.ru

Теперь посмотрим, как формально показать, что будет, если загружать следующую инструкцию в разные такты. Для этого введём вектор столкновений. Это вектор из единиц и нулей. Длина вектора равна числу тактов выполнения операции. Например, если в третьей позиции этого вектора 0, то мы можем запустить в конвейер следующую операцию, и ни на одной ступени столкновений не произойдёт. Любая операция выполнится за фиксированное число тактов, равное длине вектора (столкновений-то нет). Если в этой позиции 1, то в этом такте начинать загружать на конвейер следующую операцию нельзя.
Смотрим рис. 2.4. Основной здесь - квадратик "Начальное состояние": 11100111. Таким образом, мы можем запустить вторую инструкцию в третьем, четвёртом такте. Либо в 8-м, когда конвейер будет уже пуст. В последнем случае мы попадаем в то же самое состояние. Это стрелка ">=8". Т.е. мы можем запустить следующую операцию и в 8, и в 9, и в 10 такте, это уже ничего не изменит, конвейер будет пуст.
Стрелка "3" соответствует запуску следующей команды в 3-м такте (см. рис. "Жадная" стратегия). В этом случае (как мы уже видели) следующая команда может быть загружена только после полного освобождения конвейера, через 8 тактов. Снова попадаем на пустой конвейер.
Стрелка "4" соответствует "Терпеливой" стратегии. Из этого (11110111) состояния есть два пути. Можно загружать каждую следующую инструкцию через 4 такта после предыдущей (см. "Терпеливую" стратегию), либо ждать освобождения конвейера, снова попадая в Начальное состояние.
Таким образом, из каждого состояния выходит N+1 стрелка, где "N" - число нулей, а "+1" - это переход в Начальное состояние.

Лемма для статического конвейера - student2.ru

  1. Векторные процессоры: определение, 2 типа векторных процессоров, архитектура аппаратных средств, особенности системы команд. Примеры архитектуры векторных процессоров.

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

В средствах векторной обработки под вектором понимается одномерный массив однотипных данных (обычно в форме с плавающей запятой). Если обработке подвергаются многомерные массивы, их также рассматривают как векторы.

Векторный процессор может быть реализован в двух вариантах:

- дополнительный блок к универсальной ВС.

- основа самостоятельной ВС.

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

Пути построения векторных процессоров:

1. программный: пишется специальная библиотека программ, выполняющих векторные операции, ориентированная под конкретную имеющуюся платформу;

2. аппаратный: проектируется сначала скалярный компьютер+добавляются микрокоды векторных операций

3. изначально разрабатывалась векторная машина (с векторными командами).

Лемма для статического конвейера - student2.ru

Архитектура аппаратных средств:

1. Оперативная память. Это общее название включает в себя не только непосредственно оп-это может быть достаточно сложная иерархическая структура, включающая кэши и регистры. Причём, регистров может быть достаточно много - кроме скалярных, есть векторные регистры для хранения массивом. Быстродействие памяти во многом лимитирует быстродействие всего векторного процессора. Система памяти - это самая сложная подсистема векторного процессора. Для векторных компьютеров определён принцип расслоения памяти (для того, чтобы обеспечить суммарное быстродействие). Принцип расслоения памяти применяется и в обычных ПК, но там коэффициент расслоения небольшой. А в векторных процессорах коэффициент расслоения самый высокий на фоне других систем: 64, 128, 256. Всё это делается для того, чтобы запросное число (количество данных, поступающих из памяти за один цикл обращения) было как можно больше (хотя бы порядка ~ 100 или нескольких сотен). Требования к оперативной памяти достаточно высоки.

2. Скалярный процессор.Выполняет все функции обычного процессора (обрабатывает поток команд и имеет все необходимые устройства для выполнения скалярных операций) + дополнительные функции: распознавая наличия векторной команды (передаёт её векторному процессору (3)).

3. Векторный процессор. Базовые функции векторного процессора (при получении векторной команды):

3.1. Декодирование

3.2. Выработка системы сигналов для арифметического конвейера (6). Функция - выбор исполнительного устройства.

3.3. Вычисление логических параметров адресации (адресация к вектору).

3.4. Сопровождение выполнения операции.

3.5. Анализ состояния (по завершению операции).

4. Контроллер векторной памяти. На основе логических адресов векторов выдаёт последовательность адресов для обращения к физической памяти чтение/запись результата. Передаёт в буферную память (5).

5. Буферная память. Пассивное устройство. Нужно, т.к. поступают данные не равномерно во времени, а выдаются данные синхронно.

6. Арифметический конвейер. Один или несколько конвейеров, выполняющих векторные операции. Это может быть либо сложный конвейер (настраиваемый), либо набор конвейеров.

Лемма для статического конвейера - student2.ru Таблица занятости для обобщенной архитектуры:

А - выборка векторной команды

В - передача векторной команды и её декодирование векторным контроллером.

С - начальная выборка данных (запись/чтение)

D - выполнение команды

E - окончательное запоминание (запись) - может занимать большое количество тактов.

F - завершение операции - очистка буферов/регистров, выставление признаков состояния.

Наши рекомендации