Традиция

Random Access Machine

ОпределениеПравить

Random Access Machine («машины со произвольным доступом») — теоретическая модель вычислителя (см. например машина Тьюринга), напоминающая современный компьютер, программируемый непосредственно в терминах инструкций процессора (или на языке Assembler) (в теории сложности вычислений под машинами традиционно понимают single-purpose machines), т. е. машины, созданные для решения какой-либо одной фиксированной задачи, а в терминах программиста это скорее программы).

RAM-машина состоит из (См. Рисунок):

  • Конечная входная read-only лента, куда записываются входные данные.
  • Полубесконечная выходная write-only лента, куда записываются результат работы машины.
  • Бесконечное число регистров r 0 , r 1 , r 2 , … , r_0,r_1,r_2,\ldots, , каждый из которых может хранить целое число, причем регистр r 0 r_0 является выделенным, и называется «сумматором» — этот регистр используется при арифметических операциях как накопитель, т. е. как второй операнд и место хранения результата.
  • Программа, состоящая из конечного числа инструкций, каждая из которых содержит адрес и команду с операндом. Таблица со списком команд приведена ниже.

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

  • Регистр-счетчик «PC», указывающий на текущую команду.

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

ИллюстрацияПравить

<latex> %Created by jPicEdt 1.x %Standard LaTeX format (emulated lines) %Wed Aug 24 21:22:49 MSD 2005 \unitlength 1.3mm \begin{picture}(120.31,90.00)(0,0)

\linethickness{0.15mm} %Rectangle(10.00,10.00)(90.00,20.00) \put(10.00,10.00){\line(1,0){80.00}} \put(10.00,10.00){\line(0,1){10.00}} \put(90.00,10.00){\line(0,1){10.00}} \put(10.00,20.00){\line(1,0){80.00}} %End Rectangle

\linethickness{0.15mm} %Polygon 0 0(20.00,20.00)(20.00,10.00) \put(20.00,10.00){\line(0,1){10.00}} %End Polygon

\linethickness{0.15mm} %Polygon 0 0(30.00,20.00)(30.00,10.00) \put(30.00,10.00){\line(0,1){10.00}} %End Polygon

\linethickness{0.15mm} %Polygon 0 0(40.00,20.00)(40.00,10.00) \put(40.00,10.00){\line(0,1){10.00}} %End Polygon

\linethickness{0.15mm} %Polygon 0 0(50.00,20.00)(50.00,10.00) \put(50.00,10.00){\line(0,1){10.00}} %End Polygon

\linethickness{0.15mm} %Polygon 0 0(60.00,20.00)(60.00,10.00) \put(60.00,10.00){\line(0,1){10.00}} %End Polygon

\linethickness{0.15mm} %Polygon 0 0(70.00,20.00)(70.00,10.00) \put(70.00,10.00){\line(0,1){10.00}} %End Polygon

\linethickness{0.15mm} %Polygon 0 0(80.00,20.00)(80.00,10.00) \put(80.00,10.00){\line(0,1){10.00}} %End Polygon

\linethickness{0.15mm} %Polygon 0 0(90.00,20.00)(95.00,20.00) \put(90.00,20.00){\line(1,0){5.00}} %End Polygon

\linethickness{0.15mm} %Polygon 0 0(90.00,10.00)(95.00,10.00) \put(90.00,10.00){\line(1,0){5.00}} %End Polygon

\linethickness{0.15mm} %Polygon 0 0(95.00,20.00)(95.00,20.00)


%End Polygon

\linethickness{0.15mm} %Bezier 0 0(95.00,20.00)(98.75,13.28)(98.75,13.13) \qbezier(95.00,20.00)(98.75,13.28)(98.75,13.13) %End Bezier

\linethickness{0.15mm} %Bezier 0 0(98.75,13.13)(98.75,12.97)(95.00,10.00) \qbezier(98.75,13.13)(98.75,12.97)(95.00,10.00) %End Bezier

\linethickness{0.15mm} %Rectangle(50.00,30.00)(90.00,60.00) \put(50.00,30.00){\line(1,0){40.00}} \put(50.00,30.00){\line(0,1){30.00}} \put(90.00,30.00){\line(0,1){30.00}} \put(50.00,60.00){\line(1,0){40.00}} %End Rectangle

\linethickness{0.15mm} %Rectangle(10.00,50.00)(40.00,60.00) \put(10.00,50.00){\line(1,0){30.00}} \put(10.00,50.00){\line(0,1){10.00}} \put(40.00,50.00){\line(0,1){10.00}} \put(10.00,60.00){\line(1,0){30.00}} %End Rectangle

\linethickness{0.15mm} %Rectangle(20.00,70.00)(50.00,80.00) \put(20.00,70.00){\line(1,0){30.00}} \put(20.00,70.00){\line(0,1){10.00}} \put(50.00,70.00){\line(0,1){10.00}} \put(20.00,80.00){\line(1,0){30.00}} %End Rectangle

\linethickness{0.15mm} %Polygon 0 0(40.00,80.00)(40.00,70.00) \put(40.00,70.00){\line(0,1){10.00}} %End Polygon

\linethickness{0.15mm} %Polygon 0 0(50.00,80.00)(55.00,80.00) \put(50.00,80.00){\line(1,0){5.00}} %End Polygon

\linethickness{0.15mm} %Polygon 0 0(50.00,70.00)(55.00,70.00) \put(50.00,70.00){\line(1,0){5.00}} %End Polygon

\linethickness{0.15mm} %Polygon 0 0(105.00,90.00)(105.00,90.00)


%End Polygon

\linethickness{0.15mm} %Bezier 0 0(55.00,80.00)(58.75,73.28)(58.75,73.13) \qbezier(55.00,80.00)(58.75,73.28)(58.75,73.13) %End Bezier

\linethickness{0.15mm} %Bezier 0 0(58.75,73.13)(58.75,72.97)(55.00,70.00) \qbezier(58.75,73.13)(58.75,72.97)(55.00,70.00) %End Bezier

\linethickness{0.15mm} %Rectangle(70.00,70.00)(80.00,80.00) \put(70.00,70.00){\line(1,0){10.00}} \put(70.00,70.00){\line(0,1){10.00}} \put(80.00,70.00){\line(0,1){10.00}} \put(70.00,80.00){\line(1,0){10.00}} %End Rectangle

\linethickness{0.15mm} %Bezier 0 0(65.00,80.00)(65.47,73.28)(66.88,73.13) \qbezier(65.00,80.00)(65.47,73.28)(66.88,73.13) %End Bezier

\linethickness{0.15mm} %Bezier 0 0(66.88,73.13)(68.28,72.97)(65.00,70.00) \qbezier(66.88,73.13)(68.28,72.97)(65.00,70.00) %End Bezier

\linethickness{0.15mm} %Polygon 0 0(65.00,70.00)(70.00,70.00) \put(65.00,70.00){\line(1,0){5.00}} %End Polygon

\linethickness{0.15mm} %Polygon 0 0(70.00,80.00)(65.00,80.00) \put(65.00,80.00){\line(1,0){5.00}} %End Polygon

\put(35.00,75.00){\makebox(0,0)[cc]{$x_2$}}

\put(35.00,65.00){\makebox(0,0)[cc]{}}

\put(45.00,75.00){\makebox(0,0)[cc]{$x_3$}}

\put(75.00,75.00){\makebox(0,0)[cc]{$x_n$}}

\put(25.00,55.00){\makebox(0,0)[cc]{Program Counter}}

\put(15.00,55.00){\makebox(0,0)[cc]{}}

\put(15.00,55.00){\makebox(0,0)[cc]{}}

\put(0.00,60.00){\makebox(0,0)[cc]{}}

\linethickness{0.15mm} %Polygon 0 0(30.00,80.00)(30.00,70.00) \put(30.00,70.00){\line(0,1){10.00}} %End Polygon

\put(25.00,75.00){\makebox(0,0)[cc]{$x_1$}}

\put(70.00,55.00){\makebox(0,0)[cc]Шаблон:\Large RAM--Program}

\put(15.00,15.00){\makebox(0,0)[cc]{$y_1$}}

\put(25.00,15.00){\makebox(0,0)[cc]{$y_2$}}

\put(35.00,15.00){\makebox(0,0)[cc]{$y_3$}}

\put(45.00,15.00){\makebox(0,0)[cc]{$y_4$}}

\put(55.00,15.00){\makebox(0,0)[cc]{$y_5$}}

\put(65.00,15.00){\makebox(0,0)[cc]{$y_6$}}

\put(75.00,15.00){\makebox(0,0)[cc]{$y_7$}}

\put(85.00,15.00){\makebox(0,0)[cc]{$y_8$}}

\put(60.00,80.00){\makebox(0,0)[bc]{входная read-only лента}}

\put(25.00,85.00){\makebox(0,0)[cc]{}}

\put(55.00,10.00){\makebox(0,0)[tc]{выходная write-only лента}}

\linethickness{0.15mm} %Bezier 0 0(40.00,55.00)(43.44,54.38)(45.00,50.00) \qbezier(40.00,55.00)(43.44,54.38)(45.00,50.00) %End Bezier

\linethickness{0.15mm} %Bezier 0 1(45.00,50.00)(46.56,45.63)(50.00,45.00) \qbezier(45.00,50.00)(46.56,45.63)(50.00,45.00) \put(50.00,45.00){\vector(4,-1){0.12}} %End Bezier

\linethickness{0.15mm} %Bezier 0 0(60.00,60.00)(58.44,66.25)(47.50,65.00) \qbezier(60.00,60.00)(58.44,66.25)(47.50,65.00) %End Bezier

\linethickness{0.15mm} %Bezier 0 1(47.50,65.00)(36.56,63.75)(35.00,70.00) \qbezier(47.50,65.00)(36.56,63.75)(35.00,70.00) \put(35.00,70.00){\vector(-1,4){0.12}} %End Bezier

\linethickness{0.15mm} %Bezier 0 0(60.00,30.00)(60.47,24.69)(39.38,28.75) \qbezier(60.00,30.00)(60.47,24.69)(39.38,28.75) %End Bezier

\linethickness{0.15mm} %Bezier 0 1(39.38,28.75)(18.28,32.81)(15.00,20.00) \qbezier(39.38,28.75)(18.28,32.81)(15.00,20.00) \put(15.00,20.00){\vector(-1,-4){0.12}} %End Bezier

\put(110.00,45.00){\makebox(0,0)[cc]{}}

\put(105.00,85.00){\makebox(0,0)[cc]{}}

\linethickness{0.30mm} %Rectangle(110.00,70.00)(120.00,80.00) \put(110.00,70.00){\line(1,0){10.00}} \put(110.00,70.00){\line(0,1){10.00}} \put(120.00,70.00){\line(0,1){10.00}} \put(110.00,80.00){\line(1,0){10.00}} %End Rectangle

\put(115.00,75.00){\makebox(0,0)[cc]{$r_0$}}

\linethickness{0.15mm} %Rectangle(110.00,60.00)(120.00,70.00) \put(110.00,60.00){\line(1,0){10.00}} \put(110.00,60.00){\line(0,1){10.00}} \put(120.00,60.00){\line(0,1){10.00}} \put(110.00,70.00){\line(1,0){10.00}} %End Rectangle

\put(115.00,65.00){\makebox(0,0)[cc]{$r_1$}}

\linethickness{0.15mm} %Rectangle(110.00,50.00)(120.00,60.00) \put(110.00,50.00){\line(1,0){10.00}} \put(110.00,50.00){\line(0,1){10.00}} \put(120.00,50.00){\line(0,1){10.00}} \put(110.00,60.00){\line(1,0){10.00}} %End Rectangle

\put(115.00,55.00){\makebox(0,0)[cc]{$r_2$}}

\linethickness{0.15mm} %Rectangle(110.00,40.00)(120.00,50.00) \put(110.00,40.00){\line(1,0){10.00}} \put(110.00,40.00){\line(0,1){10.00}} \put(120.00,40.00){\line(0,1){10.00}} \put(110.00,50.00){\line(1,0){10.00}} %End Rectangle

\put(115.00,45.00){\makebox(0,0)[cc]{$r_3$}}

\linethickness{0.15mm} %Rectangle(110.00,30.00)(120.00,40.00) \put(110.00,30.00){\line(1,0){10.00}} \put(110.00,30.00){\line(0,1){10.00}} \put(120.00,30.00){\line(0,1){10.00}} \put(110.00,40.00){\line(1,0){10.00}} %End Rectangle

\put(115.00,35.00){\makebox(0,0)[cc]{$r_4$}}

\linethickness{0.15mm} %Rectangle(110.00,20.00)(120.00,30.00) \put(110.00,20.00){\line(1,0){10.00}} \put(110.00,20.00){\line(0,1){10.00}} \put(120.00,20.00){\line(0,1){10.00}} \put(110.00,30.00){\line(1,0){10.00}} %End Rectangle

\put(115.00,25.00){\makebox(0,0)[cc]{$r_5$}}

\linethickness{0.15mm} %Polygon 0 0(110.00,20.00)(110.00,15.00) \put(110.00,15.00){\line(0,1){5.00}} %End Polygon

\linethickness{0.15mm} %Polygon 0 0(120.00,20.00)(120.00,15.00) \put(120.00,15.00){\line(0,1){5.00}} %End Polygon

\linethickness{0.15mm} %Bezier 0 0(110.00,15.00)(117.19,11.72)(118.75,13.13) \qbezier(110.00,15.00)(117.19,11.72)(118.75,13.13) %End Bezier

\linethickness{0.15mm} %Bezier 0 0(118.75,13.13)(120.31,14.53)(120.00,15.00) \qbezier(118.75,13.13)(120.31,14.53)(120.00,15.00) %End Bezier

\linethickness{0.15mm} %Bezier 0 0(90.00,45.00)(93.13,47.34)(96.25,61.88) \qbezier(90.00,45.00)(93.13,47.34)(96.25,61.88) %End Bezier

\linethickness{0.15mm} %Bezier 0 1(96.25,61.88)(99.38,76.41)(110.00,75.00) \qbezier(96.25,61.88)(99.38,76.41)(110.00,75.00) \put(110.00,75.00){\vector(4,-1){0.12}} %End Bezier

\put(51.25,51.25){\makebox(0,0)[cl]Шаблон:\tiny 0: LOAD $r1$}

\put(50.00,50.00){\makebox(0,0)[cc]{}}

\put(51.25,48.75){\makebox(0,0)[cl]Шаблон:\tiny 1: ADD 3}

\put(51.25,46.25){\makebox(0,0)[cl]Шаблон:\tiny 2: STORE $r7$}

\put(51.25,43.75){\makebox(0,0)[cl]Шаблон:\tiny 3: LOAD 77}

\put(51.25,41.25){\makebox(0,0)[cl]Шаблон:\tiny 4: STORE $*r7$}

\put(51.25,38.75){\makebox(0,0)[cl]Шаблон:\tiny 5: JUMP 100}

\put(60.00,36.25){\makebox(0,0)[cc]{$\ldots$}}

\linethickness{0.30mm} %Rectangle(10.00,10.00)(20.00,20.00) \put(10.00,10.00){\line(1,0){10.00}} \put(10.00,10.00){\line(0,1){10.00}} \put(20.00,10.00){\line(0,1){10.00}} \put(10.00,20.00){\line(1,0){10.00}} %End Rectangle

\linethickness{0.30mm} %Rectangle(30.00,70.00)(40.00,80.00) \put(30.00,70.00){\line(1,0){10.00}} \put(30.00,70.00){\line(0,1){10.00}} \put(40.00,70.00){\line(0,1){10.00}} \put(30.00,80.00){\line(1,0){10.00}} %End Rectangle

\end{picture}

</latex>

Список командПравить

<latex> \begin{tabular}{|l|l|l|} \hline 

 \textbf{LOAD} OP & $r_0 \leftarrow OP$ & Загрузить операнд в сумматор \\

\hline 

 \textbf{STORE} OP & $r_{OP} \leftarrow r_0$ & Сохранить сумматор в регистре\\

\hline 

 \textbf{ADD} OP & $r_0 \leftarrow r_0 + OP$ & Прибавить операнд к сумматору\\

\hline 

 \textbf{SUB} OP & $r_0 \leftarrow r_0 - OP$ & Вычесть операнд из сумматора\\

\hline 

 \textbf{READ} OP & $r_{OP} \leftarrow input $  & Загрузить ячейку из входной ленты в $r_{OP}$ и перейти к следующей.\\

\hline 

 \textbf{WRITE} OP & $OP \rightarrow output $  & Записать $OP$ в текущую ячейку выходной ленты и перейти к следующей.\\

\hline 

 \textbf{JUMP} OP& $PC \leftarrow OP $  & Установить счетчик команд в $OP$.\\

\hline 

 \textbf{JGTZ} OP& $PC \leftarrow OP :r_0>0  $  & Установить счетчик команд в $OP$, если $r_0>0$\\

\hline 

 \textbf{JZERO} OP& $PC \leftarrow OP  :r_0=0 $  & Установить счетчик команд в $OP$, если $r_0=0$\\

\hline 

 \textbf{HALT}& & Остановить работу.\\

\hline \end{tabular} </latex>
По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.

Источник — https://traditio.wiki/w/index.php?title=Random_Access_Machine&oldid=840521