|
||
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). При расширении/^ из-за невыполнения ограничение Т= 7дОП (ИЛи из-за необходимости улучшить функциональные возможности СО] в набор включается операция, обеспечивающая максимальное уменьшение времени Г (максимальное уменьшение показателя 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. Чем в формате с фиксированной запятой заполняются избыточные старшие разряды?
|
||
|
||