Э. Таненбаум - Архитектура компьютера (1127755), страница 114
Текст из файла (страница 114)
В следующих подразделах мы предложим программы на ассемблере Репйпш 4 и (ЛтгаЯРАКС П1. Однако чтобы избежать проблем с вводом-выводом )ача, для машин Репи(пш 4 и П)сгаЯРАЕС П1 мы будем транслировать версию программы не на 1ача, а на С. Единственное различие — это замена )ага-оператора рг1 пс1 п стандартным оператором языка С; рс1пгц "Пирииестить Ииси с Хп' иа Хп"сп", 1, ~) Синтаксис строки в операторе ргппС~ не важен (строка печатается буквально за исключением символов Ы, означающих, что следующее целое число будет представлено в десятичной системе счисления). Здесь важно только то, что процедура вызывается с тремя параметрами: форматирующей строкой и двумя целыми числами. Мы использовали язык С для Репт1пш 4 и (ЛсгаЯРАВ.С П1, поскольку библиотека ввода-вывода 1ача для этих машин недоступна, в отличие от библиотеки С ввода-вывода.
Разница минимальна — всего один оператор вывода строки на экран. Ханойская башня 457 Решение задачи «Ханойская башня» на ассемблере Репбит 4 В листинге 5.7 приведен возможный вариант программы на языке С для компьютера Репс[пю 4 после трансляции. Регистр ЕВР используется в качестве указателя фрейма Первые два слова требуются для сборки, поэтому первый параметр и [или И, поскольку регистр символов в макроассемблере не важен) находится в ячейке ЕВР + 8, а за ним следуют параметры 1 и З в ячейках ЕВР + 12 и ЕВР + 1б соответственно. Локальная переменная (( находится в ЕВР + 20. «Ханойская башня» для Реп!впп 4 иоипилируется для Рент!цщ Листинг 5Л. Решение задачи .586 .МОВЕ[ РСАТ РОВ[!С тохегз ЕХТЕИИ рити(т:ИЕАИ .СВОЕ тохегз: Р05Н ЕВР МОЧ ЕВР. Е5Р зкспорт ' тохегз' иипорт рг!пт[ СМР[ЕВР+81.1 ]ИЕ [1 МОЧ ЕАХ, [ЕВР+16] Р05Н ЕАХ МОЧ ЕАХ, [ЕВР+12] Р05Н ЕАХ Р05Н ОРР5ЕТ Р[АТ.Тоипат СА[[ рг1птт АОО Е5Р, 12 ]МР Ооие МОЧ ЕАХ,6 508 ЕАХ.
[ЕВР+12] 508 ЕАХ. [ЕВРь16] МОЧ [ЕВРь20]. ЕЯХ Р05Н ЕЯХ МОЧ ЕЯХ, [ЕВРн12] Р05Н ЕАХ МОЧ ЕЯХ. [ЕВРь8] ОЕС ЕАХ Р05Н ЕАХ СЯ[[ тохегз АОО Е5Р. 12 МОЧ ЕАХ. [ЕВРь16] Р05Н ЕАХ МОЧ ЕАХ, [ЕВР+12] Р05Н ЕАХ Р05Н 1 СА[[ тохегз АОО Е5Р, 12 МОЧ ЕАХ. [ЕВР+12] Р05Н ЕЯХ МОЧ ЕАХ, [ЕВР+20] Р05Н ЕАХ МОЧ ЕАХ, [ЕВР+8] ОЕС ЕЯХ Р05Н ЕАХ СА[[ тохегз АОО Е5Р, 12 : сохраняет ЕВР (указатель фрейна) : устанавливает новый : указатель фрейна над Е5Р : 1Т(и==1) ; переход, если п не равно 1 ; рг1птт(".,", т, ]); ; сохранение паранетров т, .) и форната .
строка поиещается в стек : в обратнои порядке (требование языка С) . ОГРВЕТ Р[АТ вЂ” зто адрес фориата ; вызов процедуры рюптт : удаление паранетров из стека ; завершение ; начало вычисления И=6-1-) ; ЕАХ=6-1 ; ЕАХ=6-т-) : К=ЕАХ : начало процедуры тохегз(и-1, 1, Х) ; ЕАХ=1 , поиещает в стек ! : ЕЯХ п ЕАХ и-1 ; поиещает в стек п-1 , вызов процедуры тохегз(п-1, 1, 6-1-]) . удаляет параиетры из стека . начало процедуры Сохегз (1, 1. 1) : помещает в стек ] ; ЕАХ=1 , понещает в стек ! ; понещает в стек ! : вызывает процедуру тохегз( 1. !. З) : удаляет параметры из стека : начало процедуры тохегз(п-1. 6-1-], 1) : помещает в стек 1 ; ЕАХчй ; понещает в стек К ЕАХ - п ; ЕАХ=п-1 : поиещает в стек и-1 .
вызов процедуры тохегз(п-!, 6-1-], 1) ; корректировка указателя стека 488 Глава б. Уровень архитектуры набора команд Оспе ЕЕЯНЕ ВЕТ 0 подготовка к выходу возврат к вызывающей программе . ОР'ГД тогщас ЕМО 00 "Перенестмть диск с ДО на ДО'тп" . форматнрующая строка Решение задачи «Ханойская башняв на ассемблере ЦИгавРАВС !!! А теперь рассмотрим ту же программу на ассемблере 11!сгаБРАКС П1 (листинг 5.8). Поскольку программа для 1)!сгаЗРАКС П1 совершенно нечитабельна даже после длительной практики, мы решили определить несколько символов, чтобы прояснить дело. Чтобы такая программа работала, ее перед ассемблированием нужно пропустить через программу под названием срр (препроцессор С).
Здесь мы используем строчные буквы, поскольку ассемблер (Т!ЕгаЯРАКС П1 этого требует (это на тот случай, если читатели захотят набрать эту программу и запустить). задачи кХанойская башня» для Е!йгаЯРАЕТС Н! т* И вЂ” это входной параметр О *! /* 1 — это входной параметр 1 *! /* д — зто входной параметр 2 *т т'* К вЂ” это локальная переменная О *г' I* РагаюΠ— зто выходной параметр О *! т* Рагаю1 — это выходной параметр 1 *! т'* Рагаю2 — это выходной параметр 2 *! г* в срр комментарнн записываются как в С*! Листинг 6.8. Решение №Оеттпе М 110 №Оеттпе! 111 №Оетт'пе д Дт2 №Оеттпе К Д!О №Оеттпе Рагаюр ДоО №Оеттпе Рагаю1 До! №Оет!пе Рагащ2 До2 Не!тле 5сгавсм д!! Процедура начинается с создания нового фрейма в конце старого.
Для этого значение регистра ЕБР копируется в указатель фрейма ЕВР. Затем п сравнивается с 1, и если и > 1, совершается переход к оператору е! зе. Тогда код Е!тел помещает в стек три значения: адрес форматирующей строки, т и О, а затем вызывает сам себя. Параметры помещаются в стек в обратном порядке, поскольку это требование языка С. Необходимо поместить указатель на форматирующую строку в вершину стека.
Процедура ргтпЕГ имеет переменное число параметров, и если параметры будут помещаться в стек в прямом порядке, то процедура не сможет узнать, в каком месте стека находится форматирующая строка. После вызова процедуры к регистру ЕЯР прибавляется 12, чтобы удалить параметры из стека. На самом деле они не удаляются из памяти, но изменение регистра ЕЯР делает их недоступными через обычные операции со стеком.
Выполнение части е! зе начинается с метки Е1. Здесь сначала вычисляется выражение 6 — т — .1, а полученное значение сохраняется в переменной К. Сохранение значения в переменной !с избавляет от необходимости вычислять это выражение во второй раз. Затем процедура вызывает сама себя три раза, каждый раз с новыми параметрами. После каждого вызова стек освобождается.
Рекурсивные процедуры иногда приводят людей в замешательство. Но на самом деле они совсем не сложные. Просто параметры помещаются в стек, после чего процедура вызывает сама себя. Ханойская башня 459 .Ргос 04 .91ЬЬа1 Соиегз тоиегз ване Жзр. — Н2. Жзр сюр И, 1 ! ! И и== 1) Ьпе Е1зе ! ттб (п != 1) Опто Е1зе зеЕЬт ЖШ Егогюат), РагаюО ! ргтпттыпереиестнть диск с ЖО на ЖО)п", ! т, 1) ог РагаюО. Ж!о(тогюат). РагашО ! РагашΠ— адрес форматирующей строки шоч 1.
Рагаю1 ! Рагаш1 = 1 са11 рг1птт ! вызов ргтпСЕ ДО установки параиетра 2 Ц ) юоч О, Рагаш2 ! пустая операция для установки параиетра 2 Ь Попе ! завершение пор ~ вставляет пустую операцию Е1зе: шоч 6, К ' начало вычисления К = б -т-) зцЬ К,О.К ! К 6-3 шЬ К,1,К ! К"б-т'-О асс И, - 1, 5сгатсп юон 5сгатсп. РагаюО юон 1. Рагаю1 са)1 Еоиегз юон К, Рагаш2 ! начало процедуры Соиегз(п-1, т, К) . '5сгассп = и-1 ! параиетр 1 = т ' вызов Еоиегз ДО установки паранетра 2 ЕК) ', пустая операция после вызова ' процедуры для установки параиетра 2 ! начало процедуры Жоиегз( 1. 1.
1) ) параиетр 1 = 1 ! вызов тоиегз ДО установки параиетра 2 О ) ! параиетр 2 = ) яюч 1. РагаюО яюч 1. Рагаш1 са11 тоиегз юоч О. Рагаю2 юоч 5сгатсп, РагаюО . 'начало процедуры соиегз(п-1, К, 1) юоч К, Рагаю1 1 параиетр 1 = К са11 тоиегз ! вызов таиегз ДО установки параиетра 2 11) юоч 3, Рагаш2 ! параиетр 2 = 1 Оспе гет гезтоге ~ выход из процедуры ! вставка пустой коианды после гес ! для восстановления окон Еопват. азота "Переиестить диск с ЖО на Жйп" По алгоритму версия 1)1сгаЯРАКС П1 идентична версии Реп11цш 4. В обоих случаях сначала проверяется и, и, если и ) 1, совершается переход к е1 ее.
Основные сложности версии ШсгаЯРАКС П1 связаны с некоторыми свойствами архитектуры команд. Сначала код Б1сгаЯРАКС П1 должен передать адрес форматирующей строки в рг1пЖЕ, но машина не может просто переместить адрес в регистр, который содержит выходной параметр, поскольку нельзя поместить 32-разрядную константу в регистр одной командой. Для этого требуется выполнить две команды; зеЖЬ) и ог. После вызова не нужно делать подстройку стека, поскольку регистровое окно корректируется командой гевтоге в конце процедуры.
Возможность помещать выходные параметры в регистры, а не обращаться к памяти, дает значительный выигрыш в производительности. А теперь рассмотрим команду пор, которая следует за Попе. Это пустая операция, которая всегда будет выполняться, даже если она следует за командой ус- 460 Глава 5. Уровень архитектуры набора команд ловного перехода.
Сложность состоит в том, что процессор П1ггаЯРАЕС П1 очень конвейеризирован, и к тому моменту, когда аппаратно обнаруживается команда перехода, следующая команда уже практически заканчивает обрабатываться. Добро пожаловать в удивительный мир В1ЯС-программирования1 Эта особенность распространяется и на вызовы процедур. Рассмотрим первый вызов процедуры сонегз в части е1 зе. Процедура помещает и — 1 в 24оО, а 1— в 24о1, но совершает вызов процедуры тонегз до того, как поместит последний параметр в нужное место.
На компьютере Рептшш 4 вы сначала передаете параметры, а затем вызываете процедуру. А здесь вы сначала передаете часть параметров, затем вызываете процедуру, и только после этого передаете последний параметр. К тому моменту, когда машина осознает, что она имеет дело с командой са11, следующую команду все равно приходится выполнять (из-за конвейеризации).
А почему бы в этом случае не использовать пустую операцию, чтобы передать последний параметр? Даже если этот параметр потребуется самой первой команде вызванной процедуры, он уже будет на своем месте. Наконец, рассмотрим часть команды попе. Здесь после команды ген тоже вставляется пустая операция. Эта пустая операция используется для команды гез1оге, которая увеличивает на 1 значение Сук'Р, чтобы вернуть регистровое окно в прежнее состояние. Архитектура 1А-64 и процессор Напшт 2 Неизбежно, и очень скоро, наступит момент, когда создать на основе архитектуры команд 1А-32 и линейки процессоров Репс1пш 4 что-то более совершенное, чем существующие модели, будет уже невозможно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
