 |
Концепция машины с хранимой в памяти программой
|
|
|
|
Для начала введем новое определение термина “вычислительная машина” как совокупности технических средств, служащих для автоматизированной обработки дискретных данных по заданному алгоритму. Алгоритм – одно из фундаментальных понятий математики и вычислительной техники. Международная организация стандартов (ISO) формулирует понятие алгоритм как “конечный набор предписаний, определяющий решение задачи посредством конечного количества операций” (ISO 2382/1-84). Помимо этой стандартизированной формулировки существуют и другие определения. Приведем наиболее распространенные из них. Итак, алгоритм – это:
1. способ преобразования информации, задаваемый с помощью конечной системы правил.
2. совокупность правил, определяющих эффективную процедуру решения любой задачи из некоторого заданного класса задач.
3. точно определенное правило действий, для которого задано указание, как и в какой последовательности это правило необходимо применять к исходным данным задачи, чтобы получить ее решение.
Основными свойствами алгоритма являются: дискретность, определенность, массовость и результативность.
Дискретность выражается в том, что алгоритм описывает действия над дискретной информацией (например, числовой или символьной), причем сами эти действия также дискретны.
Свойство определенности означает, что в алгоритме указано все, что должно быть сделано, причем ни одно из действий не должно трактоваться двояко.
Массовость алгоритма подразумевает его применимость к множеству значений исходных данных, а не только к каким-то уникальным значениям.
Наконец, результативность алгоритма состоит в возможности получения результата за конечное число шагов.
|
|
|
Рассмотренные свойства алгоритмов предопределяют возможность их реализации на ВМ, при этом процесс, порождаемый алгоритмом, называют вычислительным процессом.
В основе архитектуры современных ВМ лежит представление алгоритма решения задачи в виде программы последовательных вычислений. Согласно стандарту ISO 2382/1-84, программа для ВМ – это “упорядоченная последовательность команд, подлежащая обработке”.
ВМ, где определенным образом закодированные команды программы хранятся в памяти, известна под названием вычислительной машины с хранимой в памяти программой. Идея принадлежит создателям вычислителя ENIАС Эккерту, Мочли и фон Нейману. Еще до завершения работ над ENIАС они приступили к новому проекту – EDVAC, главной особенностью которого стала концепция хранимой в памяти программы, на долгие годы определившая базовые принципы построения последующих поколений вычислительных машин. Относительно авторства существует несколько версий, но поскольку в законченном виде идея впервые была изложена в 1945 году в статье фон Неймана, именно его фамилия фигурирует в обозначении архитектуры подобных машин, составляющих подавляющую часть современного парка ВМ и ВС.
Сущность фон-неймановской концепции вычислительной машины можно свести к четырем принципам:
1. двоичного кодирования. Согласно этому принципу, вся информация, как данные, так и команды, кодируются двоичными цифрами 0 и 1. Каждый тип информации представляется двоичной последовательностью и имеет свой формат. Последовательность битов в формате, имеющая определенный смысл, называется полем. В числовой информации обычно выделяют поле знака и поле значащих разрядов. В формате команды можно выделить два поля: поле кода операции (КОп) и поле адресов(адресную часть – АЧ). Код операции представляет собой указание, какая операция должна быть выполнена, и задается с помощью r-разрядной двоичной комбинации. Вид адресной части и число составляющих ее адресов зависят от типа команды: в командах преобразования данных АЧ содержит адреса объектов обработки (операндов) и результата; в командах изменения порядка вычислений – адрес следующей команды программы; в командах ввода/вывода – номер устройства ввода/ вывода. Адресная часть также представляется двоичной последовательностью, длину которой обозначим через р. Таким образом, команда в вычислительной машине имеет вид (r+р)-разрядной двоичной комбинации.
|
|
|
2. программного управления. Все вычисления, предусмотренные алгоритмом решения задачи, должны быть представлены в виде программы, состоящей из последовательности управляющих слов – команд. Каждая команда предписывает некоторую операцию из набора операций, реализуемых вычислительной машиной. Команды программы хранятся в последовательных ячейках памяти вычислительной машины и выполняются в естественной последовательности, то есть в порядке их положения в программе. При необходимости, с помощью специальных команд, эта последовательность может быть изменена. Решение об изменении порядка выполнения команд программы принимается либо на основании анализа результатов предшествующих вычислений, либо безусловно
3. однородности памяти. Команды и данные хранятся в одной и той же памяти и внешне в памяти неразличимы. Распознать их можно только по способу использования. Это позволяет производить над командами те же операции, что и над числами, и, соответственно, открывает ряд возможностей. Так, циклически изменяя адресную часть команды, можно обеспечить обращение к последовательным элементам массива данных. Такой прием носит название модификации команд и с позиций современного программирования не приветствуется. Более полезным является другое следствие принципа однородности, когда команды одной программы могут быть получены как результат исполнения другой программы. Эта возможность лежит в основе трансляции – перевода текста программы с языка высокого уровня на язык конкретной ВМ. Концепция вычислительной машины, изложенная в статье фон Неймана, предполагает единую память для хранения команд и данных. Такой подход был принят в вычислительных машинах, создававшихся в Принстонском университете, из-за чего и получил название принстонской архитектуры. Практически одновременно в Гарвардском университете предложили иную модель, в которой ВМ имела отдельную память команд и отдельную память данных. Этот вид архитектуры называют гарвардской архитектурой. Долгие годы преобладающей была и остается принстонская архитектура, хотя она порождает проблемы пропускной способности тракта “процессор-память”. В последнее время в связи с широким использованием кэш-памяти разработчики ВМ все чаще обращаются к гарвардской архитектуре.
|
|
|
4. адресности. Структурно основная память состоит из пронумерованных ячеек, причем процессору в произвольный момент доступна любая ячейка. Двоичные коды команд и данных разделяются на единицы информации, называемые словами, и хранятся в ячейках памяти, а для доступа к ним используются номера соответствующих ячеек – адреса.
Форматы команд
Типовая команда должна указывать:
а. подлежащую исполнению операцию;
б. адреса исходных данных (операндов), над которыми выполняется операция;
в. адрес, по которому должен быть помещен результат операции.
В соответствии с этим команда состоит из двух частей: операционной и адресной:
| Операционная часть | Адресная часть |
Формат команды определяет ее структуру, то есть количество разрядов, отводимых под всю команду, а также количество и расположение отдельных полей команды. Полем называется совокупность двоичных разрядов, кодирующих составную часть команды. При создании ВМ выбор формата команды влияет на многие характеристики будущей машины. Оценивая возможные форматы, нужно учитывать следующее:
а. общее число команд;
б. общую длину команды;
в. тип полей команды (переменной или фиксированной длины) и их длина;
г. простоту декодирования;
д. адресуемость и способы адресации;
е. стоимость оборудования для декодирования и исполнения команды.
Длина команды сильно влияет на организацию и емкость памяти, структуру шин, сложность и быстродействие центрального процессора. С одной стороны, нужно иметь как можно больше команд, операндов и способов адресации. А, с другой стороны, для ускорения выборки команды желательно, чтобы команда была короткой и ее дина была бы кратной ширине шины данных. Для упрощения аппаратуры длину команды выбирают кратной байту. В рамках системы команд одной ВМ могут использоваться разные форматы команд. Обычно это связано с применением разных способов адресации. В таком случае в состав кода команды вводится поле для задания способа адресации (СА):
|
|
|
| КОп | СА | Адресная часть |
Для определения количества адресов, включаемых в адресную часть, используется термин адресность. Вообще, нужно указать три компонента: адрес первого операнда, адрес второго операнда и адрес результата. В принципе, сюда может быть добавлен еще один адрес, указывающий место хранения следующей инструкции. В итоге имеет место четырехадресный формат команды:
| Код операции | 1-й операнд | 2-й операнд | Результат | След. команда |
Такой формат команды был у машины EDVAC (40-е годы).
В фон-неймановских ВМ необходимость в четвертом адресе отпадает, так как команды располагаются в памяти в порядке их выполнения, и адрес следующей команды может быть получен путем увеличения адреса текущей команды в счетчике команд. Это позволяет перейти к трехадресному формату команд:
| Код операции | 1-й операнд | 2-й операнд | Результат |
В трехадресном формате длина команды может оказаться весьма большой. Так, если адрес ячейки основной памяти имеет длину 32 бита, а длина кода операции – 8бит, то длина команды составит 104 бита (13 байт). Если по умолчанию взять за адрес результата адрес одного из операндов (обычно второго), то в итоге получим двухадресный формат команды:
| Код операции | 1-й операнд | 2-й операнд/Результат |
Команду еще можно сократить, перейдя к одноадресному формату, что возможно при выделении определенного стандартного места для хранения первого операнда и результата. Обычно для этой цели используется специальный регистр центрального процессора (ЦП), известный под названием аккумулятора:
| Код операции | 1-й или 2-й операнд |
Применение единственного регистра для хранения одного из операндов и результата является ограничивающим фактором, поэтому помимо аккумулятора часто используют и другие регистры ЦП. Так как число регистров в ЦП невелико, для указания одного из них в команде достаточно иметь сравнительно короткое адресное поле. Соответствующий формат называется полутораадресным или регистровым:
|
|
|
| Код операции | Регистр | 2-й операнд |
Наконец, если для обоих операндов указать стандартное местоположение, или команда не требует операндов, то можно получить нульадресный (безадресный) формат команды:
| Код операции |
При выборе количества адресов в команде следует руководствоваться следующими критериями:
а. емкостью запоминающего устройства, используемого для хранения программы;
б. временем выполнения программы;
в. эффективностью использования ячеек памяти при хранении программы.
Способы адресации
В современных ВМ исполнительный адрес (Аисп) и адресный код (Ак), как правило, не совпадают, и для доступа к данным требуется соответствующее преобразование. Способом адресации называют способ формирования исполнительного адреса операнда по адресному коду команды. Исполнительным адресом операнда (Аисп) называется двоичный код номера ячейки памяти, служащей источником или приемником операнда. Этот код подается на адресные входы запоминающего устройства (ЗУ), и по нему происходит фактическое обращение к указанной ячейке. Если операнд хранится не в основной памяти, а в регистре процессора, то исполнительным адресом будет номер регистра.
Для определения, какой способ адресации используется, в разных ВМ используют разные приемы. Часто разным способам адресации соответствуют разные коды операции. Другой подход – это добавление в состав команды специального поля способа адресации, содержимое которого определяет, какой из способов адресации используется. Иногда в команде присутствует несколько таких полей – по количеству адресов в программе. Может использоваться и неявная адресация, когда адресного поля просто нет, либо оно содержит не все необходимые адреса – отсутствующий адрес подразумевается кодом операции. Так, при исключении из команды адреса результата подразумевается, что он помещается на место второго операнда. Неявная адресация часто применяется, так как позволяет сократить длину команды.
В настоящее время используются следующие способы адресации:
а. Непосредственная адресация. В этом случае в адресном поле вместо адреса содержится сам операнд:
| Код операции | Способ адресации | Непосредственный операнд |
Этот способ может применяться при выполнении арифметических операций, операций сравнения, а также для загрузки констант в регистры.
б. Прямая адресация. При прямой или абсолютной адресации адресный код прямо указывает номер ячейки памяти, к которой производится обращение, то есть адресный код совпадает с исполнительным адресом:
в. Косвенная адресация. Одним из путей преодоления проблем прямой адресации, связанных с ограниченностью адресного поля команды, служит прием, когда указывается адрес ячейки, в свою очередь, содержащей полноразрядный адрес операнда. Недостаток косвенной адресации – необходимость двукратного обращения к памяти:
г. Регистровая адресация. Она напоминает прямую адресацию. Различие лишь в том, что адресное поле указывает не на ячейку памяти, а на регистр процессора. Обычно размер адресного поля здесь – три или четыре бита (адресация до 16 регистров):
д. Косвенная регистровая адресация. Здесь исполнительный адрес хранится в регистре процессора:
е. Адресация со смещением. Здесь исполнительный адрес формируется в результате суммирования содержимого адресного поля команды с содержимым одного или нескольких регистров процессора:
Некоторые из видов адресация со смещением имеют свои названия. Например:
– относительная адресация. При этом для получения исполнительного адреса операнда содержимое подполя Ак команды складывается с содержимым счетчика команд:
– базовая регистровая адресация. В этом случае регистр, называемый базовым, содержим полноразрядный адрес, а подполе Ас – смещение относительно этого адреса. Здесь может быть вариант с базовой регистровой адресацией с базовым регистром:
и базовая регистровая адресация с использованием РОН:
– индексная адресация. В этом случае подполе Ас содержит адрес ячейки памяти, а регистр (указанный явно или неявно) – смещение относительно этого адреса. Можно выделить индексную адресацию с индексным регистром:
и индексную адресацию с одним из РОН:
В большинстве случаев увеличение или уменьшение содержимого индексного регистра осуществляется автоматически до или после обращения к нему. Такой прием называется автоиндексированием. Автоиндексирование с увеличением содержимого индексного регистра называется автоинкрементной адресацией, а с уменьшением – автодекрементной адресацией. Также индексная адресация может быть с масштабированием и смещением. ж. страничная адресация. Она предполагает разбиение адресного пространства на страницы. Старшая часть адреса хранится в специальном регистре – регистре адреса страницы (РАС), а в адресном коде команды указывается смещение внутри страницы. Исполнительный адрес получается конкатенацией (присоединением) Ас к содержимому РАС:
з. блочная адресация. Она используется в командах, единицей обработки которых является блок данных, расположенных в последовательных ячейках памяти. Этот способ удобен при работе с внешними запоминающими устройствами и в операциях с векторами. Блок данных обычно метится адресами начала и конца (или признаком конца блока, количества байт в блоке).
и. стековая адресация. Здесь в качестве адреса используется стек. Стеком называется память, по своей структурной организации отличная от основной памяти ВМ. Стек образует множество логически взаимосвязанных ячеек, взаимодействующих по принципу “последним вошел, первым вышел” (LIFO, Last In First Out). Верхнюю ячейку называют вершиной стека. Запись возможна только в верхнюю ячейку стека, при этом вся хранящаяся в стеке информация предварительно проталкивается на одну позицию вниз. Чтение допустимо также только из вершины стека. Извлеченная информация удаляется из стека, а оставшееся его содержимое продвигается вверх.
|
|
|
