Intel® Architecture Optimization (24512701.pdf) - "When programming in assembly language, try to schedule your instructions in a 4-1-1 µop sequence ... that can be decoded during one clock cycle." Agner Fog, пер. Aquila (www.wasm.ru) - 15. Доставка инструкций (PPro, PII и PIII) " ... на выполнение цикла 1000 раз уйдет 6000 тактов ... Если вы перегруппируете цикл, так чтобы инструкции для D1 или D2 не попадали в начало БДИ, тогда выполнение цикла заняло бы еще меньше - 5000 тактов." Код (Text): ====================================================================== ========== <font color="green]адрес опкод инструкция длина мопы декодер</font><!--color--> ===================================================================== = ========== 00402490 |. B9 E8030000 |MOV ECX,3E8 | 5 1 D0 00402495 |> 8906 |MOV [ESI],EAX | 2 2 D0 00402497 |. C705 00104000 00000000 |MOV DWORD PTR [401000],0 |10 2 D0 004024A1 |. 8D98 C8000000 |LEA EBX,[EAX+C8] | 6 1 D1 004024A7 |. C606 00 |MOV BYTE PTR [ESI],0 | 3 2 D0 004024AA |. 0FBDD0 |BSR EDX,EAX | 3 2 D0 004024AD |. C646 01 00 |MOV BYTE PTR [ESI+1],0 | 4 2 D0 004024B1 |. 49 |DEC ECX | 1 1 D1 004024B2 |.^ 75 E1 |JNZ SHORT 00402495 | 2 1 D2 ================================================================================ Образовательная задачка - уменьшить кол-во тактов перестановкой инструкций (ещё удалять, изменять их нельзя, можно манипулировать длиной их опкодов или добавлять инструкции) Тест в аттаче (можно править и сразу смотреть результат), на Coppermine (6.8.6) выполняется за 6010 тактов (10 возможно погрешность), на Northwood (F.2.9) за 7488 (собственно я не знаю, можно ли вообще применять 4-1-1 µop sequence к P4, AMD) 2096292434__testloop.zip
Кажется я разобрался Код (Text): ====================================================================== ================ <font color="green]адрес опкод инструкция длина мопы декодер такты</font><!--color--> ====================================================================== ================ <font color="blue]нечётные проходы цикла</font><!--color--> ====================================================================== ================ 00402490 |. B9 E8030000 |MOV ECX,3E8 | 5 1 D0 00402495 |> 8906 |MOV [ESI],EAX | 2 2 D0 1-й 00402497 |. C705 00104000 00000000 |MOV DWORD PTR [401000],0 |10 2 D0 2-й 004024A1 |. 8D98 C8000000 |LEA EBX,[EAX+C8] | 6 1 D1 004024A7 |. C606 00 |MOV BYTE PTR [ESI],0 | 3 2 D0 3-й 004024AA |. 0FBDD0 |BSR EDX,EAX | 3 2 D0 4-й 004024AD |. C646 01 00 |MOV BYTE PTR [ESI+1],0 | 4 2 D0 5-й 004024B1 |. 49 |DEC ECX | 1 1 D1 004024B2 |.^ 75 E1 |JNZ SHORT 00402495 | 2 1 D2 ====================================================================== ================ <font color="red]* первая инструкция (mov ecx,1000) через раз попадает в БДИ, но декодируется только 1 раз (при первом проходе), т.ч. её такт не считаем * т.к. в последнем БДИ (блоки отделены строкой) есть переход 16-ти байтной границы A>B то следующий БДИ начнется с инструкции по адресу 00402495</font><!--color--> ===================================================================== = ================ <font color="blue]чётные проходы цикла</font><!--color--> ====================================================================== ================ 00402495 |> 8906 |MOV [ESI],EAX | 2 2 D0 1-й 00402497 |. C705 00104000 00000000 |MOV DWORD PTR [401000],0 |10 2 D0 2-й 004024A1 |. 8D98 C8000000 |LEA EBX,[EAX+C8] | 6 1 D0 (D1) 3-й 004024A7 |. C606 00 |MOV BYTE PTR [ESI],0 | 3 2 D0 4-й 004024AA |. 0FBDD0 |BSR EDX,EAX | 3 2 D0 5-й 004024AD |. C646 01 00 |MOV BYTE PTR [ESI+1],0 | 4 2 D0 6-й 004024B1 |. 49 |DEC ECX | 1 1 D0 (D1) 7-й 004024B2 |.^ 75 E1 |JNZ SHORT 00402495 | 2 1 D1 ====================================================================== ================ <font color="red]* Первая инструкция в БДИ всегда идет в D0, по-этому LEA с 1 мопом (могла бы уйти в D1 или D2) займет такт, это слабое место * Второе слабое место - DEC ECX, тоже попадает в начало БДИ, ещё 1 такт лишний * В последнем БДИ нет перехода 16-ти байтной границы, по-этому следующий блок начнется с первой "16-aligned" инструкции, т.е. 00402490 (блоки будут смещатся через раз) ** цикл выполняется 5*500 + 7*500 = 6000 тактов</font><!--color--> ====================================================================== ================
Методом перебора нашел решение, а потом понял почему так получается , можно BSR EDX,EAX переместить в начало цикла (на метку) или после MOV [ESI],EAX Код (Text): ====================================================================== ================ <font color="green]адрес опкод инструкция длина мопы декодер такты</font><!--color--> ====================================================================== ================ <font color="blue]все проходы цикла</font><!--color--> ===================================================================== ================= 00402490 |. B9 E8030000 |MOV ECX,3E8 | 5 1 D0 00402495 |> 0FBDD0 |BSR EDX,EAX | 3 2 D0 1-й 00402498 |. 8906 |MOV [ESI],EAX | 2 2 D0 2-й 0040249A |. C705 00104000 00000000 |MOV DWORD PTR [401000],0 |10 2 D0 3-й 004024A4 |. 8D98 C8000000 |LEA EBX,[EAX+C8] | 6 1 D1 004024AA |. C606 00 |MOV BYTE PTR [ESI],0 | 3 2 D0 4-й 004024AD |. C646 01 00 |MOV BYTE PTR [ESI+1],0 | 4 2 D0 5-й 004024B1 |. 49 |DEC ECX | 1 1 D1 004024B2 |.^ 75 E1 |JNZ SHORT 00402495 | 2 1 D2 ====================================================================================== <font color="red]* Первая инструкция всегда попадает в БДИ, но декодируется только на первом проходе * Слабые места уходят в D1, по-єтому тактов не занимают * В последнем БДИ есть переход 16-ти байтной границы A>B, значит после неё всегда будет выполнятся 00402495, смещений не будет (цикл стабильный) ** выполняется 5*1000 = 5000 тактов</font><!--color--> ===================================================================== =================
Оптимизация 4-1-1 имеет смысл только для процессоров семейства Intel P6. Там параллельно работают 3 декодера, один сложный (который декодирует команды включающие более одной микрооперации) и 2 простых (декодируют команды которые включают только одну микрооперацию). Если поток команд оптимизирован по правилу 4-1-1 то не будет задержек декодирования. Для P4 такая оптимизация бессмысленна, потому что там только один декодер.
Такая оптимизация видимо не приносит ухудшений для более современных камней, по-этому нельзя ею пренебрегать, программируя на "широкую публику" Видимо его внутренности слишком отличаются, когда нибудь доберемся и до них
S_T_A_S_ Стянул AMD Athlon™ Processor x86 Code Optimization Guide, я так понял там надо остерегатся Decode Type - VectorPath, потому что только одна такая инстр-ция может декодироватся за такт где-то в MROM (блокируя DirectPath декодер), а инстр-ции DirectPath могут аж 3 декодироватся directly in hardware. Теперь думаю, можно ли как-то в 11 тактов это раскидать
"The AMD Athlon processor instruction fetcher reads 16-byte aligned code windows from the instruction cache. The instruction bytes are then merged into a 24-byte instruction queue. On each cycle, the in-order front-end engine selects for decode up to three x86 instructions from the instruction-byte queue." Ещё бы разобратся с влиянием на декодирование этой выборки 3-х инструкций из 24-х байтной очереди, потом можно будет об P4 полялякать, кстати у Агнера (англ. pdf на его сайте) он неплохо освещен (возможно поверхностно, но к каждой инстр-ции есть её мопы, порты, латентность и т.д.)
bogrus > Его и на intel'ах нужно остерегаться, просто они не делят явно. но думаю всё равно у них есть инструкции которые не могут выполняться с другими, поскольку являются по сути микропрограммами, например daa и прочие медленные. > Вот поэтому я и говорю всегда, что теория это может быть и хорошо, но практика показывает, что bsr всёже спаривается, только плохо ЗЫ: lea vector path, когда 16 битная 52961409__bsr.PNG
Да, на рис. видно что 3 DirectPath спариваются, а jnz не влезает в тройку, хотя bsr их и не ждет. И расстояние от одного jnz (темно-зелёный RESP Complete) до следующего 11 тактов, раскинем их примерно так Код (Text): ====================================================================== ======================= <font color="green]адрес опкод инструкция длина Decode Execute такты Type Latency</font><!--color--> ===================================================================== ======================== 00402490 |. B9 E8030000 |MOV ECX,3E8 | 5 DirectPath 1 00402495 |> 0FBDD0 |BSR EDX,EAX | 3 VectorPath 10 1-8-й 00402498 |. 8906 |MOV [ESI],EAX | 2 DirectPath 1 9-й 0040249A |. C705 00104000 00000000 |MOV DWORD PTR [401000],0 |10 DirectPath 3 9-й 004024A4 |. 8D98 C8000000 |LEA EBX,[EAX+C8] | 6 DirectPath 2 9-й 004024AA |. C606 00 |MOV BYTE PTR [ESI],0 | 3 DirectPath 1 10-й 004024AD |. C646 01 00 |MOV BYTE PTR [ESI+1],0 | 4 DirectPath 1 10-й 004024B1 |. 49 |DEC ECX | 1 DirectPath 1 10-й 004024B2 |.^ 75 E1 |JNZ SHORT 00402495 | 2 DirectPath 1 11-й =============================================================================================
bogrus > "выполняется за 6010 тактов (10 возможно погрешность)" Скорее всего 10 тиков - это непредсказанный переход при выходе из цикла (латентность непредсказанного перехода сравнима с длиной пайплайна - для P2,P3 это 10-12, для P4 ~20). > "Методом перебора нашел решение, а потом понял почему так получается , можно BSR EDX,EAX переместить в начало цикла (на метку) или после MOV [ESI],EAX" Это не единственное решение. Перебор рулит когда лень выписывать длины инструкций и число мопов. А здесь уже все расписано. Один пример - с точки зрения декодирования BSR и MOV BYTE [ESI],0 эквивалентны (обе по 3 байта и 2 мопа) и если их переставить, то ничего не изменится. Чему нас учит Агнер ? Во-первых, не стоит пренебрегать рекомендацией по выравниванию начала цикла. Если мы вставим align 16 перед @@, то получим в добавок 16-5=11 нопов, 2 из которых декодируются вместе с MOV ECX,1000, а 9 оставшихся за 3 такта (по 3 штуки за такт на D0-D2). Ес-но 3 тика в оверхеде по сравнению с 5000 это мелочь. От выравнивания реальной пользы может и не быть (в смысле уменьшения числа тиков на цикл), но зато получаем 100% предсказуемые результаты, т.к. первый БДИ всегда будет начинаться с первой инструкции цикла. Далее, вместе с анализом декодирования на D0-D2 следует учитывать и длину инструкций, чтобы они "плотнее" вписывались в 16 байтные блоки и не разбивались 16-байтными границами. В данном случае все тело цикла составляет 31 байт. При "плотном" размещении все уложится в два 16-байтных блока, а при "неудачном" в три. Считаем, что метка цикла выравнена, тогда в исходном варианте первые инструкции расположены неудачно (2+10+6), LEA не попадает полностью в первый блок и 4 байта первого блока летят на ветер, в итоге получим три блока вместо двух. Вывод - расположить инструкции так, чтобы они вписывались в два блока. Учитываем ограничения: DEC и JNZ трогать нельзя и перед ними должна идти инструкция на D0, соответсвенно LEA, как единственная 1моп, не должна стоять в начале БДИ и перед DEC. Возможно несколько вариантов размещения. В частности - вариант bogrus. Первый блок 3+2+10=15 - хорошо (можно еще и NOP добавить до 16-ти). Поскольку эти инструкции независимы по данным и не конфликтуют по портам, то их можно переставить и в другом (любом) порядке, а можно и BSR поменять на MOV BYTE [ESI],0 или MOV BYTE [ESI+1],0. Ну и т.п. - только на зависимость по портам не "нарваться". > "можно будет об P4 полялякать" О декодировании на P4 особо не "полялякаешь", т.к. в рамках wintest декодирование на P4 "пощупать" невозможно - оно осуществляется только при первом проходе, а дальше декодированные мопы извлекаются из кэша со скоростью 3 шт. за такт. Поэтому перестановки инструкций на P4 очень слабо влияют на результат (ес-но "близкие" перестановки в области "видимости" реордер-буфера). А у Агнера P4 освещен достаточно, но многие вещи - на уровне догадок и предположений (например, механизм предсказания переходов, работа MMX и FPU на половинной частоте).
leo > Почему же нельзя? В данном случае dec можно в любое место ставить (может и лишние 10 тактов пропадут .
S_T_A_S_ > "может и лишние 10 тактов пропадут" Если верить в чудеса и пренебрегать "теорией", то может и пропадут, а по жизни врядли. 1) 10 лишних тиков на 1000 проходов никаким иным способом, кроме как задержкой при входе в цикл и выходе из него не объяснить. Для входа это многовато, а для выхода с ошибкой предсказания перехода - в самый раз (с учетом длины конвейера на P3). 2) Динамическое предсказание перехода в IA-32 делается исключительно на основании истории предыдущих переходов (ес-но кроме статического предсказания при самом первом проходе, который в тесте от Агнер-bogrus исключается из рассмотрения). Поэтому положение DEC относительно JNZ никакой роли на предсказание оказать не может. Окончательное решение о переходе принимается по JNZ, которая стоит последней в цикле. Для бесперебойной работы декодера на момент декодирования JNZ уже должен быть загружен новый 16-байтный блок инструкций. И соответственно когда JNZ выполняется, параллельно уже идет декодирование нового блока. Это и есть принцип спекулятивного исполнения, когда начинают выполнять действия без 100% гарантии того, что они понадобятся. Если JNZ подтверждает, что этот блок был выбран верно, то все OK и обработка продолжается. Если нет, то все спекулятивные действия после JNZ отменяются и происходит выборка нового блока инструкций с соответствующей задержкой.
leo Ну иногда и можно, потому что мы всегда . На циклах нужно анализировать (это совсем не сложно) последний БДИ с переходом, чтобы он не приводил к задержкам декодера Код (Text): ===================================================================== ================= <font color="green]адрес опкод инструкция длина мопы декодер такты</font><!--color--> ====================================================================== ================ 004024A0 |> 0FBDD0 |BSR EDX,EAX | 3 2 D0 1-й 004024A3 |. 8906 |MOV [ESI],EAX | 2 2 D0 2-й 004024A5 |. C705 00104000 00000000 |MOV DWORD PTR [401000],0 |10 2 D0 3-й 004024AF |. 49 |DEC ECX | 1 1 D1 004024B0 |. C606 00 |MOV BYTE PTR [ESI],0 | 3 2 D0 4-й 004024B3 |. C646 01 00 |MOV BYTE PTR [ESI+1],0 | 4 2 D0 5-й 004024B7 |. 8D98 C8000000 |LEA EBX,[EAX+C8] | 6 1 D1 004024BD |.^ 75 E1 |JNZ SHORT 004024A0 | 2 1 D2 ====================================================================================== <font color="red]* В последнем БДИ 2-е декодируемые группы, 16-ти байтной границы нет, границы нет и в первой инстр-ции после перехода, это к задержке декодера не ведет, следующий БДИ начнется с инстр-ции после перехода т.е. 004024A0 (хотя БДИ в любом случае начнется с этой инструкции, т.к. она выровнена на 16) ** выполняется 5*1000 = 5000 тактов</font><!--color--> ===================================================================== ================= Да, можно, но ускорения в данном случае не приносит, имеем лишние нопы для выравнивания, и соотв. немного искаженный ними результат тестирования Ну тогда можно анализировать не декодирование, а выполнение инстр-ций по тактам на P4, ведь тест чего-то все-равно показывает, давайте оперировать такт-ФАКТАМИ, чтобы они не оставались попугаями
На Northwood (F.2.9) тест показывал 7488 (это селерон 2.40GHz), если брать данные из таблицы Агнера, то на тело цикла приходилось 16 мопов Код (Text): ====================================================================== ======================= <font color="green] additional execution compat uops microcode latency latency troughtput port unit subunit /notes</font><!--color--> ===================================================================== ======================== MOV m,r 1 0 1 2 0 store 86 b,c MOV m,i 3 0 2 0,3 store 86 LEA r,[r+r/i] 1 0 0.5 0.5-1 0.25 0/1 alu0/1 86 BSR r,r 2 0 4 0 2 1 int mmxsh 386 DEC r 2 0 0.5 0.5-1 0.5 0/1 alu0/1 86 Jcc short/near 1 0 0 2-4 0 alu0 branch 86 ============================================================================================= <font color="red]b) Uses an extra uop (port 3) if SIB byte used. A SIB byte is needed if the memory operand has more than one pointer register, or a scaled index, or ESP is used as base pointer. c) Add 1 uop if source or destination, but not both, is a high 8-bit register (AH, BH, CH, DH</font><!--color-->) Если брать з мопа за такт, то получится где-то (16/3)*1000=5333 тика, нехватает пару тысяч, где они могут осесть? Может BSR (latency - 4)?
Нда, чтобы в уме высчитать такты для 4пня, нужно сперва подсчитать Trace Cache Entries для каждой инструкции, я застрял на LEA, прийдется скурпулезно переводить эту главу из Агнера, т.к. видимо больше это нигде не освещено
bogrus "Скрупулезно" ИМХО не стоит. См. у Агнера раздел Bottlenecks in P4. В данном случае узкое место это не доставка мопов из кэша. Да и вообще она редко бывает критичной на P4, т.к. 3 шт. за такт это довольно быстро. Здесь дело и не в BSR, а в MOV m,r. Ради эксперимента убери LEA и BSR и получится немногим меньше ~7048, т.е. 7 тиков на цикл (довесок в 48 тиков это видимо ~20 на выход из цикла и ~28 на выталкивание буферов в cpuid). Причем эти тики не зависят от способа адресации - можно поставить 4 штуки mov [esi],eax и будет тоже самое, значит число entries роли здесь не играет и выборка из кэша тоже. А все дело в "загадочной" инструкции mov m,r. У Intel про latency и throughput записи в память вообще ничего не сказано. Единственное, пару раз подчеркивается что на запись в память не распространяется изменение порядка и спекулятивное исполнение, т.е. они не могут переставляться и видимо ждут "решения" JNZ. У Агнера интересные цифры: latency = 1, а throughput = 2 !!! А в нашем случае получается 1.5-1.75. Еще один эксперимент - оставляем только один MOV и затем добавляем по одному. Получаем Код (Text): mov тик/цикл прирост 1 2 2 3.5 +1.5 3 5.25 +1.75 4 7 +1.75 5 9 +2 ;здесь кстати возможен переход ко второму 32 байтному блоку мопов 6 10.5 +1.5 Кратность 0.5-ти обяснить можно, т.к. запись идет через double speed ALU0 и прием мопа store возможен во втором полуцикле, а вот 1.75 видимо можно обяснить только чередованием 1.5 и 2 через цикл. PS: Что касается BSR r,r то Агнер ее "преукрашивает" - у него latency\throughput равны 4\2, а Intel приводит 8\4. По жизни, если оставить в данном тесте только BSR получается 4 тика на цикл - фиг его знает: толи по 4 без перекрытия, толи по 8 с перекрытием на 4.
