Оптимизация для процессоров семейства Pentium: 25. Оптимизация циклов (все процессоры) — Архив WASM.RU
Анализируя свои программы, вы можете увидеть, что больше всего ресурсов пожирают внутренние циклы. Используя язык ассемблера можно существенно оптимизировать их. Остальную часть программы можно оставить написанной на языке высокого уровня.
Во всех следующих примерах предполагается, что все данные находятся в кэше первого уровня. Если скорость ограничивается из-за того, что данные загружаются в кэш, нет никакого смысла оптимизировать инструкции. Лучше сконцентрируйтесь на правильной организации данных (глава 7).
25.1 Циклы в PPlain и PMMX
Как правило цикл содержит счетчик, определяющий сколько раз он должен повториться, и достаточно часто еще массив данных, в один элемент которого записываются данные или считываются из него каждое повторение.
Эта процедура на C может выглядеть так:
Код (Text):
Переводя ее на ассемблер мы могли бы написать эту процедуру следующим образом:
Пример 1.1:
Код (Text):
Это выглядит как достаточно красивое решение, но оно не самое оптимальное, потому что оно использует медленные неспариваемые инструкции. Каждая итерация занимает 11 тактов при условии, что все данные находятся в кэше первого уровня.
Использование только спариваемых инструкций (PPlain и PMMX)
Пример 1.2:
Код (Text):
Здесь мы используем только спариваемые инструкции, и так их располагаем, что они все спариваются. Теперь они занимают только 4 такта за итерацию. Мы можем получить ту же самую скорость не разделяя инструкцию NEG, но другие неспариваемые инструкции все же стоит разделить.
Использования одного регистра как счетчика и индекса
Пример 1.3:
Код (Text):
Использование одного регистра как счетчика и индеска уменьшает количество инструкций в теле цикла, но он по-прежнему занимает 4 такта, так как у нас две неспариваемые инструкции.
Пусть конечное значение счетчика равняется нулю (PPlain и PMMX)
Мы хотим избавиться от инструкции CMP в примере 1.3, сделав так, чтобы последнее значение счетчика равнялось нулю, и использовать флаг нуля как знак того, что цикл закончен (как мы сделали в примере 1.2). Один вариант заключается в том, чтобы исполнить цикл задом наперед, взяв последний элемент первым. Тем не менее, кэш данных оптимизирован для получения последних в прямом порядке, а не в обратном, поэтому если вероятны промахи кэша, вам следует задать значение счетчика -N и повышать его значение до нуля. Базовые регистры тогда должны указывать на конец массива, а не на его начало:
Пример 1.4:
Код (Text):
Однако цикл по-прежнему занимает 4 такта из-за плохой спариваемости. (Если адреса и размеры массива являются константами, мы можем сохранить два регистра). Теперь давайте посмотрим, как мы можем улучшить спариваемость.
Спаривание вычислений в цикле (PPlain и PMMX)
Мы можем улучшить спаривание, перемешав инструкции вычисления с инструкциями управления циклом. Если мы хотим поместить что-нибудь между 'INC ECX' и 'JNZ L1', это должно быть что-нибудь, что не влияет на флаг нуля. Инструкция 'MOV [EDI+4*ECX],EBX после 'INC ECX' сгенерирует задержку AGI, поэтому нам придется нужно быть более искусными:
Пример 1.5:
Код (Text):
Здесь я использовал другой способ, чтобы посчитать отрицательное значение EAX: инвертирование всех битов и добавление еще одного. Причина, по которой я задействовал этот метод состоит в том, что я могу использовать хитрый трюк с инструкцией INC: INC не изменяет флаг переноса, в то время как ADD это делает. Я использую ADD вместо INC, чтобы повышать счетчик цикла и проверяю флаг переноса, а не флаг нуля. Тогда можно поместить 'INC EAX' между ними без вреда для флага переноса. Возможно вы подумали, что можно было бы использовать 'LEA EAX,[EAX+1]' вместо 'INC EAX', по крайней мере он не меняет никаких флагов, но инструкция LEA сгенерирует задержку AGI, поэтому это не лучшее решение. Обратите внимание, что трюк с инструкцией INC, которая не меняет флаг переноса, будет полезен только на PPlain и PMMX, так как на PPro, PII и PIII будут сгенерированы частичные задержки регистра флагов.
Здесь мне удалось добиться совершенного спаривания, и цикл теперь занимает только 3 такта. Хотите ли вы повышать значение счетчика цикла на 1 (как в примере 1.4) или на 4 (как в примере 1.5) - это дело вкуса, никакого влияния на время выполнения цикла это не окажет.
Пересечение времени выполнения одной операции с другой (PPlain и PMMX)
Метод, использованный в примере 1.5 подойдет далеко не во всех случаях, поэтому мы можем поискать другие способы улучшения спариваемости. Один из путей реорганизовать цикл - это сделать так, чтобы конец выполнения одной операции пересекался с началом выполнения другой. Я буду называть это свернутым циклом. У свернутого цикла в конце каждого цикла находится инструкция, выполнение которой будет закончено в следующем повторении. Фактически, в примере 1.5 последний MOV спаривается с первым. Мы исследуем этот метод поподробнее:
Пример 1.6:
Код (Text):
Здесь мы начинаем считывать второе значение до того, как сохранили первое, и это, конечно, улучшает возможности к спариванию. Инструкция 'MOV EBX,0' была помещена между 'INC ECX' и 'JNZ L1' не для того, чтобы улучшить спаривание, а для того, чтобы избежать задержку AGI.
Разворачивание цикла (PPlain и PMMX)
Один из самых часто использующихся способов улучшить спаривание - это сделать две операции на каждый проход, которых будет в два раза меньше. Это называется разворачиванием цикла:
Пример 1.7:
Код (Text):
Теперь мы делаем две операции одновременно, что приводит к лучшему спариванию. Нам приходится тестировать N на нечетность, и если оно нечетно, то делаем дополнительную операцию вне цикла, потому что внутри него мы можем сделать только четное количество операций.
В цикле есть задержка AGI, генерируемая первой инструкцией MOV, потому что ECX повышается на 1 в предыдущем такте, поэтому для двух операций цикл занимает 6 тактов.
Реорганизация цикла для удаления задержки AGI (PPlain и PMMX)
Пример 1.8:
Код (Text):
Трюк заключается в том, что найти пару инструкций, которые не используют счетчик цикла в качестве индекса, и реорганизовать цикл так, чтобы счетчик повышал свое значение в предыдущем такте. Сейчас мы близки к 5 тактам для двух операций, что близко к самому лучшему варианту.
Если кэширование данных критично, тогда вы можете улучшить скорость, соединив массивы A и B в один массив, так чтобы каждый B[i] находился непосредственно за соответствующим A[i]. Если структурированный массив выровнен по крайней мере на 8, тогда B[i] всегда будет находится в той же линии кэша, что и A[i], поэтому будет всегда случаться промах кэша при записи в B[i]. Это, конечно, может сглаживаться приростом производительности в других частях программы, поэтому вы должны взвесить все за и против.
Разворачивание более чем на 2 (PPlain и PMMX)
Вы можете прикинуть возможность более чем двух операций за одно повторение, чтобы снизить количество действий, необходимых для организации цикла. Но так как в большинстве случаев время, требуемое для выполнения таких действий, можно снизить только на один такт, то разворачивание цикла в четыре раза, а не в два, сохранит только 1/4 такта на операцию, что вряд ли стоит усилий, которые будут на это потрачены. Только если можно сохранить еще больше, и если N очень велико, вам стоит думать о разворачивании цикла в четыре раза.
Недостатки слишком большого разворачивания цикла следующие:
- Вам будет необходимо посчитать N MODULO R, где R - это коэффициент разворачивания, и сделать N MODULO R операций до или после основного цикла, чтобы выполнить недостающее количество операций. На это уйдет дополнительный код и плохо предсказуемые операции условного перехоа. И, конечно, тело цикла станет больше.
- Кусок кода обычно выполняется в первый раз гораздо дольше, и чем больше ваш код, тем больше будут связанные с этим потери, особенно, если N невелико.
- Значительное увеличение кода делает работу с кэшем менее эффективной.
Одновременная обработка нескольких 8-ми или 16-ти битных операндов в 32-х битных регистра (PPlain и PMMX)
Если вам нужно обрабатывать массивы, состоящие из 8-ми или 16-ти битных операндов, тогда у вас появятся проблемы с развернутыми циклами, потому что вы не сможете спарить две операции доступа к памяти. Например, 'MOV AL,[ESI] / MOV BL,[ESI+1]' не будут спариваться, так как оба операнда находятся внутри одного и того же двойного слова памяти. Но есть продвинутый способ обрабатывать сразу два байта за раз в одном 32-х битном регистре.
Следующий пример добавляет 2 ко всем элементам массива байтов:
Пример 1.9:
Код (Text):
Этот цикл занимает 5 тактов для каждых 4 байт. Массив, разумеется, должен быть выравнен на 4. Если количество элементов в массиве не кратно четырем, тогда вы можете добавить в конец несколько байтов, чтобы сделать его делимым на четыре. Этот цикл будет читать за концом массива, поэтому вам нужно убедиться, что тот не находится в конце сегмента, дабы избежать ошибки общей защиты.
Обратите внимание, что перед прибавлением я "спрятал" наивысший бит каждого байта, чтобы не испортить их значение (если результат сложения для конкретного байта превысит 256). Я использую XOR, а не ADD, когда помещаю последний бит на место по той же самой причине.
Инструкция 'ADD ESI,4' можно избежать, если использовать счетчик цикла в качестве индекса, как это сделано в примере 1.4. Тем не менее, в результате количество инструкций в цикле будет нечетно, а значит одна инструкция будет не спарена, и цикл по-прежнему займет 5 тактов. Делая инструкцию перехода неспаренной сохранит один такт после последней операции, если инструкция была предсказана неверно, но нам придется потратить дополнительный такт в коде пролога, чтобы установить указатель в конец массива и высчитать -N, поэтому эти два метода будут одинакого быстры. Метод, представленный здесь, является самым простым и самым коротким.
Следующий пример находит длину строки, заканчивающейся нулем, путем поиска первого байта, равного нулю. Он быстрее, чем использовать REP SCASB:
Пример 1.10:
Код (Text):
Здесь мы снова использовали метод пересечения конца выполнения одной операции с началом выполнения другой, чтобы улучшить спаривание. Я не стал разворачивать цикл, так как количество его повторений относительно невелико. Строка, конечно, должна быть выравнена на 4. Код будет считывать несколько байт за строкой, поэтому та не должна располагаться в конце сегмента.
Количество инструкций в цикле нечетно, поэтому одна из них неспарена. Сделав неспаренной инструкцию перехода, а не какую-либо другую, мы сэкономим один такт, если инструкция перехода будет предсказана неверно.
Инструкция 'TEST ECX,00008080H' неспариваема. Вы можете использовать здесь спариваемую инструкцию 'OR CH,CL' вместо нее, но тогда вам придется поместить NOP или что-нибудь еще, чтобы избежать потерь из-за последовательных инструкций перехода. Другая проблема с 'OR CH,CL' состоит в том, что она вызовет частичную задержку регистра на PPro, PII или PIII. Поэтому я выбрал использование неспариваемой инструкции TEST.
Обработка 4-х байт за раз может быть довольно сложной. Код использует формулу, которая генерирует ненулевое значение для байт только тогда, когда байт равен нулю. Это делает возможным протестировать все четыре байта за одну операцию. Этот алгоритм включает вычитание 1 из всех байтов (в инструкции LEA). Я не стал "прятать" наивысший бит перед вычитанием, как я сделал это в предыдущем примере, поэтому операция вычитания может испортить значение следующего байта в EAX, но только если текущий равен нулю, и нам не важно, что будет со следующим байтом. Если бы мы искали нулевой байт в обратном порядке, нам бы пришлось считать двойное слово повторно после обнаружения нуля, а затем протестировать все четыре байта, чтобы найти последний ноль, или использовать BSWAP для изменения порядка байтов.
Если вы хотите найти байт с другим, ненулевым значением, тогда вы можете XOR'ить все четыре байта со значением, которое вы ищете, а затем используйте метод выше для поиска нуля.
Циклы с операциями MMX (PMMX)
Обработка нескольких операндо в одном регистре проще на MMX-процессорах, потому что у них специальные инструкции и регистры именно для этих целей.
Возвращаясь к задаче добавления двух ко всем байтам в массиве, мы можем воспользоваться возможностями, предоставляемыми MMX-инструкциями:
Пример 1.11:
Код (Text):
Инструкция сохранения помещена после инструкции управления циклом, чтобы избежать задержки сохранения.
Этот цикл занимает 4 такта, потому что инструкция PADDB не спаривается с 'ADD ESI, 8'. (Инструкция MMX с доступом к памяти не может спариваться с не-MMX инструкцией или с другой инструкцией MMX с доступом к памяти). Мы можем избавиться от 'ADD ESI, 8', используя в качестве индекса ECX, но это приведет к задержке AGI.
Так как затраты на управления циклом значительны, мы можем захотеть развернуть цикл:
Пример 1.12:
Код (Text):
Этот развернутый цикл занимает 6 тактов на выполнение при обработке 16 байтов. Инструкции PADDB не спариваются. Две ветви перемешаны, чтобы избежать задержки сохранения.
Использование инструкций MMX приводит к большим потерям, если вы используете инструкции плавающей запятой неподалеку, поэтому могут быть ситуации, когда 32-х битные регистры будут предпочтительнее.
Циклы с инструкциями плавающей запятой (PPlain и PMMX).
Методы оптимизации циклов с инструкциями плавающей запятой примерно те же самые, что и для циклов с целочисленными инструкциями, хотя инструкции плавающей запятой пересекаются, а не спариваются.
У нас есть следующий код языка C:
Код (Text):
Этот кусок кода (под названием DAXPY) является ключем к решению линейных уравнений.
Пример 1.13:
Код (Text):
Здесь мы использовали те же методы, что и в примере 1.6: использовали счетчик цикла в качестве индекса и пробег от негативных значений к нулю. Конец выполнения одной операции пересекается с началом выполнени другой.
Смешение различных инструкций плавающей запятой работает прекрасно: задержка в 2 такта между FMUL и FSUBR заполняется FSTP предыдущего результата. Задержка в 3 такта между FSUBR и FSTP заполняется инструкциями управления циклом и первые двумя инструкциями следующего повторения. Задержку AGI удалось избежать благодая чтению в первом такте после изменения индекса только тех параметров, которые от индекса не зависят.
Это решение занимает 6 тактов на операцию, и оно лучше, чем аналогичное развернутое решение от Интела!
Разворачивание циклов с инструкциями плавающей запятой (PPlain и PMMX)
Цикл DAXPY, развернутый в 3 раза, довольно сложен:
Пример 1.14:
L4:Код (Text):
Причина, по которой я показываю вам, как развернуть цикл в три раза, не в том, чтобы порекомендовать подобный подход, а в том, чтобы продемонстрровать, как это сложно! Будьте готовы провести значительное количество времени, отлаживая и проверяя ваш код, когда будете делать что-нибудь подобное. Есть несколько проблем, о которых нужно позаботиться: в большинстве случаев вы не сможете устранить все задержки из цикла с инструкциями плавающей запятой, развернутого менее чем на 4, если только вы не свернете его (то есть в конце цикла будут операции, выполнение которых закончится в конце следующего повторения). Последний FLD в основном цикле выше является началом первой операции в следующем повторении. Было бы соблазнительным сделать решение, которое бы считывало после конца массива, а затем бы избавлялось от лишнего значения (как в примере 1.9 и 1.10), но это не рекомендуется с инструкциями плавающей запятой, потому что чтение дополнительного значения может сгенерировать исключение ненормального значение операнда, если после массива не находится число с плавающей запятой. Чтобы избежать этого, нам приходиться совершать по крайней мере на одну операцию больше после основного цикла.
Количество операций, которое необходимо выполнить снаружи развернутого цикла, как правило будет равно N MODULE R, где N - количество операций, а R - коэффициент развернутости цикла. Но в случае со свернутым циклом, нам нужно сделать на одну операцию больше, то есть (N-1) MODULO R + 1 в силу вышеуказанных причин.
Обычно мы делаем дополнительные операции до основного цикла, но здесь мы должны сделать их после в силу двух причин: одна причина - это позаботиться об оставшемся операнде (из-за свертывания). Другая причина состоит в том, что вычисление количества дополнительных операций требует деления, если R не является степенью 2-х, а деление занимает много времени. Дополнительные операции после цикла решают эту проблему.
Другая задача - это высчитать, как влиять на счетчик цикла так, чтобы он изменил знак в правильный момент, и привести в порядок базовые указатели. Наконец, вам следует убедиться, что оставшийся от свертывания операнд был обработан верно для всех значений N.
Эпилоговый код, делающий 1-3 операции, можно организовать как отдельный цикл, но это будет стоить неправильного предсказания, поэтому решение выше быстрее.
Теперь, когда я напугал вас трудностями разворачивания на 3, я покажу, насколько проще разворачивать на 4:
Пример 1.15:
Код (Text):
Обычно довольно легко добиться отсутствия задержек в цикле, развернутом на 4, и нет нужды в свертывании последней операции. Количество дополнительных операций, которые нужно сделать за пределами основного цикла равно N MODULO 4, что можно легко посчитать без деления, просто протестировав два нижних бита в N. Дополнительные операции делаются до основного цикла, а не после, чтобы сделать обработку счетчика цикла проще.
Недостаток разворачивания циклов в том, что дополнительные операции, выполняемые за пределами цикла медленнее из-за несовершенного пересечения и возможных неправильных предсказаний переходов, а потери при первой загрузке кода выше из-за возросшего размера кода.
В качестве основной рекомендации, я бы посоветовал, что если N велико или если сворачивание цикла без развертывания не может удалить некоторых задержек, тогда вам следует развернуть критические целочисленные циклы в два раза, а циклы с инструкциями плавающей запятой в 4 раза.
25.2 Циклы в PPro, PII и PIII
В предыдущей главе (25.1) я объяснил, как использовать свертывание и разворачивания циклов, чтобы улучшить спаривание в PPlain и PMMX. На PPro, PII и PIII нет никакой причины делать это благодяря механизму выполнения инструкций не по порядку. Но здесь есть другие проблемы, о которых надо позаботиться, связанные с границами БДИ и задержка чтения регистров.
Я выбрал те же примеры, что и в главе 25.1 для предыдущих микропроцессоров: процедура, которая считывает целые числа из массива, изменяет их знак, и сохраняет результаты в другой массив.
На C эта процедура выглядела бы так:
Код (Text):
Переводя ее на ассемблер, нам следовало бы написать так:
Пример 2.1:
Код (Text):
Это выглядит как довольно красивое решение, но не самое оптимальное, потому что он использует инструкции LOOP, LODSD и STOSD, которые генерируют много мопов. Одна итерация цикла занимает 6-7 тактов, если все данные находятся в кэше первого уровня. Если мы будем избегать данных инструкций, то получим следующее:
Пример 2.2:
Код (Text):
Комментарии интерпретируются следующим образом: инструкция 'MOV EAX,[ESI]' два байта длиной, она генерирует один моп для порта 2, который читает ESI и пишет в (переименовывает) EAX. Эта информация требуется для анализирования возможных узких мест.
Давайте сначала проанализируем раскодировку инструкций (глава 14): одна из инструкций генерирует два мопа ('MOV [EDI],EAX'). Эта инструкция должна попасть в декодер D0. Есть три раскодировываемые группы в цикле, поэтому его можно раскодировать за 3 такта.
Теперь давайте посмотрим на доставку инструкций (глава 15): если границы между БДИ не дадут первым трем инструкциям раскодироваться вместе, тогда будет три раскодировываемые группы в последнем БДИ, поэтому в следующем повторении БДИ начнется с первой инструкции, там где нам нужно, и мы получим задержку только в первом повторении. Худшим вариантом будет 16-ти байтная граница и граница БДИ в одно из следующих трех инструкций. Согласно таблице, приведенной в соотвествующей главе, это сгенерирует задержку в один такт, и приведет к тому, что в следующем повторении первый БДИ будет выровнен на 16, и проблема будет повторяться каждую итерацию. В результате время доставки будет равно 4 тактам на итерацию (а не 3). Есть два пути предотвратить подобный вариант развития событий: первый метод заключается в том, чтобы контролировать расположение 16-ти байтных границ. Другой метод проще. Так как во всем цикле только 15 байт кода, вы можете избежать 16-ти байтных границ, выровняв цикл на 16, как показано выше. Тогда весь цикл будет умещаться в один БДИ, поэтому никакого дальнейшего анализа доставки инструкций не потребуется.
Третья проблема - это задержки чтения регистров (глава 16). В этом цикле не читается ни один регистр, если по крайней мере несколько тактов назад в него не была произведена запись.
Четвертый анализ - это выполнение инструкций (глава 17). Подсчитывая мопы, предназначающиеся для разных портом, мы получаем:
порт 0 или 1: 4 мопа порт 1 : 1 моп порт 2: 1 моп порт 3: 1 моп порт 4: 1 моп
Предположив, что мопы, которые могут пойти в порт 0 или 1, распределяются оптимальным образом, время выполнения будет равно 2.5 такта на итерацию.
Последний анализ, который необходимо провести, это вывод из обращения (глава 18). Так как количество мопов в цикле не кратно 3, слоты вывода из обращения не будут использоваться оптимальным образом, когда переход будет выводиться из обращения через первый слот. Время, необходимое для вывода из обращения равно количеству мопов, деленное на 3 и округленное в сторону ближайшего целого числа. Это дает 3 такта для вывода из обращения.
В заключение, цикл, представленный выше, может выполняться за 3 такта на итерацию, если код цикла выровнен на 16. Я предполагаю, что условный переход предсказывается каждый раз, кроме выхода из цикла (глава 22.2).
Использование одного и того же регистра для счетчика и индекса, последнее значение счетчика равно нулю (PPro, PII и PIII)
Пример 2.3:
Код (Text):
Количество мопов было снижено до 6. Базовые указатели указывают на конец массивов, поэтому индекс можно увеличивать от негативных значений до нуля.
Раскодировка: в этом цикле две раскодировываемые группы, поэтому раскодировка пройдет в два такта.
Доставка инструкций:
Цикл всегда занимает по крайней мере на один такт больше, чем количество 16-ти байтных блоков. Так как в этом цикле только 11 байтов кода, можно уместить их все в один БДИ. Выровняв цикл на 16 мы будем уверены, что будет только один 16-ти байтный блок, поэтому возможно осущесвить доставку за 2 такта.
Задержки чтения регистров:
Регистры ESI и EDI прочитаны, но не модифицируются внутри цикла. Поэтому эти считывания будут осуществляться из постоянных регистров, но не в одном триплете. Регистры EAX, ECX и флаги модифицируются внутри цикла и считываются до того, как они записываются обратно, поэтому чтения постоянных регистров не будет. То есть можно сделать заключение, что задержек чтения регистров нет.
Выполнение: порт 0 or 1: 2 моп порт 1: 1 моп порт 2: 1 моп порт 3: 1 моп порт 4: 1 моп Время выполнения: 1.5 такта.
Вывод из обращения: 6 мопов = 2 такта.
Заключение: этот цикл занимает только два такта на итерацию.
Если вы используете абсолютные адреса вместо ESI и EDI, тогда цикл будет занимать 3 такта, потому что он не сможет уместиться в один 16-ти байтный блок.
Разворачивание цикла (PPro, PII и PIII)
Осуществление более чем одной операции за проход, а соответственно, и меньшего количества проходов называется разворачиванием циклов. В предыдущих процессорах вам следовало развернуть циклы, чтобы разворачивать циклы, чтобы добиться лучшего спаривания (глава 25.1). В PPro, PII и PIII это не требуется, потому что об этом заботится механизм выполнения инструкций не по порядку. Нет никакой надобности использовать два разных регистра, потому что этим занимается переименование регистров. Целью разворачивания является снижение расходов на управление циклом при каждом повторении.
Следующий пример по смыслу тот же, что и пример в 2.2, но развернутый в два разм, что означает выполнение двух операций за раз, и меньшее в два раза количество проходов.
Пример 2.4:
Код (Text):
В примере 2.2 инструкции управления циклом (то есть изменение значений указателей и счетчика, а также переход назад) занимал 4 мопа, а 'реальная работа' занимала 4 мопа. При разворачивании цикла в два раза
Анализируя доставку инструкций в этом цикле мы увидим, что новый БДИ начинается с инструкции 'ADD ESI, 8', следовательно она пойдет в декодер D0. Поэтому цикл раскодировывается за 5 тактов, а не за 4, как нам хотелось. Мы можем решить эту проблему, заменив предыдущую инструкцию на более длинную версию.
Изменить 'MOV [EDI+4],EAX' на:
Код (Text):
Это заставит новый БДИ начаться с длинной инструкции 'MOV [EDI+4]', поэтому время раскодировки сейчас близко к 4 тактам. Оставшаяся свободная часть конвеера может обрабатывать 3 мопа за такт, поэтому ожидаемое время выполнения равно 4 тактам или 2 тактам на операцию.
Тестирование этого решения показало, что в реальности оно занимает немного больше. Мои измерения показывают примерно 4.5 такта за итерацию. Вероятно это связано с неоптимальной перегруппировкой мопов. Возможно, ROB не смог найти оптимального порядка выполнения. Проблемы подобного рода непредсказуемы, и только тестирование может выявить их. Мы можем помочь ROB'у сделать часть перегруппировки сами:
Пример 2.5:
Код (Text):
Цикл теперь выполняется в 4 тактах на итерацию. Также была решена проблема с БДИ. Это стоило нам дополнительного регистра, потому что мы не могли использовать преимущества переименования регистров.
Разворачивание более чем в 2 раза
Развертка циклов рекомендуется, когда инструкции по управлению циклами занимают значительную часть общего времени выполнения. В примере 2.3 они занимают только 2 мопа, поэтому выгода будет невелика, но тем не менее я покажу, как его развернуть, просто ради упражнения.
'Настоящая работа' равна 4 мопам, на управление циклом уходит 2 мопа. Развернув его, мы получим 2*4+3 = 10 мопов. Время вывода из обращения будет равно 10/3, огругляем в сторону ближайшего целого, получается 4 такта. Эти вычисления показывают, что разворачиванием мы ничего не добьемся:
Пример 2.6:
Код (Text):
БДИ распределяются так, как нам нужно. Время раскодировки равно 6 тактам.
Задержки чтения регистров является здесь проблемой, так как ECX выводится из обращения в конце цикла, а нам нужно читать ESI, EDI и ECX. Инструкции были перегруппированы так, чтобы избежать чтения ESI рядом с концом цикла во избежания задержки чтения регистра. Другими словами причина перегруппировки инструкций и использования дополнительного регистра не та, что в предыдущем примере.
Здесь 12 мопов и цикл выполняется за 6 тактов на итерацию или 1.5 тактов на операцию.
Вы можете прикинуть возможность более чем двух операций за одно повторение, чтобы снизить количество действий, необходимых для организации цикла. Но так как в большинстве случаев время, требуемое для выполнения таких действий, можно снизить только на один такт, то разворачивание цикла в четыре раза, а не в два, сохранит только 1/4 такта на операцию, что вряд ли стоит усилий, которые будут на это потрачены. Только если можно сохранить еще больше, и если N очень велико, вам стоит думать о разворачивании цикла в четыре раза.
Недостатки слишком большого разворачивания цикла следующие:
- Вам будет необходимо посчитать N MODULO R, где R - это коэффициент разворачивания, и сделать N MODULO R операций до или после основного цикла, чтобы выполнить недостающее количество операций. На это уйдет дополнительный код и плохо предсказуемые операции условного перехоа. И, конечно, тело цикла станет больше.
- Кусок кода обычно выполняется в первый раз гораздо дольше, и чем больше ваш код, тем больше будут связанные с этим потери, особенно, если N невелико.
- Значительное увеличение кода делает работу с кэшем менее эффективной.
Использование коэффициента разворачиванивания, не являющегося степенью 2 делает вычисление N MODULO R довольно трудным, и как правило не рекомендуется, если только N не кратно R. Пример 1.14 показывает, как разворачивать в 3 раза.
Обработка нескольких 8-ми или 16-ти битных операндов одновременно в 32-х битных регистрах (PPro, PII или PIII).
Иногда возможно обрабатывать четыре байта за раз в том же 32-х битном регистре. Следующий пример добавляет 2 ко всем элементам массива байтов.
Пример 2.7:
Код (Text):
Обратите внимание, что перед прибавлением я "спрятал" наивысший бит каждого байта, чтобы не испортить их значение (если результат сложения для конкретного байта превысит 256). Я использую XOR, а не ADD, когда помещаю последний бит на место по той же самой причине.
Этот цикл в идеальном случае занимает 4 такта на итерацию, но в реальном случае он может занять немного больше из-за цепочки зависимости и трудностей с перегруппировкой. На PII и PIII вы можете это делать еще более эффективно, используя регистры MMX.
Следующий пример находит длину строки, заканчивающейся нулем. Он гораздо быстрее, чем REPNE SCASB:
Пример 2.8:
Код (Text):
Этот цикл занимает 3 такта на каждую итерацию, тестируя 4 байта. Строка, разумеется, должна быть выравнена на 4 байта. Код может считать несколько байт из памяти, находящейся за концом строки, поэтому строка не должна находиться у конца сегмента.
Обработка 4-х байт за раз может быть довольно сложной. Код использует формулу, которая генерирует ненулевое значение для байт только тогда, когда байт равен нулю. Это делает возможным протестировать все четыре байта за одну операцию. Этот алгоритм включает вычитание 1 из всех байтов (в инструкции LEA). Я не стал "прятать" наивысший бит перед вычитанием, как я сделал это в предыдущем примере, поэтому операция вычитания может испортить значение следующего байта в EAX, но только если текущий равен нулю, и нам не важно, что будет со следующим байтом. Если бы мы искали нулевой байт в обратном порядке, нам бы пришлось считать двойное слово повторно после обнаружения нуля, а затем протестировать все четыре байта, чтобы найти последний ноль, или использовать BSWAP для изменения порядка байтов.
Если вы хотите найти байт с другим, ненулевым значением, тогда вы можете XOR'ить все четыре байта со значением, которое вы ищете, а затем используйте метод выше для поиска нуля.
Циклы с инструкциями MMX (PII и PIII)
С помощью инструкций MMX мы можем сравнивать 8 байтов за одну операцию:
Пример 2.9:
Код (Text):
В этом цикле 7 мопов для порта 0 и 1, что дает среднее время выполнения 3.5 такта на итерацию. Тесты показали 3.8 тактов, что говорит о том, что ROB справляется с ситуацией достаточно хорошо, несмотря на цепочку зависимости, которая равна 6 мопам. Тестирование 8 байтов меньше, чем за 4 такта гораздо быстрее, чем REPNE SCASB.
Циклы с плавающими инструкциями (PPro, PII и PIII)
Методы оптимизирования циклов с плавающей запятой примерно те же, что и для целочисленных циклов, но вы должны еще больше остерегаться цепочек зависимости из-за долгого времени выполнения инструкций.
Предположите код на языке C:
Код (Text):
Этот кусок кода (под названием DAXPY) является ключем к решению линейных уравнений.
Пример 2.10:
Код (Text):
Цепочка зависимости длиной в 10 тактов, но цикл занимает только 4 такта на итерацию, потому что он может начать новую операцию еще до того, как выполнена предыдущая. Цель выравнивания - предотвратить 16-ти байтную границу в последнем БДИ.
Пример 2.11:
Код (Text):
Здесь мы используем тот же самый трюк, что и в примере 2.3. В идеальном случае, этот цикл будет занимать 3 такта, но измерения говорят примерно о 3.5 в виду длинной цепочки зависимости. Разворачивание цикла сэкономило немного.
Циклы с инструкциями XMM (PIII)
Инструкции XMM на PIII позволят вам оперировать четырьмя числами с плавающей запятой одинарной точности одновременно. Операнды должны быть выравнены на 16.
Алгоритм DAXPY не очень подходит для инструкций XMM, потому что точность невелика, может не быть возможности выравнять операнды на 16, поэтому вам потребуется дополнительный код, если количество операций не кратно четырем. Тем не менее, я покажу вам код в качестве примера цикла с инструкциями XMM:
Пример 2.12:
Код (Text):
Цикл L1 занимает 5-6 тактов на 4 операции. Инструкции с ECX были помещены до и после 'MULPS XMM0, XMM1', чтобы избежать задержки чтения регистра, которую бы сгенерировало чтение двух частей регистра XMM1 вместе с ESI и EDI в RAT. Дополнительный код после L2 заботится о ситуации, когда N не делится на 4. Обратите внимание, что этот код может прочитать несколько байтов после конца A и B. Это может задержать последнюю операцию, если в этих байтах не находились нормальные числа с плавающей запятой. Если возможно, поместите в массив какие-нибудь дополнительные данные, чтобы сделать количество операций кратным 4 и избавиться от лишнего кода после L2. © Агнер Фог, пер. Aquila
Оптимизация для процессоров семейства Pentium: 25. Оптимизация циклов (все процессоры)
Дата публикации 22 авг 2002
