Придумай инструкцию x86!

semen

Хорошо, тогда для начала можно обозначить ограниченный ряд инструкций, которые могут использовать параллельное выполнение, и будут иметь MMX аналог. Например основные арифметические операции: add, sub, lea, (i)mul, (i)div, neg, сдвиговые и логические операции: shl, shr, and, or, xor, not, и операции сохранения/загрузки/обмена - mov и xchg. По идее в большинстве случаев этого набора должно хватить. Есстно следующий код например будет возможно вызывать сталл:



cmp eax, [esi]

oneq sub eax, 9

mov al, ah

push eax ;; stall = waiting for cmp.

 

alpet

Вот это уже другое дело - еще mul\div убрать и можно опробовать идею т.к. умножение уж больно емкое по площади - получаем не дубль ИУ, а всего маленький дополнительный.

 

semen

Хм, можно и убрать, просто я надеюсь что можно запользовать как-нибудь ресурсы MMX, хотя там из-за использования других регистров (FPU) могут быть траблы. Интересно, с учетом особенностей технологии стоит ли интегрировать MMX и обычные целочисленные команды - как плюс смешивание обычного кода с MMX будет происходить лучше (сейчас смешивать не рекомендуется), и распределение ресурсов будет гораздо более рациональным (исполняющие устройства будут разделены - ведь для работы параллельного исполнения фактически и нужен быстрый MMX).



Ввести бы еще, ряд регулярно используемых делений, через умножение - например на 10 или 100. Если div 10 будет декодироваться в особый моп - это даст ощутимый прирост и в старых программах, и в новых не придется использовать специальные алгоритмы.

 

alpet

Уходишь от ответа

Грубо говоря о существоании регистра eax, как и прочих перманентных регистров, знают только аллокатор и ретайрмент-станция. Весь out-of-order работает только с регистрами register file (RF). Любой операции, изменяющей регистр, аллокатор для записи результата назначает новый регистр RF. Например, моп add eax,eax на выходе декодера аллокатор преобразует в моп (add r_eax',r_eax,r_eax), т.е. сложить данные из регистров r_eax и r_eax (которые на данный момент являются отображением eax) и поместить результат в новый регистр r_eax', который становится новым отображением eax. Соответсвенно каждая операция изменяющая eax будет помещать результат в новый регистр RF. Поэтому между аллокатором и ретайрментом в конвеере могут находиться n-е кол-во мопов, изменивших "свои eax" r_eax, r_eax',r_eax" и т.д. Когда моп добирается до ретайрмента, то именно его r_eax и считается регистром eax на этой стадии. Но этот eax ес-но не совпадает с теми eax, с которыми в данный момент работают аллокатор и мопы сидящие в конвеере. Поэтому я и не понимаю, как ты собираешься "связывать" eax на момент исполнения cmp. Когда приходит черед cmp мы только знаем ее порядковый номер и номер последней аллоцированной в ROB инструкции. А сколько мопов из этого промежутка выполнено, а сколько нет никто не знает. А связывать надо и уже выполненные (для ретайрмента на случай эксепшена или еще чего) и еще не выполненные, но уже аллоцированные и сидящие в ROB мопы (которым уже назначены свои входные и выходные r_eax). Как это все разгрести, если не перебором всех мопов в ROB после cmp ?

 

alpet

Насчет ресурсов MMX я уже писал - ничего не выйдет - много сложностей и тормоза в итоге. Смешивать GPR\MMX\SSE код стоит, только он уже и так смешивается в некой мере благодаря HT. Насчт div - хз, помойму в коде где перфоманс нужен все равно на умножение заменят, да и FP щас во всех играх рулит - короче может и смысла-то особого нет?

leo

Я ему уже говорил, что такая связь - нетривиальная штука =)

Сейчас-же все упростилось и у второго мини-конвеера будет свой ROB + где-то такт-два на синхронизацию регистровых файлов при запуске и остановке мини-конвеера (это конечно не все т.к. при копировании первый регистровый файл инвалидный из-за незавершенных мопов главного конвеера, но это отражается во втором ROB`е и дальнейшая синхронизация идет походу). Т.е. в коде:

Код (Text):

1. mov eax, [esi]
2. cmp eax, 0
3. oneq add eax, ebx
4. .... <- здесь n инструкций независимого от еах кода
5. use eax

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

 

leo

Значит все и стремится к тому, что бы каждый моп работал сразу с двумя парами операндов (расточительно конечно).

Вот скажем за базу береться архитектура изначально 64-битная, но код выполняется в 32-битном режиме. Есть ли функциональная возможность использовать каждую половинку регистра на уровне отображенного 32-битного регистра? Если есть - за каждым 32-битным регистром можно закрепить тег определяющий использование младшей или старшей половинки регистра, а ассоциация (выполняется по установке флагов для условной операции) приводит изменению (не изменению) этого тега. И тогда получается следующая картина: мопы выполняются, не хаотично для двух инвариантов (что приводит по твоей версии к тому что мопы одного инварианта выполняются раньше), а каждый моп работает для двух инвариантов. По аналогии - команда paddd работает с одним из 64-битных mmx регистров, а команда movd обеспечивает сохранение младших 32 бит например в GPR регистров. Ассоциация в этой модели осуществляется на инструкции movd.



Значит как может это осуществлятся:

Код (Text):

1. <font face="fixedsys]<font size=1>
2. ;; eax.lo = [esi], eax.hi = eax.lo
3. ;; eax.tag = 0 (Lo of RAX)
4.        mov   eax, [esi]
5.        test  ecx, ecx    
6. onz    sub   eax, 1     ;; (only with shadow) eax.lo -= 1
7.        add   eax, ecx   ;; Alu "paddd" rax, rcx
8. ;; когда устанавливается reg.tag в 1, lo и hi как-бы меняются местами.
9.        mov   [edi], eax ;; wait for flags and tag set, Store [edi] eax.lo
10. </font><!--size--></font><!--face-->

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

 

semen

Т.е. div10 и mul10 инструкции слишком тяжелые? Жаль, ведь человечество к сожалению не собирается переходить на шестнадцатиричную систему исчисления, поэтому мастштабирование с участием десяти всегда будет актуальным.

 

alpet

Напрмер блок умножения 32х4 бита естественно меньше и быстрее, но зачем его делать, когда уже есть 32х32(базовый скорее всего 32х16)?

 

alpet

То что ты говоришь о параллельном вычислении двух результатов а ля MMX я прекрасно понимаю. Но ты видимо не хочешь понять, что когда появляется результат cmp, то в конвеере сидит куча мопов, у которых аллокатором задано из какого RF брать операнды и в какой RF[j] класть результаты и одному и тому же eax в каждом мопе соответсвует свой RF[j]. Поэтому после cmp ты должен установить reg.tag не у какого-то одного регистра, т.к. на момент cmp просто неизвестно какой или какие регистры являются отображением eax, а проверить всю цепочку мопов после cmp. У тех мопов, которые выполнены и записывали результат в eax установить reg.tag результата в 1 (если тебе наплевать на ретайрмент, то по крайней мере нужно отыскать последний моп изменивший eax), а те что еще не выполнены перевести в нормальный режим исполнения на обычных ИУ.



Грубо говоря, в современных архитектурах четко разделены стадии in-order (аллокатор и ретайрмент), которые знают какой из регистров RF отвечает за eax, и есть out-of-order, которому по барабану эти eaх. У аллокатора и у ретайрмента eax всегда разные (за исключением отката при непредсказанном переходе), т.к. они разнесены на немалое число стадий конвеера. А ты хочешь установить таг у некоего eax внутри out-of-order - у какого ? Значение eax из ретйрмента уже устарело, из аллокатора только что поступило в ROB и еще и не исполнялось. Остается перебирать все мопы в поисках последнего изменения eax или заставить твои векторные инструкции фиксировать где-то последний RF[j] в котором сидит самое свежее значение eax. В любом случае это попытка втиснуть элемент in-order в out-of-order стадии, и ес-но легко и просто эта задачка не решается. А вот выигрыш от таких усложнений весьма сомнитетелен

 

semen

Ну для отдельных инструкций наверное и блок будет не умножения. Например на десять умножить ведь можно с помощью:

Код (Text):

1.  
2. lea eax, [eax + eax * 4]
3. add eax, eax
4.  

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

 

alpet

Ну да, в принципе - потому и говорю хз...

leo ну да =), и это только вершина айсберга трудностей =). А главное решать их бесполезно, из-за латентности векторного блока. Наконец-то кто-то поддержал...

 

leo

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

 

Вот если пытаться делать все с точностью до наоборот - не исполнять, а наоборот задерживать одну префиксную инструкцию пока не установятся флаги условия - то на вскидку это кажется более простым и более или менее реальным. (Возможно semen примерно такой вариант и предлагал - не знаю, перечитывать 6 страниц дискусии чего-то не вдохновляет

Речь идет как раз о сравнительно быстрых регистровых сравнениях, когда бывает особенно "абыдно" что можно было бы подождать 1-2 такта, "пропустить" одну инструкцию и пойти по нужной ветке, но "нетерпеливый" проц уверенный в своем предсказании идет не в ту степь и в результате вынужден откатывать назад с большим пенальти. Поэтому префикс условного исполнения мог бы как раз и притормозить инструкцию, пока не установятся флаги сравнения и в случае невыполнения условия заменить условную инструкцию на mov reg,reg. При таком подходе мы проигрываем 1-2 тика (возможно до 4х как в cmov и setcc на P4) при верном предсказании, но заметно выигрываем в случае ошибочного.

Конечно это только необоснованное ИМХО, возможно это уже где-то реализовано или наоборот до- или по-казана несостоятельность такой затеи..

 

leo

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

 

alpet

> "может статься и есть какие для нее пути реализации."

Возможно, но пока все кажется чересчур сложным...



А вот с условной операцией по типу setcc\cmovcc вроде как все довольно просто получается - достаточно лишь не устанавливать (игнорировать) флаги этой операции и вставлять вслед за ней cmov. Например,

Код (Text):

1.     cmp eax,edx
2.     oneq add eax,1
3.     ...

реализуется просто как

Код (Text):

1.     cmp eax,edx
2.     temp <- eax+1 без изменения флагов
3.     cmov eax,temp
4.     ...

 

leo

Так то оно так, но оптимизации особой не принесет. В идеале ведь цель такая, чтобы код с непродолжительным ветвлением, мог исполнятся без пенальти, независимо от результатов сравнения. Насколько мы разобрались самое сложное с моим вариантом - производит ассоциацию половинки большого регистра, после сравнения, и оперирование двумя флаговыми регистрами (впрочем можно ввести правило - теневая часть непросчитывает флаги, а использует результаты явных вычислений). Может подойдет вариант, кода тег выбора регистра, будет совмещен не с теневыми регистрами, а явными. Единственно - придется добавлять в каждую цепочку с двойным вычислением, моп который будет осуществлять ассоциацию.

Код примера:

<font face="fixedsys]

test ebx, ebx

onz add eax, edx

shl eax, 4

mov [edi], eax ;; этой инструкции придется ждать установки тега eax, поскольку используется явная часть регистра.

</font><!--face-->

У тега 3 состояния - из которых нулевое требует ожидания, 1 - выбирает младшую часть, 2 - старшую. Этим тегом оперирует также и LSu, поэтому данная инструкция может только озаботится наличием данных в кэше, и если нет загрузить, но запись в буфер будет выполнена только тогда, когда тегу будет присвоено не нулевое значение (оптимальное выполнение записи).



В свете того, что установка может произойти сразу после сравнения, этот код должен выполнятся без задержки. Хотя я опять видимо что-то недопонимаю...

 

alpet

> "самое сложное с моим вариантом - производить ассоциацию"

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

 

leo

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

Для этого можно предпринять следующую конструкцию - теги всех GRP регистров интегрируются в один регистр тегов. Мопы использующие некоторый регистр, будут сталится если тег используемого регистра равено нулю. Безграничного выполнения действительно лучше не допускать, поскольку большинство сравнений выполняется за ограниченное количество тиков (исключение - операнды в памяти).

 

alpet

> "Хотя я опять видимо что-то недопонимаю..."



Не знаю, возможно мы друг друга не понимаем. Попробую с другой стороны пояснить.

В моем варианте ассоциацию производит не cmp, а cmov которая точно знает какие регистры RF нужно с чем ассоциировать и пока она не выполнится следующая за ней инструкция использующая eax будет ждать готовности соответсвующего регистра RF.

Ты же пытаешься делать просчет вперед на неопределенное заранее число инструкций. А раз так, то моп который должен осуществить ассоциацию не может заранее знать в каком из регистров RF будет лежать последнее измененное значение eax (т.к. для обеспечения out-of-order каждое изменение eax записывается в новый регистр RF, оставляя неизменным предыдущее значение, которое может понадобиться какой-то предыдущей задержавшейся инструкции). Если отвлечься от быстродействия, то универсальным решением было бы перебрать все мопы после cmp и во всех выполненных векторных мопах установить теги выбора варианта - таким образом обеспечивается и продолжение выполнения и информация для ретайрмента выполненных мопов. Для ускорения продолжения обработки можно ввести дополнительную таблицу RAT (register alias table), которая будет указывать в каком из регистров RF лежит текущее значение GPR. В нынешних архитектурах таких таблиц две - одна у аллокатора, другая у ретайрмента (поэтому только на этих стадиях и известно где лежит eax, edx и т.д). Тогда после выполнения каждой векторной инструкции в дополнительную RAT будет записываться идекс RF, соответствующий данному GPR. Поэтому при ассоциации первым делом будут устанавливаться теги регистров, содержащихся в RAT (т.е. самых "свежих" необходимых для дальнейших вычислений). Ну а для ретайрмента все равно придется что-то накручивать (если ты думаешь выполнять более одной векторной инструкции), т.к. игнорировать его нельзя (а вдруг исключение выскочит или прерывание поступит - кстати вопрос интересный и видимо неразрешимый - как можно продолжить обработку после прерывания на инструкции, следующей за префиксой ???).

Еще вопросы. Что делать если какая-то векторная инструкция уже ушла на исполнение, но еще не обновила индексы в RAT ? Значит нужно остановить векторный планировщик, дождаться завершения ушедших в ИУ операций и только тогда провести ассоциацию. Еще не совсем понятно, что делать с оставшимися в планировщике невыполненными операциями - так и продолжать их векторное исполнение или перебросить на обычные ИУ ? Если продолжать, то нужно им сразу выставлять флаг (тег) выбранного варианта. Короче, мороки ИМХО много ...



PS: чтобы ты не говорил больше об абстракном регистре eax проиллюстрирую как твой код примерно выглядит в микроопах (индексы RF ес-но условные):

Код (Text):

1. ASM             cтадия       RAT            микрооперация
2. ------------   ---------  ----------   --------------------------
3. xor eax,eax     retire    eax=RF[13]   RF[13] <- xor RF[11],RF[11]
4. ............   .........  ..........   ...........................
5. test ebx,ebx     exec         ?        temp <- and RF[17],RF[17]
6. add eax,edx      exec         ?        RF[23] <- add RF[22],RF[19]
7. shl eax,4        exec         ?        RF[24] <- shl RF[23],4
8. mov [edi],eax    exec         ?        storebuf[4].address <- RF[18]
9.                                        storebuf[4].data    <- RF[24]
10. .............  .........  ..........   ...........................
11. xor eax,eax    allocate   eax=RF[28]   RF[29] <- xor RF[28],RF[28]
12.                           eax=RF[29]

Вопрос: где на стадии exec регистр eax ? Где нужно устанавливать тег: в RF[23] или в RF[24] или в обоих (а если их было больше, да еще какой-нить ecx изменился в результате add ecx,eax) ?

 

leo

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

Для кода я могу только пока предложить последовательность свою мопов.

Микроинструкции с суффиксами _lo обращаются к младшей части 64-битного регистра, остальные оперируют с обоими частями.

Код (Text):

1.  
2. <font size=2><font face="fixedsys]
3.  
4. 1. temp and_lo  RF[17], RF[17]
5. 2. RF[23] = add RF [22], RF [19]
6. 3. RF[24] = shl RF [23], 4
7. 4. RF[25] = rsel RF [24]
8. 5. storebuff[4].data <- RF [25]
9. </font><!--face--></font><!--size-->

В данном примере моп 4 rsel - будет ждать пока не выставится 2 битный тег регистра eax в ненулевое значение.

Если тег равен 01b - он копирует младшие 32 бита RF[24] в обе части RF [25], а если 10b - старшие 32 бита. Таким образом выбирается значение цепочки вычислений. Это в принципе скрытый эквивалент предложенного semen'ом механизма сохранения флагов:

testz tagr1, eax, eax ;; поместить 1 в tagr если eax = 0

... параллельные вычисления ...

cmovt tagr1, eax ;; если тег = 1, копировать старшую часть RAX в младшую, иначе наоборот.



В нашем случае после мопа rsel, в младшей части RF [25] уже точно лежит верное значение, но если к его моменту выполнения тег регистра все еще нулевой - возникает сталл.