Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11634
Последний выпуск: 19.06.2015

Оптимизация для pentium процессора - оптимизация цикла

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.

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог