Планирование потока инструкций

Это зигзаг-сканирование для реализации JPEG кодирования. Ворды в последствии кладутся в то же место, откуда были взяты - просто порядок их другой. При перестановке параллельно выполняется детектирование последней ненулевой тетрады для последующих этапов кодирования. Использование АЛУ пересылок приводит к значительному замедлению алгоритма, поскольку требует cmp/cmov.. на каждый поднятый ворд.

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

Может быть мои вопросы и выглядят чайниковскими, поскольку "мегабайты информации" - это все же - PDF'ы - весь Ангер Фог, Intel Optimization Manual и еще три части IA-32 Intel Architecture Software Developer's Manual плюс все что нашел по вопросу в конференциях на Гугле. К сожалению, то, что я прочитал не позволило мне сформировать набор "элементарных кодинг-рулов" для написания оптимального ассемблерного текста.

 

Описка вышла Дело в том, что в IA-32 L=4 и T=1, а у Фога L=3 и T=2
Спрашивается кому верить ? Сначала мне на вскидку показалось, что прав Фог, т.к. 4 pinsrw с разными mm дают те же 8 тиков, хотя при T=1 должно быть 4 тика. Но с другой стороны при T=2 и L=3-4 никак не может получиться 8 тиков на простой цикл из 4 pinsrw с одним mm-регистром.

По видимому тут действительно все хитрее. Дело в том, что и по Фогу и по IA-32 pinsrw состоит из двух мопов - один производит сдвиг операнда на MMX_SHIFT, а второй комбинирует сдвинутое значение с содержимым mm-регистра на MMX_MISC. Так вот, если предположить, что эти мопы выполняются независимо и имеют обычные для MMX значения L=2 и Т=1, то все становится на свои места. Вот не поленился симуляцию пайпа расписать:

Код (Text):

1. movzx   dxx..................... d - dispatch, x - execute, промежуточные стадии опущены
2. pinsrw  d..xx................... uop1: temp <- (r32 shl imm8*16)
3.         d....xx................. uop2: mm <- ((mm and mask) or temp)
4. movzx   .dxx....................
5. pinsrw  .d..xx.................. uop1 зависит от movzx и свободного слота запуска в порт p1
6.         .d.....xx............... uop2 зависит от предыдущего uop2 и свободного слота
7. movzx   ..dxx...................
8. pinsrw  ..d...xx................
9.         ..d......xx.............
10. movzx   ...dxx..................
11. pinsrw  ...d....xx..............
12.         ...d.......xx...........
13. sub     ....dx.....|............
14. jnz     ....dx.....|............
15. ===================|============
16. movzx   .....dxx...|............
17. pinsrw  .....d....xx............
18.         .....d.....|.xx.........
19. movzx   ......dxx..|............
20. pinsrw  ......d....|xx..........
21.         ......d....|...xx.......
22. movzx   .......dxx.|............
23. pinsrw  .......d...|..xx........
24.         .......d...|.....xx.....
25. movzx   ........dxx|............
26. pinsrw  ........d..|....xx......
27.         ........d..|.......xx...  <-- 8 тиков на 4 ворда
28. sub     .........dx.............
29. jnz     .........dx.............

Дальше картина повторяется - парные мопы pinsrw удачно дополняют друг друга. Поэтому и pxor тут ничего не дает кроме ухудшения, и запись в разные регистры дает те же 2 такта на ворд, т.к. на запуск 2-х мопов pinsrw требуется два слота, а не один. ИМХО, такое объяснение выглядит более правдоподобно, чем происки реплея или других хитростей планирования
Так что, видимо, из pinsrw больше скорость не выжмешь и стоит подумать чем его заменить

Не совсем понял, что есть тетрада (qword ? на входе или переставленный ?) и что с ней делать в случае обнаружения

По поводу pinsrw с операндом памяти: у меня на Northwood'e если только читать в mm-регистры (без обратной записи) получаются те же 2 тика на ворд, что и с movzx.
Насчет "скрытых" регистров: на самом деле в P4 все регистры "скрытые" и всякие EAX и т.п. это лишь ссылки на один из множества физических регистров RF, в котором на данный момент хранится результат последней ушедшей в отставку операции. Суть переименования регистров как раз заключается в том, что при каждой записи в EAX (и т.д.) ему отводится новый "скрытый" регистр, а старое значение сохраняется для чтения предыдущими операциями, которые могли задержаться из-за изменения порядка. А суть аргумента в пользу операций с памятью заключается в том, загрузка производится в "анонимный" регистр, не сопоставленный ни одному из программно доступных регистров, т.е. не мы позволяем процессору, а процессор позволяет нам не тратить на это дело программно доступные регистры

 

Большое спасибо за симуляцию пайпа Теперь все стало намного понятнее.

 

Пример "resource constraint" и как добавление инструкции может уменьшать время исполнения.
Пытаемся реализовать зигзаг-перетасовку вордов на обычных mov - читаем ворды из одного блока и пишем в другой.
Для начала проверяем работу цикла из N пар movzx r32,m16 + mov m16,r16 (т.к. цикл проще тестировать - на него не влияет дискретность rdtsc). Проверяем на P4 Northwood (model 2) и получаем первый "странный" результат: при N=4 цикл выполняется 7 тактов, при N=8 - 14 тактов и т.д. Спрашивается почему не 1 или 2 такта на ворд, а что-то среднее ближе к 2-м. Из табличек Фога может показаться, что troughput mov m,r составляет T=2 тика, но при простых способах адресации согласно тому же Фогу моп store-address в порт p3 с Т=2 отсутствует, есть только моп store-data в порт p0 c Т=1, т.е. по идее можно получить скорость 1 ворд/такт. Значит мы тут наступаем на какие-то "грабельки" и не иначе как на переполнение очереди mem-планировщика и числа буферов записи.
Чтобы разобраться в чем дело придется перейти от цикла к репиту и смотреть как меняется задержка при увеличении числа пар, учитывая дискретность rdtsc. В результате получаем нечто похожее на кусочно-линейное нарастание задержки на 4 такта через каждые 4 пары до N = 24 (28 тиков = 24+4) и резкое ухудшение при N=25 (до 44 тиков). Загадка ? Да нет, почти во всех мануалах сказано, что число буферов записи = 24 в P4 model <= 2 и 36 в старших моделях, соответсвенно одновременно в очереди могут находится не более 24 (36) мопов записи. Доставка из Т-кэша идет со скростью 3 мопа за такт, а исполнение - 2 мопа за такт, поэтому 24 мопа записи доставляются за 16 тактов и исполняются за 24 - и того и другого недостаточно, чтобы выполненные мопы успевали уходить в отставку и освобождали буферы - происходит переполнение и блокировка. Сам механизм блокировки не совсем ясен (то ли возникает реплэй, то ли просто приостановка конвеера), но это и не столь важно.
Как с этим бороться ? Например, уменьшить число записей за счет объединения вордов в дворды:

Код (Text):

1.   repeat N
2.   ;X = zigzag[%-1]*2    
3.   ;Y = zigzag[%]*2
4.   movzx eax,word[esi+Y]
5.   shl eax,16
6.   add ax,word[esi+X]     ;или or
7.   mov [edi+(%-1)*4],eax
8.   ;or eax,edx            ;или add, но только не or+or
9.   end repeat

В результате число сохранений уменьшается вдвое, общее число мопов за счет арифметики увеличивается, скорости поступления мопов и их исполнения (почти) выравниваются и блокировка очереди (почти) исчезает - получаем "заветную" скорость копирования (почти) 1 ворд за такт. "Почти" - означает, при repeat наблюдаются дополнительные скачки-отставания по ~4 тика при N ~17 и N ~29 и в результате на 64 ворда получается 72-76 тиков вместо 64, в то время как при использовании цикла получается точно 1 тик в пересчете на ворд. Эту загадку можно объяснить тем, что скорость поступления мопов при repeat остается несколько выше скорости исполнения - за два такта доставляется 6 мопов, а исполняется 5. В результате на 16 блоках накапливается 16 ожидающих мопов и на 17-м блоке происходит переполнение очереди mem-планировщика (в Northwood - 16 мопов, если верить Ф-центру . После некоторой задержки очередь частично освобождается и следующее переполнение наступает несколько раньше, чем через 16 блоков. Ес-но возникает идея выравнять скорости доставки и исполнения, добавив "лишний" моп АЛУ. Тут есть еще одна "хитрость". Если для объединения вордов используется add, то без разницы какой моп мы добавляем or\and\xor или add\sub - ситуация улучшается и в результате стабильно имеем 68 тиков на 64 ворда. А вот если для объединения использовать or\xor, то добавление мопа add\sub улучшает ситуацию, а or\xor\and резко ухудшает - возникает конфликт портов, т.к. add\sub могут идти в p0 или в p1, а логика только в p0. Вот что значит "мистика" и как с ней бороться )

PS: к or eax,edx можно прикрутить детектирование ненулевой тетрады, только лучше без тормозных setcc,cmovcc и sbb. Только не совсем понятно, что дальше с этим детектором делать

 

leo

К сожалению во время копирования нажал не ту кнопку и часть поста №23 удалилась.

Фактически необходимо знать индекс последней ненулевой тетрады или пары, как в этом случае. После зигзаг сканирования ненулевые коеффициенты упаковываются RLE. Цикл упаковки RLE сам по себе очень медленный и с этим сделать ничего нельзя, поскольку исполнение вариантов его тела управляется входной последовательностью данных - если будет интересно - расскажу подробнее. В общем случае необходимо сделать 64 итерации тела цикла RLE кодера. Это крайне расточительно, поскольку каждая итерация содержит как минимум 3 условных перехода в лучшем случае. Потому выяснение последнего ненулевого элемента в последовательности является очень важной задачей этого этапа. В моем варианте детектора я использовал сравнение с гарантированной установкой CF в случае нулевой тетрады. После этого CF задвигался в некий аккумулятор и по окончании сканирования командой bsr определялся номер последней ненулевой тетрады. Поскольку cmp эффективно является тем же вычитанием, то получение флага CF как признака нулевой пары будет тривиальным сравнением с immediate 1. В случае ненулевой пары флаг не установится и наоборот. К несчастью появится конкуренция по MMX-SHIFT, но это в худшем случае приведет к 96 тактам на 64 слова.

Код (Text):

1.   repeat N
2.   ;X = zigzag[%-1]*2    
3.   ;Y = zigzag[%]*2
4.   movzx eax,word[esi+Y]
5.   shl eax,16
6.   add ax,word[esi+X]     ;или or
7.   mov [edi+(%-1)*4],eax
8.   cmp eax,1            ;или add, но только не or+or => cmp = sub = add ?
9.   rcl edx,1
10.   end repeat

 

Здесь вот leo NetBurst грязью обливает, а AMD64-то тоже... того... не без греха... или не без глюка...
Попытался потестить на тему предсказания переходов 64-й... результаты несколько смущают.
Во-первых столкнулся с тем, что если производить сериализацию классически по cpuid, это начисто отбивает предиктору нюх. Поэтому использую всякие тормоза вроде деления, чтобы гарантировано произошел retirement у переходов измерительного цикла, затем зачитываю pcm 0 и pcm 1, которые науськаны на события C3h (retired mispredicted branch) и C4h (retired taken branch) - это для контроля, что наблюдаю именно интересующий переход, далее собственно переход, опять тормоза, чтобы он успел уйти в отставку, читаю счетчики, нахожу разность - 0 или 1, т.е. predict/mispredict и taken/not taken. Если я чего-то натупил, поправьте, пожалуйста. Так вот - результаты очень интересные получаются - сначала, как и написано в мануале переход предсказывается как невыполняемый (точнее, он вовсе не рассматривается и в таблицу не заносится); далее при первом его выполнении происходит mispredict и переход рассматривается как всегда выполняемый; далее при первом следующем невыполнении - всегда mispredict и начинается самое интересное - динамическое предсказание (до этого все в соответствии с мануалами) так вот - на паттерне tntntntnt... (где t - taken, n - not taken) и на ttttnnnnttttnnnn... результат как ни странно вполне одинаковый - где-то с ~24-й попытки предиктор перестает ошибаться. Казалась бы - адаптироваться к шаблону tntn... можно быстрее, чем к ttttnnnnttttnnnn... , но похоже что ему это пофиг Кроме того последовательные выполнения дают неодинаковые результаты - такое ощущение, что таблица у него не чистится... Иногда выпадает восемь-девять миспредиктов подряд, причем на разных шаблонах - ???. И вообще - если верить Фогу, то к шаблону длиной 8 он (процессор, а не Фог) должен адаптироваться максимум за 16 проходов - реально - фиг. Кто-нибудь может прокомментировать сие безобразие?

 

Ustus
А какое принципиальное значение имеет скорость обучения процессора шаблону переходов? Главное знать принцип построения шаблона переходов, который может быть предсказан безошибочно. При большом количестве переходов начальные 16 или даже 32 из них не окажут серьезного влияния на производительность. Дополнительные миспредикты, с моей точки зрения, могут быть связаны с переключениями контекста и вытеснением из таблицы частично обученного значения. В остальном более подробно прокомментировать не смогу, поскольку процессор на уровне микроархитектуры знаю весьма посредственно.

 

To leo

Прошу тебя написать доку по кэш-памяти, вопросами обеспечим!

Почему:
1. Нехватка четко структированного документа
2. Время шагает и то что в Агнере Фоге на текущий день иногда может не подходить(предположение)
3. Да и вообще, пора бы пополнить еще одним шедевром, а то на www.wasm.ru они не часто появляются!

 

v_mirgorodsky

Сам же себе и отвечаешь:

А каже я его буду знать, если он работает не так, как я предполагаю, исходя из того, что знаю?

вот-вот, и я такой же. И только многомудрый leo реет смело и свободно над седым от дыма процом...

 

leo

посмотри пожалуйста zip-файл - там Excel таблица с моей первой попыткой научного планирования потока инструкций для P4. Код, который там представлен занимается переносом части внутреннего буфера во внешнюю память. Исходный внутренний буффер адресуется регистром esi, внешний буффер - регистром edi. Во внутреннем буффере находятся слова, к ним добавляется константа из регистра mm7, далее результаты упаковываются командами packuswb в байты и сгружаются во внешнюю память. Для упрощения уз картины исключены команды модификации регистров esi и edi. Они выполняются на блоках ALU, потому я посчитал их влияние несущественным. Команды загрузки регистров mm0-mm3 я изобразил состоящими из двух uop'ов - загрузка 2 такта и собственно занесение в MMX регистр - 6 тактов. Команды выгрузки во внешнюю память я изобразил состоящими из одного uop'а, поскольку я не знаю точно как работают буффера записи. На данный момент получается около 0.6 такта на один перемещаемый байт, хотя по расчету должно получаться меньше 0.4. Я понимаю, что при таких скоростях уже может подтормаживать подсистема памяти, однако цифры практически не изменяются даже если буффера гарантированно помещаются в L2 кеш.

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

 

v_mirgorodsky
Посмотрел. Замечания и красочный вариант "квазинаучной" симуляции см. в аттаче.

Основная ошибка или "описка" - неучет конфликта запуска в порт p1 мопов paddw и packuswb (в последних 3-х блоках правильно, а в первых - нет). В результате скорость исполнения такого цикла (или репита) будет определятся throughput'ом порта p1 - 1 шт. paddw или packuswb за такт, итого 6 тактов на итерацию (в цикле на Northwood'е так и получается).
Не понятно, что означают стадии D1-D3. Если это что-то типа запуска мопов в планировщики, то это не верно, т.к. стадии D3 не могут идти раньше определенного момента, определяемого очередностью поступления мопов в планировщики.

А логика работы планировщиков ИМХО довольно проста.
Во-первых, хотя стадии RAT, Alloc (ROB) и Queue и относят к Out-of-order (OoO) на них соблюдается программный порядок следования мопов и действительное переупорядочивание может происходить только в самих планировщиках. Мопы выбираются из ROB в программном порядке и попадают в очереди планировщиков не более 3-х штук за такт (об этом вроде как нигде не говорится, но делать скорость выборки больше скорости поступления мопов из Т-кэша и ретайрмента не имеет смысла). Это означает, что для тонкой "научной" оптимизации и симуляции работы Exec-core мы должны учитывать упорядоченное поступление мопов в планировщик. Для этого я использую фиктивную стадию d, которая задает точку отсчета времени попадания мопа в очередь планировщика - до этого момента планировщик ничего не может знать о данном мопе и соответственно не может производить с ним никаких действий. В твоем примере это не столь важно, но для кусков кода с быстрыми операциями м.б. существенно, т.к.показывает, что несмотря на готовность операндов и свободные порты моп не может быть выполнен, т.к. он просто еще не попал в планировщик. Для учета этой очередности ес-но нужно знать кол-во мопов операций (смотрим у Фога; если более 1 мопа и не совсем ясно, что они делают, то все равно лучше их учесть в стадиях d, т.к. это влияет на задержку запуска последующих мопов).
Из принципа очередного поступления мопов следует, что "окно анализа" планировщика не является фиксированым и зависит от соотношения скорости запуска мопов в очередь (3 шт.за такт) и скорости их отправки на исполнение. Для быстрых кусков кода исполнение может идти практически "с колес", т.е. все что поступает в планировщики параллелится по разным портам и уходит на исполнение, не создавая никакой очереди. Если же исполнение отстает, то очередь нарастает и может происходить ее переполнение с приостановкой выборки мопов из ROB. Но переполнение очереди не обязательно должно приводить к дополнительным задержкам. По всей видимости "опасны" только переполнения числа операций записи и чтения, т.к. это связано с ожиданием освобождения буферов (см.выше пример с resource constraint), а при переполнении очереди прочих операций просто запуск мопов временно приостанавливается и затем возобновляется без потери тактов. Из принципа очередности запуска также следует, что переполнение очереди "арифметики" блокирует и запуск мопов в очередь чтения\записи. Поэтому в рассматриваемом примере никаких потерь не происходит (по кр.мере в цикле) - очереди периодически блокируются из-за большого числа ожидающих paddw и packuswb и переполнения буферов movq не происходит.

Во-вторых, принцип очередности соблюдается и при переупорядочивании. Т.е. если готовы два или более "равноправных" мопов, претендующих на один порт, то их запуск идет в программном порядке (FIFO). Исключения могут быть только для неравноправных мопов, например для slow и fast мопов может быть логичным независимо от их программного порядка в первом полутакте запускать slow, а во втором - fast. Какая-то более сложная логика выбора врядли задействована (например, data-forwarding, когда результат предыдущей операции сразу подается на вход следующей не дожидаясь записи\чтения из RF - тут можно запросто заблудиться в дебрях, поэтому скорее всего эта фича действует или в ограниченных простых вариантах или вообще "на удачу" - если зависимые мопы сами по себе идут друг за другом).
Соответственно при квазинаучной симуляции для каждого мопа 1) определяем момент, когда готовы операнды в результате завершения предыдущих операций (в соответствии с их латентностью), 2) смотрим свободен ли на данный момент соответствующий порт запуска. Если свободен, то запускаем моп; если занят, то просматриваем цепочку запусков всех предыдущих готовых мопов, в поисках свободного такта запуска с учетом througput данного порта и исп.блока. В рассматриваемом примере на каждом такте идет запуск мопов paddw\packuswb в порт 1, поэтому все последующие мопы вынуждены ждать запуска предыдущих и пристраиваться в хвост и поэтому никакого переупорядочивания этих мопов не происходит. Но в общем случае возможно наличие "дырок", когда более поздний моп может вклиниться в свободный такт между запусками предыдущих и выполниться вне очереди. Иногда такое вклинивание может привести к необходимости коррекции задержки запуска предыдущих по номеру, но исполняемых позднее мопов - например, запустили мы некоторый моп Х по мере готовности операндов в i-м такте, а затем оказалось, что на позицию i-1 вклинивается запуск другого независимого мопа Y в тот же порт\блок, но throughput данного порта\блока > 1 и тогда приходится отодвигать запуск мопа X (разумеется в планировщике все это получается само собой без всяких "возвратов")

PS:
> "Команды загрузки регистров mm0-mm3 я изобразил состоящими из двух uop'ов"
Все операции чтения из памяти в регистры выполняются непосредственно через порт p2 (load) и блоки регистровых пересылок mov\fp_mov порта p0 в этом не участвуют.
Операции записи в память согласно Фогу состоят из мопа store-data в порт p0 и для сложных способов адресации добавляется еще моп store-address в порт p3.

 

Прежде всего, огромное спасибо за информацию.

D1, D2 и D3 - я считал, что после стадии Dispatch мопы попадают непосредственно в очередь запуска на соответствующий порт. А уже соответствующий порт определяет возможность запуска мопа вне/по очереди и собственно запуск его на исполнение. Если бы я проектировал процессор, то я поступил бы именно так, поскольку с моей "электронной" точки зрения так было бы логичнее и эффективнее. Понял, что ошибался, тогда как понимать коментарий Фога на тему возможности эпизодического запуска сразу шести мопов на иполнение?

Еще вопрос. А куда прячется моп загрузки для арифметической операции? Если в примере положить коррекцию не с регистром mm7, а с операндом из памяти? Он же по идее, должен начать конкурировать с операциями загрузки за порт p2?

Плюс к этому можно сказать, что ALU не возможно нагрузить работой в полной мере, поскольку скорость исполнения мопов ALU четыре за такт, а скорость их доставки только 3

Еще один вывод - в P4 при использовании MMX возможно параллельное исполнение только арифметических команд и команд загрузки/сохранения данных. Таким образом PIII должен быть раза в два быстрее чем P4. В принципе - это косвенно подтверждается экспериментально. А Intel Application Note 922 приведена цифра 250 тактов для прямого DCT преобразования для PIII, тот же текст для P4 исполняется в районе 430-440 тактов. Практическая проверка показала 324 MMX сложений, сдвигов, умножений и т.п. Все остальное - работа с памятью - еще 170 операций. Таким образом PIII на частоте 1.1ГГц будет работать аналогично P4 на частоте около 2 с копейками гигагерц.

 

Ну, PIII - не думаю, а вот PM - таки да, где-то в два раза (в среднем, в задачах типа бенчмарков, но не в реальных приложениях типа Win GUI - там разница будет не столь заметна).

 

v_mirgorodsky

Ну положим в Intel тоже не сапожники работают Порт никакую возможность определять не может, т.к. в понимании Intel порт это грубо говоря обычный мукс или по простому разветвитель\распределитель, который в соответствии с управляющими сигналами просто соединяет выходы планировщиков и операнды из RF и bypass-network со входом нужного исполнительного блока. А вот управлением запуском мопов в порты как раз и занимаются планировщики.

P6 (не считая Core 2), P4 и AMD являются 3-way super scalar, т.е. они расчитаны на максимальную среднюю скорость 3 мопа за такт - с такой скоростью работают декодеры (в P4 T-кэш) и ретайрмент, и соответсвенно все остальные блоки примерно расчитаны на такую среднюю скорость (число портов, исп.блоков, очередей, длина очереди и т.п.). Но в лоб трехканальность организована только в AMD для основных GP операций - три идентичных парных канала ALU+AGU, плюс imul на p0, плюс отдельно FPU\SIMD с 3-мя специализированными портами. Итого получается аж до 9 мопов одновременно (хотя в AMD операции op+l\s считаются за один макрооп, отсюда и парные каналы ALU+AGU). Ну а Intel'овские "сапожники" всегда любили экономить на портах и исполнительных блоках и усложнять управление, поэтому у них два-три спецпорта для load\store и два порта на все остальное. В P6 два АЛУ, да и то неполноценные по сравнению с AMD, т.к. shifter\rotater один, поэтому даже номинальные 3 мопа за такт могут достигаться только при сочетании операций ALU\FPU\SIMD с load\store - явный недотяг до заявленных 3-way. Поэтому в P4 Intel'ам надо было как-то увеличивать пиковую нагрузку, но поскольку добавлять лишние порты им "западло", то придумали хитрость c fast-ALU, хотя и тут не обошлось без урезаний - быструю логику почему-то реализовали в единственном экземпляре (порт p0) и второй fast-A(L?)U выполняет только add\sub\mov. Тем не менее пик увеличился хотя и не для всех операций. И это правильно, т.к. никаким переупорядочиванием мопов от dependance chain'ов полностью избавиться невозможно, поэтому на одних кусках кода скорость исполнения может падать, увеличивая очереди ожидающих мопов, зато на последующих независимых кусках код может исполняться быстрее, выбирая мопы из образовавшихся очередей быстрее, чем 3 за такт (за счет распараллеливания по разным планировщикам и портам запуска). Но в любом случае средняя скорость не может превышать 3 мопов (в PM и AMD - макроопов op+l\s), т.к. они поступают в ROB и уходят из него в отставку именно с такой скоростью.

Никуда не прячется, поэтому его и нужно учитывать при симуляции и он ес-но будет конкурировать с другими явными и неявными мопами загрузки. А для операций типа add m32,r32 нужно учитывать моп load в p0, моп add r,r в p0 или p1, моп store-data в p0 и возможно store-address в p3 (при наличии SIB-байта)

Вот такая странная склонность Intel - улучшать одно, ухудшая другое - мне и не понятна. Отсюда и периодические "наезды" на NetBurst ) Остается надеятся на умность и логичность Core 2, хотя кто его знает ...

 

leo

Сегодня таки прикрутил код с зигзагообразным обходом матрицы. Результаты несколько удручающие x86 Family 15 Model 4 Stepping 3 - 2 такта на слово в любых комбинациях. Таки Intel что-то накрутил с исполнительными блоками в этой модели. Жаль, но буду разбираться дальше.

Добавление rcl для построения маски ненулевых коеффициентов увеличивает время до 3.5 тактов на слово - совсем уж безобразный результат. Вообще говоря, возникает впечатление, что Prescott ничего кроме высокой частоты за душой не имеет. Практически любая задача по обработке информации превращается в огромную проблему из-за очень высоких значений латентности его команд.

RCL Reg,1 => T=1,L=6
ADC Reg,Reg => T=3,L=6
SETcc => T=1.5,L=5

Таким образом все, что может дать представление о состоянии CARRY на момент исполнения имеет просто неудобоваримые тайминги. BTW, несколько не сходится картинка с реальностью. Поскольку Latency для RCL равна 6, то добавление RCL к телу зигзаг сканера должно было бы увеличить время до 360 с лишним тактов. С другой стороны Фог дает латенси равной 4 такта, что приблизительно соответствует полученным результатам.

 

v_mirgorodsky

Эт-точно Поэтому для P4 лучше пользоваться cdq (там где это возможно)
Если значения вордов лежат в диапазоне [0..2^15), то можно сделать примерно так

Код (Text):

1. xor ebx,ebx
2. mov ecx,1
3. ;...
4. ;формируем dword в eax
5. ;формируем dword в edx
6. or eax,edx
7. sub eax,1
8. cdq
9. and edx,ecx
10. add ebx,edx
11. add ecx,ecx
12. ;...

PS: Тут видимо можно еще поиграть в перестановки или проанализировать по "научному", т.к. для пробы пока проверил на шару на Pentium D 930 (модель 15.6.2) - похоже есть некоторая зависимость от положения add ecx,ecx , хотя у этого "козла" результаты rdtsc стабильно скачут на 15 тиков, а иногда и на +-30 зашкаливают ((

Ну а если ворды знаковые, то придется еще поизвращаться

 

В моем случае ворды знаковые, в интервале [-2047..2047], потому пришлось наложить маску 0x7FFFFFFF сразу после sub eax,1. Со времени опубликования моего предыдущего поста я думал о путях замены RCR на что-то другое, однако до CDQ сразу не додумался. Короче, в финальном варианте мой код выглядит следующим образом:

Код (Text):

1.     movzx   eax,word ptr [esi +  2]
2.     shl     eax,16
3.     movzx   ebx,word ptr [esi +  0]
4.     or      eax,ebx
5. //  add     ax,word ptr [esi +  0]
6.     mov     [edi],eax
7.     and     eax,0x7FFFFFFF
8.     sub     eax,1
9.     cdq
10.     sub     ecx,edx
11.     lea     ecx,[ecx + ecx]

Замена add ax,word ptr [esi] на movzx/or неожиданно ускорила последовательность - не кардинально, на 5-10 тактов на 64 словах, но все же ускорила. Замена последнего add ecx,ecx на lea тоже сказалась положительно Теперь все занимает около 2 тактов на слово )

P.S. C CDQ согласен, более того, в моем конкретном случае это оказалось очень хорошим решением, поскольку содержимое регистра eax для последующих итераций не имело значения. Однако в общем случае CDQ требует модификации регистра eax и уничтожение содержимого edx. К сожалению выгрузка/загрузка "рабочих" данных даже с одним edx приводит к нивелированию любых преимуществ CDQ по сравнению с тем же RCR/RCL.

 

Есть еще одна идиотская странность - операции с intermediate constant всегда получаются медленнее, нежели та же операция но с регистровым операндом. Разница составляет доли такта, но она есть всегда. К примеру, помещение одной из двух констант 1 или 0x7FFFFFFF в регистр позволило еще срезать несколько тактов на всем перемещении. Причем в документации о увеличении латентности с intermediate constant не сказано ни слова

Ну и кто они после этого ?

 

leo

Есть еще такой вопрос. Пусть мы имеем последовательность команд следующего вида:

Код (Text):

1. paddw mm0,dc_corr
2. paddw mm1,dc_corr
3. paddw mm2,dc_corr
4. paddw mm3,dc_corr

Будет ли процессор загружать константу dc_corr каждый раз для каждого значения или сможет сделать это один раз на всю последовательность операторов?

Еще просьба. Можешь изобразить симуляцию пайпа для такой последовательности команд с операндами из памяти? Я пытался промоделировать последовательности команд с операндами памяти, однако результаты даже приблизительно не совпадали с реальностью

 

v_mirgorodsky

Вопрос конечно интересный Быстрые int-load'ы однозначно будет, т.к. это быстрее, чем анализировать адреса всех предыдущих load и store. По видимому и для FPU\SIMD проще каждый раз лезть в кэш, чем возиться с анализом, хотя и не совсем ясно на что уходят дополнительные 6-8 тиков при загрузке FPU\SIMD

Странно, такой код на "предсказуемом" P4 Northwood ведет себя "идеально" - в цикле дает точно 1 такт на paddw. А вот на старших моделях добавляются загадочные дроби - цикл из 4-х paddw дает ~4.3 тика на итерацию, а из 8-и соотв-но ~8.7 тика. Чем объяснить не знаю, не долюбливаю я этих монстров и стараюсь с ними не связываться Но если не брать в расчет эти непонятные дробные задержки, то выглядит все достаточно просто

Код (Text):

1. paddw load  dxxxxxxxx........... моп load  - p2,T=1,L=6-8 на Northwood
2.       mmx   d........xx......... моп paddw - p1,T=1,L=2
3. paddw load  d.xxxxxxxx..........
4.       mmx   .d........xx........
5. paddw load  .d.xxxxxxxx.........
6.       mmx   .d.........xx.......
7. paddw load  ..d.xxxxxxxx........
8.       mmx   ..d.........xx......
9. sub ecx,1   ..dx................
10. jnz @B      ...dx...............
11. --------------------------------
12. paddw load  ....dxxxxxxxx.......
13.       mmx   ....d........xx.....
14. paddw load  ....d.xxxxxxxx......
15.       mmx   .....d........xx....
16. paddw load  .....d.xxxxxxxx.....
17.       mmx   .....d.........xx...
18. paddw load  ......d.xxxxxxxx....
19.       mmx   ......d.........xx..
20. sub ecx,1   ......dx............
21. jnz @B      .......dx...........

Как видим для такого цикла из независимых операций латентности мопов load и MMX_ALU роли не играют - главное, что throughput у них = 1 и идут они в разные порты

Точнее с immediate - непосредственными Я кстати разницы на твоем примере не заметил, даже на Northwood, на котором она в принципе может быть. По Фогу в младших моделях P4 в целях экономии размера T-кэша в каждом мопе отводится только 16 бит под непосредственные константы, поэтому 32-битные значения приходится "рассовывать" по соседним мопам (если они не используют константы) или же добавлять лишний моп-ноп (если у всех ближайщих соседей константы есть). А вот в старших моделях, поддерживающих EM64T поле константы в мопе увеличено до 32 бит, поэтому по идее разницы между регистрами и imm вообще не должно быть (хотя, в очередной раз добавлю - хто его знает )