135850 (722689), страница 2

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

Текст из файла (страница 2)

m3║ │ 0│ 0│ 0│ │ 0│

──╫──┼──┼──┼──┼──┼──┤

m4║ 0│ 0│ 1│ 1│ │ 0│

──╫──┼──┼──┼──┼──┼──┤

m5║ 0│ 1│ 0│ 0│ │ 0│

──╫──┼──┼──┼──┼──┼──┤

m6║ │ 0│ │ │ 0│ 1│

──╨──┴──┴──┴──┴──┴──┘

- 7 -

Структура вычислителя:

┌────────────────────────────────┐

══>╡I1 │

│ │

══>╡I2 ОА D╞══>

│ │

┌──/C rO├──>

│ │ │

│ │z p umB uwA uwB uiA urO uwO │

│ └┬──┬──A───A───A───A───A───A─────┘

│ │ │ │ │ │ │ │ │

│ │ │ │ │ │ │ │ │

│ ┌V──V──┴───┴───┴───┴───┴───┴─────┐

│ │z p y1 y2 y3 y4 y5 y6 │

│ │ │

┴──/C │

│ УА │

──>┤rI │

└────────────────────────────────┘

УА должен выполнять следующий алгоритм автоматного типа,

представленный в виде блок-текста:

m1{xxxx10}

g1<>

m2{111x10}

m3{x000x0}

<>

g2<>

m4{0011x0}

<>

m5{0100x0}

<>

m6{x0xx01}

<>

_МИКРОПРОГРАММИРОВАНИЕ. ОПРЕДЕЛЕНИЯ.

МИКРООПЕРАЦИЯ - базисное (элементарное) действие, необ-

ходимое для получения (вычисления) значения одной или более

переменных.

Микрооперация присваивания В=А означает, что переменные

левой части получают значения выражения из правой части.

Всегда разрядность левой части равна разрядности правой час-

ти. При этом биты, расположенные на одной и той же позиции в

левой и правой частях, равны.

Неиспользуемые разряды в левой части и произвольные зна-

чения в правой части микрооперации присваивания обозначаются

(х). Например:

(В[7],x,B[6..0]) = (A[7..0],x)

означает арифметический сдвиг влево на один разряд 8-разряд-

ного числа с присваиванием произвольного значения младшему

разряду и с потерей старшего после знака разряда. А, напри-

мер, микрооперация

(B[7..0],d) = (A[7],A[7..0])

означает арифметический сдвиг вправо на один разряд.

Микрооперация

(p,S[3..0]) = A[3..0] + B[3..0] + q

описывает действие, выполняемое стандартным 4-разрядным сум-

матором, если ( А,В,q ) являются его непосредственными входа-

ми, а ( р,S ) - выходами.

Микрооперация ( : ) - двоеточие - означает запоминание

(изменение значения) в памяти устройства. Переменная типа па-

мять сохраняет свое значение между двумя очередными присва-

иваниями.

- 8 -

Микрооперации всегда входят в состав микрооператоров.

МИКРООПЕРАТОР - набор взаимосвязанных микроопераций (или

одна микрооперация ), выполняемых одновременно и необходимых

для получения одного или более значений. Например:

( e,D:) = R1 + R2 + c

Фрагмент аппаратуры, реализующей этот микрооператор, мог бы

быть, например, таким:

┌───┐

c │MUX│

┌┬──┬┐ │ │ ┌───┐

││T │├───>┤0 │ ┌────┐ │MUX│ D

└┴──┴┘ ──>┤1 │ │ SM│ │ │ ┌┬──┬┐

──>┤А ├───>┤cr │ ═══>╡0 ╞═══>╡│RG│╞══>

├───┤ │ S╞═════>╡1 │ └┴──┴┘

R1 │MUX│ │ │ ═══>╡А │

┌┬──┬┐ │ │ │ │ └───┘

││RG│╞═══>╡0 ╞═══>╡I1 │ ┌───┐

└┴──┴┘ ══>╡1 │ │ │ │MUX│

══>╡А │ │ │ │ ├────────────>e

├───┤ │ p├─────>┤0 │

R2 │MUX╞═══>╡I2 │ ───>┤1 │

┌┬──┬┐ │ │ └────┘ ───>┤А │

││RG│╞═══>╡0 │ └───┘

└┴──┴┘ ══>╡1 │

══>╡А │

└───┘

Имена всех переменных, используемых в этом микрооператоре,

означают выполнение микроопераций коммутации ( транспортиров-

ки ). Значения переменных коммутируются на входы суммматора,

а результат суммирования - в места расположения переменных.

МИКРОБЛОК - набор микрооператоров, выполняемых одновре-

менно ( в одном такте ) и синхронно. В одном микроблоке любо-

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

Синхронность означает, что во всех микрооператорах одно-

го микроблока используется только "старое" значение памяти.

Например:

{ (p,A):= A + B

(C,r):= A + D }

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

же старое значение А.

В то же время в микроблоке:

{ (C,x):= A + D

(x,A)= C + B }

в первом микрооператоре используется новое значение А , а во

втором - старое значение С. Разумеется, эти два действия вы-

полняются одновременнo на двух разных сумматорах.

При реализации микроблока { A:= B ; B:= 0 } обязательна

синхронная реализация В:=0 ( хотя обычно такое действие проще

реализовать асинхронно, но это приводит к ошибке ). Другой

правильный вариант: можно выполнить В:=0 асинхронно, но в

следющем такте.

Всегда предполагается, что предикат вычисляется вместе

(в одном такте) с тем микроблоком, за которым непосредственно

следует его использование.Таким образом, здесь, также как и в

микроблоке, используется старое значение памяти, существовав-

шее перед входом в микроблок. Это связано с особенностями

взаимодействия ОА и УА. Например:

- 9 -

█ █

█ CT:=(╪0)█ █ CT:=(╪0)█

█ █

│ │

┌────V───┐ ┌────V───┐

m1│ CT:=3 │ m1│ CT:=3 │

└────┬───┘ └────┬───┘

┌──────>│ ┌──────>│

│ ─V─ │ ─V─

│ / \ =0 │ / \ =0

│ ─> │ ─>

│ \___/ │ \___/

│ │╪0 │ │╪0

│ ┌────V───┐ │ ┌────V───┐

│m2│........│ │m2│........│

│ │ │ │ │ │

│ │CT:=CT-1│ │ │CT:=CT-1│

│ └────┬───┘ │ └────┬───┘

└───────┘ │ ┌────V───┐

│m3│........│

│ └────┬───┘

└───────┘

В первом случае цикл будет выполнен 4 раза; во втором - если

в микроблоке m3 нет операций, модифицирующих СТ, - 3 ра-

за. ( Обратите внимание на начальное значение СТ!)

МИКРОКОМАНДА - набор сигналов, поступающий из УА в ОА и

интерпретируемый как управляющий,т.е. необходимый для выпол-

нения всех микроопераций одного микроблока. Сигналы, входящие

в микрокоманду, могут принимать участие в микрооперациях и в

качестве информационных.

Микрокомандой также иногда называют слово управляющей

памяти (обычно ПЗУ), являющееся частью УА. Для различения

этих понятий слово управляющей памяти будем называть МИКРО-

ИНСТРУКЦИЕЙ.

МИКРОПРОГРАММА СОДЕРЖАТЕЛЬНАЯ - алгоритм, представленный

в виде микроблоков и предикатных блоков в одной из принятых

форм, например, в виде блок-схемы или блок-текста.

МИКРОПРОГРАММА КОДИРОВАННАЯ - аппаратная форма содержа-

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

память.

_КАНОНИЧЕСКАЯ СТРУКТУРА ОПЕРАЦИОННОГО АВТОМАТА

В общем случае каноническая структура операционного ав-

томата имеет вид:

███████████████████████████████████████████████████████████

█ █

█ ┌──────────┐ ┌┬──────┬┐ ┌──────────┐ ┌───────┐ █

██>╡коммутация│ ││память││ │коммутация│ │функции▐███

│ ▐███>╡│ │▐██>╡ ▐██>╡ │

██>╡ │ ││ ││ │ │ │ ▐███>

└─A────────┘ ─/─┴┴───A──┴┘ └──A───────┘ └──A────┘

█ ┌─┐│CC █ █ █

█ SYN─>┤&├┘ █ █ █

█ ┌┤ │ █ █ █

█ yC│└─┘ █ █ █

└────────────────────────────────────────────────┘

сигналы управления

Столь четкого разграничения операций на зоны (память, комму-

тация, функции) может и не быть. Например, такие широко ис-

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

коммутацией, либо интегрируются с регистрами хранения.Также

часто интегрируются с хранением функции инкремента и

- 10 -

декремента (счетчики обычные и реверсивные).

Особо выделим сигнал yС, управляющий доступом синхросиг-

налов в ОА. Такой вариант управления, называемый условной

синхронизацией, позволяет запретить любые изменения памяти ОА

в каком-либо такте. Причем, если рабочим является срез (зад-

ний фронт) сигнала синхронизации, то используется элемент И,

как и показано на рисунке.Если же рабочим является фронт (пе-

редний фронт) сигнала, то используется элемент ИЛИ. (Первый

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

рабочим.)

_ОПТИМИЗАЦИЯ ОПЕРАЦИОННОГО АВТОМАТА

При проектировании вычислительного устройства основными

являются ограничения на:

1)- время вычисления;

2)- объем аппаратуры, реализующей вычисления;

3)- тип применяемых базовых функций.

ОПТИМИЗАЦИЯ АПППАРАТУРЫ ПРИ СОХРАНЕНИИ МИНИМАЛЬНОГО ВРЕМЕНИ

Алгоритм функционального типа обладает максимальным по-

тенциальным параллелизмом (в рамках данной алгоритмической

идеи), и,следовательно, его реализация в виде КС обладает

максимальным быстродействием по сравнению с любыми другими

вычислителями. Невозможность реализации вычислителя в виде КС

может быть обусловлена следующими причинами:

- слишком велик объем аппаратуры КС;

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

статическим отображением входных объектов на выходные: это

исключает возможность работы с объектами, которые "ведут се-

бя" более сложно во времени; невозможно также реализовать

принципиально рекуррентные алгоритмы (см.,например,алгоритм

Евклида для нахождения НОД).

Тем не менее, если формально алгоритм функционального

типа может быть записан, то проектирование устройства надо

начинать с записи именно такого алгоритма.

Минимизация аппаратуры "сложной" КС с переходом на про-

цедурный вариант реализации связан с "экономией" числа опера-

ционных элементов, т.е. со слиянием некоторых из них в один

функциональный модуль, выполняющий эти операции по очереди.

Такое решение потребует запоминания всех переменных (входных

и выходных),связанных с выполнением этих операций. Требуется

также управление памятью, связанной с этим функциональным мо-

дулем, а также - может быть - управление самим функциональным

модулем, если он объединил существенно различные функции.

Переход к процедурной реализации и, следовательно, к

дискретизации времени неизбежно увеличит время вычисления од-

ного результата - даже при реализации структуры подобной КС.

При этом, как ни странно, может уменьшиться время следующих

друг за другом вычислений именно за счет дискретизации време-

ни и применения так называемых "конвейерных" вычислений - но

об этом речь пойдет в другом курсе.

Рассмотрим возможность сокращения аппаратуры без увели-

чения времени решения, достигнутого в алгоритме функциональ-

ного типа. Сопоставим схеме устройства, реализующего алгоритм

функционального типа, простую модель в виде направленного

графа. Вершины графа будут соответствовать операциям, а дуги

- переменным алгоритма. Назовем такой граф сигнальным (графом

потоков данных). Заметим, что сигнальный граф всегда будет

ациклическим.

Минимальность времени вычислений сохранится, если совме-

щать в один функциональный модуль операции, которые располо-

жены на одном и том же пути в сигнальном графе, либо на аль-

тернативных путях решения.

- 11 -

_МИНИМИЗАЦИЯ АППАРАТУРЫ

Может оказаться, что на одном пути в сигнальном графе

расположены операции, плохо или вовсе не совмещаемые друг с

другом (т.е. совмещение не дает экономии в аппаратуре функци-

онального модуля). Возможно также, что проведенная минимиза-

ция, сохраняющая минимальное время, не позволяет выполнить

ограничение на объем аппаратуры. В таком случае необходима

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

сигнального графа. Минимизация должна быть взаимосвязанной по

всем компонентам ОА: по памяти, функциональным модулям и ком-

мутации.

В настоящее время процедуры минимизации не формализованы

и сводятся к перебору "правдоподобных" вариантов.

Можно предложить следующую последовательность действий:

1)- все "похожие" функции (операции) реализовать на одном

функциональном модуле, например, все суммирования выполнять

на одном сумматоре;

2)-скорректировать алгоритм так, чтобы в одном микроблоке не

выполнялось более одной операции на одном и том же функци-

ональном модуле;

3)- минимизировать память автомата, т.е. число запоминаемых

промежуточных переменных;

Выполнение этих этапов может привести к усложнению ком-

мутации, а значит, и к увеличению этой компоненты в аппарату-

ре ОА. Если ограничение по объему аппаратуры все еще наруше-

но, то повторить этапы 1 - 3 с другим вариантом объединения

функциональных модулей и памяти.

При реализации ОА - во избежание ошибок -необходимо бук-

вально следовать описанию алгоритма, но в то же время, при

проектировании самого алгоритма надо представлять себе реали-

зацию микроблоков. Реализация одних и тех же вычислений может

быть существенно различной по объему аппаратуры.

Например, вычисления в цикле потребуют реализации:

Характеристики

Список файлов реферата