Выполнение операций на стеке

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

Рассмотрим механизмы обработки информации на стеке и формирования безадресных команд.

Прежде всего - об идее применения безадресных команд.

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

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

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

Адреса памяти фигурируют только в командах загрузки стека и записи из стека в память.

Значения выражений можно вычислять полностью безадресным способом.

Команда, состоящая только из кода операции, извлекает из стека один или два операнда, выполняет операцию и заносит результат в стек. На рис. 3.3.1 приведен пример преобразования стека при выполнении трех команд программы.

Рис. 3.3.1 Выполнение команд на стеке

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

Например,

y := (k + (l - mn))(a - b) yklmn × - + ab - × :=

Последовательность символов в ПОЛИЗ может рассматриваться как программа вычисления значения данного выражения, если под именами понимать команды загрузки стека (кроме случая, когда имени следует знак операции :=, тогда это имя определяет запись из стека), а под знаками операций — безадресные команды, содержащие только коды операций. Удобно ввести команду вида Зп У — записи из стека по адресу У. Тогда мы получим окончательный вид программы

klmn × - + ab - × Зп Y (3.1)

Не будем отображать УВС, интерпретируя стек магазинной памятью. Тогда схема выполнения данной программы сводится к представленной на рис. 3.3.2

Рис. 3.3.2 Выполнение программы на стеке