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

Стеком называется память, по своей структурной организации отличная от основной памяти ВМ, тем что образует множество логически взаимосвязанных ячеек (рис.23), взаимодействующих по принципу «последним вошел, первым вышел» (LIFO, Last In First Out).

Принципы построения стековой памяти детально рассматриваются позже, здесь же выделим только те аспекты, которые требуются для пояснения особенностей АСК на базе стека.

Рис. 23. Принцип действия стековой памяти

Верхнюю ячейку называют вершиной стека. Для работы со стеком предусмотрены две операции: push (проталкивание данных в стек) и рор (выталкивание данных из стека). Запись возможна только в верхнюю ячейку стека, при этом вся хранящаяся в стеке информация предварительно проталкивается на одну позицию вниз. Чтение допустимо также только из вершины стека. Извлеченная информация удаляется из стека, а оставшееся его содержимое продвигается вверх. В вычислительных машинах, где реализована АСК на базе стека (их обычно называют стековыми), операнды перед обработкой помещаются в две верхних ячейки стековой памяти. Результат операции заносится в стек. Принцип действия стековой машины поясним на примере вычисления выражения а = а + Ь + ах с.

При описании вычислений с использованием стека обычно используется иная форма записи математических выражений, известная как обратная польская запись (обратная польская нотация), которую предложил польский математик Я. Лукашевич. Особенность ее в том, что в выражении отсутствуют скобки, а знак операции располагается не между операндами, а следует за ними (постфиксная форма). Последовательность операций определяется их приоритетами (табл. 2.).

Таблица 2. Приоритеты операций в обратной польской нотации

Операция	Символ операции	Приоритет
Открывающая скобка	(
Закрывающаяся скобка	)
Сложение | вычитание	+ | -
Умножение | деление	* | /
Возведение в степень	**

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

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

2. Операнды переписываются в выходную строку.

3. Знаки операций заносятся в СПО по следующим правилам:

· если СПО пуст, то операция из входной строки переписывается в СПО;

· операция выталкивает из СПО в выходную строку все операции с большим или равным приоритетом;

· если очередной символ из исходной строки есть открывающая скобка, то он проталкивается в СПО;

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

Процесс получения обратной польской записи для правой части выражения а = а + b + ас представлен в табл.3.

Таблица 3. Формирование обратной польской записи для выражения

а = a+b+a c

Просматриваемый символ
Входная строка	а	+	b	+	a	x	c
Состояние стека последовательности операций		+		+		x +		+
Выходная строка	a		b	+	a		c	x	+

Таким образом, рассмотренное выше выражение в польской записи имеет вид: а = ab+acx+. Данная форма записи однозначно определяет порядок загрузки операндов и операций в стек (рис. 24).

Рис. 24. Последовательность вычисления выражения a=ab+acx+ на вычислительной машине со стековой архитектурой

Рис. 25. Архитектура вычислительной машины на базе стека

Основные узлы и информационные тракты одного из возможных вариантов ВМ на основе стековой АСК показаны на рис. 25.

Информация может быть занесена в вершину стека из памяти или из АЛУ. Для записи в стек содержимого ячейки памяти с адресом х выполняется команда push х, по которой информация считывается из ячейки памяти, заносится в регистр данных, а затем проталкивается в стек. Результат операции из АЛУ заносится в вершину стека автоматически.

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

Для выполнения арифметической или логической операции на вход АЛУ подается информация, считанная из двух верхних ячеек стека (при этом содержимое стека продвигается на две позиции вверх, то есть операнды из стека удаляются). Результат операции заталкивается в вершину стека. Возможен вариант, когда результат сразу же переписывается в память с помощью автоматически выполняемой операции pop x.

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

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

С другой стороны, стековая АСК по определению не предполагает произвольного доступа к памяти, из-за чего компилятору трудно создать эффективный программный код, хотя создание самих компиляторов упрощается. Кроме того, стек становится «узким местом» ВМ в плане повышения производительности. В силу упомянутых причин, данный вид АСК долгое время считался неперспективным и встречался, главным образом, в вычислительных машинах 1960-х годов, напри­мер в ВМ фирмы Burroughs (B5500, В6500) или фирмы Hewlett-Packard (HP2116В, HP 3000/70).

Последние события в области вычислительной техники свидетельствуют о возрождении интереса к стековой архитектуре ВМ. Связано это с популярностью языка Java и расширением сферы применения языка Forth, семантике которых наиболее близка именно стековая архитектура. Среди современных ВМ со стековой АСК можно упомянуть машины JEM 1 и JEM 2 компании ajile Systems и Clip фирмы Imsys. Особо следует отметить стековую машину IGNITE компании Patriot Scientist, которую ее авторы считают представителем нового вида АСК — архитектурой с безоперандным набором команд. Для обозначения таких ВМ они предлагают аббревиатуру ROSC (Removed Operand Set Computer). ROSC-архитектура заложена и в некоторые российские проекты, например разработки ИТФ «Технофорт». Строго говоря, по своей сути ROSC мало отличается от традиционной архитектуры на базе стека, и выделение ее в отдельный вид представляется не вполне обоснованным.

Пример: выполнить операции в АСК а+в-авс

Дата добавления: 2014-01-06