16. ОПТИМИЗАЦИЯ ЦИКЛА
======================
Анализируя программу, вы можете заметить, что нередко до 99% времени программа
проводит во внутренних циклах. Путем к увеличению скорости может стать
использование в наиболее критических частях цикла вставок ассемблерного кода.
Остальная часть программы может быть составлена на языке высокого уровня.
Обычно цикл содержит переменную-счетчик, показывающую сколько раз будет
повторяться цикл, а так же обычно обращается к элементам массива в каждой
итерации. Я выбрал, для примера, цикл в котором происходит чтение целого
числа из массива, изменение его знака на противоположный и запись результата
в другой массив.
Исходный код этой процедуры на языке C будет выглядеть следующим образом:
void ChangeSign (int * A, int * B, int N) {
int i;
for (i=0; i<N; i++) B[i] = -A[i];}
Переведя ее на ассемблер, мы получим что-то вроде этого:
Пример 1:
_ChangeSign PROCEDURE NEAR
PUSH ESI
PUSH EDI
A EQU DWORD PTR [ESP+12]
B EQU DWORD PTR [ESP+16]
N EQU DWORD PTR [ESP+20]
MOV ECX, [N]
JECXZ L2
MOV ESI, [A]
MOV EDI, [B]
CLD
L1: LODSD
NEG EAX
STOSD
LOOP L1
L2: POP EDI
POP ESI
RET ; (ни каких других pop если мы используем соглашения C)
_ChangeSign ENDP
Это похоже на хорошее решение, но оно не оптимально, потому что в цикле
используются медленные не спаривающиеся инструкции. Цикл исполниться за
11 тактов, если все данные на уровне L1 кеша.
Используем только спариваемые инструкции
----------------------------------------
Пример 2:
MOV ECX, [N]
MOV ESI, [A]
TEST ECX, ECX
JZ SHORT L2
MOV EDI, [B]
L1: MOV EAX, [ESI] ; u
XOR EBX, EBX ; v (спаривание)
ADD ESI, 4 ; u
SUB EBX, EAX ; v (спаривание)
MOV [EDI], EBX ; u
ADD EDI, 4 ; v (спаривание)
DEC ECX ; u
JNZ L1 ; v (спаривание)
L2:
Здесь мы использовали только спариваемые инструкции, и спланировали цикл так,
что все инструкции спарились. Теперь одна итерация исполняется за 4 такта. Мы
могли бы получить ту же скорость не разбивая инструкцию NEG, но тогда нам
придется разбить другие не спаривающиеся инструкции.
Использование одного регистра для счетчика и индекса
----------------------------------------------------
Пример 3:
MOV ESI, [A]
MOV EDI, [B]
MOV ECX, [N]
XOR EDX, EDX
TEST ECX, ECX
JZ SHORT L2
L1: MOV EAX, [ESI+4*EDX] ; u
NEG EAX ; u
MOV [EDI+4*EDX], EAX ; u
INC EDX ; v (спаривание)
CMP EDX, ECX ; u
JB L1 ; v (спаривание)
L2:
Используя один регистр как счетчик и как индекс мы задействуем меньше
инструкций в теле цикла, но он все еще исполняется за 4 такта, поскольку у нас
есть две неспаренные инструкции.
Счетчик, стремящийся к нулю
---------------------------
Желая избавиться от инструкции CMP, из примера 3, мы могли бы обозначить конец
цикла нулевым значением счетчика и использовать флаг нуля (ZF) для обнаружения
конца цикла, как это мы делали в примере 2. Единственный путь сделать это -
исполнить цикл наоборот, читая последние элементы первыми. Правда, кеш данных
оптимизировался для доступа к поступающим подряд данным, а не наоборот, так
что постоянные промахи кеша весьма вероятны, что бы избегать этого мы должны
запускать счетчик от -N и увеличивать до нуля. А регистр базы должен указывать
на конец массива, а не на начало:
Пример 4:
MOV ESI, [A]
MOV EAX, [N]
MOV EDI, [B]
XOR ECX, ECX
LEA ESI, [ESI+4*EAX] ; указатель на конец массива A
SUB ECX, EAX ; -N
LEA EDI, [EDI+4*EAX] ; указатель на конец массива B
JZ SHORT L2
L1: MOV EAX, [ESI+4*ECX] ; u
NEG EAX ; u
MOV [EDI+4*ECX], EAX ; u
INC ECX ; v (спаривание)
JNZ L1 ; u
L2:
Теперь у нас пять инструкций в теле цикла, но на исполнение по прежнему
тратиться 4 такта из-за плохого спаривания. (Если адреса и длины массивов
постоянны, то мы можем сохранить два регистра заменяя A+SIZE для ESI и B+SIZE
для EDI). А теперь давайте посмотрим как можно улучшить спаривание.
Спаривание расчета с управлением цикла
--------------------------------------
Мы можем захотеть ускорить цикл, спаривая инструкции его тела с инструкциями,
контролирующими цикл. Если мы установим что-нибудь между INC ECX и JNZ L1, то
это что-нибудь не должно влиять на флаг нуля (ZF). Инструкция
MOV [EDI+4*ECX], EBX после INC ECX создаст остановку AGI, таким образом нам
нужен более удачный код:
Пример 5:
MOV EAX, [N]
XOR ECX, ECX
SHL EAX, 2 ; 4 * N
JZ SHORT L3
MOV ESI, [A]
MOV EDI, [B]
SUB ECX, EAX ; - 4 * N
ADD ESI, EAX ; указатель на конец массива A
ADD EDI, EAX ; указатель на конец массива B
JMP SHORT L2
L1: MOV [EDI+ECX-4], EAX ; u
L2: MOV EAX, [ESI+ECX] ; v (спаривание)
XOR EAX, -1 ; u
ADD ECX, 4 ; v (спаривание)
INC EAX ; u
JNC L1 ; v (спаривание)
MOV [EDI+ECX-4], EAX
L3:
Здесь я использовал другой способ смены знака у EAX: инвертирование всех бит,
с последующим увеличением на 1. Причина, по которой я использовал этот метод
в том, что я могу использовать один грязный трюк инструкции INC: инструкция
INC не изменяет флаг переноса (CF), тогда как ADD изменяет. А используя ADD
вместо INC для увеличения счетчика моего цикла, я могу использовать как
признак окончания цикла флаг переноса (CF), а не флаг нуля (ZF). Таким образом
становиться возможным вставить INC EAX не меняя флага переноса. Вы можете
подумать, что можно бы было использовать LEA EAX, [EAX+1] вместо INC EAX,
которая тоже не изменить флаг, но инструкция LEA может вызвать остановку AGI,
так что это не лучший вариант.
Здесь я получил лучшее спаривание и теперь цикл исполняется за 3 такта. Хотите
ли вы увеличивать значение цикла на 1 (как в примере 4) или на 4 (как в
примере 5) - дело вкуса, для цикла это не принципиально.
Перекрытие операций
-------------------
Метод, используемый в примере 5 не очень удобный, потому что мы можем
использовать другие способы для улучшения спаривания. Один из способов
реорганизовать цикл - совместить конец одной операции с началом следующей. Я
буду называть это - свернутый цикл. Свернутый цикл оставляет незаконченную
операцию в каждой итерации, эта операция будет завершена в следующей итерации.
Например в примере 5 последний MOV одной итерации спаривается с первым MOV
следующей, но давайте рассмотрим его:
Пример 6:
MOV ESI, [A]
MOV EAX, [N]
MOV EDI, [B]
XOR ECX, ECX
LEA ESI, [ESI+4*EAX] ; указатель на конец массива A
SUB ECX, EAX ; -N
LEA EDI, [EDI+4*EAX] ; указатель на конец массива B
JZ SHORT L3
XOR EBX, EBX
MOV EAX, [ESI+4*ECX]
INC ECX
JZ SHORT L2
L1: SUB EBX, EAX ; u
MOV EAX, [ESI+4*ECX] ; v (спаривание)
MOV [EDI+4*ECX-4], EBX ; u
INC ECX ; v (спаривание)
MOV EBX, 0 ; u
JNZ L1 ; v (спаривание)
L2: SUB EBX, EAX
MOV [EDI+4*ECX-4], EBX
L3:
Здесь мы начинаем считывать вторую величину до того как сохранили первую, что
дает возможность улучшить спаривание. Инструкция MOV EBX, 0 вставлена между
INC ECX и JNZ L1 не для улучшения спаривания, а для того что бы избежать
остановки AGI.
Развертывание цикла
-------------------
Наиболее часто предлагаемая схема улучшения цикла - это исполнение двух
операций вместо одной за каждую итерацию, таким образом вдвое снижая
необходимое количество повторений цикла. Это называется развертыванием
цикла.
Пример 7:
MOV ESI, [A]
MOV EAX, [N]
MOV EDI, [B]
XOR ECX, ECX
LEA ESI, [ESI+4*EAX] ; указатель на конец массива A
SUB ECX, EAX ; -N
LEA EDI, [EDI+4*EAX] ; указатель на конец массива B
JZ SHORT L2
TEST AL,1 ; тест на нечетность N
JZ SHORT L1
MOV EAX, [ESI+4*ECX] ; N - нечетное. делаем четным
NEG EAX
MOV [EDI+4*ECX], EAX
INC ECX ; выравниваем счетчик
JZ SHORT L2 ; N = 1
L1: MOV EAX, [ESI+4*ECX] ; u
MOV EBX, [ESI+4*ECX+4] ; v (спаривание)
NEG EAX ; u
NEG EBX ; u
MOV [EDI+4*ECX], EAX ; u
MOV [EDI+4*ECX+4], EBX ; v (спаривание)
ADD ECX, 2 ; u
JNZ L1 ; v (спаривание)
L2:
Мы делаем две операции параллельно, достигая лучшего спаривания. Мы проверяем
N на нечетность и если это так, то выполняем одну операцию за пределами цикла,
поскольку цикл теперь может выполнить только четное количество операций.
У цикла есть остановка AGI в первой инструкции MOV, поскольку ECX был изменен
в предыдущем такте цикла. У цикла уходит 6 тактов на две операции.
Реорганизация цикла, для удаления остановки AGI
-----------------------------------------------
Пример 8:
MOV ESI, [A]
MOV EAX, [N]
MOV EDI, [B]
XOR ECX, ECX
LEA ESI, [ESI+4*EAX] ; указатель на конец массива A
SUB ECX, EAX ; -N
LEA EDI, [EDI+4*EAX] ; указатель на конец массива B
JZ SHORT L3
TEST AL,1 ; тест на нечетность N
JZ L2
MOV EAX, [ESI+4*ECX] ; N - нечетное. делаем четным
NEG EAX ; нет возможности спариться
MOV [EDI+4*ECX-4], EAX
INC ECX ; выравниваем счетчик
JNZ L2
NOP ; добавляем NOPы если JNZ L2 не
NOP ; предсказан.
JMP L3 ; N = 1
L1: NEG EAX ; u
NEG EBX ; u
MOV [EDI+4*ECX-8], EAX ; u
MOV [EDI+4*ECX-4], EBX ; v (спаривание)
L2: MOV EAX, [ESI+4*ECX] ; u
MOV EBX, [ESI+4*ECX+4] ; v (спаривание)
ADD ECX, 2 ; u
JNZ L1 ; v (спаривание)
NEG EAX
NEG EBX
MOV [EDI+4*ECX-8], EAX
MOV [EDI+4*ECX-4], EBX
L3:
Хитрость в том, что бы найти спаривающиеся инструкции, таким образом, что бы
не использовать счетчик цикла как индекс и реорганизовать цикл так, что бы
счетчик цикла увеличивался в предыдущем такте. Таким образом мы достигли
5 тактов для двух операций, приблизившись к лучшему из возможных решению.
Если кеширование данных является критическим, то можно увеличить скорость
объединив массивы A и B в одну структуру что бы каждое B[i] находилось после
соответствующего A[i]. Если структура массива выравнена, то по крайней мере
на 8, то B[i] будет всегда находиться в той же строке, что и A[i] и у вас
никогда не будет промахов кеша при записи B[i]. Конечно это приведет к
усложнению других частей программы, так что вы должны взвесить все
преимущества и недостатки.
Развертывание более чем в 2 раза
--------------------------------
Вы можете подумать, что исполнение более двух операций за одну итерацию
приведет к еще большей производительности цикла. Правда потери цикла не всегда
могут сводиться к одному такту за итерацию, так что развертывая цикл в 4 раза,
вместо 2 вы сохраните только 1/4 такта за итерацию, эффект за который вряд ли
стоит бороться. Только если потери не сводятся к одному такту и N велико
стоит думать о развертывании в 4 раза.
Недостатки через мерного развертывания цикла:
1. Вам необходимо вычислить остаток от деления N на R, где R - коофициент
развертки и выполнять этот остаток до или после основного цикла, что бы
сделать кол-во операций делимым на R. Это потребует дополнительного кода с
плохо предсказуемым ветвлением. И, разумеется, увеличиться тело цикла.
2. Код, обычно, требует больше времени при первом исполнении, чем при повторах
и большое тело цикла будет выполняться дольше первый раз, что актуально, если
N невелико.
3. Через мерный размер кода уменьшает эффективность кеша кода.
Обработка команд с 8 или 16 битными оперндами - частями 32 битных регистров
---------------------------------------------------------------------------
Если вам надо манипулировать с массивами 8 или 16 битных значений, то у вас
может возникнуть проблема с развертыванием цикла из-за того, что вы не сможете
добиться спаривания операций доступа к памяти. К примеру MOV AL,[ESI] /
MOV BL,[ESI+1] не спариться, если оба операнда лежат в пределах одного двойного
слова в памяти. Но существует более простой способ, призванный что бы
оперировать со всеми четыремя байтами в одном 32 битном регистре.
Следующий пример увеличивает на 2 каждый элемент массива байт.
Пример 9:
MOV ESI, [A] ; адрес массива байт
MOV ECX, [N] ; число элементов массива
TEST ECX, ECX ; сравнение N с 0
JZ SHORT L2
MOV EAX, [ESI] ; читаем первые четыре байта
L1: MOV EBX, EAX ; копируем в EBX
AND EAX, 7F7F7F7FH ; берем младшие 7 бит каждого байта в EAX
XOR EBX, EAX ; берем старшие биты каждого байта в EBX
ADD EAX, 02020202H ; увеличивает значение всех четырех байт
XOR EBX, EAX ; возвращаем биты обратно
MOV EAX, [ESI+4] ; читаем следующие четыре байта
MOV [ESI], EBX ; сохраняем результат
ADD ESI, 4 ; приращиваем указатель
SUB ECX, 4 ; уменьшаем счетчик цикла
JA L1 ; цикл
L2:
Этот цикл исполняется за 5 тактов, для каждых 4 байт. Разумеется, массив
должен быть выравнен на 4. Если число элементов массива не делимо на 4, то
вы можете добавить несколько дополнительных байт в начале или конце массива,
что бы выравнять его на четыре. Этот цикл всегда будет читать часть байт за
концом массива, так что вы должны убедиться, что массив не расположен в конце
сегмента, что бы избежать GPF.
Примечание - я замаскировал каждый верхний бит, в каждом байте, для того что
бы избежать возможного переноса при сложении. Я, так же, использовал XOR
вместо ADD, возвращая старшие биты на место, что бы снова избежать возможного
переноса.
Инструкция ADD ESI, 4 может быть удалена, если использовать счетчик цикла
в качестве индекса, как в примере 4. Однако, это приведет к нечетному
количеству инструкций в теле цикла, так что цикл по прежнему будет исполняться
5 тактов. Используя непарную инструкцию ветвления мы можем сохранить один
такт после последней операции, когда переход непредсказан, но мы должны
затратить несколько дополнительных тактов в прологе кода, устанавливая
указатель на конец массива и расчитывая -N, таким образом два метода будут
одинаково быстрыми. Метод представленный здесь наиболее простой и короткий.
Следующий пример находит длину нуль-терминированной строки, поиском первого
нулевого байта. Это быстрее, чем REP SCASB:
Пример 10:
STRLEN PROC NEAR
MOV EAX,[ESP+4] ; получаем указатель
MOV EDX,7
ADD EDX,EAX ; pointer+7 используется в конце
PUSH EBX
MOV EBX,[EAX] ; читаем первые 4 байта
ADD EAX,4 ; увеличиваем указатель
L1: LEA ECX,[EBX-01010101H] ; уменьшаем на 1 каждый байт
XOR EBX,-1 ; инвертируем все байты
AND ECX,EBX ; и эти два
MOV EBX,[EAX] ; читаем следующие 4 байта
ADD EAX,4 ; увеличиваем указатель
AND ECX,80808080H ; проверяем все битовые знаки
JZ L1 ; нет нулевых байт, продолжаем цикл
TEST ECX,00008080H ; тестируем первые два байта
JNZ SHORT L2
SHR ECX,16 ; не первые два байта
ADD EAX,2
L2: SHL CL,1 ; флаг переноса, что бы неветвить
POP EBX
SBB EAX,EDX ; считаем длину
RET ; (или RET 4 для паскаля)
STRLEN ENDP
Снова мы использовали метод перекрывания конца одной операции с началом
другого для улучшения спаривания. Я не развернул цикл, потому что это отняло
бы много времени. Строка, конечно, должна быть выравнена на 4. Всегда будут
читаться несколько байт в конце строки, так что строка не должна находиться в
конце сегмента.
Тело цикла имеет нечетное количество инструкций, так что одна всегда будет
неспарена. Используя цикл с одной неспаренной инструкции ветвления, мы делаем
упор на другой, что и сохраняет нам 1 такт.
Инструкция TEST ECX, 00008080H - не спариваемая. Вы могли бы использовать
здесь спариваемую инструкцию OR CH, CL, но вам придется вставить NOP или
что-то подобное по следующей причине: Ветвь цикла (JZ L1) обычно непредсказана,
в последний раз, когда цикл завершается. А исполнение ветвления (JNZ L2) в
первом такте цикла, после непредсказанного ветвления приведет к задержке в
5-10 тактов. Другая проблема с OR CH, CL - это то, что такая инструкция
вызовет замедление на процессорах i486 или PentiumPro, так что я решил
оставить неспариваемую инструкцию TEST.
Обработка 4 байт одновременно может быть весьма трудной. Код использует
алгоритм генерации ненулевого значения для байта, если только значение байта -
ноль. Это дает возможность тестировать все четыре байта одной операцией.
Алгоритм включает вычитание 1 из всех байт (в инструкции LEA). Я не маскировал
верхние биты каждого байта перед вычитанием, как я делал в предыдущем примере,
потому что это может привести к заему в следующем байте, но только в том
случае, если значение текущего байта - ноль, но это нас уже не волнует, т.к.
мы ищем до первого нуля. Если мы искали в обратном направлении, то после
обнаружении нуля надо перечитать двойное слово, затем протестировать все
четыре байта, что бы найти последний ноль и использовать BSWAP, что бы
изменить порядок следования байт.
Если искомое значение не ноль, то вы можете использовать XOR для всех
четырех байт, значением, которое вы хотите найти, а затем использовать
вышеизложенный метод.
Обработка нескольких операндов в одном регистре проще на MMX процессорах,
где для этого есть специальные инструкции и специальные 64 битные регистры.
Однако при использовании MMX инструкций можно получить большие задержки, если
после них вы используете инструкции с плавающей точкой, таким образом,
возможно, вы захотите использовать 32 бинтые инструкции.
Циклы с операциями с плавающей точкой
-------------------------------------
Методы, оптимизации таких циклов базируются на оптимизации обычных циклов,
с целочисленными инструкциями, хотя инструкции с плавающей точкой
перекрываются, а не спариваются.
Рассмотрим код языка C:
int i, n; double * X; double * Y; double DA;
for (i=0; i<n; i++) Y[i] = Y[i] - DA * X[i];
Эта часть кода (называемая DAXPY) изучается специально потому, что это ключ
к решению линейных уравнений.
Пример 11:
DSIZE = 8 ; размер данных
MOV EAX, [N] ; количество элементов
MOV ESI, [X] ; указатель на X
MOV EDI, [Y] ; указатель на Y
XOR ECX, ECX
LEA ESI, [ESI+DSIZE*EAX] ; указатель на конец X
SUB ECX, EAX ; -N
LEA EDI, [EDI+DSIZE*EAX] ; указатель на конец Y
JZ SHORT L3 ; проверка N = 0
FLD DSIZE PTR [DA]
FMUL DSIZE PTR [ESI+DSIZE*ECX] ; DA * X[0]
JMP SHORT L2 ; переход в цикл
L1: FLD DSIZE PTR [DA]
FMUL DSIZE PTR [ESI+DSIZE*ECX] ; DA * X[i]
FXCH ; берем старый результат
FSTP DSIZE PTR [EDI+DSIZE*ECX-DSIZE] ; сохраняем Y[i]
L2: FSUBR DSIZE PTR [EDI+DSIZE*ECX] ; вычитаем из Y[i]
INC ECX ; увеличиваем индекс
JNZ L1 ; цикл
FSTP DSIZE PTR [EDI+DSIZE*ECX-DSIZE] ; сохраняем последний результат
L3:
Здесь мы используем те же методу, что и в примере 6: Используем счетчик цикла
в качестве индекса и ведем счет через отрицательные значения вплоть до нуля.
Конец одной операции перекрывается с началом другой.
Чередование операций с плавающей точкой здесь работает превосходно: Задержка
ы 2 такта между FMUL и FSUBR заполняется FSTP предыдущего результата. Задержка
в 3 такта между FSUBR и FSTP заполняется целочисленными операциями обслуги
цикла. Остановка AGI анулируется путем чтения единственного параметра в первом
такте, после того как счетчик-индекс был увеличен.
Данное решение дает нам 6 тактов на операцию, это лучше, чем развернутое
решение, представленное Intel!
Развертывание циклов с плавающей точкой
---------------------------------------
Цикл DAXPY, развернутый в 3 раза весьма усложнился:
Пример 12:
DSIZE = 8 ; размер данных
IF DSIZE EQ 4
SHIFTCOUNT = 2
ELSE
SHIFTCOUNT = 3
ENDIF
MOV EAX, [N] ; количество элементов
MOV ECX, 3*DSIZE ; счетчик смещения
SHL EAX, SHIFTCOUNT ; DSIZE*N
JZ L4 ; N = 0
MOV ESI, [X] ; указатель на X
SUB ECX, EAX ; (3-N)*DSIZE
MOV EDI, [Y] ; указатель на Y
SUB ESI, ECX ; указатель конца - смещение
SUB EDI, ECX
TEST ECX, ECX
FLD DSIZE PTR [ESI+ECX] ; первый X
JNS SHORT L2 ; менее чем 4 операции
L1: ; main loop
FMUL DSIZE PTR [DA]
FLD DSIZE PTR [ESI+ECX+DSIZE]
FMUL DSIZE PTR [DA]
FXCH
FSUBR DSIZE PTR [EDI+ECX]
FXCH
FLD DSIZE PTR [ESI+ECX+2*DSIZE]
FMUL DSIZE PTR [DA]
FXCH
FSUBR DSIZE PTR [EDI+ECX+DSIZE]
FXCH ST(2)
FSTP DSIZE PTR [EDI+ECX]
FSUBR DSIZE PTR [EDI+ECX+2*DSIZE]
FXCH
FSTP DSIZE PTR [EDI+ECX+DSIZE]
FLD DSIZE PTR [ESI+ECX+3*DSIZE]
FXCH
FSTP DSIZE PTR [EDI+ECX+2*DSIZE]
ADD ECX, 3*DSIZE
JS L1 ; цикл
L2: FMUL DSIZE PTR [DA] ; завершение leftover операции
FSUBR DSIZE PTR [EDI+ECX]
SUB ECX, 2*DSIZE ; изменяем указатель смещения
JZ SHORT L3 ; завершено
FLD DSIZE PTR [DA] ; старт следующей операции
FMUL DSIZE PTR [ESI+ECX+3*DSIZE]
FXCH
FSTP DSIZE PTR [EDI+ECX+2*DSIZE]
FSUBR DSIZE PTR [EDI+ECX+3*DSIZE]
ADD ECX, 1*DSIZE
JZ SHORT L3 ; завершено
FLD DSIZE PTR [DA]
FMUL DSIZE PTR [ESI+ECX+3*DSIZE]
FXCH
FSTP DSIZE PTR [EDI+ECX+2*DSIZE]
FSUBR DSIZE PTR [EDI+ECX+3*DSIZE]
ADD ECX, 1*DSIZE
L3: FSTP DSIZE PTR [EDI+ECX+2*DSIZE]
L4:
Причина, почему я показываю вам развертывание цикла в 3 раза - не
рекомендация, а предупреждение как это трудно! Будьте готовы затратить
значительное время на отладку и проверку кода, прежде чем получите что-то
похожее на это. Есть несколько проблем, о которых придется заботиться: В
большинстве случаев вам не удастся удалить все потери таков из кода с
плавающей точкой, развернутого менее, чем в 4 раза (т.е. есть незаконченные
операции в конце, которые будут завершены в следующей итерации). Последний
FLD, в конце основного цикла продолжается в начале следующем проходе.
Искушает решение читающее за концом цикла, а затем отвергающее дополнительную
величину, как в примерах 9 и 10, но это не рекомендуется в циклах с плавающей
точкой, потому что чтение дополнительного значения может привести к генерации
исключения неверного операнда, если за данные концом массива не вписываются
в стандарт плавающей точки. Что бы избежать этого мы должны делать по крайней
мере еще одну операцию за пределами основного цикла.
Количество операций, которые надо совершить за пределами развернутого цикла
равно остатку от деления N на R, где N - количество операций, а R - фактор
развертывания. Но в случае свернутого(с незаконченной операцией) цикла мы
должны делать еще одно, т.е. остаток от деления (N-1) на R + 1, по
вышеупомянутой причине.
По идее, мы должны бы предпочесть выполнить дополнительные операции перед
основным циклом, но здесь мы должны делать их после по двум причинам:
Во-первых мы должны позаботиться о незавершенном операнде leftover. Во-вторых
расчет количества дополнительных операций требует деления R, а если R не
кратно 2, то это займет много времени. Выполнение дополнительных операций
после цикла избавляет от необходимости деления.
Следующая проблема - вычислить смещение счетчика цикла, таким образом, что бы
он изменил знак в нужное время и отрегулировать базовые указатели, так что бы
компенсировать это смещение. В заключении, вы должны быть уверены, что
операнд leftover установлен правильно для всех значений N.
Эпилог кода делает 1-3 операции, могут быть организованны как отдельный цикл,
но это дополнительная нагрузка на механизм предсказания переходов, так что
приведенное выше решение - самое быстрое.
А теперь, когда я испугал вас сложностью развертывания в 3 раза, я
продемонстрирую вам более легкое развертывание в 4 раза:
Пример 13:
DSIZE = 8 ; размер данных
MOV EAX, [N] ; количество элементов
MOV ESI, [X] ; указатель на X
MOV EDI, [Y] ; указатель на Y
XOR ECX, ECX
LEA ESI, [ESI+DSIZE*EAX] ; указатель на конец X
SUB ECX, EAX ; -N
LEA EDI, [EDI+DSIZE*EAX] ; указатель на конец Y
TEST AL,1 ; тест N на нечетность
JZ SHORT L1
FLD DSIZE PTR [DA] ; делаем нечетную операцию
FMUL DSIZE PTR [ESI+DSIZE*ECX]
FSUBR DSIZE PTR [EDI+DSIZE*ECX]
INC ECX ; коррекция счетчика
FSTP DSIZE PTR [EDI+DSIZE*ECX-DSIZE]
L1: TEST AL,2 ; тест возможности более 2 операций
JZ L2
FLD DSIZE PTR [DA] ; N MOD 4 = 2 или 3. Делаем еще две
FMUL DSIZE PTR [ESI+DSIZE*ECX]
FLD DSIZE PTR [DA]
FMUL DSIZE PTR [ESI+DSIZE*ECX+DSIZE]
FXCH
FSUBR DSIZE PTR [EDI+DSIZE*ECX]
FXCH
FSUBR DSIZE PTR [EDI+DSIZE*ECX+DSIZE]
FXCH
FSTP DSIZE PTR [EDI+DSIZE*ECX]
FSTP DSIZE PTR [EDI+DSIZE*ECX+DSIZE]
ADD ECX, 2 ; счетчик теперь делим на 4
L2: TEST ECX, ECX
JZ L4 ; нет больше операций
L3: ; main loop:
FLD DSIZE PTR [DA]
FLD DSIZE PTR [ESI+DSIZE*ECX]
FMUL ST,ST(1)
FLD DSIZE PTR [ESI+DSIZE*ECX+DSIZE]
FMUL ST,ST(2)
FLD DSIZE PTR [ESI+DSIZE*ECX+2*DSIZE]
FMUL ST,ST(3)
FXCH ST(2)
FSUBR DSIZE PTR [EDI+DSIZE*ECX]
FXCH ST(3)
FMUL DSIZE PTR [ESI+DSIZE*ECX+3*DSIZE]
FXCH
FSUBR DSIZE PTR [EDI+DSIZE*ECX+DSIZE]
FXCH ST(2)
FSUBR DSIZE PTR [EDI+DSIZE*ECX+2*DSIZE]
FXCH
FSUBR DSIZE PTR [EDI+DSIZE*ECX+3*DSIZE]
FXCH ST(3)
FSTP DSIZE PTR [EDI+DSIZE*ECX]
FSTP DSIZE PTR [EDI+DSIZE*ECX+2*DSIZE]
FSTP DSIZE PTR [EDI+DSIZE*ECX+DSIZE]
FSTP DSIZE PTR [EDI+DSIZE*ECX+3*DSIZE]
ADD ECX, 4 ; увеличиваем индекс на 4
JNZ L3 ; цикл
L4:
Обычно, легче всего найти решение без потерь тактов - это использовать
развертывание в 4 раза, т.к. в этом случае нет необходимости в свертывании.
Число дополнительных операций, за пределами основного цикла - остаток от
деления N на 4 расчитываются легко, без деления. Дополнительные операции
сделаны перед основным циклом, а не после, что бы сделать обработку счетчика
цикла более простым.
Увеличение развертки цикла - это дополнительные операции за его пределами,
которые более медленные из-за незавершенных операций, возможного не верного
предсказания переходов, но главная проблема - увеличение размера кода.
В качестве общей рекомендации, я пожалуй скажу, что если N велико или если
без развертывания вы не можете удалить достаточное количество потерь тактов,
то вам следует развернуть цикл с целочисленными операциями в 2 раза, а цикл
с плавающей точкой в 4.
Дальше
|
