предсказания переходов того или иного процессора

какой можно придумать алгоритм на проверку эффективности предсказания переходов того или иного процессора? С глубиной ветвления 1,2,3,4 перехода.

Ваш отвђт?

 

Код (Text):

1. invoke timeGetTime
2. test   eax,1
3. jz     .someLabel

)))))))))))

 

locki

Прежде чем придумывать алгоритмы нужно себе примерно представлять как эти переходы "предсказываются" И не понятно, что означает "проверка эффективности" - если эти алгоритмы детерминированы и распознают лишь регулярные комбинации "переход - непереход", поэтому на одиночном прыжке всегда будет промах, а на чисто случайной длинной последовательности соотвественно около 50% промахов независимо от "того или иного процессора".

 

нет ну вот в интеле сказали, что в "Conroe" улучшили предсказания ветвлений с глубиной 3 прехода.

 

Это им кажется, что они улучшили - ведь не зря же люди свой хлеб ели Не надо конвеер до беспредела растягивать, тогда и переходы будут не так опасны

Хотя не знаю, думай сам как это улучшение можно проверить в жизни

 

Мне кажется, что АЛГОРИТМОМ ПРОВЕРКИ ЭФФЕКТИВНОСТИ ПРЕДСКАЗАНИЯ ПЕРЕХОДОВ будет следующее:

Код (Text):

1.  
2.  For i:=1 to 15000  do
3.  if (i div 1000)=0 then
4.  begin
5.      z:=massiv[16000000];
6.      z1:=massiv[16000000];
7.      ...  
8.      z5:=massiv[16000000];  
9.  end
10.  else
11.  begin
12.      z:=massiv[16000000];
13.      z1:=massiv[15000000];
14.      ...  
15.      z5:=massiv[11000000];
16.  end;
17.  

Если процессор предсказывает, то данные z,..z5 он сохраняет в кеше =т. е. попадание

Иначе ему приходится долго доставать данные из оперативной памяти из различных адресов, что дольше= т.е. промах.

в итоге можно замерить время выполнения

и поделить на время мегагерцы проца = Качестово предсказания на мегагерц.

либо общее кол-во повторений на время = Качество отдельно взятого проца.

КАК ВАМ ТАКАЯ ДОГАДКА?

 

>КАК ВАМ ТАКАЯ ДОГАДКА?



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



хотя может ты и прав, только надо по другому замерять вот так:

Код (Text):

1.  For i:=1 to 15000 do //сначала так замеряем
2.  begin
3.      j = i div 1000; <- чтобы не потерять такты
4.      z:=massiv[16000000];
5.      z1:=massiv[16000000];
6.      ...  
7.      z5:=massiv[16000000];  
8.  end
9.  
10.  ----------------------------------------------
11.  
12.  For i:=1 to 15000  do //а теперь ужо так
13.  if (i div 1000)=0 then
14.  begin
15.      z:=massiv[16000000];
16.      z1:=massiv[16000000];
17.      ...  
18.      z5:=massiv[16000000];  
19.  end
20.  else
21.  begin
22.      z:=massiv[16000000];  <- и тоже из кеша!!!
23.      z1:=massiv[16000000];
24.      ...  
25.      z5:=massiv[16000000];
26.  end;

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

 

Эх, locki, я ж тебе сказал - прежде чем строить наивные догадки нужно хотя бы познакомиться на каких принципах работает предсказание переходов. Если нет проблем с инглишем, то почитай "How to optimize for the Pentium family of microprocessors" by Agner Fog (файл pentopt.pdf на сайте www.agner.org/assem), если нужно на русском, то на wasm.ru есть перевод предыдущего издания (но там нет ни слова про P4).



Во-первых, предсказатель переходов работает не с данными, а только с кодом. Поэтому опус "если процессор предсказывает, то данные z,..z5 он сохраняет в кеше" - это полная ерунда, т.к. кэшировани данных происходит по свим законам и никак не связано с результатами ветвления кода. Процессор просто запоминает адреса переходов (вместе с адресами таргетов - куда происходит прыжок) и хранит для каждого перехода краткую историю чередований "переход-непереход" в BTB (branch target buffer). BTB стоит во главе всего конвеерного паровоза. Если при выборке инструкций из кэша BTB встречает знакомый адрес, соответсвующий уже хотя бы раз пройденному прыжку (jmp,jcc,call,ret), то он на основании истории прыжков для данного адреса BTB решает будет ли прыжок на этот раз или нет - если считает, что нет, значит выборка инструкций продолжается дальше, если считает, что должен быть переход, то выдается команда выборки инструкций с другого адреса, соответсвующего таргету перехода. Т.е. решение о том куда идти происходит в самом начале конвеера и ес-но никак не связано с обрабатываемыми данными. А подтвержение правильности происходит в конце конвеера на стадии анализа флагов и если предсказание оказывается неверным, то "сливай вода", точнее - весь неправильно загруженный конвеер и грузи заново с другого адреса - отсюда и штраф в тиках >= длины конвеера.

Отсюда выводы. 1) Проц хорошо предсказывает только регулярные последовательности чередования переход-непереход, а при случайном чередовании соответсвенно и результат предсказания получается случайным. 2) Ресурсы BTB (число запоминаемых адресов и длина истории для каждого адреса) ес-но ограничены. Например, в процах семейства P6 длина истории прыжков = 4, а в P4 Northwood = 16. Это означает, что если в P4 прыжок происходит регулярно один раз из N, где N > 17, то процессор его предсказать не может.

А ты аж 1 прыжок из тысячи замутил - такую последовательность ни один проц в принципе предсказать не может и нафиг такое предсказание не нужно, т.к. задача предсказания снизить средние потери от прыжков до приемлемого уровня (причем для типовых задач, а не на все случаи жизни). Чем длиннее последовательность, тем меньше вклад штрафа за прыжок в общее время обработки. В твоем варианте тело цикла выполняется не менее 6 тиков, умножаем на 1000 и получаем не менее 6000, а непредсказанные переход на P4 это ~20-30 тиков, т.е. в данном сл. относительные потери будут менее 30/6000 = 0.5%



И последнее - если речь идет об эффективности ПРЕДСКАЗАНИЯ переходов (а не о потерях времени), то для РАЗНЫХ процев нельзя проводить сравнение по времени, т.к. штраф в тиках за непредсказанный переход у разных процев разный - не менее длины конвеера. Соответственно для P6 и Pentium M это >= 10-12 тиков, для AMD K7 >= 10-15, P4 0.18 и 0.13мкм (Willamette,Nortwood и т.д.) >=20, P4 0.09мкм (Prescott и т.п.) >= 30. Измеряя тики можно прийти к выводу, что простой предсказатель PIII "эффективнее" навороченного продвинутого предсказателя Prescott, хотя дело лишь в том что штраф за промах в Prescott в 3 раза больше, чем в PIII.



Если тебе нужно количество промахов, то и нужно его вытаскивать из соответсвующего каунтера процессора. Возьми программы пефоманс-мониторинга VTune от Intel или CodeAnalyst от AMD и получишь, то что тебе нужно

Ну или сам разбирайся с программированием MSR-регистров, IA-32-талмуды тебе в руки ))



PS: Судя по твоим рассуждениям и приведенному коду, ты еще и не представляешь как работает кэш. У тебя в цикле используется всего 6+6 различных, но фиксированных переменных (т.к. индексы massiv не зависят от i). Поэтому после первой загрузки из ОЗУ все эти переменные преспокойно сидят в кэше. И сидеть они там могут как угодно долго, пока не будут вытеснены другими данными с конфликтующими адресами (вытеснение происходит, например, когда мы гоняем в тестах памяти большие массивы, в несколько раз превышающие размер кэша L2 или L3 если есть).

 

locki

Лирическое отступление: наглядный пример усовершенствования и "эффективности" предсказания переходов в P4.

Берем интеловскую статейку за февраль 2004 г., описывающую нововедения в P4 0.09 мкм (Prescott) по сравнению с 0.13 мкм (Northwood). По их словам благодаря усовершенствованию алгоритма предсказания удалось заметно уменьшить число промахов предсказания (mispredictions), и в докозательство приводят табличку результатов тестирования. На первый взгляд вроде как все замечательно - среднее количество промахов у Prescott меньше чем у Northwood и можно сказать что у него "предсказание более эффективно" (кстати они признаются, что "содрали" некоторые идеи у команды разработчиков Pentium M). Но пользователям внутренние тонкости реализации как правило до лампочки, им нужна не эффективность предсказания, а эффективность обработки переходов. Из приведенной таблички видно, что выигрыш в числе промахов колеблется от 1-2% до ~20% и в среднем составляет около 10%. Но позвольте, ведь у Northwood длина конвеера 20 стадий, а у Prescott более 30 !!! Получается, что 10% улучшение предсказания не может скомпенсировать 50% разницу в штрафах за промах. Поэтому в целом приходится признать, что Northwood в среднем меньше теряет на переходах, чем Prescott, а значит и более эффективен.

А несомненными лидерами по эффективности обработки переходов ес-но являются процы с умеренными конвеерами - AMD и Pentium M. К тому же пока команда разработчиков Prescott возилась со своим монструозным конвеером, надеясь перешагнуть заветный рубеж в 4ГГц, остальные тоже не дремали и вытягивали частоты за счет совершенствования техроцесса. В результате на сегодняшний день те же Northwood'ы незначительно уступают Prescott'ам по частоте, поэтому на обработку переходов они тратят не только меньше тиков, но и меньше времени - что в итоге и нужно пользователю.

Ладно там соперничество с AMD, но как в стенах Intel Corp. уживаются команды Prescott и Pentium M вообще интересно - ведь на некоторых задачах Pentium M при вдвое меньших частотах может запросто обставить этих неповоротливых монстров. Взять бы да и выбросить их на помойку, да нет - потраченных баксов жалко, да и юзверей приучили, что чем больше гигов тем лучше... А они наивные верят в "усовершенствования алгоритмов предсказания переходов" и прочую лабуду, забывая о том, что сколько какашку не совершенствуй и не облизывай, она конфеткой не станет ))

 

leo

Небольшой оффтоп - единственный попавшийся мне в руки Celeron M (Dothan) 1300MHz уверенно сделал по арифметическим тестам SiSoft Sandra 2005 Professional P4 (Northwood) 1800MHz и даже слегка натянул Athlon XP 2000+ (Thorton) 1662 MHz... Ведь могут же, если хочут... Эдак для него тоже нехило бы ввести рейтинг а-ля AMD. У него что - не такая арифметика как в P4? На одних переходах столько не вытянуть...



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

Мне только непонятно почему все считают, что branch-misspredict полностью сбросит конвеер. Ведь для чего-то трейс-кеш выдумывали? Короче тема задела, посижу-поковыряю.

Ау, Касперски, ну когда же вторая книга-то "Оптимизации" выйдет? Вопрос-то как-раз-то... А то я после первой книги до сих пор хожу с диким взглядом, полным самоуничижения

 

Ustus иди тоже кури мануал =) leo тут абсолютно прав))

 

Ustus

Статическое предсказание работает только при первом проходе куска кода (т.к. в BTB этого адреса еще нет). После декодирования прыжок засылается в BTB, который и решает что с ним делать. При повторных проходах уже рулит динамическое предсказание и наличие хинтов игнорируется. Поэтому хинты работают только для первого прохода и нужны они только для отмены правил, действующих по умолчанию. Например, по умолчанию прыжок вперед не выполняется, поэтому если при первом проходе его нужно выполнить, то можно добавить перед прыжком соответствующий хинт.



Branch-misprediction сбрасывает все стадии конвеера от BTB до retirement'а (отставки).

Трэйс кэш в P4 придумали для исключения стадий декодирования инструкций для повторяемых частей кода. При первом проходе кода P4 работает в режиме декодирования, беря код из L2 и помещая декодированные микрооперации в L1 трэйс-кэш. При повторных проходах проц уже работает в режиме доставки готовых микроопераций из трэйс кэша. Соответсвенно в P4, во-первых, два BTB - один работает с трэйс-кэшем, другой с L2, во-вторых, в режиме декодирования стадий конвеера больше - насколько больше никто не знает (интелы про это помалкивают), но например в PIII число стадий фетча и декодирования инструкций равно 5, а в P4 должно быть никак не меньше, а больше. Так вот хорошо известные 20 стадий конвеера P4 (0.18 и 0.13 мкм), как раз относятся к режиму доставки инструкций из трэйс-кэша. Причем сами интелы как раз называют эти 20 стадий misprediction pipeline. Вот цитата из статьи "The Microarchitecture of the Pentium 4 Processor" (Intel Technology Journal Q1, 2001):

"This pipeline covers the cycles it takes a processor to recover from a branch that went a different direction than the early fetch hardware predicted at the beginning of the machine pipeline".

Думаю все ясно

 

leo

Да, но эффективность может возрасти больше чем на одно попадание, поскольку не факт, что проц всегда угадывает со второго раза даже цикл.



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



Так что насчет арифметики в Pentium M, кто-нибудь обладает информацией?

 

так вот тот код который я привел работает лучше на Пресскоте, потом Нортвуд, потом КЛавхаммер

 

locki

Что значит "лучше"? Цифры в студию!

 

Ustus

> "в натуре надо мануалы полистать..."

Эт-точно, тогда вопросов и предположений в стиле "но по-моему" будет меньше )

В частности "насчет арифметики в Pentium M" - у него не только арифметика другая, но и вся архетикутера - это не NetBurst, а развитие семейства P6. Грубо говоря Pentium M это усовершенствованный PIII M (FSB 400MHz, L1 32+32Kb, L2 1Mb, поддержка SSE2, улучшенное предсказание переходов, ну и ес-но тотальная экономия энергопотребления). Поэтому достаточно открыть pentopt.pdf by Agner Fog или IA-32 Optimization, чтобы увидеть разницу в латентностях основных операций в P6 и NetBurst (например, сдвиги 1 такт против 4, mul\imul 4 против 14-16, adc\sbb 1 против 8 и т.д. и т.п.) И еще интересно сравнить латентности операций P6 и AMD - в основной массе они практически совпадают. Поэтому Pentium M и AMD и "делают" неповоротливые P4 на многих задачах даже на более низких частотах.



Насчет конвеера и трэйс-кэша. Ты говоришь "в трейс-кэш могут заносится обе ветки перехода". Да могут, но первой заносится ветка, предсказанная по static-prediction, а альтернативная ветка декодируется и заносится в кэш в случае промаха, а если промахов не было и переход всегда срабатывал в одном направлении, то альтернативная ветка может вообще не попасть в кэш. Но дело не в этом. Главная причина большого штрафа за misprediction не в том, что из кэша подгружается новый блок мопов (это максимум 1-2 тика), а в сути конвеерной обработки - чтобы моп jcc добрался из трэйс-кэша до исполнительного блока и выдал результат в BTB на P4 требуется не менее 20 тиков. Что делает процессор во время этого путешествия - ес-но спекулятивно загружает в конвеер одну из веток на основе текущего предсказания. Если угадал, то OK - ветка уже загружена и исполняется. А если не угадал - значит эти 20 тиков потрачены впустую, загружена не та ветка и все ее мопы нужно выбросить на помойку. Почему штраф в тиках не менее длины конвеера misprediction pipeline ? Потому, что даже если BTB выдает команду на загрузку из трэйс-кэша другой ветки сразу после выполнения jcc, то пока первый моп этой ветки доберется до исполнительного блока пройдет не менее 20 тиков. А больше 20 тиков м.б. потому, что этот jcc должен еще уйти в отставку (ретайрмент), чтобы зафиксировать состояние регистров на момент исполнения jcc.

 

leo

Уел, пристыдил и т.п. ))))

Действительно надо почитать мануалы. Только мне не попадались по NetBurst более-менее развернутые. Интеловские-то архитектуру описывают, а вот как это будет в жизни... может кто подскажет какой-нибудь "нетбурст для чайников"?



Только все равно непонятно - смысл тогда трейс-кэш городить - только сэкономить на prefetch-decode? Жалких три такта?



Насчет Pentium M - спасибо за информацию. Неудивительно, что у него такая производительность - странно, что интелы не сильно его развивают.

 

Ustus

> "смысл тогда трейс-кэш городить"

Проблема в реализации декодера, стабильно выдающего не менее 3-х мопов за такт на больших частотах. Проблема то известная - переменная длина инструкций x86, не позволяющая распараллелить декодирование. AMD решили эту проблему путем предварительной разметки инструкций в L1 (предварительный декодер длин). Ну а интелы пошли своим революционным путем - оставили сравнительно слабый декодер и ввели трэйс-кэш, чтобы не декодировать повторно уже пройденные куски кода

 

Решил не создавать новой темы, ибо уж очень в тему вопрос
Хотя лучше смотрелось бы в Win32...

Начитался вот мануалов of Agner Fog и захотелось самому пошчупать/померить, особенно тот самый механизм предсказания переходов. Это вообще первый более-менее вменяемый мануал по NetBurst (может, конечно, мне просто не везло...).
Мерять переходы-попадания-промахи больше всего хотелось бы через PMC. Но вот незадача - как известно их надо настроить/запустить, а это WRMSR, то есть ринг0. Изучил исходники от Фога, и от Dark_Master'а. Но создавать драйвер, чтобы прорваться только к одной - единственной WRMSR - не слишком ли тяжелая артиллерия? В Win32 я можно сказать новичок, так что может кто посоветует более простые путь решения...

P.S. Фог узнал, что на свете есть такая фирма - AMD Я не издеваюсь, просто в предыдущих его мануалах не было об АМД ни слова... зато уж если Фог за что-то берется, так объясняет лучше, чем в родных мануалах, что Интела, что АМД. Респект ему за это!

 

Проходил мимо...

По поводу моих исходников После многочисленных пинаний за code style и извратный код Processor spy хотел бы признаться что вся эта каша с MSR драйверами и мониторингом производительности это был курсач по дисциплине ООП Именно отсюда растут ноги у извращеных наследований и прочего так как все писалось "на коленке" в последнюю неделю (как обычно) и туда надо было включить наследование потому что дисциплина такая . В общем писал-писал и ввиду актуальности темы решил поделиться с народом... сейчас сильно жалею о том что послал в таком непотребном виде... Мне стыдно )