КЛ_АВС

предусматривают 2 операции: push и pop. Push – запись данных в стек (проталкивание);

Pop – чтение данных из стека (выталкивание). Запись возможна только в верхнюю ячейку стека. При этом вся хранимая в стеке информация предварительно проталкивается на первую позицию вниз. Чтение также допустимо только из вершины стека. Извлечённая информация удаляется из стека, а оставшееся содержимое продвигается вверх. В ВМ на базе стека операнды перед обработкой в верхние ячейки стека. Результат операции так же заносится в стек.

(А+В)(С+D) – Е

Для преобразований используем польскую нотацию, а затем алгоритм Дайкстра.

Приоритеты операций:

строку.

Если очередной символ из очередной строки “(”, то он проталкивается в стек.

“)” выталкивает все операции до ближайшей открывающей скобки “(”. Сами скобки в выходную строку не переносятся, а уничтожают друг друга.

Достоинства стековой архитектуры

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

Код компактный

По определению архитектура не предполагает произвольного доступа к памяти из-за чего трудно создать компилятор генерирующий эффект программного кода. Хотя создание компиляторов упрощается

Аккумуляторная архитектура

Аккумуляторная архитектура исторически возникла одной из первых.

Вней для хранения одного из операндов арифметической / логической операции в процессоре имеется выделенный регистр – аккумулятор. В этот

41

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

Для загрузки в аккумулятор содержание ячейки x предусмотрена команда загрузки load(x). По этой команде информация считывается из ячейки памяти x. Выход памяти подключается к входам аккумулятора и происходит занесение считанных данных в аккумулятор. Запись содержимого в ячейку x осуществляется командой сохранения store(x)

Для выполнения операций в АЛУ производится считывание одного из операторов в регистр данных. Второй операнд находится в аккумуляторе.

Выходы регистров данных и аккумулятор подключены к соответствующим входам АЛУ. По окончании предписанной операции результат с выхода АЛУ заносится в аккумулятор.

Достоинства аккумуляторной архитектуры

Короткие команды;

Простота декодирования команд Недостатки аккумуляторной архитектуры

Наличие всего одного регистра порождает многократное обращение к основной памяти

Регистровая архитектура (преобладающая)

Вмашинах данного типа процессор включает в себя массив регистров

(регистровый файл) -> регистры общего назначения (РОН)

Эти регистры в каком то смысле как явно управляемый КЭШ для хранения недавно использованных данных. Размер регистров обычно фиксирован и совпадает с длиной машинного слова. Размерность, обычно, совпадает с размером регистра или шины данных. К любому регистру можно обратиться указав его номер. Количество РОН в архитектуре CISC обычно невелико

(8-32) и для представления номера конкретного регистра необходимо не более пяти разрядов, благодаря чему в адресной части команд обработки допустимо одновременно держать до двух / трёх регистров. RISC архитектура предполагает использование существенно большего числа РОН

(До нескольких сотен). Однако, типичная для таких ВМ длина команд, обычно 32 разряда, позволяет определить в команде до трех регистров.

Регистровая архитектура допускает расположение операндов в одной из двух запоминающих сред: основной памяти и/или регистров. С учётом

42

возможных размещений операндов в рамках регистровых АСК выделим три подвида команд обработки:

1.Регистр-регистр (операнды только в регистрах в них же записывается операнд)

2.Регистр-память (Предполагается, что один из операндов в регистре, а другой в памяти, результат обычно записывается в какой-либо из них)

3.Память-память (оба операнда хранятся в основной памяти и туда же заносится результат)

Вариант регистр-регистр является основным в ВМ типа RISC и регистр-память – CISC; Память-память – неэффективно, но в использовании в наиболее сложных моделях CISC. Выполнение операций в АЛУ включает в себя:

1.Выбор регистра 1го операнда;

2.Определение расположения 2го операнда (память/регистр)

3.Подачу на вход АЛУ операндов и выполнение операции;

4.Выбор регистра результата и занесение в него результата операции из АЛУ. Между АЛУ и регистром файлов должны быть 3 шины;

Плюсы регистровых архитектур:

43

1.Компактность получаемого кода;

2.Высокая скорость вычислений, за счёт замены обращений к основной памяти на обращение к быстрым регистрам.

Минусы регистровых архитектур:

1.Требуются более длинные инструкции по сравнению с аккумуляторной архитектурой

Архитектура с выделенным доступом к памяти.

Вархитектуре с выделенным доступом к памяти обращение к основной памяти возможно только с помощью двух специальных команд: load и store.

Ванглийской транскрипции данную архитектуру называют Load/Store architecture. Команда load (Загрузка) обеспечивает считывание значения из основной памяти и занесение его в регистр процессора (в команде обычно указывается адрес ячейки памяти и номер регистра). Пересылка информации в противоположном направлении производится командой store (сохранение). Операнды во всех командах обработки информации могут находиться только в регистрах процессора (чаще всего в регистрах общего назначения). Результат операции также заносится в регистр. В архитектуре отсутствуют команды обработки, допускающие прямое обращение к основной памяти. Допускается наличие в АСК ограниченного числа команд, где операнд является частью кода команды.

АСК с выделенным доступом к памяти характерна для всех вычислительных машин с RISC-архитектурой. Команды в таких ВМ, как правило, имеют длину 32 бита и трехадресный формат. К достоинствам АСК следует отнести простоту декодирования и исполнения команды.

44

6. Форматы команд

Основные форматы команд

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

На рис. 5.6 показано несколько возможных форматов команд уровня архитектуры набора команд. Команды всегда содержат код операции. В команде могут присутствовать ни одного, один, два или три адреса.

Рис. 5.6. Четыре формата команд: безадресная команда (а); одноадресная команда (б); двухадресная команда (Б); трехадресная команда (г)

В одних машинах все команды но длине одинаковы, в других могут быть разными. Кроме того, команды по длине могут быть короче слова, длиннее слова или быть равными слову. Если все команды одной длины, то это упрощает декодирование, но часто требует излишнего пространства, поскольку все команды должны быть такой же длины, как самая длинная. На рис. 5.7 показано несколько возможных соотношений между размерами команды и слова.

Рис. 5.7. Некоторые возможные отношения между размерами команды и слова

Критерии разработки форматов команд

Если разработчикам нужно выбрать форматы команд для их машины, они должны принять во внимание ряд факторов. Нельзя недооценивать сложность этого решения. Если компьютер с коммерческой точки зрения получается удачным, набор команд может существовать на протяжении 20 лет и более. Имеет огромное значение возможность на протяжении

45

некоторого времени добавлять новые команды и другие элементы, но только в том случае, если архитектура (и компания, создавшая эту архитектуру) протянет достаточно долго.

Эффективность конкретной архитектуры команд зависит от технологии, которая применялась при разработке компьютера. За длительный период времени эта технология значительно изменится, и некоторые характеристики архитектуры команд окажутся (если оглянуться лет на 20 назад) неудачными. Например, если доступ к памяти осуществляется быстро, то подойдет стековая архитектура (как в IJVM), но если доступ к памяти медленный, тогда желательно иметь множество регистров (как в UltraSPARC III). Тем читателям, которые считают, что выбор сделать просто, мы предлагаем взять лист бумаги и записать следующие предположения:

+Какова будет типичная частота тактового генератора через 20 лет?

+Каково будет типичное время доступа к ОЗУ через 20 лет?

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

Если речь идет об одинаковых машинах, то лучше иметь короткие команды, чем длинные. Программа, состоящая из п 16-разрядных команд, занимает в два раза меньше пространства памяти, чем программа из п 32разрядных. Поскольку цены на память постоянно падают, этот фактор не имел бы значения в будущем, но, к сожалению, программное обеспечение разрастается гораздо быстрее, чем снижаются цены.

Более того, минимизация размера команд может усложнить их декодирование и перекрытие. Следовательно, стремление уменьшить размер команд должно уравновешиваться стремлением сократить время их декодирования и выполнения.

Есть еще одна очень важная причина минимизации длины команд, и она становится все важнее с увеличением скорости работы процессоров: пропускная способность памяти (число битов в секунду, которое память может предоставлять). Значительное повышение быстродействия процессоров за последнее десятилетие не соответствует увеличению пропускной способности памяти. Ограничения здесь связаны с неспособностью системы памяти передавать команды и операнды с той же скоростью, с которой процессор может их обрабатывать. Пропускная способность памяти зависит от технологии разработки. Встречаемые на этом пути трудности имеют отношение не только к основной памяти, но и ко всем видам кэш-памяти.

Если пропускная способность кэш-памяти команд составляет t бит/с, а средняя длина команды — г бит, то кэш-память способна передавать самое большее t/r команд в секунду. Отметим, что это — верхний предел скорости, с которой процессор может выполнять команды, хотя в настоящее время

46

предпринимаются попытки преодолеть данный барьер. Ясно, что скорость, с которой могут выполняться команды (то есть быстродействие процессора), может ограничиваться длиной команд. Чем короче команды, тем быстрее работает процессор. Поскольку современные процессоры способны выполнять несколько команд за один цикл, то вызов нескольких команд за цикл обязателен. Этот аспект применения кэш-памяти команд делает размер команд важным критерием, который нужно учитывать при разработке.

Еще один критерий — достаточный объем пространства в формате команды для представления всех требуемых операндов. Машина, поддерживающая 2п операций и длину команды менее п бит, невозможна. В этом случае в коде операции было бы недостаточно места для того, чтобы указать, какая нужна команда. К тому же история снова и снова доказывает, что обязательно нужно оставлять большое количество свободных кодов операций для будущих дополнений набора команд.

Третий критерий связан с числом битов в адресном поле. Рассмотрим проект машины с 8-разрядными символами и основной памятью, которая должна содержать 232 символов. Разработчики вольны были приписать последовательные адреса блокам по 8, 16, 24 или 32 бита.

Представим, что бы случилось, если бы команда разработчиков разбилась на две воюющие группы, одна из которых утверждает, что основной единицей памяти должен быть 8-разрядный байт, а другая требует, чтобы основной единицей памяти было 32-разрядное слово. Первая группа предложила бы память из 232 байт с номерами 0, 1, 2, 3,4 294 967 295. Вторая группа предложила бы память из 230 слов с номерами 0, 1, 2, 3, 1 073 741

823.

Первая группа скажет, что для того, чтобы сравнить два символа при организации по 32-разрядным словам, программе приходится не только вызывать из памяти слова, содержащие эти символы, но и выделять соответствующий символ из каждого слова для сравнения. А это потребует дополнительных команд и, следовательно, дополнительного пространства. 8- разрядная организация, напротив, обеспечивает адресацию каждого символа, что значительно упрощает процедуру сравнения.

Сторонники 32-разрядной организации скажут, что их проект требует всего лишь 230 отдельных адресов, что дает длину адреса всего 30 бит, тогда как при 8-разрядной организации требуется целых 32 бита для обращения к той же самой памяти. Если адрес короткий, то и команда будет более короткой. Она займет меньше пространства в памяти, и к тому же для ее вызова потребуется меньше времени. В качестве альтернативы они могут сохранить 32-разрядный адрес для обращения к памяти в 16 Гбайт вместо каких-то там 4 Гбайт.

Этот пример демонстрирует, что для получения оптимальной дискретности памяти требуются более длинные адреса и, следовательно, более длинные команды. Одна крайность — это организация памяти, при которой адресуется каждый бит (например, Burroughs В1700). Другая

47

крайность — это память, состоящая из очень длинных слов (например, серия CDC Cyber содержала 60-разрядные слова).

Современные компьютерные системы пришли к компромиссу, который, в каком-то смысле, объединил в себе худшие качества обоих вариантов. Они требуют, чтобы адреса были у отдельных байтов, но при обращении к памяти всегда считываются одно, два, а иногда даже четыре слова сразу. В результате считывания одного байта из памяти на машине UltraSPARC III единовременно вызываются минимум 16 байт (см. рис. 3.44), а иногда и вся строка кэш-памяти размером 64 байта.

Расширение кода операций

В предыдущем подразделе мы увидели, что короткие адреса препятствуют удачной дискретности памяти. В этом разделе мы рассмотрим компромиссы, связанные с кодами операций и адресами. Рассмотрим команду размером п + k бит с кодом операции в k бит и одним адресом в п бит. Такая команда допускает 2k различных операций и 2п адресуемых ячеек памяти. В качестве альтернативы те же п + k бит молено разбить на код операции в k - 1 бит и адрес в /2+ 1 бит. При этом будет либо в два раза меньше команд, но в два раза больше памяти, либо то же количество памяти, но дискретность вдвое выше. Код операции в k + 1 бит и адрес в п - 1 бит дает большее количество операций, но ценой этого является либо меньшее количество ячеек памяти, либо не очень удачная дискретность при том же объеме памяти. Наряду с подобными простыми компромиссами между битами кода операции и битами адреса существуют и более сложные. Обсуждаемый здесь механизм называется расширением кода операций.

Понятие расширения кода операций можно пояснить на примере. Рассмотрим машину, в которой длина команд составляет 16 бит, а длина адресов — 4 бита, как показано на рис. 5.8. Это вполне разумно для машины, содержащей 16 регистров (а следовательно, 4-разрядный адрес регистра), с которыми совершаются все арифметические операции. Один из возможных вариантов — включение в каждую команду 4-разрядного кода операции и трех адресов, что дает 16 трехадресных команд.

Рис. 5.8. Команда с 4-разрядным кодом операции и тремя 4-разрядными адресными полями

Если разработчикам нужно 15 трехадресных команд, 14 двухадресных команд, 31 одноадресная команда и 16 безадресных команд, они могут использовать коды операций от 0 до 14 в качестве трехадресных команд, а код операции 15 уже интерпретировать по-другому (рис. 5.9).

48

Рис. 5.9. Расширение кода операции обеспечивает 15 трехадресных команд, 14

двухадресных команд, 31 одноадресную команду и 16 безадресных команд. Поля хххх, уууу

и zzzz — это 4-разрядные адресные поля

Это значит, что код операции 15 содержится в битах с 8-го по 15-й, а не с 12-го по 15-й. Биты с 0-го по 3-й и с 4-го по 7-й, как и раньше, формируют два адреса. Все 14 двухадресных команд содержат число 1111 в старших четырех битах

ичисла от 0000 до 1101 в битах с 8-го по 11-й. Команды с числом 1111

встарших четырех битах и числом 1110 или 1111 в битах с 8-го по 11-й рассматриваются особо. Они трактуются так, как будто их коды операций находятся в битах с 4-го по 15-й. В результате получаем 32 новых кода операций. А поскольку требуется всего 31 код, то код 111111111111

49

означает, что действительный код операции находится в битах с 0-го по 15-й, что дает 16 безадресных команд.

Как видим, код операции становится все длиннее и длиннее: трехадресные команды имеют 4-разрядный код операции, двухадресные команды — 8-разрядный, одноадресные команды — 12-разрядный, а безадресные команды — 16-разрядный.

Идея расширения кода операций наглядно демонстрирует компромисс между пространством для кодов операций и пространством для другой информации. Однако на практике все не так просто и понятно, как в нашем примере. Есть только два способа изменения размера кода операций. С одной стороны, можно иметь все команды одинаковой длины, приписывая самые короткие коды операций тем командам, которым нужно больше всего битов для спецификации чего-либо другого. С другой стороны, можно свести к минимуму средний размер команды, если выбрать самые короткие коды операций для часто используемых команд и самые длинные — для редко используемых.

Если довести эту идею до конца, можно свести к минимуму среднюю длину команды, закодировав каждую команду, чтобы максимально уменьшить число требуемых битов. К сожалению, это ведет к наличию команд разных размеров, причем не выровненных в границах байтов. Пока существуют архитектуры команд с таким свойством (например, Intel 432), выравнивание будет иметь большое значение для быстрого декодирования команд. Тем не менее, эта идея часто применяется на уровне байтов. Далее мы рассмотрим архитектуру JVM-команд, чтобы показать, как можно менять форматы команд, чтобы максимально уменьшить размер программы.

Форматы команд процессора Pentium 4

Форматы команд процессора Pentium 4 очень сложны и нерегулярны. Они содержат до шести полей разной длины, пять из которых не обязательны (общая модель показана на рис. 5.10). Такая ситуация сложилась из-за того, что архитектура развивалась на протяжении нескольких поколений, и ранее в нее были включены не очень удачные варианты команд. Из-за требования обратной совместимости позднее их нельзя было изменить. Например, если один из операндов команды находится в памяти, то другой не может там находиться. В результате, существуют команды сложения двух регистров, команды прибавления регистра к слову памяти, команды прибавления слова памяти к регистру, но не существует команд для прибавления одного слова памяти к другому слову памяти.

В первых архитектурах Intel все коды операций были размером 1 байт, хотя для изменения некоторых команд часто использовался так называемый пре

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

50