Использование отклонения частного показателя от максимального. 10 страница

 

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

 

При индексной адресации (ИА) подполе А_С содержит адрес ячейки памяти, а регистр (указанный явно или неявно) — смещение относительно этого адреса. Как видно, этот способ адресации похож на базовую регистровую адресацию. Поскольку при индексной адресации в поле А_С находится полноразрядный адрес ячейки памяти, играющий роль базы, длина этого поля больше, чем при базовой регистровой адресации. Тем не менее вычисление исполнительного адреса операнда производится идентично (рис. 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. Метод формализации и систематизации

 

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

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

· Опираясь на требования пользователя.

· На основе метода условной интерпретации. С учетом соотношения «стоимость/производительность» определенные команды реализуются аппаратно или микропрограммно. Как интерпретация команд, так и метод их реализации выбираются из условий полезности данных команд, стоимости и производительности.

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

 

Выбор системы операций на основе существующих аналогов

 

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

Сначала определяется множество ВМ-аналогов, успешно применяемых для выполнения алгоритмов, близких к заданным [17], для которого составляются полный F и базовый F _Б наборы операций. Полный набор операций F= {ƒ₁, ƒ₂,..., ƒ_n } является объединением систем операций всех машин-аналогов, то есть , где k — количество аналогов. В него могут быть включены дополнительные операции, наличие которых необходимо по тем или иным соображениям. Базовый набор F_Б= {ƒ₁, ƒ₂,..., ƒ_m } включает в себя только те операции набора F, которые реализованы в большинстве аналогов, то есть здесь т<п. Полный набор F соответствует максимально возможной системе операций, а базовый набор F_Б — минимально необходимой СО.

Поиск «оптимальной» СО осуществляется в интервале от F_Б до F. В качестве начального приближения выбирается набор F_Б. Производится оценочный расчет реализуемости СО в пределах заданных ограничений (Т _доп, С _доп), функциональных возможностей и функциональной независимости системы операций.

Требуемая длительность τ_i^T операций определяется исходя из T_ДОП по формуле (2.20). Поиск оптимального варианта реализации каждой из операций осуществляется по критерию где τ_i, — реальная длительность операции, а для всего множества операций — по критерию минимума среднеквадратического отклонения

(2.18)

где S — множество рассматриваемых вариантов реализации СО.

Далее проверяется выполнение заданных ограничений (T _ДОП, С _ДОП). При их выполнении набор F_Б пополняется операцией из F (для улучшения функциональных возможностей СО), в противном случае — сокращается. Выбор операций для корректировки F_Б осуществляется следующим образом. Если принять, что полный набор F обеспечивает эффективную реализацию алгоритмов, то функциональные возможности F_Б можно оценивать длиной D программы из набора операций F_Б, интерпретирующей операции из набора F, не попавшие в F_Б (операции набора F = F- F_Б).

Функциональная независимость операций F_Б оценивается количеством операций или шагов Cƒ_i программы описания каждой из операций ƒ_i F_Б(i=1, 2, …, m) через другие операции этого набора (F_Б–ƒ_i)(i=1, 2, …, m). Показатели Cƒ_i(i=1, 2, …, m) образуют вектор с длиной т. При сокращении F_Б из-за невыполнения ограничения С= С _ДОП из набора исключается операция, которая наиболее просто выражается через другие операции F_Б (имеет минимальное значение Cƒ_i), что приводит к минимальным потерям производительности (минимальному увеличению D). При расширении F_Б из-за невыполнения ограничения Т = Т _ДОП (или из-за необходимости улучшить функциональные возможности СО) в набор включается операция, обеспечивающая максимальное уменьшение времени Т (максимальное уменьшение показателя D). Если таких операций в наборе F несколько, то из них выбирается операция с наименьшим значением Cƒ_i так как ее реализация требует минимальных аппаратных затрат.

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

 

Выбор системы операций на основе структурирования алгоритмов

 

Метод структурирования алгоритмов предполагает следующую формулировку задачи выбора системы операций: необходимо выбрать такую систему F_n, которая обеспечивает реализацию алгоритма А за заданное время Т= Т_ДОП при минимальной стоимости ВМ.

Иерархия операций F ₁, …, F_р, функционально полных для алгоритма А, может быть определена процедурой структурирования [22], сводящейся к следующему. Алгоритм А рассматривается как один оператор, реализующий операцию ƒ_i, над исходными данными с целью получения требуемых результатов, то есть F_i = {ƒ_i}. Затем оператор разделяется на части — программируется последовательностью более простых операторов. Последовательное применение процедуры структурирования (разделения оператора на более простые операторы) позволяет выявить системы операций , …, и тем самым построить иерархию операций F ₁, …, F_р.

Для каждой операции в F ₁ можно определить количество n_g,ее выполнений при одной реализации алгоритма. Тогда сумма

(2.21)

будет представлять количество операций, выполняемых при одной реализации алгоритма, запрограммированного в терминах F_i, Характеристики элементной базы позволяют задать приближенное значение средней длительности τ_i операции в ВМ. С учетом этого время выполнения алгоритма на основе F_i, составит Т_i = τ_iN_i, что дает возможность поставить в соответствие иерархии систем операций F ₁, …, F_р затраты времени на реализацию алгоритма T ₁, …, T_р, причем T ₁ <... < Т_р. Можно предположить, что минимум аппаратных затрат достигается при F_n { F ₁, …, F_р }, обеспечивающей время реализации алгоритма T_n максимально близкое к заданному значению T_ДОП. В силу сказанного, выбор системы операций сводится к нахождению такой системы F_n, для которой разность (T_ДОП - T_n) имеет минимальное положительное значение.

 

Контрольные вопросы

 

1. Какие характеристики вычислительной машины охватывает понятие «архитектура системы команд»?

2. Охарактеризуйте эволюцию архитектур системы команд вычислительных машин.

3. В чем состоит проблема семантического разрыва?

4. Поясните различия в подходах по преодолению семантического разрыва, применяемых в ВМ с CISC- и RISC-архитектурами.