Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Для стековых машин в теории автоматов см. Автомат выталкивания .

В информатике , вычислительной техники и программирования реализаций языка , стек машины является процессор компьютера или виртуальной машины , в которой логический блок Арифметический первичное взаимодействие «s это и от толчка вниз стека вместо регистров процессора . (В случае аппаратного процессора используется аппаратный стек .) Использование стека значительно сокращает необходимое количество регистров процессора . Стек-машина - это полный компьютер по Тьюрингу. Как и любой другой компьютер, он использует операционную систему для управления своими процессами. Например,Burroughs B5000 был стековой машиной, и ее набор команд определял язык программирования относительно высокого уровня. Аналогичным образом , интерпретатор Adobe «s PostScript форматирование печати языка является стек виртуальной машины.

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

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

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

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

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

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

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

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

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

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

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

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

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

Преимущества наборов инструкций стековых машин [ править ]

Очень компактный объектный код [ править ]

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

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

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

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

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

Простые компиляторы [ править ]

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

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

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

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

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

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

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

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

Простые интерпретаторы [ править ]

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

Быстрый доступ к операндам [ править ]

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

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

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

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

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

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

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

Больше ссылок на память [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Порядок жестких кодов [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

Дополнительные инструкции, более медленные переводчики [ править ]

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

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

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

Виртуальная машина Android Dalvik для 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 для помощи в выполнении своих операций.

Коммерческие стековые машины [ править ]

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

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

  • Архитектура F18A 144-процессорного чипа GA144 от GreenArrays, Inc. [4] [23] [24]
  • Z4 компьютер от Конрада Цузе . [25]
  • Burroughs больших систем архитектуры (с 1961 года)
  • Xerox одуванчик представил 27 апреля 1981, используется стек архитектурой машины для экономии памяти. [26] [27]
  • английский электрический KDF9 машина. Впервые представленный в 1964 году, KDF9 имел стек арифметических регистров глубиной 19 и глубину 17 для адресов возврата подпрограмм.
  • Collins Radio Collins Адаптивная система обработки миникомпьютер (CAPS, начиная с 1969 года) и Rockwell Collins Advanced Architecture Микропроцессор (AAMP, начиная с 1981 года). [28]
  • UCSD Паскаль р-машина (как Паскаль микродвигатель и многие другие)
  • Серии MU5 и ICL 2900 . Гибридные штабелеукладчики и аккумуляторные машины. Регистр аккумулятора буферизует верхнее значение данных стека памяти. Варианты кодов операций загрузки и сохранения, контролируемые, когда этот регистр был перенесен в стек памяти или перезагружен оттуда.
  • HP 3000 (классический, не PA-RISC)
  • Тандемные компьютеры Т / 16. Как и HP 3000, за исключением того, что компиляторы, а не микрокод, управляют, когда стек регистров перетекает в стек памяти или пополняется из стека памяти.
  • Atmel MARC4 микроконтроллер [29]
  • Несколько «чипов Forth» [30], таких как RTX2000 , RTX2010 , F21 [31] и PSC1000 [32] [33]
  • Сетунь компьютер троичного осуществляется сбалансировано тройной с использованием стеки.
  • Процессор 4stack от Bernd Paysan имеет четыре стека. [34]
  • Стековая машина Ignite компании Patriot Scientific, разработанная Чарльзом Х. Муром, является ведущим эталоном функциональной плотности .
  • Микропроцессор Saab Ericsson Space Thor с радиационной стойкостью [35]
  • Inmos transputers .
  • ZPU Физически небольшой ЦП, предназначенный для управления системами FPGA . [36]

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

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

  • Ветстоун алгол 60 интерпретирующий код, [37] , на которых были основаны некоторые особенности Burroughs B6500
  • UCSD Паскаль р-машина; который очень напоминал Берроуза
  • р-код машины Никлаус Вирт
  • Болтовня
  • виртуальная машина Java набор команд
  • WebAssembly байткодом
  • Virtual Execution System (VES) для общего промежуточного языка (CIL) набор команд в .NET Framework (ECMA 335)
  • Forth языка программирования, особенно интеграле виртуальная машина
  • Adobe PostScript
  • Язык программирования Parakeet
  • Язык программирования SwapDrop от Sun Microsystems для идентификации смарт-карт Sun Ray
  • Виртуальная машина Adobe ActionScript 2 (AVM2)
  • Эфириума EVM «сек
  • CPython байткодом переводчик
  • рубин YARV интерпретатор байт - кода
  • Rubinius виртуальная машина
  • шс (язык программирования) в Unix использует стек машину виртуальной команд процесса, после того, как первые транспонирования при условии , формы ввода языка, в обратную польскую запись
  • Луа (язык программирования) C API

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

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

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

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

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

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

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

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

См. Также [ править ]

  • Стек-ориентированный язык программирования
  • Конкатенативный язык программирования
  • Сравнение виртуальных машин приложений

Ссылки [ править ]

  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. ^ a b «GreenArrays, Inc. - Документы» . Greenarraychips.com . Проверено 8 октября 2017 года .
  5. ^ Купман, Филипп (1994). «Предварительное исследование создания оптимизированного стека кода» (PDF) . Журнал приложений и исследований Forth . 6 (3).
  6. ^ Бейли, Крис (2000). «Межграничное планирование операндов стека: предварительное исследование» (PDF) . Материалы конференции Euroforth 2000 .
  7. ^ Шеннон, Марк; Бейли С. (2006). «Глобальное распределение стека: распределение регистров для машин стека» (PDF) . Материалы конференции Euroforth 2006 .
  8. ^ a b «Стековые компьютеры: новая волна - он-лайн книга» . 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) 18 июля 2011 года . Проверено 1 ноября 2010 . CS1 maint: заархивированная копия как заголовок ( ссылка )
  14. ^ «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 21 марта 2011 года . Проверено 29 марта 2011 . CS1 maint: заархивированная копия как заголовок ( ссылка )
  15. ^ Чаттерджи, Сатраджит; Равиндран, Кошик. "BOOST: Беркли Out Of Order Stack Thingie" . Исследовательские ворота . Кошик Равиндран . Проверено 16 февраля +2016 .
  16. ^ Берг, Арндт; Кейлман, Кейт; Магенгеймер, Даниэль; Миллер, Джеймс (декабрь 1987 г.). «Эмуляция HP3000 на компьютерах с прецизионной архитектурой HP» (PDF) . Журнал Hewlett-Packard : 87–89 . Проверено 8 октября 2017 года .
  17. ^ Миграция семейства компьютеров CISC на RISC с помощью преобразования объектного кода, К. Эндрюс и Д. Сэнд, Труды 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. ^ a b " " Набор команд ядер F18A (назван colorForth по историческим причинам). " " . Colorforth.com . Архивировано из оригинала на 2016-03-10 . Проверено 8 октября 2017 года .
  24. ^ " " GreenArrays, Inc. " " . Greenarraychips.com . Проверено 8 октября 2017 года .
  25. ^ http://fpgacpu.ca/publications/Second-Generation_Stack_Computer_Architecture.pdf
  26. ^ "Принципы работы процессора Mesa" . Компьютерный музей DigiBarn . Xerox . Проверено 23 декабря 2019 .
  27. ^ «DigiBarn: Xerox Star 8010« Одуванчик » » . Компьютерный музей DigiBarn . Проверено 23 декабря 2019 .
  28. ↑ «Первый в мире процессор Java» , Дэвид А. Грев и Мэтью М. Уилдинг, Electronic Engineering Times , 12 января 1998 г.,
  29. ^ [1]
  30. ^ «Четвертые фишки» . Colorforth.com . Архивировано из оригинального 15 февраля 2006 года . Проверено 8 октября 2017 года .
  31. ^ «Обзор микропроцессора F21» . Ultratechnology.com . Проверено 8 октября 2017 года .
  32. ^ "ForthFreak wiki" . GitHub.com . 25 августа 2017 . Проверено 8 октября 2017 года .
  33. ^ «Доступен чип Java - сейчас! - Developer.com» . Developer.com . Проверено 8 октября 2017 года .
  34. ^ "4stack Processor" . bernd-paysan.de . Проверено 8 октября 2017 года .
  35. ^ «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 20 августа 2011 года . Проверено 30 марта 2011 . CS1 maint: заархивированная копия как заголовок ( ссылка )
  36. ^ «ZPU - самый маленький 32-разрядный процессор в мире с набором инструментов GCC: Обзор» . opencores.org . Проверено 7 февраля 2015 года .
  37. ^ Рэнделл, Брайан и Рассел, Лоуфорд Джон « Внедрение Алгола 60 » Лондон: Academic Press, 1964. ISBN 0-12-578150-4 . 

Внешние ссылки [ править ]

  • Stack Computers: книга новой волны Филипа Купмана-младшего, 1989 г.
  • Homebrew CPU в FPGA - доморощенный стековый компьютер с использованием FPGA
  • Mark 1 FORTH Computer - доморощенная стековая машина с дискретными логическими схемами
  • Компьютер Mark 2 FORTH - стековая машина homebrew с использованием Bitslice / PLD
  • Архитектура стекового компьютера второго поколения - Тезис об истории и конструкции стековых машин.