Устройство для стековой адресации

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ .К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 2201,79 (21) 2715033/18-24 (51) М. Кл.

Союз Советских

Социалистических

Республик с присоединением заявки № (23) Приоритет

G 06 F 9/36

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

СССР оо делам изобретений и открытий

Опубликовано 30 1180. Бюллетень ¹ 4 4

Дата опубликования описания . 30.1180 (53) УДК681. 325 (088. 8) (72) Автор изобретения

A.À. Якуба (71) Заявитель

Ордена Ленина институт кибернетики АН Украинской ССР (54) УСТРОЙСТВО СТЕКОВОЙ АДРЕСАЦИ)1

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

Известно устройство стековой адресации, содержащее один регистр указателя верхней позиции стека(1) °

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

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

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

В таблице используются следующие обозначения: А — абсолютный адрес начала текущей позиции стека; УВП старое значение указателя верхней позиции стека; УВП вЂ” модифицированное значение укаэателя верхней пози10 ции стека; УНП вЂ” старое значение указателя нижней позиции стека; УНП модифицированное значение указателя нижней позиции стека; РПС вЂ” размер позиции стека.

15 Недостатки этого устройства состоят в том, что область применения ограничена только памятью со словной организацией и в понижении производительности при работе процессо2() ра со стековыми данными переменной длины. Они возникают из-эа того, что;операцйи чтения и эиписи стековых данных производятся лишь над словами фиксированной длины, а раз25 мер позиции стека неизменен и задан в аппаратуре.

Цель изобретения — повьыение производительности устройства.

Для достижения указанной цели в

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

Первый вход адресного сумматора

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

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

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

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

Блок Формирования номера позиции содержит два элемента ИЛИ, три элемента И, два вычитателя, причем первый и второй входы первого элемента

ИЛИ соединены соответственно с вхо25

ЗО

65 дами чтения .и записи блока, выход первого элемента ИЛИ вЂ” c первым входом первого элемента И, второй вход которого соединен с первым входом данных блока, а ныход первого элемента И вЂ” с первым нходом первого вычитателя, первый и второй входы второго элемента ИЛИ соединены соответственно с входами блока чтения и подкачки, выход второго элемента ИЛИ вЂ” с первым входом второго элемента И, второй вход которого соединен с третьим входом данных блока, а выход второго элемента И вЂ” с вторым нходом первого вычитателя, выход которого соединен с первым входом второго вычитателя, первый и второй входы третьего элемента И соединены соответственно с вторым входом данных и входом смещения блока, а выход третьего элемента И вЂ” c вторым входом второго нычитателя, выход которого соединен с выходом блока.

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

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

На фиг.1 показана блок-схема устройства стековой адресации; на фиг.2блок-схема блока номера позиции; на фиг.3 - блок-схема блока моцификации; на Фиг.4 — блоксхема узла корре" ции.

Устройство стековой адресации содержит регистр 1 указателя нижней позиции стека, регистр 2 указателя верхней позиции стека, узел 3 моди783793

10 фикации, адресный сумматор 4, блок

5 модификации позиции стека, блок б формирования номера позиции, регистр 7 размера позиции стека, первый узел 8 коррекции и второй узел

9 коррекции.

Блок б содержит два .элемента ИЛИ

10, 11, три элемента И 12, 13, 14, два вычитателя 15, 16, вход 17 чтения, выход 18 записи,,первый вход

19 данных, вход 20 подкачки, третий вход 21 данных, второй вход 22 данных, вход 23 смещения, выход 24.

Блок 5 содержит сумматор 25, два коммутатора 26 и 27, элемент ИЛИ 28 и узел 29 коррекции номера, второй вход 30 данных, третий 31 и четвертый 32 входы данных, вход 33 чтения, вход 34 откачки, выход 35 данных, первый вход 36 данных, вход 37 смещения, управляющий выход 38.

Первый и второй узлы 8, 9 коррекции содержат вычитатель 39, сумматор

40, коммутатор 41, вход 42 данных, выход 43 данных, вход 44 генерации.

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

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

Сигналы Чтение, Запись, Подкачка, Откачка и Смещение поступают по управляющим входам устройства: третьему, пятому, первому, второму и четвертому соответственно.

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

55 оО

6S Откачка адрес формируется как алгебраическая сумма по модулю М значения из регистра 1 и значения коррекции указателя по типу операции. Коррекция указателя во всех четырех операциях понимается как учет положения указателя верхней или нижней позиции стека по отношению к позиции, к которой происходит обращение: например, указатель верхней позиции стека всегда установлен на начале очередной свободной позиции и для чтения последней занятой позиции его следует опустить на одну позицию.

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

Первый этап работы устройства выполняется в блоке 6. Блок 6 вырабатывает номер текущей позйции, зависящий от значения в указателе верхней позиции стека и управляющих сигналов: при сигнале Чтение номер позиции есть (УВП -„РПС), при

К сигнале Запись — УВП, при сигнале Подкачка — РПС и при сигнале Откачка значение на выходе блока б равно нулю.

Здесь УВП вЂ” УВП вЂ” при отсутствии сигнала СМЕЩЕНИЕ; (УВП-СМ) — при наличии этого сигналау

УВП вЂ” значение в регистре 2 указателя верхней позиции .стека;

РПС вЂ” значение в регистре 7 размера позиции стека;

СМ вЂ” значение на входе данных от процессора.

Блок б работает следующим образом. Первые входы вычитателей 15, 16 и сумматора 4 есть входы для уменьшаемого значения, вторые входы — для вычитаемого значения. На первый вход вычитателя 15 при наличии хотя бы одного из сигналов Чтение (вход 17 блока 6) или t За-: пись (вход 18 блока б) на входах элемента ИЛИ 10 через элемент И 12 пропускается значение иэ регистра

2, при остальных операциях значение на первом входе вычитателя 15 равно нулю. На второй вход вычитателя при наличии на входах элемента ИЛИ 11 хотя бы одного из сигналов Чтение или Подкачка (вход 20 блока 6) через элемент И 13 пропускается значение РПС иэ регистра 7, при остальных операциях значение на втором входе вычитателя 15 будет равно нулю.

783793

Выходное значение вычитателя 15 есть номер текущей позиции при нулевом смещении. Подготовительное значение номера текущей позиции поступает на первый вход вычитателя 16, а на второй его вход через элемент И 14 подается при задании варианта со смещением в операциях Чтение, Запись значение смещения (вход 22 данных от процессора) и вычитается иэ подготовительно"o значения номера,.

Результат (номера текущей позиции с учетом смещения) поступает через адресный выход 24 на второй вход адресного сумматора 4, На первый вход адресного сумматора 4 постоянно подключен регистр 1 указателя нижней позиции стека, который содержит абсолютный адрес хронологически первой позиции с достоверной информацией, ее номер равен нулю, ВыХодное значение адресного сумматора 4 корректируется по модулю М узлом 9 и поступает на адресный выход к стековому блоку памяти.

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

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

3 и блоком 5 и зависит от значений управляющих сигналов, поступающцх из блока стековых операций. Узел 3 модифицирует значение в регистре 1 ука- 45 эателя нижней позиции стека только при операциях Подкачка и Откачка, причем значение с выхода узла

3 после коррекции по модулю М в узле

8 записывается в регистр 1 по управляющему сигналу записи в регистр.

Коррекция по модулю И, выполняемая узлом 8 (или 9), заключается в следующем: проверить условие А .М (или УНП4М); если условие не выполняется, то алгебраически суммировать значения адреса А и константы коррекции по модулю И, равной 2 - М, где 2п — ближайшее большее к N. Знак определяет- о ся типом выполняемой стековой операции (в частности, для второго узла

9 коррекции Чтение и Запись задают сложение УНП и константы коррекции), а Подкачка — вычитание константы из УНП с последующим отбрасыванием возможного переноса иэ старшего (n-ro) разряда, т.е. выполняется УНП М на п-разрядном сумматоре.

Узлы 8 и 9 однотипны по структуре.

Входы левого операнда вычитателя 39 и вход правого операнда сумматора 40 постоянно соединены с входом генерации устройства, который является выходом узла генерации значения константы, равной 2 - М. Управляющие входы, определяющие тип действий на сумматоре 40 (сложение и вычитание), на фиг.4 не показаны.

На выходе вычита еля 39 формируется сигнал, указывающий выполняется ли условие А- М для узла 8 (или УНП 7 М для узла 9). Если этот сигнал отсутствует, то на выход 43 данных поступает через коммутатор 41 значение с входа 42 данных, B противном случае и при наличии управляющего сигнала, формируемого по типу операции в соответствии с таблицей, на выход 43 данных поступает значение с выхода сумматора 40. В этом случае, когда выполняемая операция не требует коррекции (на узле 8 адреса или на узле 9 значения УНП) на выход 43 данных подается входное значение с входа 42 данных.

В блоке 5 выполняется два действия: формирование номера первой свободной позиции стека для занесения в регистр 2 указателя верхней поэ;— ции стека и проверка, »е выходит ли номер текущей позиции, участвующий в формировании стекового адреса этой позиции, эа пределы значения М, Первое действие выполняется в соответствии со значениями управляющих сигналов на входе устройства (см, таблицу) .

Второе действие заключается в проверке, удовлетворяется ли соотношение

0 НП1М, где номер позиции НП вЂ” либо результат выполнения первого действия в блоке

5 при отсутствующем управляющем сигнале Смещение, либо значение с выхода блока 6 при наличии указанного сигнала. Занесение значения в регистр 2 выполняется при отсутствии сигнала Смещение сигналом записи в регистр (этот сигнал на фиг.1 не показан).

Блок 5 при модификации номера позиции работает следующим образом (фиг.3). Значение из регистра 2, т.е, УВП, подается через второй вход 30 данных блока на первый вход сумматора 25, второй вход которого соединен с коммутатором 26, выбирающим на свой выход либо значение РПС с входа 32 блока, либо значение с входа 31 данных от процессора в качестве констан783793

Знак операции, сложение или вычитатание задается управляющими сигналами на входах чтения и откачки 33, 34 блока модификации. Например, наличие сигнала Чтение от блока стековых операций задает уменьшение значения указателя, т.е. УВП вЂ” УВП - СМ. Проверка условия (1) для нового значения

УВП выполняется узлом 29 коррекции, на вход которой управляющим сигналом Смещение (вход 37 блока 5) через коммутатор 27 коммутируется значение

УВП с выхода сумматора 25.

Использование данного устройства стековой адресации расширяет область применения стековой памяти — можно равной эффективностЬю испольэовать

20 в качестве стекового блока памяти не только память со сложной организацией, но и с байговой, наиболее распространенн и в настоящее время, при этом объем памяти не ограничивается значед5 ниями, равными 2 в

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

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

Это эквивалентно увеличению объема стековой памяти, и следовательно, повышению производительности процессора из-эа значительной разницы (в 4-10 раэ) в быстродействии стековой и основной памяти.

Устройство Операция Адрес А (Г

УВП УНП (УВП РПС ) М (УВП РПС )дц>р М

Чтение

Запись

Подкачка

Откачка (УВП+РПС )„„к 4М

УВП

Известное (УНП-РПС )в@4 4 (УНП+РПС) 4й. (УНП-PIIC + 4M

УВП

УНП

Чтение (УНП+УВП+РЙС)„ ф УВП-РПС

УНП (УНП+УВП,кх М УВП+РПС

Запись

Предлагаемое (УНП-РПС „,х(М УВП+РПС

Подкачка (УНП-РПС)„, дМ

Откачка

УНП

Формула изобретения

1. Устройство стековой адресации, содержащее регистр указателя верхней позиции стека, регистр указателя ниж- Я ты модификации; управляющий вход сумматора 25 соединен с элементом ИЛИ

28, объединяющий управляющие сигналы Чтение (вход 33 блока) и Откачка (вход 34 блока), наличие одного из них задает вычитание на сумматоре

25, отсутствие обоих — сложение. Выход сумматора 25 соединен по выходу

35 блока с входом регистра 2 и через второй коммутатор 27, на второй вход которого от блока 6 приходит значение через вход 36 блока, с узлом 29 коррекции номера.

Узел 29 преобразует выходное значение коммутатора 27 в значение по модулю М, появление переноса на выходе коммутатора 27 свидетельствует о наличии переполнения или исчезновения (опустошения ) стека. Выбор одного из входных значений коммутатором 27 задается поступающим через вход 37 смещения блока управляющим сигналом Смещение, при наличии которого на вход коммутатора 27 попадает значение с входа 36 блока °

Управляющий сигнал для выбора в ком" мутаторе 26 не показан.

Таким образом, при задании, например,.операции Запись и варианте . беэ смещения сумматор 25 суммирует значение РПС с значением УВП, формируя новое значение на выходе 35 для записи в регистр 2, а результат через коммутатор 27 попадает на узел

29 коррекции, проверяющей условие (1) .

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

33R--МЬП би . одифицированное значение указателя

УВП-РПС (УНП+РПС) щ)й ней позиции стека, первый и второй управляющие входы которого соединены соответственно с входами подкачки и откачки устройства, выход регистра указателя нижней позиции стека сое783793

12 дикен с первым входом узла модификации,отличающее с ятем, что, с целью повышения производительности устройства, в него введены адресный сумматор, блок модификации позиции стека, блок формирования номера позиции, регистр размера позиции стека, первый и второй узлы коррекции, причем вход цанных первого узла коррекции соединен с выходом узла модификации, а выход данных первого узла коррекции — с входом данных регистра указателя нижней позиции стека, первый вход адресного сумматора соединен с выходом регистра указателя нижней позиции стека, второй вход адресного сумматора — с выходом блока 1$ формирования номера позиции и первым входом данных блока модификации позиции стека, а выход адрЕского сумматора соединен через второй узел коррекции с адресным выходом устройства, выход регистра указателя верхней позиции стека соединен с первым входом данкь.х блока формирования номера позиции и вторым входом данных блока модификации позиции стека, выход данных которого соединен с входом данных регистра указателя верхней пози,ии стека, входы генерации первого и второго узлов коррекции соединены с входом генерации устройства, вход данных которого соединен с третьим вхо- ?О дом данных блока модификации позиции стека, вторым входом данных блока формирования номера позиции и входом данных регистра .размера позиции стека, выход которого соединен с третьим вхо-35 дом данных блока формированиа номера позиции, вторым входом узла модификации и четвертым входом данных блока глодификации позиции стека, входы чтения блока модификации позиции стека 4О и блока формирования номера позиции соединены с входом чтения устройства, вход откачки блока модификации позиции стека соединен с входом откачки устройства, вход смещения блока модификации гозиции стека соединен с входами смещения блока формирования номера позиции и устройства, а управляющий выход блока модификации — с управляющим выходом устройства, вход записи блока формирования номера по- SO зиции соединен с входом записи устройства, вход подкачки блока формирования номера позиции соединен с входом подкачки устройства, 2. Устройство по п.1, о т л и ч а ю щ е е с я тем, что блок формирования номера позиции содержит два элемента ИЛИ, три элемента И, два вычитателя, причем первый и второй входы первого элемента ИЛИ соединены соответственно с входами чтения и записи блока, выход первого элемента

ИЛИ вЂ” с первым входом первого элемента И, второй вход которого соединен с первым входом данных блока, а выход первого элемента И вЂ” с первым входом первого вы итателя, первый и второй входы второго элемента ИЛИ соединены соответственно с входами чтения и подкачки блока, выход второго элемента ИЛИ вЂ” c первым входом второго элемента И, второй вход которого соединен с третькл входом данных блока, а выход второго элемента

И вЂ” o вторил входом первого вычитателя, выход которого соединен с первым входом второго вычитателя, первый и второй входгг третьего элемента

И соедикены соответствекко с вторыгл входом данных и входом смещения блока, а выход третьсго элемента И вЂ” с вторым входом второго вычитателя, выход которого соединен с выходом блока.

3. Устройство по п,1, о т л и ч а ю щ е е с я тем, что блок модификации позиции стека содержит сумматор, два коммутатора, элемент ИЛИ и узел коррекции номера, причем первый вход данных сумматора соединен с вторым входом данных блока, второй вход данных сумматора — с выходом первого коммутатора, первый и второй входы которого соединены соответственно с третьим и четвертым входами данкых блока, управляющий вход сумматора соединен с выходогл элемента ИЛИ, первый и второй входы которого соединены соответствекно с входами чтения и откачки блока,выход сумматора соединен с выходом данных блока и первая входом данных второго коммутатора, =-торой вход данных которого соединек с первым входом данных блока, управляющий вход второго коммутатора — с входом смещения блока, а выход второго коммутатора соединен через узел коррекции номера с управляющим выходом блока

4. Устройство по п.1, о т л и гг а ю щ е е с я тем, что первый и второй узлы коррекции содержат вычитатель, сумматор и коммутатор, причем вход левого операнда сумматора соединен с входом правого операнда вычитателя, с первым входом коммутатора и входо л данных узла коррекции, вход левого операнда вычитателя и вход правого операнда сумматсра-соединены с входом гекерацйи узла коррекции„ выход сумматора соедикек с вторым входом коммутатора, выход которого соединен с выходом данных узла коррекции.

Источники информации, принятые Во Внимание при экспертизе изобретения

1. Патент CLlA 3200379, кл, 340-172.5, 1965.

2. Патент CIAO Р 3810117, кл. 340-172.5, 1974 (прототип).

783793

4 иг. 5

Фиг. Ф

Составитель Г. Пономарева

Редактор Т. Рыбалова Техред Е.Гаврилешко Корректор М. Шароши

Заказ 8550/52 . Тираж 751 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП Патент, г ° Ужгород, ул. Проектная, 4