Стековое запоминающее устройство Советский патент 1992 года по МПК G06F12/00 G11C19/00 

(Л

С

Изобретение относится к цифровой вычислительной технике. Цель изобретения - повышение производительности вычисления за счет сокращения числа обращений в оперативную память. Изобретение можно использовать в устройстве обработки данных. Содержит блок 1 управления, блок 2 регистров, арифметико-логическое устройство 3 реверсивные счетчики 4 и 8, первый и второй формирователи 5 и 6 адреса к мультиплексор 7. 2 ил., 1 табл.

XJ СА

N ел о

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

Цель изобретения - повышение производительности вычислений за счет сокращения числа обращений в оперативную память.

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

Устройство обработки данных содержит блок 1 управления, блок 2 регистров (стек), арифметико-логическое устройство 3, первый реверсивный счетчик 4, первый 5 и второй 6 формирователи адреса, мультиплексор 7 и второй реверсивный счетчик 8.

Блок 1 состоит из коммутатора управления счетчиками 4 и 8, выполненного на элементах И 9-12 и элементе НЕ 13.

Устройство обработки данных работает следующим образом.

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

Второй формат содержит поле КОП и поле адреса операнда (АД) в памяти. Этот формат используется для загрузки стека данными из памяти и выгрузки из него.

Третий формат содержит поле КОП и поле адреса регистра (Н4), в котором задается номер любого регистра внутри стека относительно его вершины. Регистр на вершине стека считается 0, регистр первого уровня под вершиной стека имеет относительный номер 1 и т.д. Команды этого формата позволяют осуществлять доступ к любому регистру в глубине стека.

Типовые команды, управляющие работой предлагаемого устройства, приведены в таблице. Для определенности глубина регистрового стека выбрана равной 16.

Работа устройства начинается с сброса в ноль счетчиков 4 и 3. Различают два режима обмена данными с оперативной памятью: одиночный и групповой. В одиночном режиме выполняется обмен данными между вершиной стека и оперативной памятью. Любая загрузка в стек в этом режиме увеличивает на 1 содержимое счетчика 4, а выгрузка из стека уменьшает на 1 содержимое счетчика 4. Групповой режим отличается от одиночного тем, что обмен

данными с памятью выполняется от дна стека, на который указывает счетчик 8. В этом режиме загрузка или выгрузка соответственно увеличивает или уменьшает на 1 содержимое счетчика 8.

5В качестве примера рассмотрим счет по

формуле

а + (с - b x a) x (a + d).

10В обратной польской записи она имеет

вид

acbdx - tad + x +.

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

20

, , , 4p, x, -, , 4p, +, х, +,

где - адреса операндов а d в

памяти ЦВМ.

Состояние стека при выполнении этой последовательности команд на фиг. 2.

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

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

случаев занимают по 1 байту, то длина командного кода для обоих случаев составляет 17 байтов. Если адреса операндов в памяти занимают по 2 байта(что наиболее реально), то командный код для предлагаемого устройства короче на 2 байта. Следовательно, предлагаемое устройство позволяет сократить время счета и длину командного кода. Рассмотрим пример использования предлагаемого устройства для организации

циклов.

Пусть i - переменная цикла, N - верхний предел. При входе в цикл на вершину стека помещают значение С, на следующий нижний уровень - N. При каждом повторении

цикла, i увеличивается на единицу и , если К N , то управление передается на начало цикла, в противном случае со стека снимают две верхние позиции, а управление передается на следующую команду. При организации

вложенных циклов на вершине стека располагаются i и N внутреннего цикла, а в глубине стека - параметры внешнего цикла,

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

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

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

В то же время в случае использования статических языков высокого уровня (ЯВУ) (типа Ада, Алгол 68, Модула 2) уже на этапе трансляции известно, сколько регистров по- требует процедура для своей работы, т.е. каков ее аппетит. Зная аппетит процедуры и следя за заполненностью регистровой памяти, можно выгружать в оперативную память только часть регист- ров. Если свободных регистров больше, чем требуется процедуре, то выгрузка вообще может не производиться. Это позволяет экономить время вызова процедуры и возврата. С этой целью предлагаемое устройст- во содержит счетчик 8. Зная содержимое счетчиков 4 и 8, можно судить о заполненности стека. Если требуется выгрузка стека при вызове процедуры, то требуемое количество регистров выгружается от дна стека. При выгрузке каждого регистра состояния счетчика 8 увеличивается на единицу, а при загрузке (при возврате из процедуры) уменьшается на единицу. На выход мультиплексора 7 в том случае поступает содержи-

Читать на стек значение из памяти

Читать на стек значение кэ регистра Писать в память значение из стека

Писатр из стека значение а регистр

Разность

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

Инвертирование знака но псрши с (группа унарных стековых операций)

Регистровая сумма целых, результат о регистр

Л:-.хB:- SP+1КЗ АД

A:- SP- IBl-Sr-MKl| (Й

A:«SPB:-XK8 АД

A:-SP :-SP-llK12 Hii

S: SPB: SP-1K8

A:-SP H:-sr

КЗ

SJ : sr-1A: SP B:-SP-H K12 H I

ри

и е и а н и e. Kk, к8, К12 - число битов s коде оп-рации; SP - казатель с-зкл. Формируемый счотч клми it и 8; (н) - н0,-..ер реги- с.ра отеюсительно текущей вершины стека; X - э ачсние безразличие.; ЛД - поле адресации.

мое счетчика 8. Состояние счетчика 4 при этом не меняется.

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

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

Л:-.хB:- SP+1КЗ АД

A:- SP- IBl-Sr-MKl| (Й

A:«SPB:-XK8 АД

A:-SP :-SP-llK12 Hii

S: SPB: SP-1K8

A:-SP H:-sr

КЗ

a+ c-8a}x(a+d} acBa -+ad+x+

.

4P

nSoufn

обращений $ память 4