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

1. Конечно давно изобретено. Я просто указывал на ляпы х86, которых нет в других архитектурах. Про совместимость аболютно верно - потому я и писал в первом посте: "Хотя все это мало реально - совместимость необходимая штука". Так что спор ниочем =). Кстати другие архитектуры ARM\Itanium1,2\G5\XScale\MIPS\cell тоже не надо недооценивать, на своем месте они очень жизнеспособны в рыночных условиях - и во многих местах напротив без такого риск подхода решение стало бы нежизнеспособно... Кстати интересно будет посмотреть на cell - если на PS3 и впрямь без проблем пойдет линукс, я пожалуй себе куплю =)



2. Ничего не хорошо - все что ты сделаешь, это из 2х инструкций - 1 простая из 1uop и 1 простой или сложной из >=1uop сделаешь 1 сложную инструкцию из >=2uop. Про то что серьезного пенальти это вызывать не будет не понял. Тут же все тоже самое - и там и там, в момент, когда извесно, что переход предсказан неверно, проц может протопать далеко вперед (причем мноого мопов сейчас размазано по конвееру) - про только зависимый код тоже не понял - вся исполняемая сейчас ветка не верна - весь конвеер сбрасывается, про коррекцию на ходу и откат влияния мопов инструкции через которую прыгают никогда не слышал - это явно нетривиально реализовать. В любом случае, такую поддержку можно внести в процессор, не внося новые инструкции - определение, что прыжок осуществляется через одну инструкцию - это вообще семечки - это не вызовет ни утяжеление процессора(а вот ввод префиксных команд вызовет) ни пенальти - а вот откат..., непонятно вообще что делать если мопы инструкции одни в исполнительных устройствах, другие не дошли, 3и на стадии завершения и прочие гадости. Так что любых вариантов отката как небыло, так и нет пока и врядли скоро появится. Я уже указывал на то, что кондиционное исполнение и спец. поддержка некоторых инструкций, типа min\max (которые уже есть в SSE) в исполнительных устройствах это 2 большие разницы.

 

semen

1. ок, я тоже думаю о терафлопсной приставке.

2. Да, с реализацией и не говорил ни кто, что просто будет. Главное чтобы более эффективный код мог компилировать компилятор, и мы смогли себя лучше реализовать. Но тут надо привести основной пример эффективного использования холостого выполнения:

Код (Text):

1.  
2. cmp     rax, ebx       ;; Alu (1 tick)
3. onne sub rax, rbx      ;; q1 = rax - ebx (Alu shadow), no changes (1 tick)
4. add     rdx, rbx       ;; q1 = rdx + q1,  rdx += ebx { parallel operations }
5.  
6. ;; q1 - some shadow register, used for predicted calculations.
7.  

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

 

alpet

2. Я к тому что сделать префиксные команды скорее всего не получится, можно выбрать несколько наиболее нужных инструкций для внесения, без которых бы пришлось делать бранчи, и внести их в исполнительные устройства, но много тоже плохо - исп. устройства тоже не резиновые, а вносить команды условного исполнения 100% не стоит и то что оптимизации прыжка через инструкцию до сих пор нет, наглядно говорит о том что сделать откат нереально даже для одной инструкции - это слишком сложно. Можно сделать спец. поддержку для некоторых комбинаций опр. префикс\опр. инструкция, как для rep movsd в 4х пнях, но лучше всеже просто новые инструкции потому что остальные комбинации всеравно бесполезны и только утежеляют проц.

 

semen

Тем не менее это возможно, и в некоторой мере уже реализовано (пускай без опкодов).



Вот описание того как это делается в Itanium (я бы не сказал, что ядро этого процессора утяжелено сверхмеры):

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

Насчет отката, я вроде объяснял - что он реализуется за счет избыточного выполнения (впрочем, это не относится к операциям с памятью):

Код (Text):

1.  
2. cmp   eax, ecx
3. onne  add   edx, eax   ;; rg [0] = edx + eax, edx not changed
4. oneq  sub   edx, eax   ;; edx = edx - eax, (Save:rg [1] = edx) (branch)
5. mov   [edi], edx ;; вот из-за на этой инструкции ЦП будет ждать, пока не будут получены результаты сравнения.  
6. ;; Фактически код будет выполнятся так:
7. rg [0] = edx + eax ;; Alu
8. rg [1] = edx - eax ;; Alu
9. ... ;; некоторый несвязанный код.
10. edx @= rg [eax == ecx] ;; это не присваивание, а ассоциация.
11. mem [edi], edx ; операция сравнения сместилась до уровня необходимости результата.
12.  

 

alpet

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

Итаниум это да, отдельная песня, но процессор и вправду тяжел, частоты выше 1.6 нет. И никакого отката там нет, просто предикаты всегда должны успеть вычислиться - иначе сталл, что не проблема если аргументы у cmp уже вычислены. Вообще плохой пример - итаниум как раз делает упор на програмное распараллеливание и от компилера там зависит дай боже. К томуже итаниум фактически новая архитектура, с поддержкой старой IA32, а раз новая архитектура и можно что угодно - лучше уж генерация флагов в регистр и не грузить процессор проверками предикатов, которые далеко не для каждой инструкции нужны и что отражается на кол-ве стадий процессора - получаем простоту и высокую частоту =)

 

semen

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



Вот если взять к примеру мой код для поиска с упаковкой (в данном случае о прыжках речь вообще не идет - просто как улучшается реальный код):

Код (Text):

1.  
2. ;; original code (упрощенный):
3. xloop32: ;; test 4 * 8 dwords in cacheline
4.          cmp      [esi], ecx
5.          sete     bl
6.          rol      ebx, 4     ;; penalty, 32-8
7.          add      esi, 4
8.          test     esi, 20h
9.          jz       xloop32
10.          mov      [edi], ebx
11.          add      edi, 4
12.          cmp      esi, limit
13.          jb       xloop32
14.          ;; store bitset result
15.          cmp      
16. ;; optimized code
17.          
18.          xor      ebx, ebx
19. xloop32:
20.          cmp      [esi], ecx
21. oneq     or       ebx, 1  ;; rg [n] = ebx | 1
22.          rol      ebx, 4  ;; rg [n] <<= 4
23.          add      esi, 4
24.          test     esi, 20h
25.     ;; встретился условный переход - логика усложняется
26.     ;; соответственно - if ([esi] == ecx) ebx @= rg [n]; после чего n изменяется.
27.          jz       xloop32
28.          mov      [edi], ebx
29.          add      edi, 4
30.          cmp      esi, limit
31.          jb       xloop32
32.            
33.  

Обрати внимание - в первом случае код связанный - пока не будет результата сравнения, установить бит в ebx не удаться. Во втором сначала производится вычисление, и до первого ветвления храняться оба результата. Ассоциация происходит параллельно выполнению jmp-branch, но только если готовы результаты первого сравнения. То есть заметны два положительных момента - отсутствие пенальти из-за несоответствия размеров регистров (partial stall), и уменьшается латентность - пока есть что выполнять процессор занимается делом (хотя и выполняет в данном случае 50% ложной работы, что из-за параллелизма вобщем-то незначимо).



2. Вот! Там нет, а нас будет, иначе это не новация, а плагиат

3. Не могу, несогласится - компиляторы под него сложные.

 

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

2. эээ, это к чему =)

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

 

semen

1. В Itanium будет, у нас нет. Если ты внимательно прочитал, то мог бы понять - архитектура с опкодами допускает выполнение какбы двух веток одновременно, на одном конвеере. То есть какой-бы не был результат сравнения, правильный результат вычисления будет в любом случае, другое дело что зависимость кода в этом случае просто отодвигается. Иными словами - инструкция ограничиваемая префиксом выполняется всегда, и с этого момента возникает параллельный вариант выполнения - каждая команда работающая с результатами этой инструкции - выполняется дважды: для первого и второго инварианта сравнения.



Вот скажем условное выполнение представленного кода:

Код (Text):

1.  
2. <font face="Fixedsys]<font size=2>
3. xloop32:
4.       cmp     [esi], ecx    ;;DDDSHEEWR
5. oneq  or      ebx, 1        ;;DDSEWWWWR  
6.       rol     ebx, 1        ;;DDSEWWWWR
7.       add     esi, 4        ;; DSEWWWWWR
8.       test    esi, 1Fh      ;; DDDSEWWWR
9.       jz      xloop32       ;;  eDDDSEWWR
10. ; DPI - ~ 2 ticks / cycle
11. ; Pipeline Stages:
12. ; D - Dispatch
13. ; S - Scheduling
14. ; E - EXEC Executing
15. ; e - EXEC Branch Prediction
16. ; H - DACC Cache and TLB Hit
17. ; W - Waiting for retire
18. ; R - Retire
19. </font><!--size-->
20. </font><!--face-->
21.  

Ассоциация с результатом выполняется в инструкции сравнения, что занимает до одного такта дополнительно (в случае выполнения комманды).



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



[edited]

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

 

alpet

Аааа, вот оно как. Ну чтож, успехов в реализации новой архитектуры, может я и не прав и сделать это удастся. И все же я до сих пор считаю это нецелесообразным. Почему? Тебе потребуется 2 экземпляра исполнительных устройств, причем второй экземпляр используется не всегда. Итаниум он тоже тяжел в основном из-за дублей исп. устройств(ну и кэш =), но там хоть все они пытаются нагрузиться по полной компилером, а не тока при брэнчах. А так, раз есть дубли исп. устройств - лучше поделить кэш и сделать многоядерный проц =).

 

semen

Вон оно как... На счет нехватки ИУ я думаю можно не волноваться - вон на современных Pentium 4, поскольку часть из них всегда простаивает, мудрые инженеры Intel даже реализовали псевдо-двупроцессорность. Показанный подход как-раз и есть утилизация избыточных мощностей. И даже в худшем случае, удваивать количество ИУ вовсе не к чему, можно просто усовершенствовать их на манер MMX - чтобы одновременно справлялись с двойной нагрузкой.

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



А как тебе идея со стеком? Это уже направление не только на повышение производительсти, но все равно твоя критика здесь будет к месту.

 

alpet

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

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

Про стек не совсем понял - речь идет об отдельном стеке, где храняться только адреса возврата, SEH инфа и больше ничего?

 

semen

1. Почему именно полный двойной набор ? И почему нельзя модернизировать? Конечно теневому результату придется дополнительно также выделять теневой регистр флагов, хотя это еще под вопросом (одинаковые инструкции в зависимости от операндов могут получить как одинаковые флаги, так и разные, но насчет реально ли это разрулить аппаратно я сомневаюсь).

2. Головная проблема многоядерности и мультипроцессинга - не высокая обычно мастштабируемость по производительности - при увеличении количества процессоров - производительность растет не пропорционально (медленно).

3. Да именно такая реализация стека. Плюс в стандартный стек данных ss:[esp] будут эта инфа будет также сохранятся (из-за совместимости с старыми программами), а вот браться процессором (и программистом) будет из нового стека. Неочевидное его преимущество - рекуррентные вызовы можно будет сокращать с помощью счетчиков, а малый по размеру сам кодовый стек может полностью размещаться даже в кэше (L2).



[edited]

Базовые детали архитектуры кодового стека:

Стек адресуется особым 16-битным индексным регистром, который позволяет выбирать 8-байтную структуру (в 64 битный регистр к примеру). Т.е. максимальное количество структур не может превышать 64К.

<font face="fixedsys]

struct stack_x

{

DWORD data1;

BYTE some1;

BYTE some2;

BYTE some3;

BYTE sflags; // флажки описания.

}

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

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

 

alpet

1. Насколько я понял, ты собрался параллельно обе ветки исполнять на oneq - на это надо 2 конвеера и 2 комплекта исп. устройств, что явно нехорошее решение. Как ты собрался обходиться одним комплектом или откатывать результат действия инструкции в случае неправильного предсказания псевдо-ветвления я не понял.

2. Зависит от задач. Много где близко к двукратному ускорению легко.

3. Задумка вобщем неплохая, особенно со счетчиком рекурсии. Я бы не отказался от внесения сего в х86 - рекурсивные алгоритмы перестанут требовать мег стека =).

 

semen

1. Нет, тут получается не выполнение ветки параллельно, а выполнение одной и той же инструкции для двух вариантов данных (с генерацией двух-же вариантов флагов). То есть имхо это можно реализовать модфикацией ИУ до простого SIMD (отчасти даже на родственных MMX мопах! Другое дело что для инструкций MMX/FPU возможно этот механизм действительно ненужен и сложен, а следовательно не реализован).



Дело происходит так - после того как декодер встречает инструкцию с префиксом условного исполнения, он помечает ее как стартовую (т.е. она вычисляется, но результат всегда помещаяется в теневой регистр). До тех пор пока не произойдет сравнение (т.е. будет оценено предсказание на неисполнение) все инструкции, явно зависящие по результату от стартовой вычисляют действительное значение по результату не выполнения условной комманды, и одновременно , в теневой уже регистр, по ее выполнению. Иными словами, до некоторы пор (пока логика еще не определенна до конца, основной предел - получение наконец результатов сравнения-оценки предсказанного невыполнения), процессор вычисляет сразу два инварианта значения. Как только встречается условный переход, или еще одна условная выполняемая команда с этими же данными,(или запись результата в память/порт) процессор ожидает результатов первого сравнения (т.е. случай пенальти). Но как правило код, весьма даже можно оптимизировать так, что ко времени использования результата, сравнение уже происходит, и команда cmp неявно связывает (в случае выполнения условной команды) регистр результата с теневым регистром. Общая суть нововведения такая - к моменту выполнения сравнения, существуют два результа вычисленных на n команд вперед (т.е. субьективно как две ветки выполнились одновременно), и из них выбирается один по результатам сравнения.

Вот пример как это происходит в процессоре, для указанного ранее кода.

Код (Text):

1.  
2. <font face="fixedsys]
3. 1. rg0=ebx | 1
4. 2. rol   ebx, 1  && rol  rg0, 1
5. 3. cmp   [esi], ecx && if ([esi] == ecx) ebx @= rg0
6. </font><!--face-->
7.  

Показанный код может выполнится фактически за два такта!

Фактическое значение в ebx = ROL ([esi] == ecx ? : ebx | 1, 1), будет сразу по выполнению сравнения. Т.е. зависимый код or + rol выполняется одновременно с сравнением.

Конечно с некоторыми командами эти префиксы будут работать не эффективно, к примеру oneq out edx, al.





2. Близко к сожалению, а четырьмя процессорами еще хуже.

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

 

alpet

1. Значить примерно так: системные, бранчевые и работающие с памятью инструкции мы исключаем из числа дозволенных с условным префиксом(ты кстати это не упоминал, а это важно, потому что иначе траблы даже с твоей схемой). Пользуемся тем, что одна инструкция с префиксом портит 1-2 регистра, запускаем эту инструкцию на исп. устройство, результат помещаем в теневые регистры. Далее в случае зависимости по данным от этих испорченных регистров процессор сталится до появления точных данных. Так? Отмечу пока один минус - в случае зависимости по данным в твоем случае сталл, в обычном случае при правильном предсказании ветвления просто продолжается выбранная ветвь без стала. Вообще устал что-то я от этой темы =)

2. Да лан, вон Athlon X2 очень ничего(и дорого =). Если задача позволяет - легко можно загрузить все ядра - главное память не перегрузить. И таких задач много. Ато cell`у крышка =)

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

 

semen

1. Нет, просто с недозволенными инструкциями будет stall. Зависимость же проявляется когда результат действительно нужно куда-либо передать (память, порты) или когда встречается дополнительное ветвление с этими результатами (практически любой условный переход). Но сама суть - сравнение выполняется одновременно с некоторым набором зависящих от него команд, и независимо от его результата (сравнения) вычисления не пропадают зря. Даже если привлечь судя большее количество ИУ = просто гипертрейдинг станет работать эффективнее.



2. Я не спорю что эффективность выше, но к этому решению ведь пришли, когда стало ясно что частоты далее повышать неудастся прежними темпами.



3. Если учесть что и в реальном стеке (ss:esp) производятся изменения принятые для x86, экономии памяти нововведение не обеспечивает. Насчет быстродействия я еще не все продумал, но в основном это касается более эффективного использования устройства предсказания переходов (в стеке может ведь также сохраняться дополнительная инфа).

 

1. Так я и не понял до конца, такая схема или нет ^^, про сталл с недозволеными понятно. У тебя всегда будет сталл при зависимости по данным от кондиционной инструкции, потому что иначе надо уже расщиплять выполнение на 2 ветки - с теми данными что в теневых регистрах, и с данными что в нетронутых пока обычных. Что в итоге быстрее на конкретных примерах пока не понятно. Но вообще конечно попробовать стоит =)

 

semen

1. Можно представить это как параллельное выполнение двухветок кода, до след. ветвления. Как только готовы результаты сравнения ([esi] == ecx), берется уже один из готовых результатов - перевычисления веток не происходит.

 

alpet

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

 

semen

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

2. О прыжках. Это будет менее эффективно в целом по архитектуре, даже если реализация будет полностью аналогичной. Главная проблема - все инструкции выбираются и декодируются ограниченным количеством декодеров, на современных процессорах они съедаются до 3 штук за раз. Естественно префиксы в этом отношении более предпочтительны - поле боя у них регулируется не одной защищаемой инструкцией, а зависимостью по данным. Мне к тому же представляется, более сложным отделять в процессоре логику параллельного выполнения, от предказания переходов. Процессор ведь может выполнить бранч и на этапе декодирования, а как ему догадаться куда заведет очередной прыжок - к изменению логики одной команды или сразу всех - ему придется уточнять, что переход контролирует лишь одну инструцию и выполнять ее игнорируя бранч. Префиксы в отличии от условных переходов, просто регулируют работу комманды сравнения - следующие за условной коммандой инструкции выполняются на SIMD ИУ для теневого результата (для выполнившейся инструкции) и для оригинального значения регистра (как для невыполнившейся), а когда сравнение завершается - регистр может быть просто переассоциирован. Думаю хватит уже повторять одно и тоже.