Лекція 4

§ 4.1. Модель з програмою, що зберігається.

Оскільки РАМ-програма не зберігається в пам’яті РАМ, вона не може себе змінювати. Зараз ми розглянемо іншу модель обчислювальної машини, яка називається машиною з довільним доступом до пам’яті й програмою, що зберігається (або, інакше, рівно доступною адресною машиною з програмою, що зберігається – скорочено РАСП), яка відрізняється від РАМ лише тим, що її програма знаходиться в пам’яті й може змінювати себе. Набір команд для РАСП збігається з відповідним набором для РАМ у всьому, за виключенням непрямої адресації, котра вилучена, оскільки вона не потрібна. РАСП може моделювати непряму адресацію шляхом зміни команд в процесі виконання програми.

Загальна структура РАСП також подібна РАМ, лише передбачається, що РАСП-програма знаходиться в регістрах пам’яті. Кожна РАСП-команда займає два послідовних регістри пам’яті. Перший регістр містить код операції, другий – адрес. Якщо адрес має вигляд =і, то перший регістр міститиме (в закодованому вигляді) вказівку на те, що операнд є літералом, а другий регістр міститиме і. Для кодування команд беруться цілі числа. В таблиці 4.1 подано одне можливе кодування, Наприклад, команда LOAD=32 повинна у вигляді числа 2 в одному регістрі й 32 в наступному регістрі.

Так як і для РАМ, стан РАСП можна подати за допомогою

1. відображення пам’яті с, де c(i), , – вміст і-го регістру,

2. лічильника команд, який указує перший з двох послідовних регістрів пам’яті, із яких потрібно взяти команду, що побігає (те кущую команду).

Спочатку лічильник команд установлюється на деякий виділений регістр. Зазвичай початковий вміст регістрів пам’яті не складається з одних нулів, оскільки в пам’ять уже введена програма. Проте вимагається, щоб спочатку

Таблиця 4.1 Коди для команд РАСП

Команда Код	Команда Код
.LOAD і 1 LOAD = і 2 .STORE і 3 ADD і 4 ADD = і 5 SUB і 6 SUB = і 7 MULT і 6 MULT = і 9	DIV і 10 DIV =і 11 READ і 12 WRITE і 13 WRITE = і 14 JUMP і 15 JGTZ і 16 JZERO і 17 HALT 18

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

Часову складність РАСП-програм можна визначити, по суті, таким же способом як і для РАМ-програм. Можна використати або рівномірний ваговий критерій, або логарифмічний. В останньому випадку, проте, треба надавати вагу не лише обчисленню операнда, але й вибору самої команди. Вага вибору команди рівна l(СК), де СК означає вміст лічильника команд. Наприклад, вага виконання команди ADD = і, котра зберігається в регістрах j й j + 1, рівна l (j) + l (c(0)) + l (i). Вага команди ADD = і, котра зберігається в регістрах j й j + 1, рівна l (j) + l (c(0)) + l (i) + l (c(i)).

Цікаво знати, Яка різниця в складності між РАМ-програмою й відповідною РАСП-програмою. Незалежно від того, взята рівномірна вага чи логарифмічна, будь-яке відображення типу вхід – вихід, яке виконується за час T(n) однією моделлю, може виконуватися за час kT(n) іншою моделлю, де k– деяка постійна. Аналогічно обсяги пам’яті, які використовуються цими моделями, при будь-якій із двох вагових мір, які розглядаються, відрізняються одна від іншої лише на постійний множник.

Сформулюємо ці співвідношення у вигляді двох теорем. Обидві теорема доводяться побудовою алгоритмів, які моделюють одну машину іншою.

Теорема 4.1. Як при рівномірній, так і при логарифмічній вазі команд для будь-якої РАМ-програми з часовою складністю T(n) існує така постійна k, що знайдеться еквівалентна РАСП-програма, часова складність якої не перевищує kT(n).

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

Кожна РАМ-команда в Р, яка не містить непрямої адресації, прямо кодується в таку ж РАСП-команду (з відповідним збільшенням адресів). Кожна РАМ-команда в Р, котра містить непряму адресацію, переводиться в послідовність шести РАСП-команд, які моделюють непряму адресацію шляхом зміни команд.

Розглянемо моделювання непрямої адресації на прикладі. Для моделювання РАМ-команди SUB і, де і – додатне ціле, побудуємо послідовність РАСП-команд, які

1. тимчасово запам’ятовують вміст суматора в регістрі 1,

2. визивають вміст регістра r+і в суматор (РАСП-регістр з номером відповідає РАМ-регістр з номером і),

3. додаємо r до суматора,

4. запам’ятовують число, обчислене на кроці 3 в адресному полі команди SUB,

5. відновляють суматор із тимчасового регістру 1,

6. використовуючи команду SUB, створену на кроці 4,для виконання віднімання.

Наприклад, застосовуючи кодування команд РАСП, наведене в таблиці 4.1, і передбачаючи, що послідовність РАСП-команд починається в регістрі 100, можна змоделювати SUB і послідовністю, котра наведена в таблиці 4.2 вважаючи, що послідовність РАСП команд починається в регістрі 100, можна змоделювати SUB і послідовністю, наведеною в таблиці 4.2.

Таблиці 4.2 Моделювання SUB і на РАСП

Регістр	Вміст	Значення
100 101		STORE 1
102 103		LOAD
104 105		ADD
106 107		STORE 111
108 109		LOAD 1
110 111		SUB b, де b – вміст і-го регістру РАМ

Зсув r можна буде визначити, коли стане відомою кількість РАСП-команд в програмі .

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

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

Наприклад, команда SUB і для РАМ має вагу

М = l(c(0))+l(i) +l(c(i))+l(c(c(i))).

Послідовність S, яка моделює цю команду, подана в таблиці 4.3.

Таблиця 4.3.

Ваги команд РАСП.

Регістр РАСП	Команда	Вага
J	STORE 1	l(i) + l(1) + l(c(0))
j + 2	LOAD r + i	l(j + 2) + l(r + i) + l(c(i))
j + 4	ADD = r	l(j + 4) + l(c(i)) + l(r)
j + 6	STORE j + 11	l(j + 6) + l(j + 11) + l(c(i) + r)
j + 8	LOAD 1	l(j + 8) + l(1) + l(c(0))
j + 10	SUB –	l(j + 10) + l(c(i) + r) + l(c(0)) + l(c(c(i)))

Тут c(0), c(i), c(c(i)) відносяться до вмісту регістрів РАМ. Оскільки займає в РАСП регістри від 2 до r, то . Крім того, , так що вага S не перевищує

.

Тому можна зробити висновок, що константа така, чо коли Р має часову складність , то часова складність для не перевищує ,

Теорема 4.2. Як при рівномірній, так і при логарифмічній вазі команд для будь-якої РАСП-програми з часовою складністю T(n) існує така постійна k, що знайдеться еквівалентна РАМ-програма, часова складність якої не перевищує kT(n).

Доведення. РПМ-програма, котру ми побудуємо для моделювання даної РАСП використовуватиме непряму адресацію для декодування й моделювання РАСП-команд., які зберігаються в пам’яті РАМ. Деякі регістри РАМ матимуть спеціальне призначення:

регістр 1 – для непрямої адресації,

регістр 2 – для лічильника команд РАСП,

регістр 3 – для зберігання вмісту суматора РАСП.

РАСП-регістр з номером і буде зберігатися в РАМ-регістрі з номером при .

Шукана РАМ починає роботу з РАСП-програми скінченої довжини, розташованої в її пам’яті з регістра 4 й далі. Регістр 2 (лічильник команд) містить число 4; регістри 1 і 3 – число 0. РАМ-програма складається з циклу моделювання, котрий починається із зчитування РАСП-команд (за допомогою РАМ-команди LOAD 2), декодування її й розгалуження на один із 18 наборів команд, кожен із яких назначений для обробки одного типу РАСП-команд. На неправильному коді операції РАМ, як і РАСП, спинеться.

Операції декодування й розгалуження будується природнім чином.

В значенні прикладу наведемо ті команди РАМ, котрі моделюють РАСП-команду з кодом 6, тобто SUB i. Ця програма, зображена в таблиці 4.4, визивається, коли с(с(2))=6, тобто коли лічильник команд указує на регістр, який містить число 6 – код команди SUB.

Таблиця 4.4. Моделювання SUB і на РАМ.

	Збільшення лічильника команд на 1, так що він починає вказувати на регістр, який містить операнд і команди SUB і .
	Визов і в суматор, додавання числа 3 й запам’ятовування результату в регістрі 1.
	Добування вмісту суматора РАСП з регістру 3. віднімання вмісту регістру і +3 й занесення результату знову в регістр 3.
	Збільшення лічильника команд знову на 1, так що тепер він указує на наступну команду РАСП.
	Повернення до початку циклу моделювання (який тут позначається через “а“).

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

Із теорем 4.1 й 4.2 випливає, що по відношенню до часової складності (а також і ємнісної) моделі РАМ і РАСП еквівалентні з точністю до постійного множника, тобто порядки величин їх складності однакові для одного й того ж алгоритму.