Более подробно обсуждать этот вопрос не имеет смысла, так как возможности машин в плане распЕфаплеливания вычислений на уровне команд существенно различаются. Например, процессор ШМ RS/6000, созданный в 1992 году, имеет трехвходовой сумматор и может параллельно выполнять две следующие друг за другом команды сложения, даже если одна из них использует результаты другой команды (например, когда команда сложения использует результат команды сравнения или основной регистр команды загрузки). В качестве обратного примера можно рассмотреть простейший дешевый встраиваемый в различные системы компьютер, у которого регистр ввода-вывода имеет только один порт для чтения Естественно, что такой машине для вьшолнения команды с двумя операндами-источниками потребуется дополнительный такт для повторного чтения регистра ввода-вывода. Однако если команда выдает операнд для команды, непосредственно следующей за ней, то этот операнд оказывается доступным и без чтения регистра ввода-вывода. На машинах такого типа возможно ускорение работы, если каждая команда предоставляет данные для следующй! команды, т.е. если параллелизмы в коде отсутствуют.

ГЛАВА 2 ОСНОВЫ

2.1. Манипуляции с младшими битами

Многае из приведенных в этом разделе формул используются в следующих главах. Для того чтобы обнулить крайний справа единичный бит {тпрямер, 01011000 => 01010000), используется формула

ж&(ж-1).

Эту формулу можно применять для проверки того, является ли беззнаковое целое степенью 2 (путем проверки результата вычислений на равенство 0).

Для проверки того, имеет ли беззнаковое целое число вид 2-1, можно воспользоваться следующей формулой:

х&{х+1).

Чтобы выделить в слове крайний справа единичный бит (например, 01011000 => 00СЮ10ОО, если такого бита нет, возвращает 0), используется формула

х&{-х).

Чтобы выделить в слове крайний справа нулевой бит (например, 10100111 => 00СЮ1000, если такого бита нет, возвращает 0), используется формула

-&{х + 1).

Для создания маски, идентифицирующей заверщающие нулевые биты, можно воспользоваться одной из приведенных ниже формул. (Например, 01011000 => 000СЮ111, если исходное слово равно О, все биты маски будут равны 1.)

-х&[х-1), или

-,{х\-х),ши

{х&-х)-1

Первая из этих формул позволяет распараллелить вычисления на уровне команд.

Приведенная далее формула используется для создания маски, идентифицирующей крайний сгфава единичный бит и все завершающие нулевые биты (например, 01011000 => 00СЮ1111, если исходное слово равно О, все биты маски будут равны 1).

х®{х-1)

Очередная формула распространяет вправо крайний правый единичный бит (например, 01011000 => 01011111, если исходное слово равно О, все биты результата будут равны 1).

х\{х-1)

Для обнуления крайней справа непрерывной подстроки единичных битов (например, 01011000 => 01000000) можно использовать формулу

{{х\{х-1)) + \)&х.

Эта формула позволяет проверить, имеет ли положительное целое число вид 11-2, где]>к>0{ъ этом случае формула возвращает нулевой результат).

Для всех приведенных выше формул выполняется принцип Дуализма: если в описаниях формул единицы заменить нулями (и нули единицами), а в самих формулах заменить х -1 на лг +1 и обратно, -х на ->[х +1), & на и j на &, оставив без изменений только лг и -л,

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

Для того чтобы установить крайний справа нулевой бит (например, 10100111 => 10101111, если исходное слово равно О, возвращает слово, состоящее из одних единиц), используется следующая формула:

х\{х + 1].

Имеется простая проверка того, можно ли реализовать заданную функцию в виде последовательности команд сложения, вычитания, и, или и отрицания [59]. К перечисленным выше командам можно добавить другие команды из основного множества, которые, в свою очередь, являются комбинацией команд сложения, вычитания, и, или и не, например можно добавить команду сдвиг влево на определенную величину (которая эквивалентна по-след<яательности команд сложения) ша команду умножения. Команды, которые не могут быть выражены через команды сложения, вычитания и другие из основного списка, исключаются из рассмотрения. Критерий проверки следует из приведенной теоремы.

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

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

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

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

г,=х,\{х,&у,). (1)

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

Запишем машинные слова х, х, сдвинутое на два бита влево, и у, сдвинутое на один бит влево, как показано ниже. Добавим к записи маску, которая выделяет второй бит.