Штабелеукладчик - Stack machine

Для стековых машин в теории автоматов см. Выталкивающий автомат.

В Информатика, компьютерная инженерия и реализации языков программирования, а штабелеукладчик - это режим вычислений, в котором исполнительное управление полностью поддерживается посредством добавления (push), чтения и усечения (pop) в порядке очереди (FILO, также последний вошел - первым вышел или LIFO) буфер памяти, известный как куча, требуя очень мало регистры процессора. Стековой машины достаточно для координации работы всего компьютера и операционной системы, например, Берроуз B5000, может определять конкретную программу, например, интерпретатор для Adobe с PostScript язык форматирования печати, или может использоваться только в части потока выполнения программы.

Описание такого метода, требующего одновременного хранения в регистрах только двух значений, с ограниченным набором предопределенных операндов, которые можно было расширить путем определения дополнительных операндов, функций и подпрограмм, было впервые представлено на конференции Роберт С. Бартон в 1961 г.[1][2]

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

В стековой машине операнды, используемые в инструкциях, всегда имеют известное смещение (заданное в указателе стека) от фиксированного местоположения (нижняя часть стека, которая в конструкции оборудования всегда может быть в нулевой ячейке памяти), экономия драгоценного в-тайник или в-ЦПУ хранилище из-за того, что оно использовалось для хранения довольно большого количества адреса памяти или порядковые номера. Это приводит к архитектура набора команд (ISA) стиль, известный как формат нулевого адреса,[3] и может сохранять такие регистры и кэш для использования в непоточных вычислениях.[нужна цитата ]

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

В Ява язык программирования виртуальная машина, ядро ​​к ОС Android используется на смартфоны, является очень часто встречающимся примером стековой машины.

Практические машины стека выражений

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

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

Для увеличения скорости стековая машина часто реализует часть своего стека с регистрами. Для быстрого выполнения операнды арифметико-логическое устройство (ALU) может быть двумя верхними регистрами стека, а результат ALU сохраняется в верхнем регистре стека. Некоторые стековые машины имеют стек ограниченного размера, реализованный как регистровый файл. ALU получит доступ к нему с помощью индекса. Некоторые машины имеют стек неограниченного размера, реализованный в виде массива в ОЗУ, доступ к которому осуществляется адресным регистром «вершины стека». Это медленнее, но количество триггеров меньше, что делает ЦП менее дорогим и компактным. Его самые верхние значения N могут быть кешированный для скорости. Некоторые машины имеют как стек выражений в памяти, так и отдельный стек регистров. В этом случае программное обеспечение или прерывание могут перемещать данные между ними.

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

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

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

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

Преимущества наборов команд стековой машины

Очень компактный объектный код

В коде стековой машины наиболее частые инструкции состоят только из кода операции, выбирающего операцию. Это может легко поместиться в 6 бит или меньше. Инструкции для ветвей, немедленной загрузки и загрузки / сохранения требуют поля аргумента, но стековые машины часто организуют так, чтобы частые случаи их по-прежнему умещались вместе с кодом операции в компактную группу битов. Выбор операндов из предыдущих результатов осуществляется неявно путем упорядочивания инструкций. В отличие от этого, регистровым машинам для выбора операндов требуется два или три поля номеров регистров на команду ALU; машины с самым плотным регистром в среднем составляют около 16 бит на инструкцию.

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

Все практичные стековые машины имеют варианты кодов операций загрузки-сохранения для доступа локальные переменные и формальные параметры без явных вычислений адреса. Это может быть смещение от текущего адреса вершины стека или смещение от стабильного регистра базы данных. Регистровые машины обрабатывают это в режиме адреса «регистр + смещение», но используют более широкое поле смещения.

Плотный машинный код была очень ценной в 1960-х, когда основная память была очень дорогой и очень ограниченной даже на мэйнфреймах. Это снова стало важным благодаря крошечным воспоминаниям о мини-компьютерах, а затем о микропроцессорах. Плотность остается важной сегодня для приложений для смартфонов, приложений, загружаемых в браузеры через медленное подключение к Интернету, а также в ПЗУ для встроенных приложений. Более общим преимуществом повышенной плотности является повышенная эффективность кеширования и предварительной выборки инструкций.

Некоторая плотность Берроуз B6700 Код был связан с перемещением важной информации об операнде в другое место, в «теги» каждого слова данных или в таблицы указателей. Сама инструкция Add была универсальной или полиморфной. Он должен был получить операнд, чтобы определить, было ли это добавлением целого числа или сложения с плавающей запятой. Команда загрузки могла отключиться от косвенный адрес или, что еще хуже, замаскированный звонок вызов по имени thunk рутина. Для общих кодов операций требуется меньше битов кода операции, но аппаратное обеспечение больше похоже на интерпретатор с меньшими возможностями конвейерной обработки общих случаев.

Простые компиляторы

Компиляторы для стековых машин проще и быстрее строить, чем компиляторы для других машин. Генерация кода тривиальна и не зависит от предыдущего или последующего кода. На рисунке показано синтаксическое дерево, соответствующее примеру выражения А*(B-C)+(D+E).

Дерево двоичного синтаксиса для выражения А*(B-C) + (D+E)

Скомпилированный код для простой стековой машины примет форму (соответствующую обратной польской нотации выражений А B C - * D E + +):

                 # содержимое стека (крайний левый = верхний): push A # A push B # BA push C # CBA вычесть # BC A умножить # A * (BC) push D # DA * (BC) нажать E # EDA * (BC) добавить # D + EA * (BC) добавить # A * (BC) + (D + E)

Арифметические операции «вычитание», «умножение» и «сложение» действуют на два самых верхних операнда стека.

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

Эта простота позволила компиляторам приспособиться к очень маленьким машинам. Простые компиляторы позволили новым линиям продуктов быстро выйти на рынок и позволили новым операционным системам быть написанными полностью на языке высокого уровня, а не на ассемблере. Например, UCSD p-система поддерживал полную среду программирования студентов на ранних 8-битных микропроцессорах с плохим набором инструкций и небольшим объемом оперативной памяти путем компиляции в виртуальную стековую машину, а не на фактическое оборудование.

Обратной стороной простоты компиляторов для стековых машин является то, что чистые стековые машины имеют меньше оптимизаций (см. Подразделы в § недостатки производительности стековых машин ). Однако оптимизация скомпилированного кода стека вполне возможна. Было продемонстрировано, что внутренняя оптимизация вывода компилятора значительно улучшает код,[5][6] и, возможно, производительность, в то время как глобальная оптимизация в самом компиляторе дает дополнительный выигрыш.[7]

Простые переводчики

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

Быстрый доступ к операнду

Поскольку нет полей операндов для декодирования, стековые машины извлекают каждую инструкцию и ее операнды одновременно. Стековые машины могут пропускать этап выборки операндов регистровой машины.[8] Кроме того, за исключением явной загрузки из памяти инструкций, порядок использования операндов идентичен порядку операндов в стеке данных. Превосходная предварительная выборка легко достигается за счет хранения операндов наверху стека в быстром хранилище. Например, в Оптимизированный для Java процессор (JOP) микропроцессор 2 верхних операнда стека напрямую входят в схему пересылки данных, которая работает быстрее, чем регистровый файл.[9]

Избегает прохождения данных через память, более быстрые интерпретаторы

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

Минимальное состояние процессора

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

Ответ на прерывание включает в себя сохранение регистров в стек, а затем переход к коду обработчика прерывания. В стековой машине большинство параметров уже находится в стеке. Следовательно, нет необходимости их туда толкать. Часто стековые машины быстрее реагируют на прерывания. Некоторые регистровые машины справляются с этим, имея несколько файлов регистров, которые могут быть мгновенно заменены[10] но это увеличивает затраты и замедляет регистрацию файла.

Недостатки производительности стековых машин

Больше ссылок на память

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

На машинах со стеком временные значения часто перетекают в память, тогда как на машинах с большим количеством регистров эти временные значения обычно остаются в регистрах. (Однако эти значения часто необходимо разделить на «кадры активации» в конце определения процедуры, в базовом блоке или, по крайней мере, в буфер памяти во время обработки прерывания). Значения, перенесенные в память, увеличивают количество циклов кеширования. Этот эффект пролива зависит от количества скрытых регистров, используемых для буферизации значений вершины стека, от частоты вызовов вложенных процедур и от скорости обработки прерываний главного компьютера.

Некоторые простые стековые машины или интерпретаторы стека не используют аппаратные регистры верхнего уровня. Эти минимальные реализации всегда медленнее, чем стандартные регистровые машины. Типичное выражение, такое как Х + 1 компилируется в Загрузить X; Нагрузка 1; Добавлять. Это неявная запись и чтение стека памяти, которые не нужны:

  • Загрузить X, поместить в память
  • Загрузить 1, вставить в память
  • Извлечь 2 значения из памяти, сложить и передать результат в память

всего 5 ссылок на кэш данных.

Следующий шаг - стек-машина или интерпретатор с одним регистром вершины стека. Приведенный выше код делает:

  • Загрузите X в пустой регистр TOS (если аппаратная машина), или
  • Поместите регистр TOS в память, загрузите X в регистр TOS (если интерпретатор)
  • Вставьте регистр TOS в память, загрузите 1 в регистр TOS
  • Извлечь левый операнд из памяти, добавить в регистр TOS и оставить там

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

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

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

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

Высокая стоимость выделения общих подвыражений

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

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

Второй способ оставляет вычисленное значение в стеке данных, дублируя его по мере необходимости. При этом используются операции для копирования записей стека. Стек должен иметь достаточно мелкую глубину для доступных инструкций копирования ЦП. Рукописный стековый код часто использует этот подход и достигает скорости, как у регистровых машин общего назначения.[8][12][13] К сожалению, алгоритмы оптимального «планирования стека» не широко используются языками программирования.

Порядок жесткого кода

В современных машинах время выборки переменной из кэша данных часто в несколько раз больше, чем время, необходимое для базовых операций ALU. Программа работает быстрее без остановок, если загрузка ее памяти может быть запущена за несколько циклов до инструкции, которая нуждается в этой переменной. Сложные машины могут делать это с помощью глубокого конвейера и «выполнения вне очереди», которые проверяют и выполняют множество инструкций одновременно. Регистрирующие машины могут делать это даже с помощью гораздо более простого «упорядоченного» оборудования, неглубокого конвейера и немного более умных компиляторов. Шаг загрузки становится отдельной инструкцией, и эта инструкция статически планируется намного раньше в кодовой последовательности. Компилятор помещает между ними независимые шаги.

Для планирования доступа к памяти требуются явные резервные регистры. Это невозможно на стековых машинах без раскрытия программисту некоторых аспектов микроархитектуры. Для выражения A-B правый операнд должен быть вычислен и передан непосредственно перед шагом минус. Без перестановки стека или аппаратной многопоточности относительно небольшой полезный код может быть вставлен между ними, ожидая завершения загрузки B. Стековые машины могут обойти задержку памяти, либо имея глубокий конвейер выполнения вне очереди, охватывающий сразу несколько инструкций, либо, что более вероятно, они могут переставлять стек, чтобы они могли работать с другими рабочими нагрузками, пока загрузка завершается, либо они может чередовать выполнение различных программных потоков, как в системе Unisys A9.[14] Однако сегодняшние все более параллельные вычислительные нагрузки предполагают, однако, что это не может быть недостатком, который, как считалось, был в прошлом.

Возможность использовать исполнение вне очереди

В Алгоритм Томасуло находит параллелизм на уровне инструкций путем выдачи инструкций по мере того, как их данные становятся доступными. По сути, адреса позиций в стеке ничем не отличаются от регистровых индексов регистрового файла. Эта точка зрения позволяет внеочередное исполнение алгоритма Томасуло для использования со стековыми машинами.

Выполнение вне очереди в стековых машинах, кажется, уменьшает или позволяет избежать многих теоретических и практических трудностей.[15] Процитированное исследование показывает, что такая стековая машина может использовать параллелизм на уровне команд, и полученное оборудование должно кэшировать данные для инструкций. Такие машины эффективно обходят большинство обращений к стеку памяти. В результате достигается пропускная способность (инструкции на Часы ) сравним с RISC регистровые машины с гораздо более высокой плотностью кода (поскольку адреса операндов неявны).

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

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

Скрывает внутри более быструю регистровую машину

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

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

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

Трансляторы объектного кода для HP 3000 и Тандем Другой пример - T / 16.[16][17]Они преобразовали последовательности кода стека в эквивалентные последовательности кода RISC. Незначительные «локальные» оптимизации устранили большую часть накладных расходов на стековую архитектуру. Для исключения повторных вычислений адресов использовались резервные регистры. В переведенном коде по-прежнему сохраняется много накладных расходов на эмуляцию из-за несоответствия между исходной и целевой машинами. Несмотря на это бремя, эффективность цикла транслированного кода соответствовала эффективности цикла исходного кода стека. А когда исходный код был перекомпилирован прямо на регистровую машину с помощью оптимизирующих компиляторов, эффективность удвоилась. Это показывает, что архитектура стека и ее неоптимизирующие компиляторы расходовали более половины мощности основного оборудования.

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

Больше инструкций, более медленные переводчики

Интерпретаторы для виртуальных машин стека часто медленнее, чем интерпретаторы для других стилей виртуальных машин.[18] Это замедление является наиболее сильным при работе на хост-машинах с глубокими конвейерами выполнения, такими как современные чипы x86.

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

В некоторых интерпретаторах интерпретатор должен выполнить N-позиционный переход переключателя, чтобы декодировать следующий код операции и перейти к его шагам для этого конкретного кода операции. Другой метод выбора кодов операций: многопоточный код. Механизмы предварительной выборки хост-машины не могут предсказать и получить цель этого индексированного или косвенного перехода. Таким образом, конвейер выполнения на главной машине должен перезапускаться каждый раз, когда размещенный интерпретатор декодирует другую виртуальную инструкцию. Это происходит чаще для виртуальных стековых машин, чем для других стилей виртуальных машин.[19]

Android Дальвик виртуальная машина для Java использует 16-битный набор команд виртуального регистра вместо обычного 8-битного кода стека Java, чтобы минимизировать количество команд и задержки отправки кода операции. Арифметические инструкции напрямую выбирают или сохраняют локальные переменные через 4-битные (или более крупные) поля инструкций. Версия 5.0 Lua заменила свою виртуальную стековую машину на более быструю виртуальную регистровую машину.[20][21]

С тех пор, как виртуальная машина Java стала популярной, микропроцессоры стали использовать передовые предикторы ветвления для непрямых прыжков.[22] Это усовершенствование позволяет избежать большинства перезапусков конвейера из N-образных переходов и устраняет большую часть затрат на подсчет инструкций, которые влияют на интерпретаторы стека.

Гибридные машины

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

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

Другой распространенный гибрид - начать с архитектуры регистровой машины и добавить еще один режим адресации памяти, который имитирует операции push или pop стековых машин: 'memaddress = reg; reg + = instr.displ '. Впервые это было использовано в DEC с PDP-11 миникомпьютер. Эта функция была перенесена в VAX компьютеры и в Motorola 6800 и M68000 микропроцессоры. Это позволило использовать более простые методы стека в ранних компиляторах. Он также эффективно поддерживает виртуальные машины с помощью интерпретаторов стека или многопоточный код. Однако эта функция не помогла собственному коду регистровой машины стать таким же компактным, как код чистой стековой машины. Кроме того, скорость выполнения была меньше, чем при хорошей компиляции в регистровую архитектуру. Менять указатель вершины стека только изредка (один раз за вызов или возврат) быстрее, чем постоянно повышать и опускать его на протяжении каждого оператора программы, и еще быстрее полностью избежать ссылок на память.

Совсем недавно так называемые стековые машины второго поколения приняли специальный набор регистров, которые служат в качестве адресных регистров, что позволяет избавиться от задач адресации памяти из стека данных. Например, MuP21 использует регистр под названием «A», тогда как более поздние процессоры GreenArrays используют два регистра: A и B.[23]

Семейство микропроцессоров Intel x86 имеет набор инструкций регистрового стиля (аккумулятор) для большинства операций, но для его выполнения используются инструкции стека. x87, Intel 8087 арифметика с плавающей запятой, восходящая к сопроцессору iAPX87 (8087) для 8086 и 8088. То есть нет доступных программисту регистров с плавающей запятой, а есть только 80-битный стек с глубиной 8. X87 в значительной степени полагается на процессор x86 для помощи в выполнении своих операций.

Коммерческие штабелеукладчики

Смотрите также: Архитектура компьютера на языке высокого уровня

Примеры наборов команд стека, непосредственно выполняемых на оборудовании, включают

Виртуальные стековые машины

Примеры виртуальный стековые машины интерпретируются в программном обеспечении:

Компьютеры, использующие стеки вызовов и фреймы стека

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

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

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

Некоторые стековые машины Burroughs поддерживают ссылки верхнего уровня непосредственно в аппаратном обеспечении со специализированными режимами адресации и специальным файлом регистров отображения, содержащим адреса фреймов всех внешних областей видимости. Никакие последующие компьютерные линейки не сделали этого аппаратно. Когда Никлаус Вирт разработал первый Паскаль компилятор для CDC 6000, он обнаружил, что в целом быстрее передавать указатели кадров в виде цепочки, чем постоянно обновлять полные массивы указателей кадров. Этот программный метод также не добавляет накладных расходов для распространенных языков, таких как C, в которых отсутствуют ссылки верхнего уровня.

Те же машины Burroughs также поддерживали вложение задач или потоков. Задача и ее создатель совместно используют кадры стека, которые существовали во время создания задачи, но не последующие кадры создателя или собственные кадры задачи. Это было поддержано кактус, компоновочная схема которого напоминала ствол и руки Сагуаро кактус. У каждой задачи был свой сегмент памяти, содержащий ее стек и принадлежащие ей фреймы. Основание этого стека связано с серединой стека его создателя. На машинах с обычным плоским адресным пространством стек создателя и стеки задач будут отдельными объектами кучи в одной куче.

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

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

Смотрите также

Рекомендации

  1. ^ Бартон, Роберт С. (1961). «Новый подход к функциональному дизайну цифрового компьютера». IRE-AIEE-ACM '61 (Western): доклады, представленные на совместной компьютерной конференции IRE-AIEE-ACM 9–11 мая 1961 года..
  2. ^ Бартон, Роберт С. (1987). «Новый подход к функциональному дизайну цифрового компьютера». IEEE Annals of the History of Computing.
  3. ^ Борода, Боб (осень 1997 г.). «Компьютер KDF9 - 30 лет спустя». Компьютерное ВОСКРЕСЕНИЕ.
  4. ^ а б "GreenArrays, Inc. - Документы". Greenarraychips.com. Получено 8 октября 2017.
  5. ^ Купман, Филипп (1994). «Предварительное исследование создания оптимизированного стекового кода» (PDF). Журнал приложений и исследований Forth. 6 (3).
  6. ^ Бейли, Крис (2000). «Межграничное планирование операндов стека: предварительное исследование» (PDF). Материалы конференции Euroforth 2000.
  7. ^ Шеннон, Марк; Бейли С. (2006). «Глобальное распределение стека: распределение регистров для машин стека» (PDF). Материалы конференции Euroforth 2006 г..
  8. ^ а б «Stack Computers: новая волна - онлайн-книга». Ece.cmu.edu. Получено 8 октября 2017.
  9. ^ «Разработка и внедрение эффективной штабелеукладчика» (PDF). Jopdesign.com. Получено 8 октября 2017.
  10. ^ Руководство по процессору 8051, Intel, 1980
  11. ^ «Компьютерная архитектура: количественный подход», Джон Л. Хеннесси, Дэвид Паттерсон; См. Обсуждение стековых машин.
  12. ^ «Стековая архитектура второго поколения» (PDF). Fpgacpu.ca. Получено 8 октября 2017.
  13. ^ «Архивная копия» (PDF). Архивировано из оригинал (PDF) на 2011-07-18. Получено 2010-11-01.CS1 maint: заархивированная копия как заголовок (связь)
  14. ^ «Архивная копия» (PDF). Архивировано из оригинал (PDF) на 2011-03-21. Получено 2011-03-29.CS1 maint: заархивированная копия как заголовок (связь)
  15. ^ Чаттерджи, Сатраджит; Равиндран, Кошик. "BOOST: Беркли вышла из строя Stack Stack Thingie". Исследовательские ворота. Кошик Равиндран. Получено 16 февраля 2016.
  16. ^ Берг, Арндт; Кейлман, Кейт; Магенгеймер, Даниэль; Миллер, Джеймс (декабрь 1987 г.). «Эмуляция HP3000 на компьютерах с прецизионной архитектурой HP» (PDF). Журнал Hewlett-Packard: 87–89. Получено 8 октября 2017.
  17. ^ Миграция семейства компьютеров CISC на RISC с помощью преобразования объектного кода, К. Эндрюс и Д. Сэнд, Proceedings of ASPLOS-V, октябрь 1992 г.
  18. ^ Ши, Юньхэ; Грегг, Дэвид; Битти, Эндрю; Эртле, М. Антон. ""Противостояние виртуальных машин: стек против регистровой машины"" (PDF). Usenix.org. Получено 8 октября 2017.
  19. ^ Дэвис, Брайан; Битти, Эндрю; Кейси, Кевин; Грегг, Дэвид; Уолдрон, Джон. "'Аргументы в пользу виртуальных регистровых машин'" (PDF). Scss.tcd.ie. Получено 8 октября 2017.
  20. ^ «Реализация Lua 5.0» (PDF). Lua.org. Получено 8 октября 2017.
  21. ^ «Виртуальная машина Lua 5.0» (PDF). Inf.puc-rio.br. Получено 8 октября 2017.
  22. ^ «Предсказание ветвей и работа переводчиков - не верьте фольклору». Hal.inria.fr. Получено 8 октября 2017.
  23. ^ а б ""Набор инструкций ядер F18A (назван colorForth по историческим причинам)."". Colorforth.com. Архивировано из оригинал на 2016-03-10. Получено 8 октября 2017.
  24. ^ ""GreenArrays, Inc."". Greenarraychips.com. Получено 8 октября 2017.
  25. ^ «Принципы работы процессора Mesa». Компьютерный музей DigiBarn. Ксерокс. Получено 23 декабря 2019.
  26. ^ "DigiBarn: Xerox Star 8010" Одуванчик"". Компьютерный музей DigiBarn. Получено 23 декабря 2019.
  27. ^ «Первый в мире процессор Java», Дэвид А. Грев и Мэтью М. Уайлдинг, Electronic Engineering Times, 12 января 1998 г.,
  28. ^ [1]
  29. ^ «Четвертые фишки». Colorforth.com. Архивировано из оригинал 15 февраля 2006 г.. Получено 8 октября 2017.
  30. ^ «Обзор микропроцессора F21». Ultratechnology.com. Получено 8 октября 2017.
  31. ^ "ForthFreak wiki". GitHub.com. 25 августа 2017 г.. Получено 8 октября 2017.
  32. ^ "Доступен чип Java - сейчас! - Developer.com". Developer.com. Получено 8 октября 2017.
  33. ^ «4стековый процессор». bernd-paysan.de. Получено 8 октября 2017.
  34. ^ «Архивная копия» (PDF). Архивировано из оригинал (PDF) на 2011-08-20. Получено 2011-03-30.CS1 maint: заархивированная копия как заголовок (связь)
  35. ^ «ZPU - самый маленький 32-разрядный процессор в мире с набором инструментов GCC: обзор». opencores.org. Получено 7 февраля 2015.
  36. ^ Рэнделл, Брайан и Рассел, Лоуфорд Джон "Реализация Algol 60 "Лондон: Academic Press, 1964. ISBN  0-12-578150-4.

внешняя ссылка