116 Глава 2. Архитектура системы команд
Из приведенных данных следует, что в среднем 75% переходов происходит в на­правлении увеличения адреса. Из переходов в сторону уменьшения адреса около 90% связаны с выполнением циклов.
Система операций
Системой операций называется список операций, непосредственно выполняемых техническими средствами вычислительной машины. Система операций ВМ опре-
Форматы команд 117
деляется областью ее применения, требованиями к стоимости, производительнос­ти и точности вычислений.
Связь системы операций с алгоритмами решаемых задач проявляется в степе­ни ее приспособленности для записи программ реализации этих алгоритмов. Сте­пень приспособленности характеризуется близостью списка операций системы команд и операций, используемых на каждом шаге выполнения алгоритмов. Про­стоту программирования алгоритма часто определяют термином «программируе-мость вычислительной машины». Чем меньше команд требуется для составления программы реализации какого-либо алгоритма, тем программируемость выше. В архитектурах типа CISC улучшения Программируемо добиваются введени­ем в систему операций большого количества операций, в том числе и достаточно сложных. Это может приводить и к повышению производительности ВМ, хотя в любом случае увеличивает аппаратурные затраты.
Обоснованный выбор системы операций (СО) возможен лишь исходя из ана­лиза подлежащих реализации алгоритмов. Для этого определяется частотный век­тор используемых в алгоритме операторов (q1 ..., q„). Изучив вектор, составляют список основных, наиболее часто встречающихся операторов. Операторы основ­ного списка реализуются системой машинных операций ВМ (каждому оператору сопоставляется своя машинная операция). Остальные операторы получают путем их разложения на операторы основного списка.
Показатели эффективности системы операций
Качество системы операций можно характеризовать двумя свойствами: функцио­нальной полнотой и эффективностью.
Функциональная полнота — это достаточность системы операций для описания любых алгоритмов. Системы операций ВМ включают в себя большое количество машинных операций и практически всегда являются функционально полными.
Эффективность системы операций показывает степень соответствия СО задан­ному классу алгоритмов и требованиям к производительности ВМ. Количествен­но эффективность характеризуется затратами оборудования, затратами времени на реализацию алгоритмов и вероятностью правильного выполнения программ.
Затраты оборудования С можно описать выражением
где Спр затраты в процессоре на реализацию системы операций, Сзузатраты памяти на размещение данных и программ, представляющих алгоритм в терминах заданной системы операций.
Величина СПрпропорциональна количеству и сложности машинных операций, а СЗУемкости памяти, необходимой для хранения закодированного алгоритма. Усложнение машинных операций приводит к сокращению Количества операций (команд), требуемых для описания алгоритма, и, следовательно, к уменьшению необходимой емкости памяти.
Затраты времени на реализацию алгоритма (Т) пропорциональны количеству команд (операций) в программе. Введение в СО более сложных операций позво­ляет программировать сложные действия одной командой, в результате чего умень­шается количество команд программы.
118 Глава 2. Архитектура системы команд
Вероятность правильного выполнения программ Р определяется подформуле
(2.13)
где /— количество операций в СО; п — количество операций (команд) в програм­мах; лямбда i, тета i — интенсивность отказов и время выполнения операции (команд типа; qtчастота появления операций z'-ro типа в программах; р— вероятность правильного выполнения «^операций z'-ro типа.
В [16] утверждается, что показатель Р оптимален при условии
(2.14) Условие (2.14) можно переписать в ином виде:
(2.15)
Равенство (2.15) позволяет найти оптимальное соотношение параметров лямбда i, при реализации системы операций. Принимая параметры аппаратной реализации ■одной из операций за эталон (*эт> %г)· из (2.15) получим соотношение
(2.16)
позволяющее по известным параметрам для 5 различных вариантов системы опе­раций выбрать лучший. Критерием качества реализации каждой операции для раз­работки 5-го варианта СО является
(2.17)
При выборе одного из нескольких вариантов реализации системы опера­ций критерием качества может служить минимум среднеквадратического от­клонения
(2.18)
Если значения λ, (ΐ - 1,..., /) Неизвестны, то оправдано следующее допущение:
При этом условие (2.15) преобразуется в условие «равного временного учас­тия» операций в программах [28]:
ϊΛ-ί^, 0W = 1, 2, ..., /).                               (2.19)
Форматы команд 119
Условие (2.19) совместно с рассчитанным частотным вектором и известным ограничением на время выполнения программы Тдоп можно применить для вычис­ления оптимальной длительности машинных операций:
(2.20)
■s
Иерархия систем операций
Пусть задан некоторый класс алгоритмов Л, и для его описания используется функ­ционально полная система операций F2 .содержащая любые математические опе­рации (интегрирование, In, d/dt, sin,...). Многие сложные операции с помощью численных мет дов могут быгапредставлены в терминах элементарных операций. Последовательно применяя процедуру такого разложения сложных операций на простые, можно построить новые системы операций F2,,..., Fp, также функционально полные по отношению к классу алгоритмов Л. Системы операций F2 ..., Fp можно упорядо­чить по сложности входящих в них операций так, чтобы для каждой пары F2 и 7^+1 выполнялось условие: каждая операция fR из , либо входит в Fi+ либо представ­ляется композицией операций^ из Fl+1. Упорядоченная последовательность Fj...,Fp образует иерархию систем операций.
Зависимость показателей эффективности /для иерархии систем операций FT,.., Fp представлена на рис. 2.64. Кривая СПР характеризует затраты оборудования ВМ в зависимости от состава операций Ffi = 1, ...,р). Поскольку операции в Fi+ менее сложны, чем операции в Ft до затраты СПр процессора, реализующего JF|+lT будут меньше затрат СПР процессора, реализующего^,το есть иерархия систем опе~
120 Глава 2. Архитектура системы команд
раций Fj ..., Fp соответствует иерархии процессоров с аппаратными затратами
сПР1 1Рг>_>СпРр
Затратам памяти на рис. 2.64 соответствует кривая Сзу. Она показывает, что если кодированию алгоритма в терминах операций Ft адекватны затраты памяти СЗУ;, то использование более простых операций Fi+ приводит к увеличению коли­чества команд в программе и CWi±l > СЗУ, то есть иерархия систем операций Fr, Fp
имеет следствием иерархию затрат памяти С3у < С3у2 < ... < СЗУр. Характер из­менения суммарных затрат оборудования С = СПР + Сзу представлен кривой С. Видно, что существует система операций F„, которой соответствуют минимальные затраты оборудования С. Система операций Fm занимает промежуточное положе­ние между наиболее сложной F, и наименее сложной Fp системами операций. На­конец, кривая Г демонстрирует, что время выполнения алгоритмов возрастает от минимального значения Г, (при наиболее сложной СО ^)до максимального зна­чения Тр (при наименее сложной СО Fp).
Таким образом, снижение сложности операций в иерархии Fp..., Fp вызывает:
•   уменьшение аппаратных затрат в процессоре;
•   увеличение затрат памяти для хранения программ;
•   увеличение времени реализации алгоритмов (убавление производительности ВМ).
Последний вывод можно считать справедливым лишь для архитектур типа CISC. По отношению к RISC-архитектурам, где сокращение системы операций сопровождается коренными изменениями в других аспектах АСК, подобное ут­верждение представляется весьма спорным.
Выбор системы операций
Выбор оптимальной системы операций является сложной задачей. Основные труд­ности в ее решении связаны с установлением точной функциональной зависимос­ти показателей эффективности С, Т, Рот.состава СО. Поэтому найти чисто фор­мальный метод выбора оптимальной СО пока не удается, а существующие подходы к ее решению основываются на комбинации формальных и эвристических при­емов. Используемые в настоящее время методы разработки системы команд мож­но классифицировать следующим образом:
•   На основе существующих аналогов, применяемых для решения задач данного класса.
•   На основе статистики использования отдельных команд в «старых» вычисли­тельных машинах. Подобная статистика уже заложена во многие общепризнан­ные контрольно-оценочные тесты, такие, например, как смесь Гибсона или SPEC.
•   Сориентацией на языки программирования высокого уровня. Выбор системы операций направлен на реализацию типовых операторов языков программиро­вания. Подобные попытки можно встретить в вычислительных машинах фирм Wang, Hewlett-Packard, Tektronix, IBM.
•   На основе формализации и систематизации. Сущность этого метода поясняет рис. 2.65.
Форматы команд 1_2_1
Форматы команд 121
Рис. 2.65. Метод формализации и систематизации
•  На базе метода группировки. Для упрощения декодирования и повышения про-
изводительности все операции группируются (арифметические, логические, передачи управления и т. д.). Выбор состава операций во многом зависит от принципа группировки и возможности извлечения из нее реальных выгод.
•   На основе восходящей совместимости в рамках семейства вычислительных машин. Новая система операций должна быть надмножеством старой системы, причем пересечение множеств должно быть существенным.
•   Опираясь на требования пользователя.
•  На основе метода условной интерпретации. С учетом соотношения «стоимость/
производительность» определенные команды реализуются аппаратно или мик­ропрограммно. Как интерпретация команд, так и метод их реализации выбира­ются из условий полезности данных команд, стоимости и производительности. В качестве примеров рассмотрим два способа решения задачи выбора оптималь­ной системы операций, соответствующие упомянутым выше принципам. Выбор системы операций на основе существующих аналогов
Заданы алгоритмы А. Необходимо выбрать функционально полную систему опе­раций, удовлетворяющую ограничениям на время реализации 'алгоритмов А (Г=дОП), и аппаратную сложность ВМ (С = CmJ.
Сначала определяется множество ВМ-аналогов, успешно применяемых для выполнения алгоритмов, близких к заданным [17], для которого составляются пол-. ный Fn базовый FB наборы операций. Полный набор операций F { f2...,fn} явля-
к ется объединением систем операций всех машин-аналогов, то есть ^объединение
Ft от 1 до к, где к — количество аналогов. В него могут быть включены дополнительные one] наличие которых необходимо по тем или иным соображениям. Базовый набор = if и/2···»/исключает в себя только те операции набора F, которые реализова­ны в большинстве аналогов, то есть здесь т<п. Полный набор ^соответствует максимально возможной системе операций, а базовый набор FEминимально не­обходимой СО.
Поиск «оптимальной» СО осуществляется в интервале от FE до F. В качестве начального приближения выбирается набор FE. Производится оценочный расчет реализуемости СО в пределах заданных ограничений (Гдоп, Сдоп), функциональ­ных возможностей и функциональной независимости системы операций.
122 Глава 2. Архитектура системы команд
Требуемая длительность τ,- операций определяется исходя из Тлоп п0 формуле (2.20). Поиск оптимального варианта реализации каждой из операций осуществ-ляется по критерию ιηίηΔ,. = min|x/ - τ;|, где τ, - реальная длитеЛьность опера-ции, а для всего множества операций — по критерию минимума среднеквадрати-ческого отклонения
где S— множество рассматриваемых вариантов реализации СО.
Далее проверяется выполнение заданных ограничений (Хдош Сдоп)· При их выполнении набор FE пополняется операцией из г (для улучшения функциональ­ных возможностей СО), в противном случае — сокращается. Выбор операций для корректировки FE осуществляется следующим образом. Если принять, что полный набор ^обеспечивает эффективную реализацию алгоритмов, то функциональные возможности FB можно оценивать длиной D программы из набора операций FE,
интерпретирующей операции из набора F, не попавшие в FE (операции набора F-F-FB).
Функциональная независимость операции F^ оценивается количеством опера­ций или шагов ^ программы описания каждой,из операции-'' ^Е '^Г ""' через другие операции этого набора (*в-/<) (*~1ι 2..... m). Показатели
(г ~ * * "*' mf образуют вектор с длиной т. При сокращений из-за невы­полнения ограничения' ^ ™ Чдоп >из набора исключается операция, которая наибо­лее просто выражается через другие операции ^ (имеет минимальное значение Cyj), что приводит к минимальным потерям производительности (минимальному
увеличению D). При расширении/^ из-за невыполнения ограничение Т= ОП (ИЛи из-за необходимости улучшить функциональные возможности СО] в набор вклю­чается операция, обеспечивающая максимальное уменьшение времени Г (макси­мальное уменьшение показателя D). Если таких операций в наборе Fнесколько, то
......          J·                                                                                   ...                                                                         .                      *-т                                                                  ....
из них выоирается операция с наименьшим значением так как ее реализация требует минимальных аппаратных затрат.
Описанная последовательность действий повторяется многократно до получе­ния системы операций, удовлетворяющей заданным ограничениям. Выбор системы операций на основе структурирования алгоритмов
Метод структурирования алгоритмов предполагает следующую формулировку задачи выбора системы операций: необходимо выбрать такую систему F„, которая обеспечивает реализацию алгоритма А за заданное время Т= доп при минималь­ной стоимости ВМ.
Иерархия операций Flt..., Fp, функционально полных для алгоритма А, может быть определена процедурой структурирования [22], сводящейся к следующему. Алгоритм А рассматривается как один оператор, реализующий операцию/Ί над исходными данными с целью получения требуемых результатов, то есть Fx = {/J. Затем оператор разделяется на части — программируется последовательностью более простых операторов. Последовательное применение процедуры структури­рования (разделения оператора на более простые операторы) позволяет выявить
Контрольные вопросы - 123
системы операций F, - {/,}, F2 - {f2,f3}, F3 ~ ifsJvfs), F4 - {UUUfi}, -, и тем са­мым построить иерархию операций Ftt.... Fp.
Для каждой операции в Fs можно определить количество и^ее выполнений при одной реализации алгоритма. Тогда сумма
(2.21)
будет представлять количество операций, выполняемых при одной реализации алгоритма, запрограммированного в терминах Ft. Характеристики элементной базы позволяют задать приближенное значение средней длительности т., операции в ВМ. С учетом этого время выполнения алгоритма на основе Fi составит Т.= τ , что дает
возможность поставить в соответствие иерархии систем операций F.....Fp затраты
времени на реализацию алгоритма Т,..., Тр, причем Т, < ... < Тр. Можно предполо­жить, что минимум аппаратных затрат достигается при F„ принадлежит {Fr.., Fp}, обеспечит ющей время реализации алгоритма Тп, максимально близкое к заданному значе­нию Удоп- В силу сказанного, выбор системы операций сводится к нахождению такой системы F„, для которой разность (Гдоп - Г„) имеет минимальное положи­тельное значение.
Контрольные вопросы
1.   Какие характеристики вычислительной машины охватывает понятие «архитек­тура системы команд»?
2.   Охарактеризуйте эволюцию архитектур системы команд вычислительных ма­шин.
3.   В чем состоит проблема семантического разрыва?
4.   Поясните различия в подходах по преодолению семантического разрыва, при­меняемых в ВМ с CISC- и RISC-архитектурами.
5.   Какая форма записи математических выражений наиболее соответствует сте­ковой архитектуре системы команд и почему?
6.   Какие средства используются для ускорения доступа к вершине стека в ВМ со стековой архитектурой?
7.   Чем обусловлено возрождение интереса к стековой архитектуре?
8.   Какие особенности аккумуляторной архитектуры можно считать ее достоин­ствами и недостатками?
9. Какие доводы можно привести за и против увеличения числа регистров общего
назначения в ВМ с регистровой архитектурой системы команд?
10.   Почему для ВМ с RISC-архитектурой наиболее подходящей представляется АСК с выделенным доступом к памяти?
11.  Какую позицию запятой в формате с фиксированной запятой можно считать общепринятой?
12.   Чем в формате с фиксированной запятой заполняются избыточные старшие разряды?
Hosted by uCoz