Становление и эволюция цифровой вычислительной техники 8 страница

Двумя основными преимуществами регистровой адресации являются: короткое адресное поле в команде и исключение обращений к памяти. Малое число РОН позволяет сократить длину адресного поля команды, то есть С_РА « С_ПА. Кроме того, Т_РА = t_РОН, где t_РОН — время выборки операнда из регистра общего назначения, причем t_РОН « 2t_ЗУ. К сожалению, возможности по использованию регистровой адресации ограничены малым числом РОН в составе процессора.

Рис. 2.50. Регистровая адресация

Косвенная регистровая адресация

Косвенная регистровая адресация (КРА) представляет собой косвенную адресацию, где исполнительный адрес операнда хранится не в ячейке основной памяти, а в регистре процессора. Соответственно, адресное поле команды указывает не на ячейку памяти, а на регистр (рис. 2.51).

Рис. 2.51. Косвенная регистровая адресация

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

; ,

где R_РОН – разрядность регистров общего назначения.

Адресация со смещением

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

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

Рис. 2.52. Адресация со смещением

Если же составляющая адреса может располагаться в произвольном регистре общего назначения, то для указания конкретного регистра в команду включается дополнительное поле R (при составлении адреса более чем из двух составляющих в команде будет несколько таких полей). Еще одно поле R может появиться в командах, где смещение перед вычислением исполнительного адреса умножается на масштабный коэффициент. Такой коэффициент заносится в один из РОН, на который и указывает это дополнительное поле. В наиболее общем случае адресация со смещением подразумевает наличие двух адресных полей: А_К и R.

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

Ниже рассматриваются основные способы адресации со смещением, каждый из которых, впрочем, имеет собственное название.

Относительная адресация

При относительной адресации (OA) для получения исполнительного адреса операнда содержимое подполя А_к команды складывается с содержимым счетчика команд (рис. 2.53). Таким образом, адресный код в команде представляет собой смещение относительно адреса текущей команды. Следует отметить, что в момент вычисления исполнительного адреса операнда в счетчике команд может уже быть сформирован адрес следующей команды, что нужно учитывать при выборе величины смещения. Обычно подполе А_к трактуется как двоичное число в дополнительном коде.

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

Рис. 2.53. Относительная адресация

Эффективность данного способа адресации можно описать выражениями: ;

где t_CJl — время сложения составляющих исполнительного адреса; R_CK — разрядность счетчика команд.

Базовая регистровая адресация

В случае базовой регистровой адресации (БРА) регистр, называемый базовым, содержит полноразрядный адрес, а подполе А_с — смещение относительно этого ад­реса. Ссылка на базовый регистр может быть явной или неявной. В некоторых ВМ имеется специальный базовый регистр и его использование является неявным, то есть подполе R в команде отсутствует (рис. 2.54).

Рис. 2.55. Базовая регистровая адресация с базовым регистром

Более типичен случай, когда в роли базового регистра выступает один из регистров общего назначения (РОН), тогда его номер явно указывается в подполе R команды (рис. 2.55).

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

Рис. 2.55. Базовая регистровая адресация с использованием одного из РОН

Распределение значений смещения, оцененное в [120] при выполнении пятитестовых программ пакета SPECInt92 и пяти программ пакета SPECftp92, показано на рис. 2.56.

Рис. 2.56. Распределение размеров смещений при базовой регистровой адресации

Длина смещения превысила 16 бит лишь в 1% случаев базовой регистровой адресации, то есть в подавляющем большинстве случаев длина смещения существенно меньше.

Разрядность смещения R_CM и, соответственно, затраты оборудования определяются из условия , где N_ОПi количество операндов i-й программы.

Затраты времени составляют: .

Индексная адресация

При индексной адресации (ИА) подполе А_С содержит адрес ячейки памяти, а регистр (указанный явно или неявно) — смещение относительно этого адреса. Как видно, этот способ адресации похож на базовую регистровую адресацию. Поскольку при индексной адресации в поле А_С находится полноразрядный адрес ячейки памяти, играющий роль базы, длина этого поля больше, чем при базовой регистровой адресации. Тем не менее вычисление исполнительного адреса операнда производится идентично (рис. 2.57, 2.58).

Рис. 2.57. Индексная адресация с индексным регистром

Рис. 2.58. Индексная адресация с использованием одного из РОН

Индексная адресация предоставляет удобный механизм для организации итеративных вычислений. Пусть, например, имеется массив чисел, расположенных в памяти последовательно, начиная с адреса N, и мы хотим увеличить на единицу все элементы данного массива. Для этого требуется извлечь каждое число из памяти, прибавить к нему 1 и вернуть обратно, а последовательность исполнительных адресов будет следующей: N,N + 1, N + 2 и т. д., вплоть до последней ячейки, занимаемой рассматриваемым массивом. Значение N берется из подполя А_с ко­манды, а в выбранный регистр, называемый индексным регистром, сначала заносится 0. После каждой операции содержимое индексного регистра увеличивается на 1.

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

Автоиндексирование с увеличением содержимого индексного регистра носит название автоинкрементной адресации и может быть описано следующим образом:

или

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

Автоиндексирование с уменьшением содержимого индексного регистра носит название автодекрементной адресации и может быть описано так:

или

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

Интересным и весьма полезным является еще один вариант индексной адресации — индексная адресация с масштабированием и смещением: содержимое индексного регистра умножается на масштабный коэффициент и суммируется с А_С. Масштабный коэффициент может принимать значения 1,2,4 или 8, для чего в адресной части команды выделяется дополнительное поле. Описанный способ адресации реализован, например, в микропроцессорах фирмы Intel.

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

Страничная адресация

Страничная адресация (СТА) предполагает разбиение адресного пространства на страницы. Страница определяется своим начальным адресом, выступающим в качестве базы. Старшая часть этого адреса хранится в специальном регистре — регистре адреса страницы (РАС). В адресном коде команды указывается смещение внутри страницы, рассматриваемое как младшая часть исполнительного адреса. Исполнительный адрес образуется конкатенацией (присоединением) А_С к содержимому РАС, как показано на рис. 2.59. На рисунке символ || обозначает операцию конкатенации.

Рис. 2.59. Страничная адресация

Показатели эффективности страничной адресации имеют вид:

, ,

где М — количество страниц в памяти

Блочная адресация

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

Стековая адресация

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

Распространенность различных видов адресации

Частота использования различных способов адресации существенно зависит от типа АСК. Для машин со стековой архитектурой очевидно, что основным способом адресации является стековая адресация. Для ВМ с аккумуляторной АСК главные способы адресации — это прямая и непосредственная.

Достаточно ясна и ситуация с RISC-архитектурой. Из самой идеи этого подхода вытекает, что преимущественный способ адресации здесь — регистровая адресация.

Более сложным является вопрос о частоте использования различных видов адресации в регистровых ВМ. В рамках этой архитектуры существует множество машин с самыми разнообразными списками команд и различными сочетаниями способов адресации, в силу чего дать однозначный ответ относительно наиболее распространенных вариантов практически невозможно. Сказанное подтверждают результаты, полученные при выполнении программ GCC и Spice на вычислительной машине DEC VAX (рис. 2.60) и на ВМ с микропроцессором класса 80×86 (рис. 2.61).

Из диаграмм видно, что в машине VAX из применявшихся способов адресации доминируют непосредственная, базовая регистровая и косвенная регистровая. Доля не упомянутых в таблице способов адресации не превышает 2%.

Рис. 2.60. Частота использования методов адресации на программах GCC и Spice (DEC VAX)

Рис. 2.61. Частота использования методов адресации на программах GCC и Spice (Intel 80x86)

При выполнении программ GCC и Spice на ВМ с микропроцессорами серии 80x86 наиболее активно используются прямая и базовая регистровая адресации.

Как видно, сделать однозначный вывод о наибольшей распространенности какого-либо способа адресации для архитектур с РОН достаточно сложно. Единственное общее замечание — интенсивность применения конкретных способов адресации ощутимо зависит от характера решаемой задачи. Это обстоятельство обязательно должно учитываться пользователями при выборе ВМ под конкретное применение.

Способы адресации в командах управления потоком команд

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

Для команд безусловного и условного перехода (ветвления) наиболее типична относительная адресация, когда в адресной части команды указывается смещение адреса точки перехода относительно текущей команды, то есть смещение относительно текущего содержимого счетчика команд. Использование данного способа адресации позволяет программе выполняться в любом месте памяти — программы становятся перемещаемыми. Среди команд безусловного перехода доля относительной адресации составляет около 90%.

Для команд перехода чрезвычайно важно, насколько далеко адрес перехода отстоит от адреса команды перехода, иными словами, какова типичная величина смещения. В [120] приведены данные о типовой величине смещения, оцененной по программам GCC, Spice, ТеХ; они представлены на рис. 2.62. Результаты, полученные на смесях программ с преимущественной обработкой целочисленных и вещественных данных, показаны на нижнем графике того же рисунка.

Как видно, длина смещения в основном не превышает 8 бит, что соответствует смещению в пределах ±128 относительно команды ветвления. В подавляющем большинстве случаев переход идет в пределах 3-7 команд относительно команды перехода.

Рисунок 2.63 дает представление о преимущественном направлении переходов

Рис. 2.62. Средние значения смещения в командах условного перехода

Рис. 2.63. Доля переходов назад в программах GCC, Spice и ТеХ

Из приведенных данных следует, что в среднем 75% переходов происходит в направлении увеличения адреса. Из переходов в сторону уменьшения адреса около 90% связаны с выполнением циклов.

Система операций

Системой операций называется список операций, непосредственно выполняемых техническими средствами вычислительной машины. Система операций ВМ определяется областью ее применения, требованиями к стоимости, производительности и точности вычислений.

Связь системы операций с алгоритмами решаемых задач проявляется в степени ее приспособленности для записи программ реализации этих алгоритмов. Степень приспособленности характеризуется близостью списка операций системы команд и операций, используемых на каждом шаге выполнения алгоритмов. Простоту программирования алгоритма часто определяют термином «программируемость вычислительной машины». Чем меньше команд требуется для составления программы реализации какого-либо алгоритма, тем программируемость выше. В архитектурах типа CISC улучшения программируемости добиваются введением в систему операций большого количества операций, в том числе и достаточно сложных. Это может приводить и к повышению производительности ВМ, хотя в любом случае увеличивает аппаратурные затраты.

Обоснованный выбор системы операций (СО) возможен лишь исходя из анализа подлежащих реализации алгоритмов. Для этого определяется частотный вектор используемых в алгоритме операторов (q₁, …, q_n). Изучив вектор, составляют список основных, наиболее часто встречающихся операторов. Операторы основного списка реализуются системой машинных операций ВМ (каждому оператору сопоставляется своя машинная операция). Остальные операторы получают путем их разложения на операторы основного списка.

Показатели эффективности системы операций

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

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

Затраты оборудования С можно описать выражением

где С_ПР — затраты в процессоре на реализацию системы операций, С_ЗУ — затраты памяти на размещение данных и программ, представляющих алгоритм в терминах заданной системы операций.

Величина С_ПР пропорциональна количеству и сложности машинных операций, а С_ЗУ – емкости памяти, необходимой для хранения закодированного алгоритма. Усложнение машинных операций приводит к сокращению количества операций (команд), требуемых для описания алгоритма, и, следовательно, к уменьшению необходимой емкости памяти.

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

Вероятность правильного выполнения программ Р определяется по формуле

где l — количество операций в СО; п — количество операций (команд) в программах;λ_i, τ_i — интенсивность отказов и время выполнения операции (команды) i-ro типа; q_i — частота появления операций i-гo типа в программах; р_i — вероятность правильного выполнения nq_i операций i-гo типа.

В [16] утверждается, что показатель Р оптимален при условии

, . (2.14)

Условие (2.14) можно переписать в ином виде:

, (2.15)

Равенство (2.15) позволяет найти оптимальное соотношение параметров λ_i, и τ_i при реализации системы операций. Принимая параметры аппаратной реализации одной из операций за эталон(λ_ЭТ, τ_ЭТ), из (2.15) получим соотношение

, (I = 1, 2, …, l), (2.16)

позволяющее по известным параметрам для S различных вариантов системы операций выбрать лучший. Критерием качества реализации каждой операции для разработки s-го варианта СО является

(i = 1, …, l). (2.17)

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

(2.18)

Если значения λ_i (i = 1, …, l) неизвестны, то оправдано следующее допущение: λ_i = λ_j, ((i,j = 1, 2, …, l)).

При этом условие (2.15) преобразуется в условие «равного временного участия» операций в программах [28]:

, (2.19)

Условие (2.19) совместно с рассчитанным частотным вектором и известным ограничением на время выполнения программы Т_ДОП можно применить для вычисления оптимальной длительности машинных операций:

, (2.20)

Иерархия систем операций

Пусть задан некоторый класс алгоритмов А, и для его описания используется функционально полная система операций F₁, содержащая любые математические операции Многие сложные операции с помощью численных методов могут быть представлены в терминах элементарных операций. Последовательно применяя процедуру такого разложения сложных операций на простые, можно построить новые системы операций F₂, F₃, …, Fр, также функционально полные по отношению к классу алгоритмов А. Системы операций F₁, …, Fр можно упорядочить по сложности входящих в них операций так, чтобы для каждой пары F_i и F_i+1 выполнялось условие: каждая операция ƒ_g из F_i либо входит в F_i+1 либо представляется композицией операций ƒ_h из F_i+1. Упорядоченная последовательность F₁, …, Fр образует иерархию систем операций.

Зависимость показателей эффективности I для иерархии систем операций F₁, …, Fр представлена на рис. 2.64. Кривая С_ПР характеризует затраты оборудования ВМ в зависимости от состава операций F_t (I = 1, …, р). Поскольку операции в F_i+1 менее сложны, чем операции в F_i, то затраты С_ПРi+1 процессора, реализующего F_i+1, будут меньше затрат С_ПР процессора, реализующего F_i, то есть иерархия систем операций F₁, …, Fр соответствует иерархии процессоров с аппаратными затратами C_ПР1 > C_ПР2 > … > C_ПРp

Рис. 2.64. Показатели эффективности иерархии систем операций

Затратам памяти на рис. 2.64 соответствует кривая С_ЗУ. Она показывает, что если кодированию алгоритма в терминах операций F_i+1 адекватны затраты памяти С_ЗУ, то использование более простых операций F₁, …, Fр приводит к увеличению количества команд в программе и С_{ЗУ i+1}. > С_ЗУ, то есть иерархия систем операций F_u F_p имеет следствием иерархию затрат памяти С_ЗУ1 < С_ЗУ2 < ... < С_{ЗУ р}. Характер изменения суммарных затрат оборудования С = С_ПР + С_ЗУ представлен кривой С. Видно, что существует система операций F_т которой соответствуют минимальные затраты оборудования С. Система операций F_m занимает промежуточное положение между наиболее сложной F₁ и наименее сложной F_p системами операций. Наконец, кривая Т демонстрирует, что время выполнения алгоритмов возрастает от минимального значения Т₁ (при наиболее сложной СО F₁) до максимального значения Т_р (при наименее сложной СО F_p).

Таким образом, снижение сложности операций в иерархии F₁, …, Fр вызывает:

· уменьшение аппаратных затрат в процессоре;

· увеличение затрат памяти для хранения программ;

· увеличение времени реализации алгоритмов (убавление производительности ВМ).

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

Выбор системы операций

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

· На основе существующих аналогов, применяемых для решения задач данного класса.

· На основе статистики использования отдельных команд в «старых» вычислительных машинах. Подобная статистика уже заложена во многие общепризнанные контрольно-оценочные тесты, такие, например, как смесь Гибсона или SPEC.

· С ориентацией на языки программирования высокого уровня. Выбор системы операций направлен на реализацию типовых операторов языков программирования. Подобные попытки можно встретить в вычислительных машинах фирм Wang, Hewlett-Packard, Tektronix, IBM.

· На основе формализации и систематизации. Сущность этого метода поясняет рис. 2.65.

Рис. 2.65. Метод формализации и систематизации