выше значешм. Здесь выполняется обмен битов а [к], определяемых маской т, с битами а [к+j ], сдвинутыми вправо на j и выделенными с помощью маски т, что эквивалентно выделению битов а [к+j ] с помощью дополнения к маске т. Код, выполняющий обмен, использует методику трех исключающих или, описанную в разделе 2.19.

Листинг 7.3. Компактный код транспонирования битовой матрицы 32x32

void transpose32(unsigned А[32])

int j, к; unsigned m, t; m = OxOOOOFFFF;

for (j = 16; j != 0; j = j » 1, m = m * (m << j))

for (k = 0; к < 32; к = (к + j +1) & -j)

t = (A[k] " (A[k+j] » j)) & ra;

A[k] = A[k] " t;

A[k+j] = A[k+j] " (t « j) ;

Откомпилированный с помощью GNU С для компьютера, аналогичного RISC с базовым набором команд, этот код содержит 31 команду- 20 во внутреннем цикле и 7 во внешнем без учета внутреннего. Следовательно, всего выполняется 4-(-5(7-(-16-20) = 1639 команд. Если при транспонировании матрицы использовать 16 обращений к процедуре транспонирования матрицы 8x8 из листинга 7.2, то в этом случае транспонирование выполняется за 16(101 •(5) = 1696 команд в предположении, что все 16 вызовов следуют

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

С другой стороны, код из листинга 7.3 легко модифицировать для 64-битовой машины и транспонирования битовой матрицы размером 64x64. В этом случае понадобится вьшолнить примерно 46(7 •(-32 20) = 3886 команд. Транспонирование той же матрицы с вызовом

функций транспонирования матрицы 8x8 требует вьшолнения 64(85 5) = 5760 команд.

В алгоритме все преобразования выполняются без использования дополнительной памяти, следовательно, этот алгоритм может применяться для транспонирования матриц больших размеров, с дополнительными действиями по пересылке подматриц 32x32. Это же можно сделать, поместив результирующую матрицу в другой области памяти и выполняя пересьшку подматриц в первой либо последней итерации внешнего цикла.

Около половины команд, выполняемых в функции из листинга 7.3, используются для управления циклом, и функция пять раз загружает и сохраняет всю матрицу. Может быть, имеет смысл развертывание циклов, которое позволит убрать из кода команды управления? Да, имеет, если вас интересует в первую очередь скорость работы программы, если дополнительные расходы памяти не представляют для вас проблемы, если юш процессора вашего компьютера имеет достаточный размер для хранения больших блоков кода, а главное - при медленном вьшолнении команд ветвления вашим компьютером. Тело программы будет состоять из 80 (5 -16) повторных обменов битов при помощи

шести команд. Кроме того, в программе будет 32 команды загрузки исходной матрицы и 32 команды сохранения результата; итого по меньшей мере 544 команды.

Компилятор GNU С не в состоянии выполнить развертывание по такому большому числу итераций (16 для внутреннего цикла и пять для внешнего). В листинге 7.4 представлен код, в котором это развертывание выполнено вручную. Как видите, данная функция помешает транспонированную матрицу в другой массив, отличный от исходного; однако, если параметрами функции выступает один и тот же массив, по завершении работы программы он будет транспонирован. Количество строк swap в данном коде равно 80. После компиляции GNU С для RISC-компьютера с базовым набором команд код содержит, включая пролог и эпилог, 576 команд, среди которых нет команд ветвления (не считая команды возврата из функции). У целевого компьютера нет команд сохранить несколько слов и загрузить несколько слов, но он в состоянии сохранять и загружать по два регистра за такт при помоши команд сохранить двойное слово и загрузить двойное слово.

Листинг 7.4. Линейный код траиспонироваиия матрицы 32x32

ttdefine swap(aO, al, j, m) t = (aO * (al >>j)) & m; \

ao = ao * t; \ al = al * (t << j);

void transpose32(unsigned A[32], unsigned В [32]) {

unsigned m, t;

unsigned aO, al, a2, аЗ, a4, a5, аб, a7,

a8, a9, alO, all, al2, al3, al4, al5,

al6, al7, al8, al9, a20, a21, a22, a23,

a24, a25, a26, a27, a28, a29, аЗО, а31;

aO = A[ 0]; al = A[ 1]; a2 = A[ 2]; аЗ = A[ 3] ; a4 = A[ 4]; a5 = A[ 5]; аб = A[ 6]; a7 = A[ 7] ;

a28 = A[28]; a29 = A[29]; аЗО = A[30]; а31 = A[31];

m = OxOOOOFFFF;

swap(aO, al6, 16, m) swap(al, al7, 16, m)

swap(al5, а31, 16, m) m = OxOOFFOOFF; swap(aO, a8, 8, m) swap(al, a9, 8, m)

swap(a28, a29, 1, m) swap(a3 0, а31, 1, m)

B[ 0] = aO; B[ 1] = al; B[ 2] = a2; B[ 3] = аЗ; B[ 4] = a4; B[ 5] = a5; B[ 6] = аб; B[ 7] = a7;

B[28] = a28; B[29] = a29; B[30] = аЗО; B[31] = а31;

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

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

Сначала вьшолняется Щ1клический сдвиг вправо на 16 разрядов слов A[l6..3l] (т.е.

А[к] для I6<:k<:3l). Затем выполняется обмен местами правых половин слов: а[0] с

а[16] , а[1] с а[17] и т.д., аналогично коду из листинга 7.4. После этого вьшолняется

циклический сдвиг вправо на-восемь разрядов слов а[0..8] и а[24..31] и обмен битами,

соответствующими маске OxOOFFOOFF, между словами л[0] и а[8], A[l] и а[9] и т.д.

После выполнения пяти этапов транспонирование полностью не завершено. Необходимо вьшолнить циклический сдвиг слова а[1] на один разряд, слова А[2] - на два разряда и

т.д. (всего 31 команда). Код для этого метода не приводится, однако ниже показана последовательность шагов для битовой матрицы 4x4.

abed abed abij abij aeim aeim

efgh => efgh => efmn => nefm => nbfj => bfjn

ijkl klij kled kled koeg egko

mnop opmn opgh hopg hlpd dhlp

Часть программы из листинга 7.4, в которой выполняются перестановки битов, требует выполнения 480 команд (80 перестановок по шесть команд в каждой). В исправленной программе с использованием команд циклического сдвига вьшолняется 80 перестановок по четыре команды каждая, плюс 80 команд циклического сдвига (16 5) на первых пяти этапах и завершающая 31 команда циклического сдвига- итого 431 команда. Поскольку код пролога и эпилога остается неизменным, использование команд циклического сдвига позволяет сэкономить 49 команд.

Существует еще один метод транспонирования битовой матрицы, основанный на трёх преобразованиях сдвига [19]. Если имеется матрица размером пХп, то выполняются следующие шаги; 1) циклический сдвиг строки i вправо на i разрядов; 2) циклический сдвиг столбца J вверх на {j + l)modn разрядов; 3) циклический сдвиг строки i вправо на

{i + l)modn разрядов; 4) отражение матрицы относительно горизонтальной оси, проходящей через ее середину. Проиллюстрируем сказанное ца примере матрицы 4x4.

abed abed hlpd dhlp aeim

efgh => hefg => koeg => egko => bfjn

ijkl klij nbfj bfjn egko

mnop nopm aeim aeim dhlp

Этот метод не может конкурировать с другими из-за высокой стоимости шага 2. (Чтобы выполнить этот шаг за разумное количество шагов, сначала вьшолняется циклический сдвиг вверх на п/2 позиции всех столбцов, которые должны быть сдвинуты на

п/2 разряда или более (это столбцы от n/2-l до и- 2), затем выполняется циклический

сдвиг вверх на п/4 позиции и т.д.) Шаги 1 и 3 требуют выполнения всего лишь по п-1

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

Если битовая матрица 8x8 сохраняется в 64-разрядном слове как обычно (верхняя строка помещается в старшие восемь битов и т.д.), то операщм транспонирования такой матрицы эквиваленша трем внешним идеальным перемешиваниям или обратным им