Козин И.В. Организация ЭВМ и систем

Подождите немного. Документ загружается.

В алгоритмы вычисления сложных функций наряду с микроопера-

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

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

граммой. По этой причине для реализации алгоритма вычисления сложных

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

граммам более простых операций.

Признаком того, является ли микропрограмма частью алгоритма вы-

числения сложной функции или используется самостоятельно, может слу-

жить специальное одноразрядное слово МР, если считать МР = 0 в случае,

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

случае. Значение МР должно присваиваться перед началом вычисления

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

рая входит в состав алгоритма вычисления сложной функции. Проверка

значения МР осуществляется после окончания каждой такой операции в

процессе вычисления сложной функции. После окончания операции вычис-

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

стых операций осуществлять эту проверку нет необходимости.

В рассмотренном в [2] примере вычислени я функции

каждая

подпрограмма используется только один раз. Для другой функции возможна

иная ситуация.

Для функции

()

Fx x

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

рентной формуле (1) и

() ( )

111

nnn

aFF

−

где n =1,2,…,

()

Граф-схема

этого алгоритма приведена на рис. 5. Легко заметить, что в алгоритме три-

жды используется операция умножения (вершины 8, 9, 12).Операцию, за-

данную в вершине 10, выгоднее выполнять по другой микропрограмме. Ал-

горитм содержит также одну операцию деления (вершина 13) и одну опе-

рацию сложения (вершина 16). Так как числа z и n здесь целые, можно счи-

тать, что в вершинах 11 и 15 задана микрооперация счета.

При многократном использовании в алгоритме одной и той же опера-

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

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

увеличить на единицу значение специального слова (счетчика числа вхож-

дений в подпрограмму) и избрать дальнейший путь в микропрограмме в за-

висимости от полученного значения этого слова. Число разрядов такого

слова равно

][

,log

где N – общее количество вхождений в данную под-

программу.

На рис. 6 приведена микропрограмма, соответствующая алгоритму,

изображенному на рис. 5. В вершине 2 здесь присваиваются исходные зна-

чения переменных. Слову RG6(0:16) – значение

, слову RG3(0:15) – зна-

чение

, слову RG4(0:15) – значение x, которое предварительно было при-

своено полю RG(1:16) слова RG(0:16), слову CT1(0:15) присваивается на-

чальное значение числа n = 1. В вершине 3 осуществляется пересылка опе-

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

([2 , рис. 2.3]) и присваивается начальное значение слову CT2, используе-

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

случае это слово имеет два разряда T1 и T2, значения которых проверяются

в вершинах 7, 8, 13. При втором вхождении в подпрограмму умножения

реализуется операция x·a. При этом значение множителя оказалось при-

своено полю RG(1:16) слова RG(0:16) после первого умножения, а новое

значение множимого присваивается в вершине 9. После второго умножения

в вершине 14 результат присваивается слову RG5(0:15). В вершине 15 слову

RG присваивается текущее значение n. В вершине 10 слову CT3 присваива-

ется значение 2n, в вершине 11 это число увеличивается на единицу, а в

вершине 12 результат присваивается слову RG1. Значение множителя для

третьего умножения присвоено полю RG(1:16) слова RG(0:16) в вершине 16.

После третьего умножения результат присваивается слову RG1 (вершина

18), играющему роль делителя в микропрограмме деления ([2 , рис. 2.4]), а

полю RG(1:16) слова RG(0:16), играющего роль делимого в вершине 20,

присваивается значение a, вычисленное в вершине 14. В вершине 22 про-

веряется на нуль величина общего члена разложения. Если он не равен ну-

лю, то в вершине 23 его значение присваивается слову RG6 и, кроме того,

используется в вершине 24 в качестве одного их слагаемых. В вершине 23 в

качестве второго слагаемого для вершины 24 слову RG1 присваивается те-

кущее значение F

. Результат сложения присваивается слову RG3 в вершине

26 в качестве нового значения F

. В вершине 27 текущее значение n увели-

чивается на единицу. В вершине 28 результат вычисления функции при-

сваивается полю RG(1:16) слова RG(0:16).

Если бы в этой микропрограмме и другие подпрограммы использова-

лись неоднократно, то для подсчета числа вхождений в них наряду со сло-

вом CT2 нужно было бы взять аналогичные слова с соответствующим чис-

лом разрядов.

Сказанное позволяет представить алгоритм вычисления функции shx

в виде рис.6.

В рассматриваемом примере негласно полагалось, что операнды хра-

нятся в ОП в прямом коде. Следует иметь в виду, что законченная микро-

программа любой операции в общем случае имеет три части:

1) преобразование кода из вида, хранимого в ОП, к виду, используе-

мому в операции;

2) выполнение собственно операции;

3) преобразование кода из вида, используемого в операции, к виду,

хранимому в ОП.

При использовании микропрограмм в составе более сложной опера-

ции первая или третья части микропрограммы или даже обе эти части

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

Это объясняется тем, что внутри микропрограммы обращение к ОП не

производится.

Рис.

Начало

RG6 := x

RG3 := x

RG4 :=RG(1:16

)

CT1 := 1

CT2 := CT2+1

Микропро-

грамма

умно

жения

RG(1:16) := RG4

RG1 := RG6(0:15)

CT2 := 0

RG5 := RG(1:16)

Микропро-

грамма

0 1

Конец

RG(1:16) := RG3

RG := 0.CT1

RG1 := RG4

CT3 := RG(1:16)

CT3 := CT3+1

RG1 := CT3

RG1:= RG(1:16)

Микропро-

грамма

деления

RG(1:16) := RG5

Микропро-

грамма

сложения

RG1 := RG3

RG6 := RG(1:16).0

RG3 := RG(1:16)

RG =0

Да

CT1 := CT1+1

Нет

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

микропрограмм сводится к перечислению в множестве S слов с попарно

различными идентификаторами, причем, если два слова с одинаковыми

идентификаторами имеют разную длину, то в множестве S вводится только

слово с максимальной длиной и считается, что слово меньшей длины может

быть представлено в большем формате. В частности, на рис. 6 в микропро-

грамме умножения используется слово RG(0:16), а не слово RG(0:15), как

это имеет место на рис. 2.3 в [2]. При этом поле RG(0:1) слова RG использу-

ется для представления знака числа.

Множество Y микроопераций, используемых в микропрограммах, по-

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

ритмов операторов присваивания, представляющих микрооперации.

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

микропрограммах.

3.4. Разработка объединенной микропрограммы работы АЛУ

Процессор состоит из АЛУ и УЦУ.

В объединенном списке микроопераций, используемых в микропро-

граммах минимального набора операций АЛУ, для унификации формы за-

писи различных операций и форматов одноименных слов следует по срав-

нению с рис. 2.3 из [2] изменить три микрооперации:

- для вершины 2 вместо микрооперации RG2 := RG нужно использо-

вать микрооперацию RG2 := RG(1:16).0;

- для вершины 6 вместо микрооперации

()

21:15:

() ( )

()

115.21:15

RRG RG

использовать микрооперацию RG2(1:15) :=

=R1(RG(16).RG2(1:16), а вместо микрооперации

()

1:0

в вершине 11 ис-

пользовать микрооперацию RG(0:1) := 11.

Благодаря этим изменениям значение числовой части результата каж-

дой операции присваивается полю RG(2:16) слова RG, а нулевой и первый

разряды этого слова используются для представления знака числа. Кроме

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

над двумя операндами в АЛУ значение первого операнда присваивается по-

лю RG(1:16) слова RG, а значение второго операнда – слову RG1. При вы-

полнении этого условия перед началом сложения и вычитания необходимо

произвести присваивание RG(0) := RG(1), перед началом умножения нужно

осуществить передачу RG2 := RG(1:16).0, а перед делением – микроопера-

ции RG2(0):= RG(1) и RG(0:1):= 00.

В списке слов, использованных в АЛУ, слову RG1 следует приписать

тип IL, а слову МР тип L.

В объединенную микропрограмму работы АЛУ следует включить

микрооперации MP:=0 и MP:=1, отсутствующие в микропрограммах мини-

мального набора операций, выполняемых в АЛУ. Это сделано потому, что

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

самостоятельно, так и в качестве составляющих микропрограммы вычисле-

ния функции shx. По этой же причине осведомительный сигнал MP вклю-

чен в состав осведомительных сигналов, соответствующих операции сло-

жения.

Микропрограммы операций объединяются с помощью двоичных пе-

ременных g

, g

, определяющих код операции (КО). Он подается в АЛУ

из УЦУ. Запуск АЛУ производится управляющим сигналом АЛУ, возбуж-

дающим начало операции, заданной КО. В АЛУ формируются осведоми-

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

сигнал АЛО, идентифицирующий состояние устройства.

Устройство считается занятым выполнением операции, если АЛО =1.

Если АЛО = 0, устройство закончило выполнение операции, т. е. результат

операции присвоен RG.

3.5. Разработка структурной схемы операционного автомата АЛУ

Операционный автомат АЛУ может быть реализован как по схеме с

закрепленными микрооперациями, так и по схеме с общими микроопера-

циями. Метод синтеза таких автоматов изложен в [1,2]. Исходными данны-

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

вий, соответствующие микропрограммам минимального набора операций,

выполняемых АЛУ.

Для автомата с закрепленными микрооперациями каждому слову из

объединенного списка слов, не являющемуся вспомогательным, ставится в

соответствие регистр с тем же наименованием и того же формата. Тип этого

регистра определяется типом слова. Каждому входному регистру ставится в

соответствие вход автомата, а каждому выходному регистру – выход авто-

мата. Затем каждая микрооперация из объединенного списка микроопера-

ций закрепляется за регистром, которому присваивается результат этой

микрооперации. Регистр с закрепленным за ним списком микроопераций

объявляется операционным элементом. За ним сохраняется имя регистра.

Каждый список микроопераций, закрепленных за каким-либо регистром,

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

микрооперации считаются однотипными, если они определяются одинако-

выми функциями, возможно и с различным числом аргументов. Каждому

аргументу такой функции сопоставляется вход операционного элемента. К

нему подводится управляемая шина, с управляющим сигналом, помечен-

ным тем же индексом, что и функция, определяющая микрооперацию. Если

ко входу операционного элемента подходит несколько шин, необходимо

ставить мультиплексор. Микрооперации установки и инвертирования изо-

бражаются просто управляющим сигналом, подведенным к операционному

элементу.

Цепи осведомительных сигналов находятся с помощью объединенно-

го списка условий.

После соединения операционных элементов соответствующими ши-

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

структурную схему операционного автомата АЛУ с закрепленными микро-

операциями. Конкретные примеры таких схем имеются в [2].

Все операционные автоматы с общими микрооперациями имеют оди-

наковую структуру, содержащую набор внутренних регистров одинакового

формата, две шины, на каждую из которых может быть передано содержи-

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

рой служит содержимое этих шин. Результат с выхода комбинационной

схемы может быть передан в любой из внутренних регистров. Микроопера-

ции выборки слов на шины, преобразования слов в комбинационной схеме

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

микроопераций, используемых в микропрограмме. Каждая микрооперация

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

стью операторов. Логические условия обычно представляются в виде зна-

чения булевой функции результата на выходе комбинационной схемы.

Исходными данными для синтеза операционного автомата с общими

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

циями, служат объединенные списки слов, микроопераций и условий.

Процедура синтеза операционного автомата с общими микроопера-

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

в [1,2]. Там же приведены конкретные примеры синтеза.

Результатом данного раздела проекта служит структурная схема опе-

рационного автомата АЛУ.

3.6. Выбор системы команд

На этом этапе считаются заданными адресность команды, наличие

или отсутствие признака засылки, способ адресации ОЗУ и список опера-

ций АЛУ. Используя эти данные, составляют программы вычисления

функций F2, F3 по алгоритмам, разработанным в подразд. 3.2. По оконча-

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

мых для программирования F2, F3. Этот список и является минимальной

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

темы команд для всех предусмотренных заданием вариантов форматов ко-

манд приведены в [2].

Далее, с помощью полученных программ вычисления F1, F2, F3 по

методике, изложенной в [2], нужно рассчитать верхнюю границу времени

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

числитель является машиной с синхронным управлением и постоянной

длительностью такта. Для полученного варианта системы команд СП раз-

рабатывается аклгоритм микропрограммы УЦУ.

Конечным результатом выполнения этого этапа будут программы вы-

числения F1, F2, F3; максимальное значение T

max

решения одного цикла

задачи; алгоритм микропрограммы.

Пусть процессор состоит из АЛУ и УЦУ .

3.7. Разработка объединенной микропрограммы

работы УЦУ

Будем считать, что в АЛУ для основных операций над одним оп е-

рандом (ОО1) значение операнда перед началом операции присваивается

слову RG, для основных операций над двумя операндами (ОО2) значение

первого операнда присваивается слову RG, а значение второго – слову RG1.

Результат всякой основной операции присваивается слову RG. Код опера-

ции КО подается в АЛУ из УЦУ. Запуск АЛУ производится поступающим

из УЦУ управляющим сигналом АЛУ, возбуждающим начало операции,

заданной кодом операции КО. В АЛУ формируются осведомительные сиг-

налы, определяющие признаки результата (неотрицательность, равенство

нулю и т. д.), и осведомительный сигнал АЛО, идентифицирующий состоя-

ние устройства. Устройство считается занятым выполнением операции, ес-

ли АЛО = 1. Если же АЛО = 0 считается, что устройство закончило опера-

цию, т.е. результат операции присвоен слову RG.

УЦУ выбирает команды из ОП в требуемой последовательности, оп-

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

реходов, выбирает операнды, заданные адресами, запускает в АЛУ выпол-

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

результат и переходит к выборке следущей команды из ОП.

ОП является самостоятельным устройством. В нем выделяется ре-

гистр адреса RGA, регистр слова RGC, управляющие входы ЗП и ЧТ и осве-

домительный выход ОПО. Сигналы ЗП и ЧТ возбуждают в ОП операции

записи и чтения слова:

ЗП) ОП[RGA]:=RGC ЧТ) RGC:=ОП[RGA]

Период выполнения этих операций, реализуемых под управлением

местного устройства управления ОП, отмечается осведомительным сигна-

лом ОПО, который принимает значение 1 в момент начала обращения к па-

мяти и значение 0 – в момент окончания операций ЗП и ЧТ.

Если ОП работает с отдельными байтами, а слово, представляющее

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

ется из ОП за несколько обращений. Будем считать, что байты одного и того

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

что после выборки первого байта слова адрес следующего байта получается

прибавлением единицы к адресу выбранного байта и т. д. В том же порядке

осуществляется и запись слов.

Пусть в УЦУ значения выбранных из ОП команд присваиваются сло-

ву RGK, значения адресов команд присваиваются слову СТАК. Также имеет-

ся возможность с пульта управления процессором слову СТАК присвоить

начальное значение адреса программы (пусковой адрес) и остановить рабо-

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

нов». Ситуация, при которой во время выполнения основной операции при-

знаку переполнения разрядной сетки ПП присвоено значение 1, пусть счи-

тается аварийной и приводит к прекращению работы процессора с выдачей

сигнала на пульт управления. Работа процессора при этом должна автома-

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

признаку ПП значения 0.

В нашем случае специализированный процессор взаимодействует с

единственным устройством ввода и с единственным устройством вывода.

Операция ввода (ВВД) состоит из трех частей:

1. В УЦУ одноразрядному слову ВВО присваивается значение 1. Это

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

слову BRG1 из УЦУ значение вводимой переменной, после чего присваива-

ет слову ВВО значение 0.

2. Проверяется значение слова ВВО. Если ВВО = 0, то слову RG при-

сваивается значение слова BRG1.

3. Ячейке ОП с указанным в команде ввода адресом присваивается

значение слова RG.

Операция вывода (ВЫВ) пусть также состоит из трех частей:

1. Слову RG из АЛУ присваивается значение ячейки ОП с указанным

в команде вывода адресом.

2. В УЦУ проверяется значение одноразрядного слова ВЫО. Если

ВЫО = 0, слову BRG2 из УЦУ присваивается значение слова RG.

3. Слову ВЫО присваивается значение 1, что служит сигналом, за-

пускающим устройство вывода. Это устройство записывает значение слова

BRG2 после чего присваивает слову ВЫО значение 0.

Содержательные граф-схемы микропрограмм работы УЦУ, соответст-

вующие всем предусмотренным заданием форматам команд, приведены в

[2].

3.8 . Разработка структурной схемы

операционного автомата УЦУ

Исходными данными для разработки структурной схемы операцио н-

ного автомата УЦУ служат списки слов, микроопераций и условий, полу-

ченные из содержательной граф-схемы алгоритма работы УЦУ. Нахожде-

ние этих списков и служит первым шагом построения структурной схемы

операционного автомата УЦУ. Затем, как и при построении операционного

автомата АЛУ, в соответствии с заданием строится либо автомат с закреп-

ленными, либо с общими микрооперациями. Примеры синтеза структурных

схем таких автоматов приведены в [2].

3.9. Разработка управляющего автомата АЛУ

Рекомендуется следующая последовательность действий:

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

в закодированную ГСА.

2. Выделение фрагментов в закодированной ГСА, эквивалентных

одной микрокоманде (с учетом способа адресации и кодирования операци-

онной зоны).

3. Микропрограммирование ГСА, т.е. формирование упорядо-

ченного списка микрокоманд, интерпретирующих ГСА, в условных адре-

сах.

4. Расчет формата микрокоманды и определение информацион-

ной организации ПЗУ – М слов × k бит, где М – число микрокоманд, реали-

зующтх ГСА; k – разрядность микрокоманды.

Если автомат предназначен для управления операционным автоматом

с общими микрооперациями, то закодированная ГСА должна быть предва-

рительно преобразована так, чтобы каждая операторная вершина, содержа-

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

соответствующим числом операторных вершин, каждая из которых содер-

жала бы ровно по одной микрооперации.

Конечным результатом данного пункта являются:

1. Структурная схема управляющего автомата с учетом заданного

способа адресации микрокоманд.

2. Списочная форма микропрограммы ГСА в условных адресах и

с выделенными операционными и адреснымиполями каждой микрокоман-

ды.

3. Рассчитанные значения разрядности в битах каждого поля

микрокоманды и информационная организация ПЗУ.

По данной методике разрабатывается как УА АЛУ, так и УА УЦУ.

Примеры составления микропрограмм приведены в [2].

3.10. Разработка операционной структуры

специализированного процессора

Исходными данными для выполнения п. 3.10 служат структурные

схемы АЛУ и УЦУ. На этом этапе проектирования выполняется композиция

АЛУ и УЦУ, которая и образует операционное устройство как специализи-

рованный процессор. Результатом выполнения этого этапа является струк-

турная схема специализированного процессора [1,2].

3.11. Оценка времени реализации алгоритма

Требуется рассчитать время реализации одного цикла решения задачи

для случая, когда используется АЛУ с закрепленными микрооперациями, и

случая, когда используется АЛУ с общими микрооперациями. Методика

расчета приведена в [2].

Библиографический список

1. Майоров С.А., Новиков Г.И. Структура электронных вычислитель-

ных машин. Л.: Машиностроение, 1979. 384 с.

2. Козин И.В., Хмельницкий С.В. Синтез специализированных процес-

соров: Учеб. пособие/ЛИАП. Л., 1987. 107 с.

3. Корн Т., Корн Г. Справочник по математике. М.: Мир, 1977. 831 с.

СОДЕРЖАНИЕ

1. ОБЪЕКТ И ЭТАПЫ ПРОЕКТИРОВАНИЯ……………………………. 3

2. ЗАДАНИЕ НА КУРСОВОЕ ПРОЕКТИРОВАНИЕ…………………… 4

3. МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ ЭТАПОВ

ПРОЕКТА………………………………………………………………… 7

3.1. Разработка алгоритмов решения функциональной задачи……. 7

3.2. Определение минимального набора операций АЛУ…………… 9

3.3. Разработка алгоритмов микропрограмм выполнения

минимально необходимого набора операций АЛУ…………… 9

3.4. Разработка объединенной микропрограммы работы АЛУ……. 14

3.5. Разработка структурной схемы операционного автомата АЛУ.. 15

3.6. Выбор системы команд………………………………………….. 16

3.7. Разработка объединенной микропрограммы работы УЦУ…… 17

3.8. Разработка структурной схемы операционного автомата УЦУ.. 18

3.9. Разработка управляющего автомата АЛУ……………………… 18

3.10. Разработка операционной структуры специализированного

процессора………………………………………………………... 19

3.11. Оценка времени реализации алгоритма………………………… 19

Библиографический список………………………………………………… 20