2.1 Трёхмерное пространство стековых архитектур



==24

Всё разнообразие конструкций стековых компьютеров может быть разложено по координатам трёхмерного пространства, как изображено на рис. 2.1 . В эти три измерения входят: число поддерживаемых аппаратурой стеков, объём буфера, отведённого под каждый стек [* буфер - та часть стека, работать с которой машина может, не обращаясь к основной памяти ] , и число параметров, допускаемых форматом машинной инструкции.



==25

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

• число стеков = Один или Несколько;
• размер стековых буферов = Маленькие или Большие;
• число адресных аргументов = 0, 1 или 2.

2.1.1 Разница между одним и несколькими стеками

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

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



==26

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

Недостатком единственного стека является принудительная вложенность данных для подпрограмм и адресов возврата. Модульный подход к программированию вызывает постоянное появление новых копий данных при прохождении информационных блоков сквозь программные интерфейсы между многочисленными уровнями программы. Дубли появляются в ходе создания новых активационных записей [* для функций следующего уровня вложенности ] .

У компьютеров с несколькими стеками ( Multiple Stack ) имеются и поддерживаются системой команд два или более стека. Один обычно хранит адреса возврата, а остальные используют для вычисления выражений и передачи параметров. Несколько стеков позволяют разделять логику управления и данные [*] .

В том случае, когда стек параметров отделён от стека адресов возврата, данные могут передаваться сквозь несколько уровней программы без размножения через новые списки параметров [*] .

[* Выделено мной]
[* Одно из в высшей степени важных свойств стековых машин, позволяющее существенно уменьшить расход стекового пространства при рекурсивном спуске по алгоритму ( §6.4.1 ) или при проходе через множество уровней вложенности программы. И, понятное дело, заодно полностью уничтожает само понятие инкапсуляции, приватности данных, свободы личности, неприкосновенности частной собственности... Осталось только чужих тёток обобществить].

Важным преимуществом нескольких стеков является скорость, т.к. такая конфигурация позволяет в одном такте получить доступ сразу к группе параметров. Например, машина, которая имеет одновременный доступ к параметрам и адресу возврата, может выполнять вызов подпрограммы или возврат из неё одновременно с выполнением действий над данными [* подробнее об этом см. описание модели NC4016 фирмы Novix в §4.4 ] .

2.1.2 Размер стековых буферов

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

Архитектуры с маленьким стековым буфером ( Small Stack Buffer ) располагают его в зарезервированной части памяти общего назначения. При этом используется та же подсистема памяти, что и для хранения кода и переменных. Это, в свою очередь, позволяет при необходимости использовать для доступа к элементам стека обычные инструкции обращения к памяти. Отдельные операнды могут адресоваться со смещением от значения регистра-указателя стека или стекового кадра.

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



==27

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

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

Если величина стековых буферов достаточна для того, чтобы не загружать шину памяти доступом к элементам стека, то архитектура попадает в классификационную группу с большими стековыми буферами ( Large Stack Buffer ). Такие буфера могут иметь несколько форм. Это может быть большой набор регистров, доступный через регистровое окно, подобный используемому в процессоре RISC I ( Sequin & Patterson 1982 ), отдельный блок памяти, независимый от основного её объёма, или специальный стековый кэш в процессоре ( Ditzel & McLellan 1982 ). В любом случае, стековый буфер считается «большим», если несколько уровней подпрограмм ( скажем, пять или более ) могут обрабатываться без исчерпания его объёма. В случае стека, используемого только для вычисления выражений, термин «большой» может означать 16 элементов, так как выражения редко имеют глубокую вложенность ( Haley 1962 ). В шестой части будет рассмотрена статистика исполнения программ, которая покажет, насколько большим должен быть «большой» буфер.

Преимуществом больших стековых буферов является отсутствие циклов обращения к памяти при обращении к операндам или адресам возврата. Это приводит к существенному приросту скорости в системах с интенсивным использованием подпрограмм.

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

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

2.1.3 0-, 1- и 2-операндная адресация

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



==28

0-операндные инструкции не допускают никаких операндов, связанных с кодом команды. Все операции подразумевают действия над одним или несколькими верхними элементами стека. Такой вид адресации часто называется «чисто стековой» адресацией.

0-операндная архитектура вынуждена использовать один из своих стеков для вычисления выражений.

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

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

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

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

Машины с 1-операндным форматом инструкций обычно производят операции, подразумевая вершину стека в качестве второго операнда. 1-операндная адресация, называемая также «стеково-аккумуляторной», обеспечивает большую гибкость, чем 0-операндная, так как совмещает выборку операнда с действиями над стеком.

Keedy ( 1978a и 1978b ) доказал, что для вычисления выражений архитектура со стеком и аккумулятором использует меньше инструкций, чем чисто стековая. Его аргументы указывают на то, что общий размер программы для 1-операндной конструкции может быть меньше, чем для 0-операндной. Естественно, не без компромиссов. Так как операнд указывается в инструкции, эффективная реализация должна включать конвейер выборки параметров или иметь увеличенную длительность цикла, учитывающую время доступа к ним. В тех случаях, когда операнд находится в стеке параметров или в стеке для вычисления выражений, и адресация должна производиться через смещение на конкретный элемент, на исполнение требуется больше времени или более сложная реализация конвейера, чем простая предвыборка верхушки стека в ожидании операции.



==29

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

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

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



==29