§12.8. Функции управления в конвейерных системах.

Аппаратное управление инициациями.

Основная функция управления состоит в определении момента, когда может быть сделана новая инициация. Этот момент зависит как от свойств соответствующих таблиц занятости, так и от времени фактически поступления данных на вход конвейера. Имеется несколько типовых комбинаций, охватывающих весь диапазон от конвейера со статической конфигурацией и жесткой временной организацией до конвейера с динамической конфигурацией, при которой время поступления данных заранее не определено. Для статического конвейера из полученного цикла периода Р можно сформировать р- разрядный вектор i-ый разряд этого вектора равен нулю, если в i-ой единице времени любого цикла создается новая инициация . Затем простой контроллер со сдвиговым регистром может выбрать этот вектор и циклически сдвигать его на один разряд за один период синхронизации. Если в момент поступления синхроимпульса в самом левом разряде находиться 0, то в этот период начинается новая инициация.

Рисунок 12.27.

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

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

Рисунок 12.28.

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

• В начале любого периода синхронизации вектор сдвигается влево на 1 разряд.

• Если в левом разряде стоит 1, то инициация не может быть осуществлена в данный момент (период синхронизации).

• Если в левом разряде стоит 0 и имеются данные, то осуществляется инициация, а начальный вектор столкновений модифицируется операцией ИЛИ, применяемой к нему и вектору в сдвиговом регистре.

• Если в левом разряде стоит 0, но данных нет, то инициация не выполняется, а содержимое сдвигового регистра не модифицируются.

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

Этот контроллер гибкий: достаточно изменить начальный вектор столкновений, что бы изменилось поведение системы.

Если начальный вектор никогда не изменяется, то модификация этого контроллера может следовать стратегиям, отличным от жадной.

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

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

Рисунок 12.29.

В этом случае также невозможно динамически вычислить оптимальное расписание. Однако, как и ранее, можно реализовать контролер, который будет последовательно придерживаться жадной стратегии (рисунок 12.30).

Рисунок 12.30.

Имеется m начальных матриц столкновений и m сдвиговых регистров, представляющих текущее состояние матриц столкновений. Все регистры сдвигаются и загружаются одновременно. Выход i-го сдвигового регистра указывает на может или нет осуществляться инициация i-го типа в текущий момент времени. Эти выводы комбинируются с помощью операции логической И с соответствующими сигналами о наличии данных, поступающих из буферов входных данных. Комбинированные сигналы подаются затем на функциональный блок поиска в таблице (ПЗУ, ПЛМ). По этим входам в таблице выбирается наибольший совместимый набор инициаций, и данные всех выбранных типов одновременно вводятся в конвейер. Матрица столкновений затем обновляется с помощью операций логического ИЛИ над ней и над копиями соответствующих начальных матриц столкновений. Как и раннее, этот контроллер может быть расширен так, чтобы вырабатывались последовательности инициаций более общего вида, однако, в силу большого размера матрицы столкновений это расширение оказывается слишком дорогим для любого конвейера кроме тривиальных.

Внутриконвейерное управление.

После того, как инициация осуществлена, связанные с ней данные должны продвигаться в конвейере по пути, соответствующему таблице занятости и матрице столкновений. Механизм, который планировал инициацию и привел в действие, уже не связан с дальнейшими действиями. Однако во всех конвейерах требуется еще большой объем работы системы управления для проведения инициации и доведения её до конца. Работа системы управления включает в себя:

1. Генерирование сигнала инициация завершена.

2. Активизация логики внутри ступени.

3. Управление маршрутом.

4. Выбор функции внутри ступени.

Генерирование сигнала о завершении инициации связано с внешними устройствами, которым может требоваться информация о завершении функции.

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

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

Управляющие сигналы могут изменять функцию выполняемую ступенью. Существует много способов реализации всех режимов управления. Простая реализация первых двух-«инициация завершена» и «данные подлинные»-состоит в добавлении одного дополнительного разряда на фиксатор ступени, который управляется также, как и остальные разряды, но соединяются с соответствующим дополнительным разрядом следующей ступени с помощью холостой логики, которая просто повторяет его значение (рисунок 12.31).

Рисунок 12.31.

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

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

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

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

Рисунок 12.32.

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

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

При управлении с привязкой к данным сигналы управления «сопровождают» данные по конвейеру, обеспечивая по мере необходимости управление на любой ступени. Централизованного источника управления нет. Вместо этого, всякий раз, когда осуществляется инициация, сигналы управления для соответствующих таблиц занятости поступают в конвейер наряду с данными. До тех пор, пока устройство инициации гарантирует, что столкновений не будет, нет опасности, что два управляющих сигнала попытаются одновременно использовать одну ступень. Один из возможных контроллеров с привязкой к данным, построенный по образцу временной цепочки, показан на рисунке 12.33.

Рисунок 12.33.

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

Микропрограммное управление.

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

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

В качестве демонстрирации на рисунке 12.34 представлен пример двухступенчатого конвейера и центральная часть его микропрограммного контроллера.

Рисунок 12.34.

Этот конвейер построен для сложения чисел с плавающей запятой, где логика первой ступени (модуль F) выполняет сравнение порядков и выравнивание мантисс логика двух ступеней (модуль G) выполняет сложение мантисс и нормализации результата. Данные берутся из памяти, проходят по конвейеру и возвращаются снова в память. Фиксатор на выходе модуля G является двухрегистровым файлом, любой из регистров которого в любой момент времени может быть загружен из G, его содержание может быть записано в память или возвращено на выход модуля

Каждая микрокоманда содержат 5 полей:

- поле чтения, указывающее, какие 2 слова надо прочитать из памяти в фиксатор X и Y;

- поле F указывающее, какие входы надо использовать( X, Y, Fo (позиция 0 регистрщвого файла) или F1(позиция 1 регистрового файла) и что должна делать логика модуля F (например, начать выравнивание входных величин, начать вычисление или передать данные с левого входа неизменными);

- поле G выбирает, что должен делать модуль G (сложить, вычислить или передать Х` неизменным), и куда поместить результат (в F0 или F1);

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

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

Пример проектирования конвейера.

Пусть нужно спроектировать конвейер, который с периодическим интервалом принимает аналоговый сигнал Х, на любом интервале времени берет последние 4 значения Х(i), Х(i-1), Х(i-2), Х(i-3) и, применяя к ним симметричный фильтр, вычисляет выходную величину:

Считаем, что имеются следующие компоненты: одноступенчатые аналого-цифровые преобразователи (АЦП), двухступенчатый сумматор, одноступенчатый цифро-аналоговый преобразователь (ЦАП) (все с минимальным временем Т для ступени), четырехпозиционная память, способная выполнить одну операцию чтения или записи за Т секунд и двухступенчатый умножитель, способный принимать новые входные данные любые 2Т секунды. Наконец предполагаем, что имеется также любая логика необходимая для объединения всех компонент в систему.

Разбиение рассматриваемой функции на подфункции приводит к инициации, которая выглядит следующим образом:

1. использовать АЦП для получения Х(i);

2. циклически записывать это значение в четырехпозиционную память, так что в ней будут храниться Х(i),Х(i-1),Х(i-2),Х(i-3);

3. прочитать Х(i) и Х(i-3) и сложить их;

4. результат шага 2 умножить на a;

5. прочитать Х(i-1),Х(i-2) и сложить;

6. умножить результат шага 5 на b;

7. сложить результаты шагов 4 и 6;

8. вывести результат шага 7 через ЦАП;

На основе этого разбиения можно составить возможную таблицу занятости (таблица 1).

Таблица 1.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
1. АЦП	1
2. 4-х позиционная память		2	3	3	5	5
3. Суммирование, 1ступень					3		5					7
4. Суммирование, 2 стпень						3		5					7
5.Умножение, 1ступень							4	4	6	6
6.Умножение, 1ступени								4	4	6	6
7. ЦАП														8

Числа в клетках таблицы соответствуют шагу разбиения. Из таблицы получим множество запрещенных латентностей {0,1,2,3,4,5,7} и начальный вектор столкновений 11111101. Из таблицы занятости следует, что нижняя граница для MAL равна 5 (5 меток во второй строке), а из вектора столкновений следует, что имеется хотя бы один жадный цикл средней латентности 7 (7 единиц в векторе). Это показывает, что мы можем запускать новую инициацию в среднем, по меньшей мере, один раз на каждые 7 циклов, но не чаще, чем один раз на каждые 5 циклов. Что бы выяснить, что именно возможно, можно построить и проанализировать диаграмму состояний (отыскать вектор 11111101 в таблице). В результате находим, что (6) является оптимальным жадным циклом. При этом не достигается нижняя граница (5) для МАL и возможности ступеней оказываются недоиспользованными.

Теперь допустим, что разработчик системы хочет повысить её производительность, доведя среднюю латентность до 5, и хочет реализовать постоянный цикл латентности (5). Это возможно, что если все строки таблиц занятости могут быть выражены через максимальные классы совместимости отличительного множества Нс mod 5 цикла (5). Из леммы (приведенной выше) следует, что в эти классы входит набор {0,1,2,3,4} и все другие наборы, получаемые из него, прибавлением ко всем элементам константы и/или произвольных кратных числа 5.

С первой строкой таблицы занятости проблем не возникает; вторая строка имеет вид 1+{0,1,2,3,4}, так как удовлетворяет ограничениям. Точно также строки 5 и 6 имеют вид x+{0,1,2,3}, а строка 7 как 13+{0}. Проблема возникает со строками 3 и 4. Строку 3 можно представить как 4+{0,2,3+1х5}, что требует задержки операции 7 на один такт. Аналогичная ситуация наблюдается и со строкой 4. Всё это требует также задержки и операции вывода 8. Теперь таблица занятости имеет следующий вид (таблица 2):

Таблица 2.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
1. АЦП	1
2. 4-х позиционная память		2	3	3	5	5
3. Суммирование, 1ступень					3		5					d	7
4. Суммирование, 2 стпень						3		5					d	7
5.Умножение, 1ступень							4	4	6	6
6.Умножение, 1ступени								4	4	6	6
7. ЦАП															8

Таблица занятости с задержкой.

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

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

Некоторые из них, например файлы А и В используются потому, что задача требует двух отдельных сложений. Таким образом пара А0, В0 поддерживает сложение x(i)+x(i-3), пара А1,В1- x(i)+x(i-2). Точно также файлы Е и F поддерживают два умножителя. Предполагается, что частью инициализации является загрузка F0 и F1 двумя константами а и в. Наконец файлы С и D поддерживают заключительное сложение с его входной задержкой.

Рисунок 12.35.

Следующий шаг построения последовательностей латентностей (стратегия диспетчеризации) и конвейера заключается в том, что бы составить план работы конвейера во времени, которому должен следовать механизм управления. Так как период равен 5, а время вычисления равно 15, в любом наборе из 15 тактов будут иметься различные части 15/5=3 инициаций. Одна из инициаций только начинается, другая находится в середине вычислений, а третья заканчивается. При микропрограммном управлении важно, чтобы механизм управления отслеживал, в каком месте вычислений находятся все три инициации. Для формализации сказанного, разделим все время на наборы на 5 тактов в каждой инициации (таблица 3).

Таблица 3.

	i	i-1	i-2
5i	Преобразование аналог-цифра	Чтение x(i-1-2) в В1. Выдача маршрута для выходных данных сумматора к Е0	Выдача маршрута для выходных данных к D0
5i+1	Запоминание данных для преобразования в памяти	Запуск сложений А1 и В1 Запуск сложений Е0и F0
5i+2	Чтение x(i) вA0	Выдача маршрута для выходных данных сумматора к Е1. Продолжение E0хF0	Запуск сложений C0+В0
5i+3	Чтение x(i-3) в В0	Запуск умножения Е1хF1. Выдача маршрута для выхода данных умножения к С0	Выдача маршрута для выходных данных сумматора к ЦАП
5i+4	Чтение x(i-1) вA1. Запуск сложения А0 и В0	Продолжение умножения Е1хF1	Выполнение преобразования цифра-аналог

Предполагается, что в момент 5i i-я инициация только начинается, (i-1)-я находится на шаге 5 своих вычислений, а (i-2) начинает свой 10 шаг. В момент 5 i+1 все 3 инициации продвигаются на 1 шаг. Пустая клетка в третьем столбце означает задержку на один такт. Заметим, что запись в регистр D0 осуществляется момент 5i, а чтение из него в момент 5i+2, как и требуется для задержки на единицу времени. Однако, в данной задаче никакая другая инициация не делает попытки писать в файл D за этот период. Поэтому, строго говоря, нет необходимости использовать здесь регистровые файлы, достаточно иметь простой фиксатор. Однако, в общем случае подобный анализ необходимо вычислить, чтобы определить, необходимы или нет регистровые файлы.

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