Стековые машины

Многостековые 0-операндные машины


Многостековые 0-операндные машины имеют ряд преимуществ перед иными архитектурами: 0-операндная адресация ведёт к малому размеру инструкции, несколько стеков позволяют одновременно использовать вызовы подпрограмм и манипулировать стеком данных. Это приводит к малому размеру программ и малой сложности системы.

Локальность обращений стеку даёт возможность уменьшить траффик "стек-память" на большинстве задач управления. Простота построения системы позволяет уменьшить время проектирования микросхем. Применение стековой модели позволяет уменьшить время обработки прерываний, так как не требуется сохранение контекста.

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


Типичная стековая архитектура.

Рассмотрим архитектуру канонической стековой машины.

Структурная схема

На рис. 1 показана структурная схема стековой машины. Основными компонентами являются: шина данных, стек данных (DS), стек возвратов (RS), арифметико-логическое устройство (ALU) с регистром вершины стека (TOS), счётчик инструкций (PC), память с регистром адреса памяти (MAR), логика управления с регистром инструкции (IR), и секция ввода/вывода (I/O).


Рис. 1. Каноническая стековая машина.

Шина данных

Для упрощения конструкции стековая машина имеет одну шину, соединяющую ресурсы системы. Реальные процессоры имеют более одной шины для параллеьной выборки данных и выполнения вычислений. В канонической стековой машине (КСМ) на шине может находится только один передающий блок, и только один принимающий блок в течении цикла.

Стек данных.

Стек данных - вид памяти, который реализует стек с процедурой LIFO. Традиционной реализацией является блок быстродействующей памяти с счетчиком (инкрементно-декрементным), использующимся для генерации адреса. Стек данных допускает 2 операции: push и pop. Операция push выделяет новую ячейку на вершине стека и записывает в неё значение с шины данных. Операция pop кладёт значение из вершины стека на шину данных, затем освобождает ячейку.

Стек возвратов

Стек возвратов - это LIFO стек, реализованый аналогично стеку данных. Единственное отличие состоит в том, что стек возвратов используется для хранения адресов возвратов из процедур, а не операндов инструкций.

АЛУ и регистр вершины стека

Блок АЛУ осуществляет арифметико-логические операции над парами элементов данных. Один из этих элементов - регистр вершины стека, хранящий его верхний элемент, поэтому в стек-памяти реально вершиной является второе значение. Такое решение позволяет иметь однопортовую память, реально используя два элемента данных.

АЛУ поддерживает стандартные операции, используемые любой ЭВМ, как минимум сложение, вычитание, логические функции и тестирование на 0. Арифметика может быть целочисленной или плавающей.

Счетчик инструкций

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

Память

Блок содержит регситр адреса памяти (MAR) и некоторый объём памяти. Для доступа в память в MAR записывается адрес, откуда/куда будет производится чтение/запись. В следующий цикл память будет прочитана или записана (с помощью шины данных).

Устройство ввода/вывода

Некоторое устройство, "черный ящик", которое позволяет вести информационный обмен с внешними устройствами.


Обработка данных

В таблице 1 показан минимальный набор операций канонической стековой машины. Набор призван только проиллюстрировать исопльзование машины - он должен быть намного сложнее для реальных применений.

Нотация взята из языка Форт, специальный знак ! обозначает "сохранить", а знак @ обозначает "загрузить".


Инструк-   Стек данных
ция       было    -> стало    Функция 

 !       N1 ADDR ->           Сохранить N1 по адресу ADDR в памяти

 +       N1 N2   -> N3        Сложить N1 и N2, получив сумму N3

 -       N1 N2   -> N3        Вычесть N2 из N1, получив разность N3

 >R      N1      ->           Положить N1 на стек возвратов

 @       ADDR    -> N1        Загрузить значение по адресу
                                 ADDR из памяти, получив N1

 AND     N1 N2   -> N3        Логическое И над N1 и N2, получив результат N3

 DROP    N1      ->           Выгрузить N1 со стека

 DUP     N1      -> N1 N1     Сделать дубль N1, создав копию на стеке

 OR      N1 N2   -> N3        Логическое ИЛИ над N1 и N2, с результатом N3

 OVER    N1 N2   -> N1 N2 N1  Положить копию второго элемента стека, N1,
                                 на вершину стека

 R>              -> N1      Убрать верхний элемент со стека возвратов
                                 положив его на стек данных как N1

 SWAP    N1 N2   -> N2 N1      Переставить два верхних элемента стека

 XOR     N1  N2  -> N3         Логическое исключающее ИЛИ
                                 над N1 и N2, получив результат N3

 [IF]    N1      ->            Если N1 - ложь (значение = 0)
                                  перейти по адресу, разположенносу в 
                                  следующей ячейке памяти программ, иначе 
                                  продолжить выполнение

 [CALL]          ->            Вызов процедуры, адрес находится в 
				следующей ячейке памяти программ

 [EXIT]          ->            Возврат из процедуры.

 [LIT]           -> N1         Загрузить значение из следующей
 				  ячейки памяти программ как число
 			      и положить его на стек данных как N1

Таблица 1. Набор инструкций канонической стековой машины.

Обратная польская нотация

Стековые машины обрабатывают данные, "используя" постфиксную нотацию:

98 12 45 + * (эквивалентно (12+45)*98)


Рис. 2. -- Пример работы стековой машины.

Каноническая стековая машина разработана для прямого исполнения обратной польской нотации (в компиляторе исчезает фаза распределения регистров).


Механизм прерываний

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

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

Заключение

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

Однако, идеи стековых машин очень популярны. На базе виртуальной стековой архитектуры построены виртуfльные машины Java и C#. В Беларуси выпускался стековый процессор-контроллер серии Дофин, 7 моделей, разрядность 16 и 32 бит, пригодный для задач цифовой обработки сигналов, за один такт он мог выполнить до 6 стандартных операций стековой машины. Сейчас выпускаются 4-битные стековые микроконтроллеры серии MARC фирмы Atmel.