А стековые архитектуры процессоров - совсем умерли?
От: dmz Россия  
Дата: 21.10.08 04:21
Оценка:
Смотрю вот, стековые архитектуры совсем почили? Больше такого никто не использует и не делает? Последние статьи, которые я читал по теме и где выказывался какой-то оптимизм относительно таких архитектур, датированы началом 2000 — 2001 годом, потом все.

Т.е. есть может было какое-то событие — исследование или статья, которая показала их принципиальную ущербность?

Я собственно это к чему. Хочется поиграться, и ради развлечения воплотить какую-нибудь VM в железе, на базе FPGA, а поверх нее —
какую-нибудь операционку — просто посмотреть, что получится, ну и попрактиковаться в написании компиляторов. С/Unix портировать бессмысленно,
неинтересно и нереализуемо, а вот какой-нибудь альтернативный язык — типа форта и какую-нибудь легковесную ОС — вполне реально. Основная цель — посмотреть, что может получится в плане архитектуры и возможностей, если принципиально не ставить целей совместимости и преемственности.

Собственно, гораздо более интересно было бы реализовать не форт-машину, а что-то, ориентированное на функциональные языки — но совершенно
не представляю их модели вычислений — и есть ли вообще общая модель.
Re: А стековые архитектуры процессоров - совсем умерли?
От: deniok Россия  
Дата: 21.10.08 06:45
Оценка:
Здравствуйте, dmz, Вы писали:


dmz>Собственно, гораздо более интересно было бы реализовать не форт-машину, а что-то, ориентированное на функциональные языки — но совершенно

dmz>не представляю их модели вычислений — и есть ли вообще общая модель.

Для ленивого функционального языка моделью вычислений является редукция графов (G-машина); вообще про модели вычислений для ФЯ много написано в Харрисон, Филд, Функциональное программирование, М., Мир, 1993. В качестве примера можно привести STGMachine для Хаскелла: здесь.
Re: А стековые архитектуры процессоров - совсем умерли?
От: LaptevVV Россия  
Дата: 21.10.08 09:06
Оценка:
Здравствуйте, dmz, Вы писали:

dmz>Собственно, гораздо более интересно было бы реализовать не форт-машину, а что-то, ориентированное на функциональные языки — но совершенно

dmz>не представляю их модели вычислений — и есть ли вообще общая модель.

1. А.Филд, П.Харрисон. Функциональное программирование. М., «Мир», 1993.
2. П.Хендерсон. Функциональное программирование. Применение и реализация.
Серия: Математическое обеспечение ЭВМ, М., «Мир», 1983.
3. P.Hudak, J.Peterson, J.H.Fasel. A Gentle Introduction to Haskell 98. 1999.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re: А стековые архитектуры процессоров - совсем умерли?
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 21.10.08 12:42
Оценка:
Здравствуйте, dmz, Вы писали:

dmz>Т.е. есть может было какое-то событие — исследование или статья, которая показала их принципиальную ущербность?


Мои небольшие эксперименты показали, что стековая ВМ примерно вдвое медленнее регистровой — просто больше операций приходится делать.

dmz>Собственно, гораздо более интересно было бы реализовать не форт-машину, а что-то, ориентированное на функциональные языки — но совершенно

dmz>не представляю их модели вычислений — и есть ли вообще общая модель.

Если язык не ленивый, можно взглянуть на ВМ Окамла, она как раз стековая. здесь
Re[2]: А стековые архитектуры процессоров - совсем умерли?
От: dmz Россия  
Дата: 22.10.08 02:04
Оценка:
DM>Мои небольшие эксперименты показали, что стековая ВМ примерно вдвое медленнее регистровой — просто больше операций приходится делать.

В софте неважно, стековая машина или регистровая — тк накладные расходы несущественны. В железе все слегка иначе.


DM>Если язык не ленивый, можно взглянуть на ВМ Окамла, она как раз стековая. здесь


Ага, спасибо, гляну.
Re: А стековые архитектуры процессоров - совсем умерли?
От: geniepro http://geniepro.livejournal.com/
Дата: 22.10.08 06:35
Оценка:
Здравствуйте, dmz, Вы писали:

dmz>Смотрю вот, стековые архитектуры совсем почили? Больше такого никто не использует и не делает? Последние статьи, которые я читал по теме и где выказывался какой-то оптимизм относительно таких архитектур, датированы началом 2000 — 2001 годом, потом все.


Вполне современные разработки:

IntellaSys 40-core Processor Announced; Forth-based Dev Environment

SEAforth® 40C18
Re: А стековые архитектуры процессоров - совсем умерли?
От: merk Россия  
Дата: 24.10.08 18:55
Оценка:
Здравствуйте, dmz, Вы писали:

dmz>Собственно, гораздо более интересно было бы реализовать не форт-машину, а что-то, ориентированное на функциональные языки — но совершенно

dmz>не представляю их модели вычислений — и есть ли вообще общая модель.

удивительно, что люди не знают классики НАСТОЯЩИХ стековых машин.
принимайте. проект Lilith и modula-2 от Никлауса Вирта.
и отечественное расширение — 32 разрядный проц "кронос". это когда еще интелы были шышнадцатибитными(если не меньше)
сцыла по кроносу.
http://kronos.iis.nsk.su/
копайте вокруг. это короче машина высокоуровнего языка, типа модулы-2, с поддержкой динамической линковки(за счет индексной адресации, там модули вообще не линкуются, ну кроме одной ссылки в импортирующем модуле).

это архитектура проца, там даже есть текст интерпретатора
http://kronos.iis.nsk.su/sites/default/files/AR.DOC_.pdf

впрочем сам готовый интерпретатор есть и где-то внутри первой сцылы.
кстати было бы интересно сделать джит для этой машины и пускать прям на писи. если конечно в новосибире или еще где этого уже не сделали.
машина компактная, хорошо описанная, хорошо (вроде) отображаемая в обычную железку, должно получиться.
Re: А стековые архитектуры процессоров - совсем умерли?
От: Cyberax Марс  
Дата: 24.10.08 19:15
Оценка:
Здравствуйте, dmz, Вы писали:

dmz>Смотрю вот, стековые архитектуры совсем почили? Больше такого никто не использует и не делает? Последние статьи, которые я читал по теме и где выказывался какой-то оптимизм относительно таких архитектур, датированы началом 2000 — 2001 годом, потом все.

Да. Плохо на железки ложатся.

dmz>Я собственно это к чему. Хочется поиграться, и ради развлечения воплотить какую-нибудь VM в железе, на базе FPGA, а поверх нее Эффективнее получается перевести стековый код в регистровый, чем делать железки для стекового.
Sapienti sat!
Re: А стековые архитектуры процессоров - совсем умерли?
От: chukichuki  
Дата: 24.10.08 20:20
Оценка:
Здравствуйте, dmz, Вы писали:


dmz>Смотрю вот, стековые архитектуры совсем почили? Больше такого никто не использует и не делает? Последние статьи, которые я читал по теме и где выказывался какой-то оптимизм относительно таких архитектур, датированы началом 2000 — 2001 годом, потом все.


А как же аппаратные реализации Java VM ? В тех же современных мобильниках ? Вроде есть такие.

dmz>Собственно, гораздо более интересно было бы реализовать не форт-машину, а что-то, ориентированное на функциональные языки — но совершенно

dmz>не представляю их модели вычислений — и есть ли вообще общая модель.

Если не ленивая функциональщина, а энергиная то модель вычислений ровно такая же как и в обычном императивном программировании. Есть несколько тонкостей для реализации замыканий, обязательна сборка мусора, а в остальном все тоже самое как и в обычном Си
Re[2]: А стековые архитектуры процессоров - совсем умерли?
От: thesz Россия http://thesz.livejournal.com
Дата: 24.10.08 23:28
Оценка: 18 (1)
D>Для ленивого функционального языка моделью вычислений является редукция графов (G-машина); вообще про модели вычислений для ФЯ много написано в Харрисон, Филд, Функциональное программирование, М., Мир, 1993. В качестве примера можно привести STGMachine для Хаскелла: здесь.

An Architecture for Combinator Graph Reduction (TIGRE)
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[2]: А стековые архитектуры процессоров - совсем умерли?
От: thesz Россия http://thesz.livejournal.com
Дата: 24.10.08 23:35
Оценка: +1
dmz>>Т.е. есть может было какое-то событие — исследование или статья, которая показала их принципиальную ущербность?
DM>Мои небольшие эксперименты показали, что стековая ВМ примерно вдвое медленнее регистровой — просто больше операций приходится делать.

VM в виде программы и в виде процессора — разные вещи.

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

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

Вкратце: выбираем не одну команду, а две-три. Или выбрав одну команду, сразу выбираем вторую и переходим на оптимизированный кусок, если таковой определен для пару команд (а там и тройки подтянутся.)

Поэтому вместо двух операций LIT n; + получится одна LIT+.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[2]: А стековые архитектуры процессоров - совсем умерли?
От: thesz Россия http://thesz.livejournal.com
Дата: 24.10.08 23:48
Оценка: +1
dmz>>Смотрю вот, стековые архитектуры совсем почили? Больше такого никто не использует и не делает? Последние статьи, которые я читал по теме и где выказывался какой-то оптимизм относительно таких архитектур, датированы началом 2000 — 2001 годом, потом все.
C>Да. Плохо на железки ложатся.

Перевожу.

"Плохо на железки ложатся" означает "проблемы с конвейеризацией". Вместо четырех-семи этапов конвейера (fetch-[decode-]read-exec-mem-[exception-]-write, хотя у всех по-разному) получается всего два: fetch+decode-read+exec+write+mem. Соответственно, удлиняется критическая цепочка и тактовые частоты стековых процессоров заметно ниже регистровых.

Однако, конвейер не везде нужен. И он усложняет дизайн процессора.

Простой пример: у MIPS и SPARC после перехода добавляется команда для заполнения такта простоя конвейера. Этот "элегантный и получающийся естественно" прием приводит к усложнению обработки прерываний и трудностям при реализации внеочередного выполнения команд.

В более поздних разработках от этой особенности отказались (DEC Alpha, который был рассчитан на 20 лет эксплуатации без изменения набора команд, то есть, только-только бы начал устаревать, другие более свежие процессора, например, Beyond Architecture).

PS
Клатко обозрел PA-RISC. До чего же они все одинаковые!..
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Re[2]: А стековые архитектуры процессоров - совсем умерли?
От: Cyberax Марс  
Дата: 25.10.08 00:09
Оценка:
Здравствуйте, chukichuki, Вы писали:

dmz>>Смотрю вот, стековые архитектуры совсем почили? Больше такого никто не использует и не делает? Последние статьи, которые я читал по теме и где выказывался какой-то оптимизм относительно таких архитектур, датированы началом 2000 — 2001 годом, потом все.

C>А как же аппаратные реализации Java VM ? В тех же современных мобильниках ? Вроде есть такие.
У них задача — выполнять Java-байткод с приемлимой скоростью там, где нормальный JIT недоступен. Т.е. такой процессор будет неоптимальным, но хоть Java-байткод выполняться будет быстрее.
Sapienti sat!
Re[3]: А стековые архитектуры процессоров - совсем умерли?
От: merk Россия  
Дата: 25.10.08 09:09
Оценка:
Здравствуйте, thesz, Вы писали:

dmz>>>Смотрю вот, стековые архитектуры совсем почили? Больше такого никто не использует и не делает? Последние статьи, которые я читал по теме и где выказывался какой-то оптимизм относительно таких архитектур, датированы началом 2000 — 2001 годом, потом все.

C>>Да. Плохо на железки ложатся.

T>Перевожу.


T>"Плохо на железки ложатся" означает "проблемы с конвейеризацией". Вместо четырех-семи этапов конвейера (fetch-[decode-]read-exec-mem-[exception-]-write, хотя у всех по-разному) получается всего два: fetch+decode-read+exec+write+mem. Соответственно, удлиняется критическая цепочка и тактовые частоты стековых процессоров заметно ниже регистровых.


стековая машина в лоб реализуется как регистровая с большим регистровым пулом и регистром — указатель номера регистра(из пула) — текущей вершины стека.
разница будет только в том, что в оычной регистровой регистры доступны непоследственно, потому могут использоваться как кеш неких данных(ну там локальные переменные положить), в стековой они непосредственно не доступны.
но такая фича чисторегистровой машины тормозит переключение тредов, поскольку приходится спасать весь пул регистров. в стековой, по регистру StackTop всегда видно сколько регистров занято и спасаются только занятые. то есть на стековой быстрее можно сделать переключение тредов и переключать их чаще.
по поводу плохой конвейризации стековой машины непонятно, поскольку она по сути регистровая, с некоей модификацией. ну единственная трудность что по коду команды непонятно какой физически регистр она использует(это зависит от stacktop), но эта проблема обходится.
короче просьба пояснить про конвейер.
Re: А стековые архитектуры процессоров - совсем умерли?
От: mkizub Литва http://symade.tigris.org
Дата: 25.10.08 15:46
Оценка:
Здравствуйте, dmz, Вы писали:

У нас есть trade-off между количеством регистров общего назначения и размером инструкции.

При большом количестве регистров возможна хорошая оптимизация исполнения кода, как на этапе компиляции, так и на этапе исполнения (параллельное исполнение нескольких инструкций). Но каждый регистр — это его адрес в инструкции процессора. Если регистров 8, то на каждый регистр надо 3 бита, и на три регистра надо 9 бит. Если регистров 16, то на три регистра надо 12 бит и так далее. А ещё нужны биты для задания операции с регистрами. Инструкции процессора пухнут, в память они не влазят.
Как с этим борются?
MIPS — прострые инструкции, много регистров. Много вырожденных комманд, скажем, чтоб взять элемент массива 32-битных int-ов — надо отдельной коммандой сдвинуть регистр индекса, и отдельной коммандой загрузить значение из памяти.
ARM — более сложные инструкции с дополнительными операциями для одного из регистров (скажем, можно во время операции сдвинуть регистр индекса и взять значение из 32-битного массива int-ов за одну комманду), но меньше регистров (банально не влазят в инструкцию процессора номера регистров).
ARM Thumb — 16-ти битные комманды, за счёт упрощения системы комманд, уменьшения числа регистров, 2-х регистровых комманд — зато комманды занимают меньше места в памяти и грузятся из неё быстрее.
И другие способы борьбы (специализированные регистры, плавающий размер инструкций процессора и пр).
Можно добавить совсем много регистров, увеличивать размер инструкции (особенного когда память экономить не надо) — но начинаются проблемы с переключением контекстов, размером файлов регистров для всех конвееров и пр., а сильного увеличения производительности уже нет.
Все они имеют свои недостатки и достоинства, но однозначно лучшей среди них нет.

Стековые архитектуры стоят особняком — у них другой выбор в этом trade-off-е. Они жертвуют возможностью оптимизации (и выполняются значительно медленнее), но выигрывают в размере комманд. По одному байту на комманду. Регистры вообще не надо адресовать.

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

Что лучше? Зависит от задачи и прочих условий. Сейчас мы имеем ситуацию, когда скорость процессоров растёт медленно, а количество транзисторов растёт быстро. И плюс — большинство приложений однопоточны.
Очевидно, что для данных условий — регистровая модель лучше. Можно сделать достаточно сложный процессор, и он будет быстро исполнять наши потоки.
Для массового параллелизма — лучше выглядит стековая модель. Можно сделать много очень простых ядер и хоть каждое будет работать медленее, чем регистровое ядро — но в сумме они бы работали быстрее.
Да, на каждое ядро сейчас надо не только ALU, но и плавающие вычисления и синхронизацию кэшей и много чего, что усложняет архитектуру процессора так, что много ядер не сделаешь. Но если код будет действительно массово-параллельный, то можно будет сделать разделяемые FPU для простых ядер. Всё равно надо будет делать выделенную память для каждого ядра, переключение контекстов будет минимальным (при таком-то количество ядер — зачем их вообще переключать). То есть для массового параллелизма (сотни и тысячи потоков/ядер) стековая архитектура может оказаться в выигрышном положении. Фактически, это будет модель вычислений более близкая к нейронной. Каждое ядрышко будет себе таким нейрончиком, с небольшой своей памятью, очень небольшое само по себе, связанное с ближайшими соседями (так как общая шина не будет хорошо работать для тысяч процессоров на ней сидящих), выполняющее свой небольшой код (и хорошо, что он будет небольшого размера — у нас же нейро-ядро маленькое будет).

Скорее всего, архитектура будущего процессора будет совмещать несколько различных типов ядер — несколько ядер с максимальной скоростью выполнения потока. Сотни/тысячи стековы ядер для нейроно-подобных архитектур. Разделяемые FPU блоки, особенно для векторных графических 3D вычислений.

Так что, стековые архитектуры скорее всего вернутся, но в другом качестве. Вернутся, когда более выигрышной стратегией будет большее число ядер/тредов, а не более быстрое исполнение одного потока.
SOP & SymADE: http://symade.tigris.org , блог http://mkizub.livejournal.com
Re[2]: А стековые архитектуры процессоров - совсем умерли?
От: merk Россия  
Дата: 25.10.08 16:27
Оценка:
Здравствуйте, mkizub, Вы писали:

M>Здравствуйте, dmz, Вы писали:

M>Стековые архитектуры стоят особняком — у них другой выбор в этом trade-off-е. Они жертвуют возможностью оптимизации (и выполняются значительно медленнее), но выигрывают в размере комманд. По одному байту на комманду. Регистры вообще не надо адресовать.
чета вы путаете. основной выигрыш регистровых машин в использовании регистров в качестве кеша данных. время выполнение самих инструкций в обоих архитектурах — примерно одинаковые(при равной тактовой частоте). "медленное выполнение" команд стековой машины — это как-то спорно.
вопрос не в скорости выполнгения команд, а в модели вычислений — регистровая использует регистры как быструю память, стековая явным образом регистров не имеет, потому переменные у нее в некоей другой памяти.
но тут же виден импрувмент стековой машины, если так уж нужно увеличить скорость в данном случае — делать файл "быстрой памяти"(что есть на самом деле обычные регистры), но использовать их только для хранения данных, то есть в систему команд стекмашины добавить только команды
1.записать в/из быстрой памяти в обычную
2. push/pop с арифметического стека в обычную память.
это четыре команды всего.

M>Что мы имеем в сухом остатке? Для регистровых архитектур — сложный дизайн процессора, большой размер кода — но быстрое исполнение комманд. Для стековых архитектур — простой дизайн процессора и небольшой размер кода — но медленное исполнение комманд. Увеличение сложности процессора позволяет ускорить исполнение кода и там и там, но максимальная скорость регистровых архитектур для стековых недостижима.

недостижима. но лишь потому, что можно данные держать на регистрах. а доступ к регистрам это даже быстрей чем доступ к ближ. кешу.
если стековая машина сделана на регистровом пуле, где регистр stacktop есть индекс верхушки стека, то всегда можно вычислить реальные номера регистров пула просмотром команд вперед, то есть можно просматривать команды стекмашины вперед, динамически предсказывая верхушку стека. тогда последовательность команд стекмашины "видна" как обычные регистровые команды на физических регистрах неких номеров. то есть вся регистровая кухня предсказаний и параллельных запусков тоже работает.
вроде так.
Re[3]: А стековые архитектуры процессоров - совсем умерли?
От: merk Россия  
Дата: 25.10.08 16:34
Оценка:
M>1.записать в/из быстрой памяти в обычную
M>2. push/pop с арифметического стека в обычную память.
M>это четыре команды всего.
тут я ошибся — push/pop в быструю память. в обычную там есть и так.
в терминах регистровой машины(на которую мы отобразили стековую) команда push fast_mem[i] будет представлять собой команду
mov fast_mem_regs[i], stack_reg_pool[stack_top_reg++]
где fast_mem_regs — регистры пула "быстрой памяти"
stack_regs_pool — регистры на которые отображен арифметический стек нашей машины.
Re[4]: А стековые архитектуры процессоров - совсем умерли?
От: Cyberax Марс  
Дата: 25.10.08 16:42
Оценка:
Здравствуйте, merk, Вы писали:

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

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

M>по поводу плохой конвейризации стековой машины непонятно, поскольку она по сути регистровая, с некоей модификацией.

Нельзя по командам узнать какие данные для каких команд нужны. Точнее, можно — но это, фактически, требует перевода в регистровую форму. Спрашивается: и нафига городить тогда огород?
Sapienti sat!
Re[3]: А стековые архитектуры процессоров - совсем умерли?
От: Cyberax Марс  
Дата: 25.10.08 16:47
Оценка:
Здравствуйте, merk, Вы писали:

M>недостижима. но лишь потому, что можно данные держать на регистрах. а доступ к регистрам это даже быстрей чем доступ к ближ. кешу.

Она почти одинакова. Проблема в том, что код с регистрами проще параллелить — сразу видны зависимости по данным. А код, адресующий данные в памяти, придётся проверять на aliasing.
Sapienti sat!
Re[4]: А стековые архитектуры процессоров - совсем умерли?
От: mkizub Литва http://symade.tigris.org
Дата: 25.10.08 17:01
Оценка:
Здравствуйте, merk, Вы писали:

Если у нас есть адресуемую быструю "регистровую" память (а так оно и есть в java/.net байткоде), то мы можем
а) реализовать в железе сложный декдер, который будет последовательность
load r1
load r2
add
save r3
декодировать в одну комманду
add r1, r2, r3
и выполнять её за 1 такт.
б) реализовать в процессоре простой декодер, который будет воспринимать эту последовательность как 4 комманды, и выполнять за 4 такта.

Случай (а) фактически равнозначен реализации регистровой архитектуры, но при этом декодер будет сложнее, чем для регистровых комманд. Это раз. Второе, таким образом мы фактически имитируем MIPS архитектуру, с её упрощёнными коммандами. При том, что такие комманды у нас будут по факту 32-битными (как в MIPS), а вот регистров мы сможем адресовать меньше (4 регистра в ява-байткоде за счёт информации о типах, можно сделать 8 если объединить int+float и long+double). А у MIPS-а влазит в 32-разрядную комманду 16 регистров общего назначения. Вторая сложность, это то, что у нас будет, фактически, система инструкций переменной длинны, и адресация для jump-ов будет более короткой (её надо будет указывать в байтно, а при 16/32-битных коммандах — в коммандах). То есть в общем зачёте стековая архитектура/система комманд проиграет регистровой.

Под "более медленным исполнением" стековых комманд я имел в виду случай (б). Поскольку случай (a) нет смысла реализовывать — будет проще и дешевле реализовать регистровый процессор/набор комманд, который мы ещё и исполнить сможем быстрее (можно уложить тот-же по функциональности код в меньшее число комманд/тактов).
SOP & SymADE: http://symade.tigris.org , блог http://mkizub.livejournal.com
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.