Операции с десятичными числами

Десятичные числа представляются в ВМ в двоично-кодированной форме. В вычи­слительных машинах первых поколений для обработки таких чисел предусматрива­лись специальные команды, обеспечивавшие выполнение основных арифметиче­ских операций (сложение, вычитание, умножение и деление). В АСК современных машин подобных команд обычно нет, а соответствующие вычисления имитируют­ся с помощью команд целочисленной арифметики.

Simd-команды

Название данного типа команд представляет собой аббревиатуру от Single Instruc­tion Multiple Data — буквально «одна инструкция — много данных». В отличие от обычных команд, оперирующих двумя числами, SIMD-команды обрабатывают сразу две группы чисел (в принципе их можно называть групповыми командами). Операнды таких команд обычно представлены в одном из упакованных форматов.

Идея SIMD-обработки была выдвинута в Институте точной механики и вы­числительной техники им. С. А. Лебедева в 1978 году в рамках проекта «Эльбрус-1». С 1992 года команды типа SIMD становятся неотъемлемым элементом АСК мик­ропроцессоров фирм Intel и AMD. Поводом послужило широкое распространение мультимедийных приложений. Видео, трехмерная графика и звук в ВМ представ­ляются большими массивами данных, элементы которых чаще всего обрабатыва­ются идентично. Так, при сжатии видео и преобразовании его в формат MPEG один и тот же алгоритм применяется к тысячам битов данных. В трехмерной гра­фике часто встречаются операции, которые можно выполнить за один такт: интер­полирование и нормировка векторов, вычисление скалярного произведения век­торов, интерполяция компонентов цвета и т. д. Включение SIMD-команд в АСК позволяет существенно ускорить подобные вычисления.

Первой на мультимедийный бум отреагировала фирма Intel, добавив в систему команд своего микропроцессора Pentium ММХ 57 SIMD-команд. Название ММХ (MultiMedia eXtention — мультимедийное расширение) разработчики обосновы-

Типы команд 91

вали тем, что при выборе состава новых команд были проанализированы алгоритмы, применяемые в различных мультимедийных приложениях. Команды ММХ спечивали параллельную обработку упакованных целых чисел. При выполнении арифметических операций каждое из чисел, входящих в группу, рассматриваются как самостоятельное, без связи с соседними числами. Учитывая специфику обрабатываемой информации, команды ММХ реализуют так называемую арифметику с насыщением: если в результате сложения образуется число, выходящее в пределы отведенных под него позиций, оно заменяется наибольшим двоичным числом, которое в эти позиции вмещается. На рис. 2.33 показано сложение двух групп четырехразрядных целых чисел, упакованных в 32-разрядные слова.

Рис. 2.33. Сложение с насыщением упакованных целых чисел

Следующим шагом стало создание новых наборов SIMD-команд, работающих также с операндами, представленными в виде упакованных чисел с плавающей запятой. Такие команды в соответствующих приложениях повышают производи­тельность процессора примерно вдвое. Первой подобную технологию в середине 1998 года предложила фирма AMD в микропроцессоре К6-2. Это мультимедий­ное расширение включало в себя 21 SIMD-команду и получило название SDNowL Расширение SDNow! в дополнение к SIMD-обработке целочисленной информа­ции типа ММХ позволяло оперировать парой упакованных чисел в формате с пла­вающей запятой.

Полугодом позже фирма Intel ввела в свои микропроцессоры так называемые потоковые SIMD-команды, обозначив их аббревиатурой SSE — Streaming SIMD Extension (потоковая обработка по принципу «одна команда — много данных»). Сначала это были 70 команд в микропроцессоре Pentium III. Команды дополняли групповые целочисленные операции ММХ и расширяли их за счет групповых опе­раций с 32-разрядными вещественными числами.

В зависимости от типа чисел (целые или вещественные) команды SSE делятся на три категории:

* работа с упакованными группами целых чисел, которые могут иметь размер байта, слова, двойного слова или квадрослова (количество чисел в группе зави­сит от их разрядности и от разрядности всей группы — 64 или 128);

* оперирование одной парой 32-разрядных или 64-разрядных чисел с плаваю­щей запятой (обычная или двойная точность);

92

* обработка четырех пар вещественных чисел обычной точности или двух пар вещественных чисел двойной точности.

Дальнейшее развитие технологии SSE вылилось в SSE2 и получило реализа­цию в Pentium 4. Этот вариант включает в себя 271 команду и позволяет выпол­нять групповые арифметические и логические операции, сдвиги, сравнения чисел перегруппировку и извлечение отдельных чисел, различные варианты пересылок' За один такт обрабатываются четыре 32-разрядных числа с плавающей запятой упакованных в 128-разрядное слово.

Новый импульс получила и технология SDNow!, более совершенный вариант которой получил название Enhanced SDNow!. Этот набор команд близок к SSE2.

Таблица 2.15 дает представление о том, какие из рассмотренных мультимедий­ных расширений поддерживаются наиболее популярными микропроцессорами класса Pentium.

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

	MMX	SDNow!	SSE	SSE2
VIAC3	Да	Да	Нет	Нет
Celeron-2, Pentium HI	Да	Нет	Да	Нет
Pentium 4	Да	Нет	Да	Да
Duron	Да	Да	Да	Нет
Athlon XP	Да	Да	Да	Нет

Еще один вариант архитектуры системы команд с SIMD-командами воплощен фирмой IBM в процессорах серии PowerPC. Эта реализация носит название AltiVec и во многих отношениях превосходит вышеупомянутые расширения АСК. В част­ности, имеются трехоперандные команды, допускаются нестандартные целочис­ленные форматы, например «упаковка» из 1+5 + 5 + 5 битов.

Команды для работы со строками

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

Команды преобразования

Команды преобразования осуществляют изменение формата представления дан­ных. Примером может служить преобразование из десятичной системы счисления в двоичную или перевод 8-разрядного кода символа из кодировки ASCII в коди­ровку EBCDIC, и наоборот.

Команды ввода/вывода

Команды этой группы могут быть подразделены на команды управления периферийным устройством (ПУ), проверки его состояния, ввода и вывода.

Команды управления периферийным устройством служат для запуска ПУ и yказания ему требуемого действия. Например, накопителю на магнитной ленте может

93

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

Собственно обмен информацией с ПУ обеспечивают команды ввода и вывода. Команды ввода предписывают модулю В/ВЫВ получить элемент данных (байт ми слово) от ПУ и поместить его на шину данных, а команды вывода — заставля­ют модуль В/ВЫВ принять элемент данных с шины данных и переслать его на ПУ.

Команды управления системой

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

Команды управления потоком команд

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

В системе команд ВМ можно выделить три типа команд, способных изменить последовательность вычислений

безусловные переходы;

условные переходы (ветвления);

вызовы процедур и возвраты из процедур.

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

Согласно приведенным данным, среди команд рассматриваемой группы доминируют условные переходы.

Несмотря на то что присутствие в программе большого числа команд безусловного перехода считается признаком плохого стиля программирования, такие

94

Рис. 2.34. Частота использования команд управления потоком команд

команды обязательно входят в АСК любой ВМ. Для их обозначения в языке ассемблера обычно используется английское слово jump (прыжок). Команда безусловного перехода обеспечивает переход по заданному адресу без проверки каких-либо условий.

Условный переход происходит только при соблюдении определенного условия, в противном случае выполняется следующая по порядку команда программы. Боль­шинство производителей ВМ в своих ассемблерах обозначают подобные команды словом branch (ветвление). Статистика случаев, когда переход имеет место, приве­дена на рис. 2.35.

Рис. 2.35. Частота выполнения условия перехода

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

В системе команд ВМ для каждого признака результата предусматривается своя команда ветвления (иногда — две: переход при наличии признака и переход при его отсутствии). Большая часть условных переходов связана с проверкой взаим­ного соотношения двух величин или с равенством (неравенством) некоторой ве­личины нулю. Последний вид проверок используется в программах наиболее ин­тенсивно, о чем свидетельствуют статистические данные, приведенные на рис. 2.36. На верхней диаграмме показаны частоты употребления разных видов условий для программ GCC, Spice и ТеХ, выполнявшихся на ВМ MIPS 2000. Нижняя диаг­рамма дает представление о результатах, полученных для двух тестовых смесей

95

Рис. 2.36. Средняя частота использования различных условий перехода в командах ветвления

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

Помимо приведенных на рис. 2.36 данных необходимо отметить, что по резуль­татам тех же исследований доля команд, где проверяются простые условия (= или <>), составляет в среднем 50%. Кроме того, в качестве одного из операндов в ко­мандах, вычисляющих результат сравнения, как правило, выступает константа. Доля таких команд для уже упоминавшихся программ составляет: GCC — 84%, Spice-92%, ТеХ-83%.

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

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

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

96

ложенную за командой вызова. Такой режим предполагает наличие средств для сохранения текущего состояния содержимого счетчика команд в момент вызова (запоминание адреса точки возврата) и его восстановления при выходе из процедуры.

Форматы команд

Типовая команда, в общем случае, должна указывать: подлежащую выполнению операцию;

адреса исходных данных (операндов), над которыми выполняется операция; адрес, по которому должен быть помещен результат операции.

В соответствии с этим команда состоит из двух частей: операционной и адрес­ной,(рис. 2.37).

Операционная часть

Адресная часть

Рис. 2.37. Структура команды

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

- общее число различных команд;

- общую длину команды;

- тип полей команды (фиксированной или переменной длины) и их длина;

- простоту декодирования;

- адресуемость и способы адресации;

- стоимость оборудования для декодирования и исполнения команд.

Длина команды

Это важнейшее обстоятельство, влияющее на организацию и емкость памяти, струк­туру шин, сложность и быстродействие ЦП. С одной стороны, удобно иметь в рас­поряжении мощный набор команд, то есть как можно больше кодов операций, опе­рандов, способов адресации, и максимальное адресное пространство. Однако все это требует выделения большего количества разрядов под каждое поле команды» что приводит к увеличению ее длины. Вместе с тем, для ускорения выборки из памяти желательно, чтобы команда была как можно короче, а ее длина была равна или кратна ширине шины данных. Для упрощения аппаратуры и повышения быс­тродействия ВМ длину команды обычно выбирают кратной байту, поскольку в большинстве ВМ основная память организована в виде 8-битовых ячеек. В рамках системы команд одной ВМ могут использоваться разные форматы команд. Обычно это связано с применением различных способов адресации. В таком случае в состав кода команды вводится поле для задания способа адресации (СА), и обобщенный формат команды приобретает вид, показанный на рис. 2.38.

Коп

СА

Адресная часть

Рис. 2.38. Обобщенный формат команды

Общая длина команды R_k может быть описана следующим соотношением:

(2.1)

l-количество адресов в команде; - количество разрядов для записиi-ro ^; -разрядность поля кода операции;R_СА - разрядность поля способа адресации

В большинстве ВМ одновременно уживаются несколько различных форматов команд.

Разрядность полей команды

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

Разрядность поля кода операции

Количество двоичных разрядов, отводимых под код операции, выбирается так, чтобы можно было представить любую из операций. Если система команд предпо­лагает Nкон, различных операций, то минимальная разрядность поля кода опера­ции R_КОп определяется следующим образом:

где int означает округление в большую сторону до целого числа.

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

Разрядность адресной части

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

98

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

Разрядности полей R_Аi и R_СА рассчитываются по формулам:

2.3

2.4

где N _i — количество ячеек памяти, к которому можно обратиться с помощью i-г₀ адреса; N_CA — количество способов адресации (int означает округление в большую сторону до целого числа).

Количество адресов в команде

Для определения количества адресов, включаемых в адресную часть, будем исполь­зовать термин адресность. В «максимальном» варианте необходимо указать три компонента: адрес первого операнда, адрес второго операнда и адрес ячейки, куда заносится результат операции. В принципе может быть добавлен еще один адрес, указывающий место хранения следующей инструкции. В итоге имеет место четы­рехадресный формат команды (рис. 2.39). Такой формат поддерживался в ВМ EDVAC, разработанной в 1940-х годах [116].

Операция	Адреса
Код операции	1-й операнд	2-й операнд	Результат	Следующая команда

Рис. 2.39. Четырехадресный формат команды

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

Операция	Адреса
Код операции	1-й операнд	2-й операнд	результат

Рис. 2.40. Трехадресный формат команды

К сожалению, и в трехадресном формате длина команды может оказаться весьма большой. Так, если адрес ячейки основной памяти имеет длину 32 бита, а длина кода операции — 8 бит, то длина команды составит 104 бита (13 байт).

99

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

Операция	Адреса
Код операции	1-й операнд	2-й операнд / результат

Рис. 2.41. Двухадресный формат команды

Команду можно еще более сократить, перейдя к одноадресному формату (рис 2.42), что возможно при выделении определенного стандартного места для хранения первого операнда и результата. Обычно для этой цели используется спе­циальный регистр центрального процессора (ЦП), известный под названием ак­кумулятора, поскольку здесь аккумулируется результат.

Операция	Адрес
Код операции	1-й или 2-й операнд

Рис. 2.42. Одноадресный формат команды

Применение единственного регистра для хранения одного из операндов и ре­зультата является ограничивающим фактором, поэтому помимо аккумулятора ча­сто используют и другие регистры ЦП. Так как число регистров в ЦП невелико, для указания одного из них в команде достаточно иметь сравнительно короткое адресное поле. Соответствующий формат носит название полутораадресного или регистрового формата (рис. 2.43).

Операция	Адреса
Код операции	Регистр	2-й операнд

Рис. 2.43. Полутораадресный формат команды

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

Рис. 2.44. Нульадресный формат команды

100

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

Выбор адресности команд

При выборе количества адресов в адресной части команды обычно руководству ются следующими критериями:

* емкостью запоминающего устройства, требуемой для хранения программы' - временем выполнения программы;

* эффективностью использования ячеек памяти при хранении программы.

Для оценки влияния адресности на каждый из перечисленных элементов вос­пользуемся методикой и выводами, изложенными в [25].

Адресность и емкость запоминающего устройства

Емкость запоминающего устройства для хранения программы Е_А можно оценить из соотношения

где N_A — количество программ в программе; R_K — разрядность команды, опреде­ляемая в соответствии с формулой (2.1); А — индекс, указывающий адресность команд программы. С этих позиций оптимальная адресность команды определяется путем решения уравнения при условии, что найденное значение обес­печивает минимум Е_А. В [29] показано, что в среднем Е_А монотонно возрастает с увеличением А. Таким образом, при выборе количества адресов по критерию «ем­кость ЗУ» предпочтение следует отдавать одноадресным командам.

Адресность и время выполнения программы

Время выполнения одной команды складывается из времени выполнения опера­ции и времени обращения к памяти.

Для трехадресной команды последнее суммируется из четырех составляющих времени:

выборки команды;

выборки первого операнда;

выборки второго операнда;

записи в память результата.

Одноадресная команда требует двух обращений к памяти:

выборки команды;

выборки операнда.

Как видно, на выполнение одноадресной команды затрачивается меньше вр^е мени, чем на обработку трехадресной команды, однако для реализации одной трехадресной команды, как правило, нужно три одноадресных. Этих соображений тем

101

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

В самой общей постановке задачи время выполнения алгоритма Т_А можно определить выражением

(2.5)

в котором N _а — количество арифметических и логических команд в программе; -время выполнения одной арифметической или логической команды;N —количество неарифметических команд; - время выполнения одной неариф­метической команды;А = (1, 2, 3} - индекс, определяющий количество адресов в команде. В свою очередь, N_{l можно определить как А^г_п = N _y + n_ba, где N _y - коли­чество команд передачи управления (их число в программе не зависит от адресно­сти) а N_ва — количество вспомогательных команд пересылок данных в регистр сумматора и из него.

Время выполнения как арифметической (т_а)), так и неарифметической (т_п/1) команды складывается из времени выборки команды из памяти Т₀ (т₀ — время, за­трачиваемое на одно обращение к памяти) и времени считывания/записи данных Ат₀. В случае арифметической команды следует учесть также вклад на исполнение арифметической операции т_а. Таким образом, имеем:

и выражение (2.5) принимает вид:

(2.8)

Подставляя в (2.8) значения А = 1 и А = 3, можно определить разность времени Т реализации алгоритма с помощью одноадресных и трехадресных команд, при­нимая во внимание, что для трехадресных команд

(2.9)

Теперь проанализируем «выгодность» той или иной адресности команды в за­висимости от типа целевого алгоритма. Возможные типы алгоритмов условно разделим на три группы:

• последовательные;

• параллельные;

• комбинированные.

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

102

как

согласно выражению (2.9), составит

выигрыш во времени для подобного алгоритма

где N_v — количество команд передачи управления. Таким образом, в последовательных алгоритмах чем больше N_a , тем выгоднее оказываются одноадресен команды.

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

и выигрыш по времени определяется как

(2.11)

где N — количество операций передачи управления. Таким образом, при N_a > N_y} целесообразно ориентироваться на трехадресные команды.

В комбинированном алгоритме вычислительный процесс образуют как после­довательные, так и параллельные части, при этом

и выигрыш во времени с учетом (2.10) и (2.11) можно оценить как

(2.12)

где Ny = Ny + N_v — количество команд передачи управления в обеих частях ал­горитма.

Из (2.12) следует, что при N_a + N_y > 2 + N_a предпочтение следует отдать одноадресным командам.

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