Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 18:47

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ 1 сообщение ] 
Автор Сообщение
 Заголовок сообщения: Почему стек
СообщениеДобавлено: Чт май 21, 2009 19:33 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Автор: mOleg
Дата публикации: 2009.05.21
публикуется впервые

Почему стек

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

Любой алгоритм можно выполнить, используя всего четыре регистра: 2 регистра данных: ra и rb , указатель на выполняемую команду ip, и флаговый регистр f. Регистры ra, rb, ip могут получать данные из памяти, а так же, скорее всего, пересылать данные между собой. Флаговый регистр f содержит битовые флаги, отражающие особенности полученного результата после выполнения последней операции: арифметической, логической либо операции сравнения, а так же, если есть возможность, операции прямой установки флага. Операции управления потоком исполнения (переходы, ветвления) возлагаются на команды пересылки между регистрами или памятью и регистром ip.
Практически любая процессорная архитектура является развитием этой простейшей вычислительной модели.

О "четверках"

Собственно, одна из методик преобразования кода основана на генерации, так называемых, «четверок»(tuples), которые, по сути, и отражают «базовую архитектуру» описанную выше. Четверки – это перечисление двух взаимодействующих операндов, выполняемой операции, и операнда приемника. Формально любая доступная ячейка памяти может быть любым из операндов.
Четверки выглядят следующим образом:
для простейшей формулы: a+b=c четверка будет выглядеть так: a b + c .
Более сложные формулы, преобразуются последовательно к виду большого количества последовательно идущих «четверок» : d = (a+b)*c ,приведенное к виду четверок, будет состоять из двух «четверок»:
a b + t1
t1 c * d
где t1 – временная переменная, которая так же может быть регистром, впрочем, возможен и другой вариант:
a b + d
d c * d
при условии, что d не хранит важных (нужных в дальнейшем) данных, а так же том условии, что регистр источник одновременно может являться и приемником результата (что является достаточно обычной практикой), однако, это относится уже к области оптимизации кода.

Проблемы базовой архитектуры

Тому, кто уже задался вопросом, почему же не существует процессоров с описанной выше «базовой архитектурой», стоит отметить, что такой «четверочный» процессор будет очень сильно нагружать память, а более-менее сложные алгоритмы будут приводить к дополнительным обращениям в память для сохранения/восстановления промежуточных данных (регистр t1 в примере). Когда вычисления линейны, то есть операнды для следующей операции являются результатом предыдущей операции, накладных расходов не возникает. Но, как только эта особенность вычислений нарушается, приходится:
1) сохранять промежуточный результат где-то в памяти;
2) выгружать, нужные в последствии операнды, уже находящиеся в регистре;
3) загружать в регистры новые значения (которые уже возможно там ранее находились).
Все это плохо по нескольким причинам:
1) падение быстродействия, так как обращение к памяти практически всегда медленнее работает, чем регистровые операции;
2) дополнительные расходы памяти для хранения временных переменных;
3) возникают проблемы реентерабельности кода, то есть при попытке, к примеру, рекурсивно вызвать кусок кода, возникнет конфликт из-за места хранения временной переменной;
4) разрешение проблемы повторного выполнения (3) приводит к дополнительным пересылкам, а значит расходу памяти и особенно затрачиваемого времени.

Возможные варианты
Первое, что приходит в голову, увеличить количество доступных регистров – тогда придется реже выгружать нужные данные, и реже обращаться к памяти – это путь, по которому пошли практически все процессорные архитектуры, и в первую очередь RISC процессоры. Однако такой подход не решает всех проблем, и создает дополнительные:
- регистров всеравно не хватает,
- в многопоточных программах приходится сохранять/восстанавливать весь массив регистров,
- усложняется формат команды, а значит и средняя ее длина,
- увеличивается размер кода,
- значительно увеличивается время реакции на прерывания,
- усложняется архитектура самого процессора.
В плюс ко всему усложняется работа компилятора, которому нужно выкрутиться таким образом, чтобы в регистровый файл попали наиболее часто встречающиеся данные, то есть уменьшить по возможности количество сохранений и восстановлений содержимого регистров, которое при любом размере регистрового файла существует, а это не так уж и просто. CISC архитектура обычно меньше регистров использует, чем RISC, та же Intel x86 архитектура имеет всего 10 регистров (без учета сегментных и других подобных) против массивов в 30, 60 и более регистров общего назначения у RISC.

Альтернативой является стек. Стек изумительная по своей простоте и мощи вещь. Идея заключается в том, что, вместо «выгрузки» промежуточного результата в память, значение «утапливается» в тот же регистр (который теперь стал стеком). Как только значение становится нужным, оно «всплывает» и занимает то же самое место. Стек располагается в отдельной памяти, иначе выигрыша никакого по сравнению с регистровой архитектурой собственно почти и нет. Даже есть небольшой проигрыш в виде появления еще одного регистра (указателя на вершину стека) и сверх него еще одного, указывающего на «дно» стека (последнее не обязательно). То есть стек позволяет остаться с минимумом регистров, при этом кэширует данные, причем только те, которые гарантированно будут затребованы в дальнейшем!

Чтобы было понятнее, давайте посмотрим на стековый процессор, в нашем случае Форт-процессор.
Форт процессор «нарастил» стеки всего под двумя регистрами: ip и rb , остальные регистры остались регистрами:
1. top – обычный регистр (доступ на чтение, запись, и одновременно чтение + запись);
2. sub – вершина стека данных (доступ на чтение и запись, но кроме того, еще и утопление, всплытие данных обеспечивает);
3. f – флаговый процессор практически не меняет своего вида;
4. ip – вершина стека возвратов, как и sub позволяет читать/записывать/заталкивать/выталкивать данные.
Понятно, что данный подход не убирает всех проблем (а такое вообще возможно?).

Кстати, было бы занятно, если бы и top был стековым регистром, то есть и под ним был бы стек и под sub. Это не есть классическое решение, потому как Форт рассматривает регистры ra(top) и rb(sub) как принадлежащие к одному стеку. То есть идеологически top не выделяется из стека данных, а так как вся «обвязка» уже разработана, используется одна и та же модель поведения регистров.

Итоги
Так или иначе, стековая архитектура остается со своими преимуществами:
1. очень простая генерация кода (не надо раскладывать данные по регистрам);
2. быстрое и простое восстановление и сохранение промежуточных результатов;
3. очень простой и компактный формат команды, а значит меньше расход памяти кода;
4. реентерабельность кода;
5. очень простое и при том эффективное кэширование данных;
6. сравнительно простая реализация «в железе», т.к. стек имеет простую и регулярную структуру без запутанных связей (по сравнению с регистровым файлом);
7. очень высокая скорость реакции на прерывания.

В противовес появляются следующие проблемы:
1. для нормальной работы (а не эмуляции ее) необходимо отдельное адресное пространство под каждый из стеков;
2. сложно «вынуть» произвольное значение из стека, так как доступно только последнее значение;
3. проблемы организации многопоточных программ (стек надо либо сохранять, либо переключать);
4. размер стека, как и размер регистрового файла, лимитирован, но это не так явно ощущается, как в случае с регистровым файлом.

Литература:

1. Stack Computers: the new wave
2. Начальный курс программирования на языке Форт

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 10


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

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB