В теоретической информатике модель машины с произвольным доступом и хранимой программой (RASP) представляет собой абстрактную машину , используемую для целей разработки алгоритмов и теории сложности алгоритмов .
RASP — это модель машины с произвольным доступом (RAM), которая, в отличие от RAM, хранит свою программу в своих «регистрах» вместе с входными данными. Регистры не ограничены (имеют бесконечную емкость); конечность числа регистров зависит от модели. Таким образом, RASP относится к RAM так же, как универсальная машина Тьюринга относится к машине Тьюринга . RASP является примером архитектуры фон Неймана , тогда как RAM является примером архитектуры Гарварда .
Из всех абстрактных моделей RASP наиболее близка к общему понятию компьютера . Но в отличие от реальных компьютеров модель RASP обычно имеет очень простой набор инструкций, значительно сокращенный по сравнению с CISC и даже RISC процессорами до простейших арифметических, регистр-регистровых "перемещений" и инструкций "тест/прыжок". Некоторые модели имеют несколько дополнительных регистров, таких как аккумулятор .
Вместе с регистровой машиной , ОЗУ и указателем RASP образует четыре общие последовательные модели машин, названные так, чтобы отличать их от «параллельных» моделей (например, параллельных машин с произвольным доступом ) [ср. ван Эмде Боас (1990)].
Краткое описание RASP:
Читатель помнит, что UTM — это машина Тьюринга с «универсальной» конечно-статистической таблицей инструкций, которая может интерпретировать любую правильно сформированную «программу», записанную на ленте, как строку 5-кортежей Тьюринга, отсюда ее универсальность. В то время как классическая модель UTM ожидает найти 5-кортежи Тьюринга на своей ленте, туда можно поместить любой мыслимый программный набор, при условии, что машина Тьюринга ожидает их найти, — при условии, что ее конечная таблица состояний может интерпретировать их и преобразовывать в желаемое действие. Вместе с программой на ленте будут напечатаны входные данные/параметры/числа (обычно справа от программы), а в конечном итоге — выходные данные/числа (обычно справа от обоих, или смешанные с вводом, или заменяющие его). «Пользователь» должен расположить головку машины Тьюринга над первой инструкцией, а ввод должен быть помещен в указанное место и формат, соответствующие как программе на ленте, так и таблице инструкций конечно-статистической машины.
RASP имитирует эту конструкцию: он помещает «программу» и «данные» в отверстия (регистры). Но в отличие от UTM RASP продолжает «извлекать» свои инструкции последовательно, если только условный тест не отправляет их в другое место.
Момент путаницы: два набора инструкций : в отличие от UTM, модель RASP имеет два набора инструкций – таблицу инструкций конечного автомата («интерпретатор») и «программу» в дырках. Два набора не обязательно должны быть взяты из одного и того же набора.
Следующий пример программы переместит содержимое регистра (отверстия) №18 в регистр (отверстие) №19, стирая при этом содержимое №18.
5: 03 18 15 JZ 18 , 15 ; если [18] равно нулю, перейти к 15 для завершения программы 02 18 DEC 18 ; Уменьшение [18] 01 19 INC 19 ; Увеличение [19] 03 15 05 JZ 15 , 5 ; Если [15] равно нулю, перейти к 5 для повторения цикла (используйте Halt для имитации безусловного перехода) 15: 00 H ; Остановка 18: n ; Исходное значение для копирования 19: ; Место назначения для копирования Для краткости примера доступные в этой машине RASP программные инструкции будут представлять собой простой набор :
Для простоты примера мы оснастим конечный автомат RAM-as-RASP примитивными инструкциями, взятыми из того же набора, но дополненными двумя косвенными инструкциями копирования:
Поскольку конечный автомат машины RASP интерпретирует программу в регистрах, что именно будет делать конечный автомат? Столбец, содержащий восклицательный знак !, будет перечислять во временной последовательности действия конечного автомата, поскольку он «интерпретирует» — преобразует в действие — программу:
Традиция делит действия конечного автомата на две основные «фазы», называемые Fetch и Execute . Ниже мы увидим, что в этих двух основных фазах есть «подфазы». Не существует общепринятой конвенции; каждая модель потребует своего собственного точного описания.
Конечный автомат имеет доступ ко всем регистрам, как напрямую, так и косвенно. Поэтому он принимает #1 как "счетчик программ" PC. Роль счетчика программ будет заключаться в "сохранении места" в списке программы; конечный автомат имеет свой собственный регистр состояний для своего личного использования.
При запуске конечный автомат ожидает найти число в ПК — первую «программную инструкцию» в программе (т. е. под номером 5).
(Без использования косвенных COPY задача помещения указанной программной инструкции в #2 была бы немного трудной. Конечный автомат косвенно уменьшил бы указанный регистр, одновременно напрямую увеличивая (пустой) регистр #2. Во время фазы «анализа» он восстановит пожертвованное содержимое #5, пожертвовав счетчиком в #2.)
Целью приведенного выше отступления является демонстрация того, что жизнь становится намного проще, когда конечный автомат имеет доступ к двум видам косвенного копирования:
Следующий пример показывает, что происходит во время фазы "выборки" конечного автомата. Операции конечного автомата перечислены в столбце с надписью "Инструкция конечного автомата ↓". Обратите внимание, что в конце выборки регистр № 2 содержит числовое значение 3 "кода операции" ("opcode") первой инструкции JZ :
Теперь, когда номер программной инструкции (например, 3 = «JZ») находится в регистре № 2 — «Регистре программной инструкции» PIR — конечный автомат продолжает уменьшать номер до тех пор, пока IR не станет пустым:
Если бы IR был пустым до декремента, то инструкция программы была бы 0 = HALT, и машина перешла бы к своей процедуре "HALT". После первого декремента, если бы отверстие было пустым, инструкция была бы INC, и машина перешла бы к инструкции "inc_routine". После второго декремента пустой IR представлял бы DEC, и машина перешла бы к "dec_routine". После третьего декремента IR действительно пуст, и это вызывает переход к процедуре "JZ_routine". Если бы в IR все еще было неожиданное число, то машина обнаружила бы ошибку и могла бы HALT (например).
Теперь конечный автомат знает, какую программу-инструкцию выполнять; действительно, он перешел к последовательности инструкций "JZ_routine". Инструкция JZ имеет 2 операнда — (i) номер регистра для проверки и (ii) адрес, по которому следует перейти, если проверка прошла успешно (отверстие пусто).
(i) Извлечение операнда — какой регистр проверять на пустоту?: Аналогично фазе извлечения конечный автомат перемещает содержимое регистра, на который указывает ПК, т. е. отверстие № 6, в регистр программных инструкций PIR № 2. Затем он использует содержимое регистра № 2 для указания на регистр, который должен быть проверен на ноль, т. е. регистр № 18. Отверстие № 18 содержит число «n». Для выполнения теста теперь конечный автомат использует содержимое PIR для косвенного копирования содержимого регистра № 18 в запасной регистр № 3. Таким образом, есть две возможности (ia), регистр № 18 пуст, (ib) регистр № 18 не пуст.
(ia): Если регистр № 3 пуст, то конечный автомат переходит к (ii) выборке второго операнда — выборке адреса перехода.
(ib): Если регистр № 3 не пуст, то конечный автомат может пропустить (ii) выборку второго операнда. Он просто увеличивает PC вдвое, а затем безоговорочно возвращается к фазе выборки инструкций, где он выбирает инструкцию программы № 8 (DEC).
(ii) Извлечение операнда — адрес перехода . Если регистр № 3 пуст, конечный автомат продолжает использовать ПК для косвенного копирования содержимого регистра, на который он указывает (№ 8), в себя . Теперь ПК удерживает адрес перехода 15. Затем конечный автомат безоговорочно возвращается к фазе извлечения инструкции, где он извлекает программную инструкцию № 15 (HALT).
Ниже приводится описание интерпретации конечным автоматом RAM программных инструкций INC h, DEC h и, таким образом, демонстрация того, как RAM может «выдавать себя» за RASP:
Без косвенных инструкций конечного автомата INCi и DECi для выполнения программных инструкций INC и DEC конечный автомат должен использовать косвенное копирование, чтобы переместить содержимое указанного регистра в резервный регистр № 3, DEC или INC его, а затем использовать косвенное копирование, чтобы отправить его обратно в указанный регистр.
Альтернативные инструкции : Хотя в результате демонстрации получился примитивный RASP, состоящий всего из четырех инструкций, читатель может представить, как можно реализовать дополнительную инструкцию, например «ADD ⟨h⟩ » или «MULT ⟨h a ⟩ ,⟪h b >».
Когда RAM действует как RASP, достигается нечто новое: в отличие от RAM, RASP имеет возможность самомодифицировать свои программные инструкции (инструкции конечного автомата заморожены, не могут быть изменены машиной). Кук-Рекхоу (1971) (стр. 75) комментируют это в своем описании своей модели RASP, как и Хартманис (1971) (стр. 239 и далее)
Раннее описание этого понятия можно найти у Голдстайна-фон Неймана (1946):
Такая способность делает возможным следующее:
В влиятельной статье Стивен А. Кук и Роберт А. Рекхоу определяют свою версию RASP:
Их целью было сравнить время выполнения различных моделей: RAM, RASP и многоленточной машины Тьюринга для использования в теории анализа сложности .
Характерной чертой их модели RASP является отсутствие возможности для косвенных программных инструкций (см. их обсуждение на стр. 75). Этого они достигают, требуя от программы изменять себя: при необходимости инструкция может изменять «параметр» (их слово, т. е. «операнд») конкретной инструкции. Они разработали свою модель таким образом, что каждая «инструкция» использует два последовательных регистра, один для «кода операции» (их слова) и параметр «либо адрес, либо целочисленная константа».
Их регистры RASP не ограничены по емкости и не ограничены по количеству; также не ограничены их аккумулятор AC и счетчик команд IC. Набор команд следующий:
Часто и RAM и RASP машины представлены вместе в одной статье. Они были скопированы из Random-access machine ; за некоторыми исключениями, эти ссылки те же, что и в Register machine .