Способы адресации данных

Элементы информации, участвующие в операциях, именуются с помощью адресов, указываемых в командах. Для различных применений разработано большое число способов представления адресов в командах и доступа к операндам, определяемым адресами. Правило определения адреса и операнда на основе информации, указанной в команде, называется способом адресации. Каждый способ адресации порождает определенный тип адреса: способ прямой адресации – прямые адреса, способ относительной адресации – относительные адреса.

Эффективность способа адресации характеризуется двумя показателями: затратами оборудования и затратами времени на доступ к адресуемой информации. Затраты оборудования определяются суммой затрат оборудования на обработку адресов в процессоре и затрат памяти на хранение адресов, указываемых в командах программы. Последние составляют основную долю затрат оборудования, и поэтому при оценке затрат оборудования обычно ограничиваются учетом затрат памяти на адресацию информации. Затраты времени принято характеризовать числом обращений к основной памяти, выполняемых с целью выборки или записи операнда.

Рассмотрим основные способы адресации информации, используемые в компьютерах.

Прямая адресация. Прямой адрес - это номер ячейки памяти, в которой хранится операнд. Прямой адрес представляется в команде m-разрядным полем, где m = log₂Е и Е – емкость адресуемой памяти, исчисляемая в машинных элементах информации – словах или байтах. Прямой адрес А передается в память, и путем обращения к памяти из ячейки А читается или в нее записывается операнд. Прямая адресация – это основополагающий способ адресации.

Непосредственная адресация. В программах достаточно часто используются целочисленные константы: 0, 1, 2, … Если использовать прямую адресацию, то для размещения константы необходимо выделять ячейку памяти и для выборки константы производить одно обращение к памяти. Затраты памяти и времени уменьшаются, если константу представлять непосредственно в m-разрядном поле адреса. В этом случае для констант со значениями 0, 1, …, 2^m–1 нет необходимости выделять ячейки памяти, а поскольку константа размещена в команде, экономится одно обращение к памяти на каждую константу. Адрес, в котором размещается значение константы, называется непосредственным адресом. Непосредственная адресация позволяет экономить память и время, когда константа является целым положительным числом со значением, меньшим 2^m.

Косвенная адресация. При программировании некоторых задач широко используются указатели, определяющие местоположение операндов в памяти. Указатель – это адрес операнда, хранимый в определенной ячейке памяти. Значение указателя может меняться в процессе выполнения программы по мере обработки одних операндов и перехода к обработке других, но адрес самого указателя остается постоянным, обеспечивая на каждом этапе вычислений обращение к соответствующему операнду. В таком случае адрес определен в ячейке с заданным адресом. Адрес, определяющий адрес операнда, называется косвенным адресом. Для доступа к косвенно адресуемому операнду с помощью прямых адресов требуется выполнить следующие действия: 1) обращение к памяти по адресу А с целью выборки адреса А₁ операнда; 2) формирование команды, состоящей из кода операции и адреса операнда А₁; 3) запись сформированной команды в соответствующую ячейку памяти; 4) обращение к операнду с помощью сформированной команды. Эта процедура программируется с помощью четырех команд и порождает восемь обращений к памяти.

Чтобы избежать столь значительных затрат памяти и времени, используется косвенная адресация. Косвенный адрес А_к, указанный в команде, обрабатывается следующим образом:

А_к ® А_к ® … ® А_к ® А ® Операнд.

Здесь стрелка обозначает обращение к памяти по адресу, указанному в начале стрелки. Первое обращение к памяти по адресу А_к может привести к выборке нового косвенного адреса А_к, для обработки которого производятся последующие обращения к памяти до тех пор, пока не будет получен прямой адрес А и по нему – операнд. Количество обращений к памяти с целью определения прямого адреса по косвенному называется глубиной косвенной адресации. Если первое же обращение к памяти гарантирует получение прямого адреса, то глубина косвенной адресации равна 1. Если процессор может обращаться к памяти произвольное число раз с целью поиска прямого адреса, то косвенная адресация имеет произвольную глубину, для обеспечения которой необходимо, чтобы код косвенного адреса отличался от кода прямого адреса.

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

Способ адресации может указываться с помощью специального поля – признака адресации (ПА). При использовании трех способов адресации признак адресации занимает два разряда и имеет следующий смысл: ПА = 00 – прямая адресация; ПА = 01 – непосредственная адресация; ПА = 10 – косвенная адресация. При этом 1-адресная команда имеет следующий формат:

		,

 

где КО – код операции и А₁ – адрес в команде.

Использование непосредственной и косвенной адресации в дополнение к прямым адресам способствует уменьшению числа ячеек памяти, необходимых для программы, и числа выполняемых операций. Однако введение дополнительных способов адресации приводит к увеличению длины команды. Поэтому использование непосредственной и косвенной адресации оправдано только в том случае, когда экономия памяти и времени, получаемая за счет дополнительных способов адресации, превышает затраты памяти, связанные с введением в команды признаков адресации. Экономия памяти и времени пропорциональна частоте использования непосредственной и косвенной адресации и зависит от класса алгоритмов, реализуемых компьютером. Непосредственная адресация используется достаточно часто. Применение косвенной адресации оправдано только в тех случаях, когда в алгоритмах широко используются информационные структуры вида «адрес – адрес – … – адрес – операнд».

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

Модифицируемые адреса.Рассмотренные способы адресации обеспечивают доступ к простым переменными константам. В качестве операндов могут использоваться переменные с индексами, являющиеся элементами массивов. Массив представляет собой совокупность однотипных значений (слов или полей). Элемент массива x_i выделяется идентификатором массива х и индексом i, определяющим порядковый номер элемента в массиве. В программе массив принято идентифицировать адресом B_x первого элемента массива x₀, называемым базовым адресом. Адрес [x_i] элемента x_i определяется значением

[x_i] = B_x + i, (3.4)

где i = 0, 1, …, m. В команде с операндом x_i может быть указан только базовый адрес массива B_x, и перед выполнением команды адрес должен быть увеличен на значение индекса i. Процедура изменения адреса в команде называется модификацией.

Модификация может выполняться программно – совокупностью команд, изменяющих адрес в команде в соответствии с (3.4). В 1-адресном компьютере для этого требуется три дополнительных команды и одна константа, задающая первоначальную форму модифицируемой команды. Следовательно, программная модификация адресов значительно замедляет процесс обработки переменных с индексами и приводит к большим затратам памяти.

Затраты времени и памяти на обработку переменных с индексами значительно снижаются за счет схемной модификации адресов в процессоре. Для хранения значений индексов используется память процессора – регистры общего назначения РОН, емкостью Q = 2^q – 1 слов (рис. 3.3). Модифицируемый адрес имеет следующую структуру:

 

 

где X – адрес регистра общего назначения, в котором хранится индекс и А₁ – адрес в основной памяти. Адрес операнда определяется следующим образом:

 

Когда адрес А₁ определяет простую переменную или константу, то модификация исключается нулевым значением поля Х. При Х¹0 адрес А₁ имеет смысл базового адреса массива. В этом случае производится обращение к внутренней памяти по адресу Х и сложение базового адреса А₁ с индексом РОН[X], в результате чего определяется адрес А операнда, хранимого в основной памяти.

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

Рассмотрим вопрос о необходимом числе индексов, которые должны находиться во внутренней памяти процессора. На каждом этапе вычислений используется ограниченное количество индексов – один, два или более, которое определяется числом различных индексов, фигурирующих в вычисляемом выражении. Вероятность того, что на этапе вычислений будут использоваться k = 1, 2, … индекса, зависит от свойств алгоритмов. Если емкость памяти, отведенной для хранения индексов, Q<k, то в процессе вычислений возникает необходимость разгрузить память индексов путем переходами их в основную память и загрузить в освободившиеся ячейки другие необходимые индексы. Для этого в программу включаются дополнительные команды, обеспечивающие передачу индексов между регистрами процессора и оперативной памятью, что увеличивает длину программы и время вычислений. Чем больше емкость памяти индексов, тем меньше вероятность того, что требуемое для вычислений количество индексов превысит емкость регистровой памяти процессора. Минимально необходимое число индексов для модификации адресов равно 1. Увеличение емкости памяти индексов уменьшает длину программы и время вычислений, что является позитивным явлением, но наряду с этим увеличиваются затраты оборудования в процессоре за счет увеличения емкости его регистровой памяти и, что самое главное, увеличивается длина поля Х, т. е. длина команды. Практика проектирования компьютеров и программирования показывает, что в общем случае в процессе вычислений одновременно используются не более четырех – восьми индексов.

Относительная адресация. Компьютеры общего применения работают в мультипрограммном режиме, который существенно увеличивает системную производительность компьютеров. В таком случае в основной памяти компьютера, должно размещаться несколько программ, обеспечивающих хорошую загрузку процессора, системы ввода-вывода и прочих устройств компьютера. Чтобы обеспечить возможность размещения программ и связанных с ними данных в любом месте основной памяти, необходимо все программы, получаемые путем трансляции с языков высокого уровня в машинный код, размещать начиная с адреса 0 и использовать специальный механизм адресации – относительную адресацию. Пример организации мультипрограммной обработки представлен на рис. 3.5. Организация мультипрограммирования возлагается на операционную систему компьютера, поэтому для размещения программ операционной системы используется область основной памяти от адреса В₀ и длиной L₀. Затем в основной памяти размещается программа А, начинающаяся с адреса В₁ и имеющая длину L_1, затем программа В, начинающаяся с адреса В₂ и имеющая длину L₂ и т. д. Адреса В_0, В_1, В₂, … являются базовыми адресами программ, определяющими физическое положение программ в основной памяти. Естественно, что при обращении к памяти процессор должен добавлять значение базового адреса ко всем адресам, выполняемых команд и данных, чтобы обеспечить выполнение команд и обращение к адресуемым данным. Для обеспечения мультипрограммной обработки данных в процессор встраиваются средства, обеспечивающие относительную адресацию команд и данных.

Относительная адресация основывается на размещении в памяти процессора базовых адресов и представлении всех адресов, кроме непосредственных, в виде двух полей:

 

 

Здесь B – адрес регистра процессора, в котором размещается базовый адрес, и D – смещение, определяющее порядковый номер операнда. Адрес операнда определяется суммой А = РОН [B] +D, где РОН [B] – содержимое регистра памяти процессора с адресом В.

При использовании относительной адресации адреса операндов задаются значениями D = 0, 1, …, 2^m-1 относительно произвольных базовых адресов, которые определяются только косвенно – адресами В регистров памяти процессора, содержащих значения базовых адресов. При загрузке программы в основную память в соответствующие ячейки памяти засылаются базовые адреса, определяющие местоположение информации в адресном поле основной памяти. При выполнении программы относительные адреса (3.7), указанные в командах, обрабатываются процессором путем выборки из памяти значения базового адреса РОН [B] и сложения его со смещением D. Сумма определяет абсолютный базовый адрес – адрес ячейки основной памяти, в которой хранится операнд. При любом местоположении программы в памяти команды не изменяются, а изменяются лишь значения в ячейках регистровой памяти процессора, отведенных для хранения базовых адресов.

Емкость регистровой памяти процессора, необходимая для размещения базовых адресов, – один базовый адрес для указания начала выполняемой программы и базовые адреса для адресации массивов данных, количество которых определяется свойствами алгоритма и в первую очередь – структурой данных, обрабатываемых программой. Если на этапе вычислений используется k базовых адресов и емкость регистровой памяти, отведенная под базовые адреса, Q<k, то в процессе вычислений возникает необходимость разгружать память базовых адресов путем передачи их в основную память и загружать в освободившиеся ячейки необходимые базовые адреса. Как и в случае с индексами, передачи базовых адресов между регистровой памятью процессора и основной памятью приводит к увеличению длины и времени выполнения программы. Чем больше емкость памяти базовых адресов, тем меньше вероятность того, что количество базовых адресов, используемых на текущем шаге вычислений, превысит емкость памяти. Следовательно, увеличение емкости памяти для хранения базовых адресов приводит к уменьшению длины и времени выполнения программы. Однако одновременно с этим, увеличивается длина поля В в адресе (3.7), т. е. длина команд, и затраты оборудования в процессоре.

Относительные модифицируемые адреса. Чтобы эффективно обрабатывать переменные с индексами при относительной адресации информации, используются относительные модифицируемые адреса со следующей структурой:

 

Здесь B и Х – адреса базового адреса и индекса соответственно и D – смещение. Адрес (3,8) обрабатывается с целью вычисления адреса операнда А по схеме, показанной на рис.3.6. Адрес операнда определяется m-разрядным значением

	. . .

 

 

. . . Q

. . .

Смещение D в (3.8) при Х¹0 имеет смысл относительно базового адреса массива, элементом которого является адресуемый операнд – переменная с индексом.

Страничная организация памяти.Компьютеры общего применения оснащаются оперативной памятью большой емкости, достигающей 2²⁶ и более байт, так что адреса могут иметь длину от 26 бит и более. При определении форматов команд стремятся длину команды согласовать с длиной слова, поскольку представление команды, например, в виде двух слов может увеличить время выборки команды из памяти. В компьютерах общего применения длина слова обычно равна 32 или 64 битам. Чтобы освободить часть слова для размещения необходимых полей команды (кода операции, базового адреса, индекса и т.д.), необходимо уменьшить длину адреса, представляемого в команде. Для этого используется следующий прием. Множество адресов памяти разделяется на группы, состоящие из Р=2^р соседних адресов, называемых страницами памяти. Количество слов или байтов в странице называется размером страницы.Для уменьшения длины команды адрес в команде представляется только младшими р разрядами, т. е. адресом слова в странице. Размер страницы обычно составляет от 4 до 64 Кбайт, и для представления адреса байта в команде требуется от 12 до 16 бит, благодаря чему длина адреса значительно сокращается – в 3-6 раз. Такой способ адресации называется страничной адресацией памяти и используется в компьютерах общего применения, работающих в мультипрограммном режиме (см. рис. 3.5). Вычисление адреса ячейки памяти на основе информации, содержащейся в команде, происходит следующим образом (рис. 3.7). В момент начала обработки k-й программы операционная система загружает в регистр процессора адрес В_k и длину L_k сегмента, отведенного в памяти для размещения k-й программы и соответствующих данных. Таким образом определяется местоположение в памяти k-й программы В_k и длина сегмента L_k, определяемая числом страниц, отведенных программе. При обработке команд формируется относительный адрес, состоящий их трех полей: базового адреса, определяющего местоположение первого слова В в массиве, индекса Х, если X≠0, и смещения D, определяющего относительно адреса В положение простой переменной, константы и т. д. Сумма базового адреса программы В_k, базового адреса массива В, индекса X, если X≠0, и смещения D, определяющего адрес в странице, образуют исполнительный адрес, по которому производится обращение к памяти. Дополнительно отметим, что значения базового адреса и индекса выбираются по значениям B и X из регистров общего назначения РОН, входящих в состав процессора.

Стековая адресация. Стек (от английского слова stack – стог сена) входит в состав процессора и состоит из совокупности регистров, объединенных особой системой адресации – стековой адресацией. Для стековой адресации используется счетчик стека СС, который при запуске компьютера устанавливается в состояние 0, указывающее, что стек пуст. Для загрузки величин в стек используется команда загрузить стек ЗАГС А, где А – адрес ячейки памяти. Например, если в программе появились команды загрузки стека ЗАГС [α] и ЗАГС [β], где [α] и [β] – адреса ячеек памяти, в которых размещены слова α и β, то слово α будет размещено в регистре стека с адресом СС=0, после чего счетчик стека автоматически переключается в состояние СС=1, и при выполнении следующей команды в следующий регистр стека будет записано слово β, после чего счетчик стека автоматически прейдет в состояние СС=2. Если затем в программе появятся команды записи в память из стека ЗАПС А₁ и ЗАПС А₂, где А₁ и А₂ – адреса ячеек памяти, то будут выполнены следующие действия:

СС: = СС-1, [А₁]: = β;

СС: = СС-1, [А₂]: = α.

При этом счетчик стека уменьшается на единицу и слово β передается в ячейку памяти с адресом А₁. Вслед за этим действие повторяется: опять счетчик стека уменьшается на единицу и слово α передается в ячейку памяти с адресом А₂. Таким образом, адресация стека выполняется автоматически: при каждой загрузке слова в стек состояние счетчика стека автоматически увеличивается на единицу, а при записи слова в память состояние счетчика стека сначала уменьшается на единицу, и затем слово передается из стека в память. Счетчик стека всегда определяет адрес следующего свободного регистра стека. При этом, если слова α, β, γ загружены в регистры стека последовательно, выборка из стека этих слов происходит в обратном порядке γ, β, α, соответствующим текущим состояням счетчика стека, который при выборке сначала переходит в состояние, на единицу меньшее текущего, после чего очередное слово выбирается из стека.

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

Y: = AB(С+D)/(EF+H)

Соответствует следующая бесскобочная форма:

ABCD+EFH+/X à Y

По этому представлению выражения построена программа, приведенная в табл. 3.3. Переменные a, b, …, y обозначают адреса ячеек памяти, в которых хранятся значения A, B, …, Y соответственно. Символ * отмечает состояние счетчика адреса стека на момент окончания операции. Из приведенной программы видно, что количество обращений к памяти равно числу переменных в арифметическом выражении. Все промежуточные результаты автоматически сохраняются в памяти, благодаря чему исключается

 

Таблица 3.3. Вычисление арифметического выражения

Команды	Содержание регистров стека с адресами 0,…, 4
ЗАГРУЗИТЬ a ЗАГРУЗИТЬ b УМНОЖИТЬ ЗАГРУЗИТЬ c ЗАГРУЗИТЬ d СЛОЖИТЬ ЗАГРУЗИТЬ e ЗАГРУЗИТЬ f УМНОЖИТЬ ЗАГРУЗИТЬ h СЛОЖИТЬ РАЗДЕЛИТЬ УМНОЖИТЬ ЗАПИСАТЬ y	A A AB AB AB AB AB AB AB AB AB АВ Y *	* B * C C C + D C + D C + D C + D C + D C + D (C+D)/(EF+H) *	* * D * E E EF EF EF + H *	* * F * H *	* *

 

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

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

Другой пример применения стековой памяти – хранение локальных переменных, используемых в теле процедуры для выполнения вычислений. Для размещения локальных переменных процедур используется пара указателей: счетчик стека СС1 и счетчик стека СС2, определяющие соответственно верхнюю и нижнюю границы области локальных переменных, выделенную для их хранения в стеке. Если стек пуст, оба счетчика указывают адрес первой свободной ячейки стека. Когда начинается выполнение процедуры А, происходит загрузка локальных переменных процедуры в стек. При обращении процедуры А к процедуре В локальные переменные процедуры В также загружаются в стек и процесс вычислений продолжается. Самое главное свойство стека – возможность исполнения рекурсивных процедур, предписывающих многократное выполнение процедур с одним и тем же именем D, но с разными наборами фактических параметров в процедурах D. При многократных обращениях к рекурсивным процедурам только стек позволяет для каждого обращения выделять новую область для размещения локальных переменных процедуры. Детально функции стека описаны в книге [1].