Главная Промышленная автоматика.

1.4. МОДЕЛЬ С ХРАНИМОЙ ПРОГРАММОЙ

Поскольку РАМ-программа не хранится в памяти РАМ, она не может изменять себя. Сейчас мы рассмотрим другую модель вычислительной машины, называемую машиной с произвольным доступом к памяти и хранимой программой (или, иначе, равнодоступной адресной машиной с хранимой программой - сокращенно РАСП), которая отличается от РАМ лишь тем, что ее программа находится в памяти и может изменять себя.

Набор команд для РАСП совпадает с соответствующим набором для РАМ во всем, кроме косвенной адресации, которая исключена, ибо она не нужна. Мы увидим, что РАСП может моделировать косвенную адресацию путем изменения команд в процессе выполнения программы.

Общая структура РАСП также подобна структуре РАМ, но только предполагается, что РАСП-программа находится в регистрах памяти. Каждая РАСП-команда занимает два последовательных регистра памяти. Первый регистр содержит код операции, второй - адрес. Если адрес имеет вид =i, то первый регистр будет содержать (в закодированном виде) указание на то, что операнд является литералом, а второй регистр будет содержать i. Для кодирования команд берутся целые числа. На рис. 1.12 представлено одно возможное кодирование. Например, команда LOAD=32 должна храниться в виде числа 2 в одном регистре и 32 в следующем регистре.

Так же как для РАМ, состояние РАСП можно представить с помощью

1) отображения памяти с, где c{i), t>0,- содержимое t-ro регистра,

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

Вначале счетчик команд устанавливается на некоторый выделенный регистр. Обычно исходное содержимое регистров памяти не состоит из одних нулей, так как в память уже введена программа. Однако мы требуем, чтобы вначале все регистры, кроме конечного числа, содержали О, и чтобы сумматор также содержал 0. После выполнения каждой команды счетчик команд всегда увеличивается на 2, кроме случаев JUMP г, JGTZ i (при положительном сумматоре) и JZERO i (при нулевом сумматоре), когда он устанавливается на i. Действие каждой команды в точности то же, что и у соответствующей команды РАМ.

Временную сложность РАСП-программы можно определить, по существу, тем же способом, что и для РАМ-программы. Можно использовать либо равномерный весовой критерий, либо логарифмический. В последнем случае, однако, надо приписать вес не только



Команда

Команда

LOAD i

LOAD = i

STORE i

READ

ADD i

WRITE

ADD = i

WRITE

SUB i

JUMP

SUB = /

JGTZ

MULT i

JZERO

MULT =i

HALT

Рис. 1.12. Коды для команд РАСП.

вычислению операнда, но и выбору самой команды. Вес выбора команды равен /(СК), где СК означает содержимое счетчика команд. Например, вес выполнения команды ADD=t, хранимой в регистрах / и /+1, равен l(j)-\-l(c(fS))-\-l(i) Вес команды ADD i, хранимой в регистрах / и /+1, равен /(/)+/{c(0))+/(i)+/(c(i)).

Интересно узнать, какова разница в сложности между РАМ-про-граммой и соответствующей РАСП-программой. Ответ не будет неожиданным. Независимо от того, взят ли равномерный вес или логарифмический, любое отображение типа вход - выход, выполнимое за время Т {п) одной моделью, может выполнить за время kT{n) другая модель, где k - некоторая постоянная. Аналогично объемы памяти, используемые этими моделями, при любой из двух рассматриваемых весовых мер отличаются друг от друга только на постоянный множитель.

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

Теорема 1.1. Как при равномерном, так и при логарифмическом весе команд для любой PAlA-программы с временной сложностью Т (и) существует такая постоянная k, что найдется эквивалентная РАСП-программа, временная сложность которой не превосходит кТ{п).

1) Можно было бы также добавить и вес считывания регистра /-j-l, но он не может сильно отличаться от / (/). Во всей этой главе нас не интересует величина мультипликативных постоянных, а только порядок роста функций. Поэтому 0)+(/+0 «приблизительно» равняется /(/)> т. е. с точностью до множителя, не превышающего 3.



Доказательство. Покажем, как моделировать РАМ-программу некоторой РАСП-программой. Регистр 1 в РАСП будет служить для временного запоминания содержимого сумматора РАМ. Отправляясь от Р, мы будем строить РАСП-программу Р,, которая будет занимать следующие г-1 регистров РАСП. Постоянная г определяется РАМ-программой Р. Содержимое регистра РАМ с номером t, tl, будет храниться в регистре РАСП с номером r+t, так что все адреса в РАСП-программе будут на г больше соответствующих адресов в РАМ-программе.

Каждая РАМ-команда в Р, не содержащая косвенной адресации, прямо кодируется в такую же РАСП-команду (с надлежащим увеличением адресов). Каждая РАМ-команда в Р, содержащая косвенную адресацию, переводится в последовательность из шести РАСП-команд, которые моделируют косвенную адресацию путем изменения команд.

Проиллюстрируем моделирование косвенной адресации на примере. Для моделирования РАМ-команды SUB *i, где i - положительное целое, построим последовательность РАСП-команд, которые

1) временно запоминают содержимое сумматора в регистре 1,

2) вызывают содержимое регистра r+t в сумматор (РАСП-ре-гистр с номером r+i соответствует РАМ-регистру с номером t),

3) прибавляют г к сумматору,

4) запоминают число, вычисленное на шаге 3 в адресном поле команды SUB,

5) восстанавливают сумматор из временного регистра 1,

6) используют команду SUB, созданную на шаге 4, для выполнения вычитания.

Например, применяя кодирование команд РАСП, приведенное на рис. 1.12, и предполагая, что последовательность РАСП-команд начинается в регистре 100, можно смоделировать SUB »t последовательностью, показанной на рис. 1.13. Сдвиг г можно будет определить, когда станет известно количество РАСП-команд в программе

Мы видим, что для моделирования каждой РАМ-команды требуется самое большее шесть РАСП-команд, так что при равномерном весовом критерии временная сложность получаемой РАСП-программы не превосходит 6Г (п). (Заметим, что эта мера не зависит от того, каким способом определен размер входа.)

При- логарифмическом весовом критерии каждая команда / из РАМ-программы Р моделируется последовательностью S, состоящей в Ps либо из одной, либо из шести РАСП-команд. Можно показать, что существует постоянная k, зависящая от Р, такая, что суммарный вес команд в S не более чем в й раз превосходит вес команды /.





0 1 2 3 4 [5] 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0022