Кодирование микроопераций

Теперь рассмотрим, как можно использовать разряды поля микроопераций (МО). Различают [2] три способа кодирования поля микроопераций:

□ горизонтальный;

□ вертикальный;

□ смешанный.

Ранее мы говорили, что управляющий автомат проектируется для выдачи в заданной последовательности наборов микроопераций из некоторого наперед определенного множества микроопераций Y={y _1, у ₂,..., у_n}.

При горизонтальном способе кодирования каждой микрооперации у_i {y ₁,..., y_n}ставится в соответствие разряд поля микроопераций микрокомандного слова. В этом случае количество разрядов поля микроопераций N равно числу n различных микроопераций, вырабатываемых УА.

Достоинствами горизонтального способа кодирования являются:

□ возможность формирования произвольных микрокоманд из заданного набора микроопераций;

□ простота реализации схем формирования микроопераций, фактически — их отсутствие, т. к. выход каждого разряда поля микроопераций регистра микрокоманд является выходной линией УА — соответствующей микрооперацией.

Недостаток — чаще всего неэффективно используется память микрокоманд. Действительно, если число микроопераций УА составляет 80, а количество выполняемых в микрокоманде микроопераций — не более 6 (типичные характеристики для УА АЛУ), то в восьмидесятиразрядном поле микроопераций каждого микрокомандного слова будет не более 6 единиц.

(Страница114)

При вертикальном способе кодирования в поле микроопераций помещается номер выполняемой микрооперации. При этом количество разрядов N, которое следует предусмотреть в поле микроопераций, определяется выражением: N=k ≥log₂ n. Достоинство способа в экономном использовании памяти микрокоманд. Недостаток — в невозможности реализовать в микрокоманде более одной микрооперации.

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

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

Вертикальный и горизонтальный способы кодирования — две крайности. Истина обычно лежит "посередине". Рассмотрим смешанный способ кодирования, идея которого состоит в следующем. Если во всех микропрограммах, реализуемых УА, нет микрокоманды с большим, чем s, числом микроопераций, то в поле микроопераций можно предусмотреть s подполей разрядностью k, в каждом из которых помещать номер нужной микрооперации. Такой способ позволяет в любой микрокоманде реализовать произвольную s-ку микроопераций, т. е. сохранить гибкость горизонтального кодирования, при возможном значительном сокращении разрядности поля микроопераций: N=s*k=s log₂ n. Так, для приведенного выше примера (п= 80, s =6) определим k=7≥log₂80, N= 7*6=42 (тоже, конечно, немало), что позволит почти вдвое сократить разрядность поля микроопераций по сравнению с горизонтальным способом кодирования.

Эффективность применения смешанного кодирования существенно зависит от значения s, которое может лежать в диапазоне 1≤ s≤п. При s=1 имеем случай вертикального кодирования, при s = n — горизонтального.

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

С целью сокращения разрядности полей микроопераций множество микроопераций Y разбивается на подмножества Y₁, Y₂,..., Y_p, такие, что

Каждое подполе поля микроопераций кодирует микрооперации только одного подмножества . Поскольку разрядность k_i каждого из подполей может быть меньше k. Очевидно, при "удачном" (пока скажем так) распределении микроопераций по подмножествам можно будет реализовать любую операторную вершину ГСА микропрограммы с помощью одной микрокоманды (т. е. достигнуть быстродействия, характерного для горизонтального способа кодирования), при этом значительно уменьшить разрядность поля микроопераций даже по сравнению с каноническим способом смешанного кодирования.

"Удачное" разбиение исходного множества микроопераций связано с понятием совместимости (несовместимости) микроопераций [7]. Некоторые из используемых в микропрограмме микроопераций могут выполняться параллельно во времени, в то время как другие — только последовательно. Свойство совокупности микроопераций, гарантирующее возможность их одновременного выполнения, называется совместимостью. Микрооперации, не обладающие указанным свойством, называются несовместимыми.

Рассматриваются два аспекта совместимости. Совместимость, обусловленная содержанием операторов, реализуемых под действием микроопераций, называется функциональной. Примером двух функционально несовместимых микроопераций могут служить следующая пара: (у₈: Сч n:=0) и (y₁₅: Сч n:= Сч n- 1) и вообще любые микрооперации, присваивающие различные значения одной и той же переменной.

Если невозможность одновременного выполнения микроопераций связана с ограничениями возможностей структуры операционного автомата, то такая несовместимость называется структурной. Например, операторы (Рг C=Рг А) и (Рг D:=Рг В) функционально совместимы, но если в конкретной структуре ОА связь между этими регистрами осуществляется через общую магистраль (шину), то они структурно несовместимы.

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

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

Если рассматривать в качестве совместимых только те микрооперации, которые размещаются в одной операторной вершине реализуемых алгоритмов, а все остальные считать несовместимыми, даже если их можно выполнить одновременно в структуре ОА (но не требуется при реализации данных алгоритмов), то p → s, эффективность кодирования будет значительно выше. Правда, если потребуется модифицировать реализуемый алгоритм или добавить еще группу алгоритмов для реализации, и в одной операторной вершине окажутся микрооперации, включенные ранее в одно подмножество, придется заново перепроектировать УА.

Разработано несколько формальных методов [7] разбиения множества микроопераций на подмножества. В простейшем случае можно воспользоваться методом "прямого включения". Рассмотрим пример проектирования УАПЛ по заданной микропрограмме.