а после внутреннего полного перемешивания: АаВЬ CcDd EeFf GgHh liJj KkLl MitiNn OoPp.

Пусть длина слова Игфедставляет собой степень 2. Тогда операщпо внешнего идеального 1 перемешивания можно выполнить при помощи базовых RISC-команд за log {W/2) шагов,

причем на каждом шаге выполняется перестановка второй и третьей четвертей во все меньших частях слова [19], т.е. 32-битовое слово преобразуется следующим образом:

abed efgh ijkl mnop ABCD EFGH IJKL MNOP abed efgh ABCD EFGH ijkl mnop IJKL MNOP abed ABCD efgh EFGH ijkl IJKL mnop MNOP abAB cdCD efEF ghGH ijIJ klKL mnMN opOP aAbB eCdD eEfF gGhH iljJ kKlL тМпЫ oOpP

Приведем код, непосредственно реализующий описанный алгоритм н требующий выполнения 42 базовых RISC-команд.

X = (х & OxOOOOFFOO) « 8

X = (х & OxOOFOOOFO) << 4

X = (х & ОхОСОСОСОС) << 2

X = (х & 0x22222222) « 1

(X » 8)

(X » 4)

(х » 2)

(X » 1)

& OxOOOOFFOO & OXOOFOOOFO & ОхОСОСОСОС & 0x22222222

X & OxFFOOOOFF X & OxFOOFFOOF X Sc ОхСЗСЗСЗСЗ X & 0x99999999

Этот код можно сократить до 30 команд (хотя при этом время вьшолнения возрастет с 17 до 21 такта на машинах с неограниченными возможностями распараллеливания вычислений на /ровне команд), если использовать для обмена двух полей регистра метод исключающего или который рассматривался в разделе 2.19). Все используемые величины беззнаковые.

. = (х * (х » 8)) & OxOOOOFFOO; X = X * t * (t « 8)

: = (х (х >> 4)) & OxOOFOOOFO; X = X t * (t « 4)

= (х (х » 2)) & ОхОСОСОСОС; X = X * t * (t « 2)

= (х * (х >> 1)) & 0x22222222; х = х t * (t « 1)

Для выполнения обратной операщ1и достаточно изменить последовательность обме-ов на обратную.

= (X = (х

= (X

= (х

(х »

(х >>

(х >>

(х >>

1) )

2) ) 4)) 8))

0x22222222; ОхОСОСОСОС; OxOOFOOOFO; OxOOOOFFOO;

(t (t (t (t

<< << << «

2) 4) 8)

Использование только последних двух шагов обоих приведенных алгоритмов пере-гшивает биты в пределах байтов; три последних шага приводят к перемешиванию би-1В в пределах полуслова и т.д. В двух последних строках этого кода выполняется пере-;шивание битов в каждом отдельном байте; в трех последних строках - в каждом по-слове и т.д. То же замечание справедливо н для операции, обратной перемешиванию, лько в этом случае вместо последних шагов рассматриваются первые.

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

= (х » 16) I (X << 16);

(либо нему бавля Е< кажд част} ным Б

полу из щ обра

в сл

вып дач ком уро лев

X = X

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

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

Пожалуй, стоит упомянуть один частный случай, когда левая половина слова (левое полуслово) X состоит из одних нулевых битов; иначе говоря, требуется разместить биты из правой половины слова х так, чтобы они оказались в каждом втором разряде, т.е. преобразовать исходное 32-битовое слово

0000 0000 0000 0000 ABCD EFGH IJKL ШОР

В слово

ОАОВ 0C0D OEOF OGOH OIOJ OKOL ОМОМ ОООР.

Внешнее идеальное перемешивание может быть упрощено так, что будет требовать выполнения 22 базовых RISC-команд. Приведенный же ниже код для нашей частной задачи выполняется только за 19 базовых RISC-команд без увеличения времени работы на компьютере с неограниченными возможностями распараллеливания вычислений на уровне команд (12 тактов при любом методе). Для данного кода не требуется установка левой половины слова х равной 0.

X = ((х & OxFFOO) << 8) I (х & OxOOFF);

X = ( (Х « 4) X = ( (х << 2) X = ( (х << 1)

х) & OXOFOFOFOF х) & 0x33333333 х) & 0x55555555

Аналогично, код обратной операции (частный случай упаковки; см. раздел 7.4) может быть упрощен до 26 или 29 базовых RISC-команд, в зависимости от того, требуется ли вьшолнение команды и для очистки битов в нечетных разрядах или нет. Код, приведенный ниже, позволяет решить задачу обратного идеального перемешивания для частного случая ненулевых четных битов за 18 или 21 базовую RISC-команду, со временем работы на компьютере с неограниченными возможностями распараллеливания вычислений на уровне команд, составляющим 12 или 15 тактов.

7.3. Транспонирование битовой матрицы

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

Это несложное на первый взгляд преобразование оказывается чрезвычайно громоздким по количеству выполняемых команд.

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

Как именно хранится матрица-по строкам или столбцам, значения не имеет: в любом случае выполняются одни и те же действия. Предположим для определенности, что матрица хранится построчно и загрузка подматршц.! 8x8 в восемь регистров осуществляется восемью командами загрузить байт, адресующими столбцы исходной матрицы (т.е. значения адресов, используемые в командах загрузить байт, отличаются на величину, кратную ширине исходной матрицы в байтах). После транспонирования подматрица 8x8 сохраняется в столбце результирующей матригцл, т.е. сохранение подматриц выполняется за восемь команд сохранить байт в ячейки, адреса которых отличаются на величину, кратную ширине выходной матрищ>1 в байтах (эта величина может отличаться от ширины исходной матрицы, если, конечно, матрицы не являются квадратными). Таким образом, в регистрах аО, al,а7 у нас есть восемь 8-битовых величин, выровненных по правой границе. Требуется вычислить и разместить в регистрах ьо, Ы, Ь7 восемь 8-битовых величин, выровненных по правой границе, которые затем будут использоваться командами сохранить байт. Каким именно должно быть содержимое регистров после вычислений, показано ниже. Каждая цифра и буква здесь представляет один бит. Заметим, что главная диагональ проходит через бит 7 байта О (аО) и бит О байта 7 (а7). Те, кому это привычнее, могут считать, что, главная диагональ проходит через бит О байта О и бит 7 байта 7.

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

ГЛАВА7. nEPFCTAHORK-A китпв и кдйтпо