Диаграмма состояний

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

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

Вектор столкновений для начального состояния называется начальным вектором столкновений. Поскольку он соответствует моменту времени начального запуска конвейера, то он определяет, какие латентности вообще допустимы только между двумя инициациями: в моменты 0 и i. Он определяет также допустимую латентность между любыми двумя инициациями без учета ранних действий конвейера. Вычисление начального вектора столкновений производится непосредственно. Для любого значения i между 0 и d-1 копия таблица занятости сдвигается на i единиц времени вправо и накладывается на несдивагаемую копию таблицы. Если где-либо в пределах наложения таблиц в одной графе «время- ступень» оказываются 2 метки, то i-й разряд начального вектора столкновений полагается равным 1, в противном случае 0. Во всех случаях нулевой разряд вектора столкновений равен 1, поскольку наложение таблицы занятости самой на себя приводит к столкновению во всех графах, содержащих метки. Аналогично, во всех разрядах, начиная с d, всегда стоят нули, поскольку сдвинутая и несдвинутая таблицы не перекрываются. Так как это имеет место всегда, нет необходимости представлять эти разряды в векторе столкновений.

Альтернативный подход состоит в построении множества запрещенных латентностей. Число i является членом этого множества в том и только в том случае, когда хотя бы в одной строке таблицы занятости имеются 2 метки, разделенные i столбцами. С помощью анализа меток в любой строке быстро определяется все члены множества, 0 всегда ему принадлежит. Для всех i принадлежащему этому множеству, соответствующий разряд в начальном векторе столкновений равен 1. Все остальные разряды равны 0. Например, для таблицы В множество запрещенных латентностей равно {0,1,2,5,6,7,}, а соответствующий вектор столкновении равен 11100111.

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

Генерирование диаграммы состояний:

1. Вектор столкновений для момента времени t сдвигается влево на 1 разряд, самый левый разряд отбрасывается, а в правый разряд заносится 0.

2. Если в нулевом разряде этого вектора содержится 1, то это новый вектор столкновений.

3. Если в нулевом разряде содержится 0, то в момент t+1 возможны два состояния в зависимости от того, произведена ли новая инициация в момент t+1. Если инициация не произведена, то сдвинутый вектор столкновений представляет очередное состояние. Если же в момент t+1 произведена инициация, то новый вектор столкновений является результатом поразрядной логической операции ИЛИ, сдвинутого вектора и копии начального вектора столкновений.

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

Правильность процедуры вытекает из следующего: если в момент времени t вектор столкновений имеет единицу в i разряде, то необходимо избегать инициации в момент t+1. Следовательно, вектор столкновений в момент t+1 должен учитывать это, но тогда требуется, чтобы в разряде i-1 для момента t+1 стояла единица. Если в момент t+1 не производится новая инициация, то верно и обратное, а именно, в разряде i-1 стоит единица, только если в момент t стояла единица. Этим оправдываются шаги 1 и 2.

Шаг 3 учитывает возможность инициации в момент t+1. Это имеет место, только если в момент t в разряде 1 вектора столкновения стоял 0 (или в момент t+1 в результате шага 1 в разряде 0 стоял 0). Если эта диаграмма должна охватить все возможные последовательности латентности, то, следовательно, нужно рассматривать обе возможности, то есть выполнение и невыполнение инициации. Это требует введения двух дуг исходящих из состояния соответствующему моменту времени t. Разумеется, всякая последовательность латентностей «пойдет» лишь по одной из них. Первая дуга относится к случаю, когда инициация не выполняется. Здесь вектор столкновений в момент t+1 будет вектор, полученный на шаге 1. Вторая дуга относится к новой инициации в момент t+1. В этом случае всякая дальнейшая инициация, выполняемая после момента t+1, должна избегать столкновений, как с инициациями, выполненными до момента t+1, так и с инициацией, произведенной в момент t+1. Но эти последние столкновения полностью определяются копией начального вектора столкновения. Связывание его операцией логического ИЛИ со сдвинутым вектором дает вектор, перечисляющий те и только те будущие моменты времени, в котором может наступить столкновений какого либо из этих двух видов.

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

Для таблицы занятости В диаграмма состояний имеет следующий вид (рисунок 12.17):

Рисунок 12.17.

В диаграмме имеются циклы, например цикл(4), в котором через любые четыре такта может быть выполнена новая инициация. В диаграмме также имеются циклы (3,8), (3,9), (3,10), (8), (4,8,3,8).

Модифицированная диаграмма состояний.

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

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

На рисунке 12.18 представлена модифицированная диаграмма.

Рисунок 12.18.

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

Процедура генерирования модифицированной диаграммы состояний:

1. В качестве начального состояния диаграммы принять начальный вектор столкновений.

2. Для любого необработанного состояния и каждого к такого, что к-й разряд соответствующего вектора столкновения равен 0 выполнить следующие шаги:

a) сдвинуть вектор столкновений на к разрядов влево, отбросив первые к разрядов и добавив к нулей справа;

b) произвести операцию логического ИЛИ с копией начального вектора столкновений;

c) полученное новое состояние соединить с текущим состоянием дугой с меткой к.

3. Добавить дугу с меткой ≥ d от любого состояния назад к начальному состоянию, где d – время вычисления для таблицы занятости.

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

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

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

Простой цикл – цикл, в котором любое состояние проходится не более одного раза за одно повторение цикла.

Лемма. Если в произвольной модифицированной диаграмме состояний имеется цикл с средней латентностью L, то имеется по меньшей мере один простой цикл со средней латентностью не большей L.

Если этот цикл простой, то лемма тривиальна. Если же он не является простым, то представляет собой некоторую комбинацию простых циклов. Допустим, цикл состоит из m простых циклов, из которых i -й проходится К(i) раз и имеет период Р(i) с S(i) состояниями (период цикла – сумма латентностей). Тогда средняя латентность определяется выражением:

Если бы лемма была ложной, то латентности всех простых циклов должны были бы превышать это среднее, то есть:

< , для любого j

Выберем цикл r так, чтобы латентность P(r)/S(r) была наименьшей по всем i, тогда

< 0

Так как K(i) ≥ 0 для любого i, то хотя бы один из членов должен быть отрицательным:

P(i)S(r)-P(r)S(i) < 0

Если это имеет место для i, то P(i)S(r)< P(r)S(i), что противоречит предположению относительно r. (Получается, что < .)

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

Процедура определения всех жадных циклов следующая:

1. Выбрать любое состояние из модифицированной диаграммы состояний.

2. Идти по последовательности дуг минимальной латентности, пока не встретится состояние, выбранное на шаге 1, либо пока не останется больше дуг.

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

4. Выбрать другое состояние и вернуться к шагу 2.

Правильность процедуры очевидна. Ей требуется самое большое N итераций, где N – число состояний диаграммы.

Лемма Средняя латентность любого жадного простого цикла меньше или равно числу единиц в начальном векторе столкновений. Пусть состояния составляющие жадный цикл обозначаются S(1), S(2),.., S(m), а дуги имеют латентности L(1),L(2),.., L(m) (рисунок 12.19).

Рисунок 12.19.

Пусть х(i) – общее число единиц в векторе столкновений для состояния S(i), Х – число единиц в начальном векторе столкновений. Для жадного цикла вектор столкновений для S(i) должен иметь L(i) левых единиц, за которым следует 0, в противном случае эта дуга не является жадной. Таким образом, в векторе столкновений для S(i+1) имеется самое большое х(i)- L(i) единиц из сдвинутого вектора для S(i) и Х единиц из копии начального вектора столкновений, то есть:

x(i+1) ≤ x(i)-L(i)+x

Тогда получим:

x(2) ≤ x(1)-L(1)+x

x(3) ≤ x(2)-L(2)+x ≤ x(1)-L(1)-L(2)+2x

…

x(m) ≤ x(m-1)-L(m-1)+x ≤ x(1)-L(1)- … - L(m-1)+ (m-1)x

Для замыкающей дуги получим:

x(1) ≤ x(m)-L(m)+x

или

x(1) ≤ x(1) - + mx

Отсюда:

= x

Левая часть – средняя латентность для данного цикла, а правая- число единиц в начальном векторе столкновений.

Эта лемма устанавливает верхнюю границу для средней латентности любого жадного цикла. Ранее доказанная лемма установила нижнюю границу для средней латентности любого цикла. Из этих лемм имеем:

Максимальное число меток в любой строке таблицы занятости ≤ MAL;

MAL ≤ средняя латентность любого жадного цикла(т.к. жадная стратегия не всегда оптимальна);

Средняя латентность любого жадного цикла ≤ число единиц в начальном векторе столкновений.

Таким образом:

Максимальное число меток в любой строке ≤ MAL ≤ число единиц в начальном векторе столкновений

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

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

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

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

§12.6. Генерирование таблиц занятости на основе циклов.

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

Определим множество G_с интервалов инициации данного цикла С как множество всех целых чисел i, таких, что интервал между некоторой парой инициаций (не обязательно последовательных) равен i. Если цикл латентностей С есть (L(1), L(2),.., L(k)), тогда < L(1),.., L(k), L(1),.., L(k), L(1),.. > эквивалентные последовательности латентностей, а Т(0),Т(1), Т(2), … - последовательность моментов инициации.

Здесь T(j)- начальный момент j-й инициации равен сумме латентностей предыдущих инициаций, то есть:

T(j)=

Тогда множество G_с записывается как

G_с = {T(i)-T(j), i>j }, где T(i) и T(j) принадлежат последовательности моментов инициации. Таким образом, G_с- множество интервалов между инициациями, когда инициации выполняются согласно циклу С. Для цикла (3,5,7) последовательностью латентностей будет <3,5,7,3,5,7,3,5,7,..>, последовательностью моментов инициации- [0,3,8,15,18,23,30,33,38,45, …], а множеством G_с – множество {3,5,7,8,10,12,15,18,20,22,23,25,…}. Например, число 22 принадлежит к множеству G_с, так как инициации наступают в момент времени 30 и 8.

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

Удобнее рассмотреть дополнительное множество Н_с = Z/G_с, где Z – множество всех целых неотрицательных чисел. Если i принадлежит к множеству Н_с, то допустимо (хотя и не обязательно) разделять две метки в строке i тактами. Аналогично, допустимо иметь как 0 так и 1 в i-ом разряде начального вектора столкновений. Запишем строку таблицы занятости как множество {Z(1),Z(2),..}, если метки стоят в ней в момент Z(i).

Пусть дан цикл С. Любая строка в любой таблицы занятости, которая поддерживает этот цикл должна быть представлена как {Z(1),Z(2),..}, в которой для любых i,j |Z(i)-Z(j)| H_c (*)

Если F – множество запрещенных латентностей таблицы занятости, то цикл с будет справедливой для нее последовательностью инициации, только если F является подмножеством H_c, что равносильно F G_с = .

Доказательство очевидно и вытекает из предыдущих лемм. Так как множество H_c и G_с бесконечны, то их трудно использовать на практике. Заменим H_c и G_с на конечные множества.

Для любого i G_с

G_с mod P = {i mod P}/{0},

H_c mod P = Z_p - G_с mod P,

где Р- период цикла (то есть сумма латентностей), а

Z_p = {0,1, …, Р-1}

Множество G_с mod P – это множество латентностей между инициациями, разделенными самое большее Р тактами, которое повторяется с периодом Р.

Для цикла (3,5,7) период Р=15, множество G_с mod P = {3,5,7,8,10,12},

а H_c mod P ={0,1,2,4,6,9,11,13,14}.

Часто оказываются полезными следующие свойства этих множеств:

1. Если g G_с mod P, то для любого i ≥ 0 (g+ip) G_с

2. Если g 0, то g G_с mod P, только если (р-g) G_с mod P

3. Если h 0, то h H_c mod P, если (р-h) H_c mod P.

Теперь можно определить набор правил для построения таблицы занятости.

Пусть Z_p = {0,1, …, p-1}. Два числа i,j из Z_p совместимы по отношению к H_c mod P, если |i-j| mod P H_c mod P.

Классом совместимости относительно H_c mod P называется любое подмножество Z_p, все пары элементов которые совместимы.

Максимальный класс совместимости относительно H_c mod P – это класс, который не является подмножеством никакого другого класса совместимости.

Например, для цикла (3,5,7) числа 9 и 13 совместимы, так как |13-9| mod 15 = 4 H_c mod P. Множество {0.9.13} является классом совместимости, тогда как множества {0,9,11,13},{5,6,7} и {0,1,2} является максимальными классами совместимости.

Если некоторое множество целых чисел {Z(1),Z(2), …} совместимо, то оно автоматически удовлетворяют условиям (*) и может служить строкой некоторой таблицы занятости, поддерживающей этот цикл. Верно и обратное: множество индексов любой строки таблицы занятости, поддерживающей данный цикл, должно быть совместимым. Таким образом, приходим к следующему:

Теорема: Для любого цикла С с периодом Р любая таблица занятости, поддерживающая этот цикл как последовательность инициаций, должна иметь строки вида:

{Z(1)+ i(1)P, Z(2)+ i(2)P, … }, где {Z(1), Z(2), … }- некоторый класс совместимости H_c mod P, а i(1),i(2),.. – произвольные числа.

Доказательство следует из предыдущих лемм.

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

Максимальные классы совместимости определяются с помощью перечислительных алгоритмов, так как отношение совместимости не транзитивно.

Рассмотрим пример, в котором при обнаружении несовместимости, множество расщепляется на два новых, ни одно из которых не содержит этой несовместимости. Хотя все множества, отыскиваемые алгоритмом, совместимы, некоторые из них являются подмножествами других и должны быть обращены. Алгоритм вычисляет только те максимальные совместимые множества, которые содержат Z(1) (в типичном случае 0).

Расширение предыдущих лемм показывает, что если некоторое подмножество S является совместимым множеством, то таким же будет и подмножество S' = { (S+a) mod P}; 1≤ a ≤ P-1, S S'.

Следовательно, после завершения базового алгоритма остальная часть максимально совместимых подмножеств вычисляется простым сложением.

Исходное множество – все числа меньше Р. Определяем совместимость этого множества и 0 (всегда принадлежит множеству H_c) то есть |Z/{0}| относительно H_c mod P. Получаем само множество H_c mod P. Далее определяем совместимые множества в H_c mod P по следующей процедуре.

Процедура: определить множества (S,j).

(вычисляет все совместимые множества S; j – элемент в S)

1. Если j ≥ P, то добавить S к множеству всех совместимых подмножеств и выйти из процедуры.

2. Если j S, то j:= j+1 и идти к пункту 1.

3. Если j совместимо со всеми остальными элементами S, то j:= j+1 и идти к пункту 1.

4. Если U – множество всех элементов S, несовместимых с j, то:

Определить множества (S-{j},j+1)		Comment:
	вернуться к началу процедуры
Определить множества (S-U,j+1)

5. Удалить из множества совместимых подмножеств те, которые являются подмножествами других.

6. Для любого множества и для любого числа i в области построить новое множество, любой элемент, которого является суммой по модулю Р числа i и элементов в исходном множестве.

Например, для цикла (3,5,7) процедура имеет вид, показанный на рисунке 12.20:

Рисунок 12.20.

Для получения всех максимальных совместимых подмножеств надо к полученным максимально совместимым подмножествам прибавить по mod P некоторое число i из .

Например, из {0,2,4,13} образуется {1,3,5,14}, {2,4,6,0}, {3,5,7,1}, … Немаксимальные подмножества не учитываются.

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

Время ступень
	х	х	х
		х		х		х		х

Время Ступень
	х	х	х
	х	х	х
		х	х	х

Время Ступень
	х		х		х		х
		х				х		х
			х				х		х
								х		х

{0,2,4,6} {0,4,6}+1 {0,4,6}+2 {4,6}+3

Время Ступень
			х		х
		х		х		х
	х		х				х

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

Рисунок 12.21.

Здесь одни строки являются максимально совместимыми множествами, а другие – подмножествами этих множеств. Некоторые строки имеют постоянное смещение.

Совершенные циклы.

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

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

Циклы, для которых верхняя граница равна 100 % называется совершенными. Показатель использования ступени – это отношении числа меток в соответствующей строке таблицы занятости к средней латентности цикла. Но, в соответствии с вышеприведенной теоремой, любая строка в таблице занятости, поддерживающей тот или иной цикл должна относиться к классу совместимости по отношению к H_c mod P. Отсюда получим:

Теорема. Для любого цикла С максимальное возможное использование любой ступени (таблицы занятости), поддерживаемого этот цикл не превышает m/L.

m- число элементов в наибольшем классе совместимости по отношению к H_c mod P, L- средняя латентность цикла.

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

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

Цикл является совершенным, только если m=L. Например, цикл (3,5,7) со средней латентностью равной 5 имеет самое большее 4 элемента в любом классе совместимости и, следовательно, максимальное использование им ступеней составляется 80 %. То есть он не совершенен, а вот циклы (5,3) и (1,7), которые также поддерживаются этой таблицей занятости (таблица А) совершенны, так как средняя латентность их равна 4.

Лемма. Если цикл постоянный, то есть имеет вид (L), то он совершенен. Для такого цикла H_c mod P является множеством {0,1,2,.., L-1}, а множество {0,1,2,.., L-1} совместимо. Оно имеет L элементов и таким образом граница использования L/L =1.

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

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

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

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

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

Цикл (1,5); <1,5,1,5,1,5,…..>последняя латентность

[0,1,6,7,12,13,18,19,24,….] последние инициации

[1,5,6,7,11,12,…] -Gc

[1.5]-Gc mod6

[0.2.3.4] -Hc mod6

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

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

Доказательства приводится путем следующего построения. Пусть метки в строках приходятся на индексы а(1), а(2),… и пусть с(1),с(2),… значения, вход в класс совместимости (не обязателен в порядке возрастания). Начнем с первого элемента или множества. Если а(1)< c(1), то вставим с(1)-а(1) входных задержек перед первой меткой в этой строке; все метки справа тоже передвинутся на с(1)-а(1) позиций вправо.

Если а(1)>с(1), то а(1)-с(1)складывается с любым элементом класса совместимости по mod P (Р- период цикла), что создает новый, но эквивалентный класс используемый в дальнейшем, оставшиеся метки просматривают, затем слева на право. Если а(i)< c(i), i-я метка задерживается на с(i)-а(i) синхроимпульсы, а все метки в этой строке справа от i-й, передвигаются вправо. Если же а(i)>с(i), то достаточно большое краткое периода цикла Р добавляется к с(i), чтобы отправить это неравенство. Метка а(i) задерживается затем на соответствующую разность.

Пример (рисунок 12.22).

Пусть задана следующая таблица занятости:

	х		х			х
		х	х		х
			х	х

Граница латентности=3

Оптимальный цикл=(4)

MAL=4

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

Запрещенные латентности {0,1,2,3,5}

Вектор столкновений =111101

(4)

Модифицированная диаграмма состояний.

Рисунок 12.22.

То есть оптимальным является цикл (4), нижняя граница латентности равна 3 и латентность не достигает нижней границы.

Возьмем цикл (1,5).

Цикл (1,5); <1,5,1,5,1,5,…..>- последовательность латентностей.

[0,1,6,7,12,13,18,19,24,….] - последовательность инициаций.

[1,5,6,7,11,12,…] –множество Gc

[1,5]- множество Gc mod6

[0,2,3,4] - множество Hc mod6

Для цикла (1,5) Hc mod6 равно {0,2,3,4}. Используя приведенный выше алгоритм, определим все совместимые подмножества (Рис.12.23).

Рисунок 12.23.

В число максимальных классов совместимости цикла входят классы{0.2.4},{0,3}.

Модифицируем таблицу занятости в соответствии с классами совместимости. В первой строке таблиц занятости стоят три метки в позициях{0,2,5}. При сравнении с классом {0,2,4} обнаруживаем, что первые 2 элемента уже совпадают а(1)=0=с(1) и а(2)=2=с(2). Но с(3)=4 меньше а(3)=5. Прибавление периода Р=6 к с(3) дает 10-число больше чем а(3).Задержка а(3) на 5 периодов синхронизации дает первую строку матрицы. В строке 2 а(1)=1 больше чем с(1) из {0,2,4}. Поэтому мы строим эквивалентный класс совместимости{1,3,5} и задерживаем вторую метку на один такт. Третья метка становится на свое место. Третья строка таблицы замен приводится к классу {2,4} путем задержки на один такт второй метки. Заметим, что{2,4} не только подмножество {0,2,4}, но еще и класс совместимости.

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

В результате получим следующую таблицу занятости (рисунок 12.24):

	х		х	d		d	d	d	d	d	х
		х	d	х		х
			х	d	х

Граница=3

Оптимальный цикл = (1,5)

MAL=3

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

d – задержка

Рисунок 12.24.

Описанная структура позволяет разработчику теоретически выбрать любой цикл, средняя латентность которого не меньше, чем максимальное число меток в строке и откорректировать затем таблицу занятости так, чтобы она допускала этот цикл. Сюда относятся и постоянные циклы, в частности, постоянные циклы (L), где L=max числу меток в строках таблицы. Такие циклы совершенны, что приводит к таблицам занятости, у которых MAL достигает нижней границы и у которых хотя бы одна ступень конвейера используется на 100%.

Хотя все это теоретически возможно, в реальных системах встречаются ограничения, которые препятствуют достижению оптимальной производительности:

1) Не всегда фиксаторы являются регистровыми файлами (несущественное ограничение - всегда можно обойти).

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

Это должно учитываться при разработке конвейера.

Дата добавления: 2014-12-26