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

alpet

Истиный паралелелизм - это неколько ИУ + обвязка. Хипертрединг например - не истиный параллелелизм, верно?

Правильно ли я понял - кондиционная инструкция используется только когда не ожидается зависимости? т.е. такое не прокатит:

Код (Text):

1. cmp eax, [ebx] <= возможна гиганская задержка и минимальная тоже довольно высока
2. oneq add eax, edx <= не может быть быстро предсказано, выполнять инструкцию или нет.

Да ну? Ты собрался обойтись одним мопом? Как же ты в кеше трасс будещь хранить инфу о кондиционном префиксе - все равно 1 слот займет(1моп). Повторяюсь: Ладно, даже если не кэш трасс или ты во всех слотах сделал поля - в участке кода с ветвлениями никогда небыл узким местом декодер(древние P-P3 в расчет не берем) и доставка ~6 мопов за такт выше крыши, так что занятый слот не проблема.

Чем они предпочтительны? Отвечаю: только объемом кода и местом в кеше, если это не кэш трасс. Это абсолютный аналог прыжка через инструкцию.

Я опять повторюсь:

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

Действительно =)

 

semen

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

add ebx, eax

onnz sub ebx, 1 ;; выполнить синхронно не удатся.

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

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



4. Я не вношу новые инструкции, а дорабатываю исполнительные устройства и логику декодирования.

 

Добавь аппаратную сортировку массива (заданной длины)

таких элементов:



struct data

{

long value;

void* psomething;

};[/b]

 

1. Да ну? В современных процах ~3 такта тока кумекать будет в L1 данные или нет, а если в L2? то 20. А если память - то вообще хана. Соответственно быстро предсказать псевдоветвление мы не сможем, т.е. сталл будет долгим, если сразу после кондиционной инструкции есть зависимость от нее. В обычном же случае, если переход верно предсказан - никаких пенальти не будет. А твой пример вообще на зависимость по данным, а не на предсказание. Вот о чем я говорю:

Код (Text):

1. ...на данный момент нет зависимостей...
2. cmp eax, [ebx] <= результат будет через ~3~20~много тактов
3. oneq add eax, edx <= на eax\edx нет зависимостей - можем сразу вычислить и поместить в теневой регистр.
4. cmp eax, ecx <= сталл в твоем случае т.к. eax неизвесно, однако в обычном случае оно извесно и соответствует выбраной ветке
5.                    и в случае неправильного предсказания откатится [b]все[/b].

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

3. Чего? Я имел ввиду аналог с точки зрения результата. А с точки зрения реализации - я бы сделал так: как я уже описывал в 2.^^ 1моп переводящий состояние в обоих случаях. Различие только в декодере - далее все идентично - так что полный аналог. Мой случай можно еще упростить - при исполнения обычного мопа внетвления мы делаем эту проверку и непосредственно меняем состояние, т.е. новых мопов не вносим - то что я предлагал сначала.

4. Ммм? Новые префиксы + дополнительный моп, других путей не вижу.

 

man

Сложные специализированные алгоритмы не годятся!



semen

1. Я просто не видел в предыдущем коде требование конечного результата. У тебя оно уже есть, хотя еще не факт что второй cmp нельзя будет заставить работать с теневыми данными.



Вот к примеру другое развитие:

cmp eax, [ebx] ;; если ebx = 0, команда вообще не выполнится, будет exception

oneq add eax, ebx ;; данная команда выполняется не обращая никакого внимания на cmp, только результат попадает в eax_shadow.

shl eax, 4 ;; эта команда выполняется уже и для теневого результата, и для eax

;; который предыдущей командой небыл затронут

mov [eax], esi ;; Оп-па! Адрес уже нужен реальный, и эта команда ждет, пока cmp не выполнится, и в eax

;; не будет результат условного вычисления.



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



2. Как обычно декодер реагирует на jmp? В Code-Analyst (Pipeline emulation) это выглядит как выполнение branch, то есть он банально декодирует дальше уже с предсказанного адреса... до тех пор пока не завершится установка флагов противоречащая предсказанию - в этом случае конвейер сбрасывается и выходит нехилое пенальти. В твоем случае декодер выполняет бранч не сразу, а только после того как убедится - мол за jcc стоит несколько инструкций, а не одна. Если же одна - начинает действовать уже известная логика. В данном случае вся избыточность скрывается в том что бранчи будут выполнятся мгновенно не с первого раза, и это возможно будет замедлять работу декодера. Иными словами вся ситуация проявится только в тот момент, когда код береться из памяти и заносится в IC, в следующих же итерациях цикла на том же код, это влиять не будет.



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



3. Я упомянул - при первом проходе. Это врядли можно считать за значимую задержку, но все же менее эффективно префиксов.



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

 

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

2. Такое ощущение, что ты только в Code-Analyst и работал, а с созданием процессоров дело не имел =) Во первых, работа декодера меня мало волнует - в кэше трасс уже сгенерированные мопы. Во вторых jmp плохой пример - его и оптимизировать не надо, он даже в трассу не пишется. Третье - работу декодера это сравнение не замедлит - я уже это опробовал - да это и так ясно любому кто знаком с vhdl.

3. Опять 25. Я же написал схему в которой это одно и тоже после фазы декодера, декодер будет работать так-же эффективно и вообще декодер не важен, т.к. код в основном исполняется из трассы, с чего "менее эффективно префиксов"? Напиши наконец свою схему как все происходит на нижнем уровне.

4. Если насчет мопа не ясно - предложи свое решение - я их уже 2 предлагал - моп в одном слоте трассы и поле в каждом слоте(менее эффективно - раздутие кэша, в слоте каждый бит на счету). И вообще сколько пока ни бился - выжать выгоду на симуляторе из твоей идеи пока не удается, т.к. зависимость после ветвления часто случается и BTB буффер показывает результаты лучше.

 

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

2. Процессоры я не создавал.

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



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

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



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

Вот типичный пример кода:

Код (Text):

1.  
2. <font face="fixedsys]<font size=1>
3. xor       eax, eax
4. xor       ecx, ecx
5. xor       edx, edx
6. xor       ebx, ebx
7. cmp       [esi + 0], ebp
8. sete      al
9. cmp       [esi + 1], ebp
10. sete      cl
11. shl       ecx, 1
12. cmp       [esi + 2], ebp
13. sete      bl
14. shl       ebx, 2
15. cmp       [esi + 3], ebp
16. sete      dl
17. shl       edx, 3
18.  
19. or        eax, ecx ;; wait for 1, 2 cmp
20. or        ebx, edx ;; wait for 3, 4 cmp
21. or        eax, ebx
22. mov       [eax]
23. </font><!--size--></font><!--face-->
24.  

На правильной реализации - результаты первого и второго сравнения потребуются только с первой командой or. То есть процессор сможет успеть расчитать 2 варианта для каждого из четырех регистров, используя SIMD затратив на это столько же тиков как и на обычное выполнение (иными словами каждый mop работает с 64-битными данными):

Код (Text):

1.  
2. <font face="fixedsys]
3. mov       al, 0   ;; mov sh_al, 1
4. mov       cl, 0   ;; mov sh_cl, 1
5. shl       ecx, 1  ;; shl sh_ecx, 1
6. mov       dl, 0   ;; mov sh_dl, 1
7. shl       edx, 2  ;; shl sh_edx, 1
8. mov       bl, 0   ;; mov sh_bl, 1
9. shl       ebx, 3  ;; shl sh_ebx, 1
10. ;; eax == ecx == 0; sh_eax == 1, sh_ecx == 2
11. <if ([esi + 0] == ebp) eax @= sh_eax>
12. <if ([esi + 1] == ebp) ecx @= sh_ecx>
13. or        eax, ecx ;;
14. <if ([esi + 2] == ebp) edx @= sh_edx>
15. <if ([esi + 3] == ebp) ebx @= sh_ebx>
16. or        ebx, edx
17. or        eax, edx
18. </font><!--face-->
19.  

Надеюсь иллюстрация понятная

 

1. C MMX совсем другая история. Например итаниумовский pcmp - n паралелльных вычитаний с сохранением битовых флагов в регистре - где тут связь вообще? Или SSEшный PCMP*, либо операнды готовы и можно исполнить, либо инструкция стоит и ждет операндов, а независимый код далее исполняется. У нас ведь проблема в чем? eflags зависит от какого-нибудь cmp, который ждет свои операнды, от eflags зависит исполнять ли кондиционную инструкцию или нет, а от этого зависит откуда брать результат в случае зависимости от кондиционной инструкции - из теневых регистров или нет. Ничего кроме стала тут не придумаешь - параллельно исполнять нужно 2 полноценных конвеера. Аналогии с MMX никакой.

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

4. Не понял, как этот код к нашему случаю относится, видимо из-за непоняток со смид аналогией. Ну а так, заткнется это дело на первом shl в твоем случае т.к. неизвесно какой ecx брать. С какой стати в комментах тока ";; shl sh_ecx, 1" а не ";; shl sh_ecx, 1 shl ecx, 1"? Или ты собрался делать оптимизацию что сдвиг нуля эффекта не даст? Обломись, он еще флаги апдейтит - оба варианта надо исполнять. И еще одна неточность - не mov cl, 0 а без изменений. Код в твоем варианте ведь вот:

Код (Text):

1. [b]xor       eax, eax
2. xor       ecx, ecx
3. xor       edx, edx
4. xor       ebx, ebx
5. cmp       [esi + 0], ebp
6. oneq      mov al, 1
7. cmp       [esi + 1], ebp
8. oneq      mov cl, 1
9. shl       ecx, 1
10. cmp       [esi + 2], ebp
11. oneq      mov bl, 1
12. shl       ebx, 2
13. cmp       [esi + 3], ebp
14. oneq      mov dl, 1
15. shl       edx, 3
16.  
17. or        eax, ecx ;; wait for 1, 2 cmp
18. or        ebx, edx ;; wait for 3, 4 cmp
19. or        eax, ebx
20. mov       [eax][/b]

Или mov cl, 0 не ошибка и ты собрался реализацию sete менять?

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

....

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

 

semen

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

4. Я показывал в комментах выполнение для теневого результата, а в коде - для реального результата. Почему mov cl,0? Я понимаю логику команд setcc как оценку флагов и занесение в параметр значения 1 по выполнению, и 0 по не выполнению. В случае не теневого кода - команда не выполняется всегда - что означает эквивалент mov r8, 0. То есть это как бы представление команды sete на уровне параллельного выполнения. Одновременно в cl заносится 0, a его теневую пару - 1, далее идет операция сдвига сразу обоих чисел (также как это делает psllq).

С флагами конечно действительно придется подумать, иначе получается если используется результат флагов - при третьем cmp в коде - а результат shl двоится - для 1 и 0.

 

1. Потому что для пар значений надо либо дважды направить оп на исп. устройства или иметь 2 исп. устройства. Единственный способ избежать сталла - не выполнять ее, а идти дальше. Реализовать я это сам не смог - требуется глобальная переделка ROB`а + приходится делать схемы коммутации регистровых файлов, что вносит задержки (этого ведь не требуется просто для разрешения зависимостей - для этого есть красивое решение - ROB). Вобщем это выше моих знаний - так что считаем что ответ мне неизвестен. Тем не менее я считаю что префиксы все равно излишни с точки зрения баланса усложнения процессора. Цитата: "В любом случае можно просто оптимизировать без внесения префиксов - это точно." т.е. видимых преимуществ кроме объема экзешника я не вижу, а на заполнение кэша трасс это не скажется.

 

semen

1. А почему одна инструкция не может обрабатывать данные удвоенной разрядности? Скажем psllq работает на 64-битных данных. Если представить что работа префиксной оптимизации будет эффективной только для 32-битных данных, то особых проблем я не вижу - все теневые регистры в самых последних процессорах - 64 битные, и использовать старшую половинку впринципе ничто не запрещает. Есстественно потребуется модификация ИУ, что бы они работали в 32-битном режиме сразу на двух частях регистров. И в крайнем случае - почему бы тогда не удвоить количество ИУ - гипертрединг от этого только лучше заработает.

 

alpet

Потому что это эквивалент удвоения исп. блоков - это и есть работающие параллельно 2 конвеера, только регистровые файлы у них связаны, что тоже сказывается не положительным образом. Как я уже изначально говорил - сделать поддержку исключения пенальти неправильного предсказания для нескольких нужных инструкций - это можно, только другим способом - именно модификацией ИУ без всяких теневых веток исполнения и ROB переделывать не надо - только много так не внесешь, баланс нужен и не каждая инструкция легко поддастся - к томуже все равно при зависимости от нее, зависимая инструкция застрянет а ROB`е (то что ты пытаешься избежать параллельным исполнением 2х веток), но конвеер не остановится. Хотим же универсальность и все инструкции - такая байда, что ничего хорошего из метода теневого исполнения не выходит. Можно например еще пробовать без внесения новых ИУ поддержать все простые не SSE инструкции и исполнять их в SSE блоке - типа там-то можно 2 регистра сразу сложить в одном XMM =) - увы ничего не выйдет - сложностей дофига - integer возможности XMM скудны, там нет битового сдвига, выдвижения во флаги нет, надо коммутировать и пересобирать вохд\выход - различий и трудностей ну тыща - всего не перечислить, а самое то главное - латентность блока XMM какая? Ты оптимизировать хочешь или замедлить? Потому-то это и разные блоки - векторный и нет, и мопы в разных блоках параллельно исполняются. И чтоб исполнять "с двойной разрядностью" - это полный дубль всех ИУ. А это =) хаха накладно - двухядерность явно выгоднее, да и проще - регистровые файлы не связаны. Короче все - конструктор сделай сам =) а мне надоело уже.

 

alpet, сделай сортировку. Для 256 элементов аппаратная

на параллельных сравнивателях занимает не более 36 тактов ( Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ ). Зато фирме Интел можно будет гордиться не только обработкой строк.

 

man

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



И причем здесь Intel, она вроде своим путем идет?

 

alpet

> "использовать старшую половинку в принципе ничто не запрещает. Есстественно потребуется модификация ИУ..."



Ну допустим, вычислили мы для n инструкций по два результата. А что дальше, ты подумал что скрывается за простой строчкой "<if (...) eax @= sh_eax>" ? О каком eax идет речь ? Если все n инструкций изменяют eax, то мы имеем не менее n разных регистров RF, соответсвующих разным мопам и последовательным состояниям eax. И все эти мопы обязаны пройти ретайрмент. Значит нужно либо усложнять логику ретайрмента (и врядли он тогда сможет обрабатывать 3 мопа за такт), либо в каждом из выполненных мопов установить флаг - какая из половинок соответствует результату (это соответсвенно перебор всех мопов после cmp). Но это еще не все - вопрос как вернуться в нормальный режим исполнения ? Раз конвейер рулит без остановки, то на момент исполнения cmp в ROB сидят не только выполненные мопы, но и уже подготовленные для такого же "двойного" исполнения. Что с ними делать - тоже все просматривать и переводить в нормальный режим ? Представляю, сколько это займет времени Или есть другие решения ?

 

alpet, я говорю не о улучшении алгоритмов, а о существенной добавке к электрической схеме процессора. Нужно добавить (много) простеньких сравнивателей. Оценка 36 для 256 не является (я думаю) наилучшей, но она достижима.

 

leo

1. Все инструкции меняют eax это верно, но ведь после выполнения условной команды будет всего два варианта значения - и над вторым значением можно выполнять вычисления синхронно с первым. Откуда здесь n значений в таком случае?

Сложностей конечно не мало, тем более что после идеи сразу правильную реализацию продумать очень сложно, практически нереально.

Код (Text):

1.  
2.  
3. <font face="fixedsys]<font size=1>
4.  
5.      mov  eax, 0    ;; Load
6.  
7.      cmp  ebx, 3    ;; Alu with ebx
8.  
9. oneq mov  eax, 5    ;; Load <shadow_eax = 5>
10.  
11.      add  eax, ebx  ;; eax += ebx, shadow_eax += ebx
12.  
13.      xor  eax, edx  ;; eax ^= edx, shadow_eax ^= edx
14.  
15.      shl  eax, 2    ;; Эквивалент psllq для eax и shadow_eax
16.  
17.  ;; флаги после cmp готовы, в зависимости
18.  
19.  ;; от выполнения условия eq, в eax может быть скопирован shadow_eax
20.  
21.  
22.  
23.      
24.  
25. </font><!--size--></font><!--face-->
26.  
27. Что касается рейтармента - требуется серьезная переделка, с таким расчетом чтобы каждый моп производил свою операцию на двух операндах сразу - т.е. с каждым GRP регистром связываются уже целых два теневых регистра - таким образом чтобы переассоциация GPR регистра к одному из них осуществлялась с минимумом задержек (например специальным мопом). Без усложнения здесь действительно не обойтись, и далеко не факт что всякий код использующий технологию будет от нее много выигрывать.
28.  
29. Основной момент для простой реализации - каждый моп выполняет всегда "лишнюю, избыточную работу", за исключением когда он используется какой-нибудь MMX командой (если здесь можно оптимизировать). Сложность здесь основная в том что по "теневым" данным также придется выставлять "теневые" флаги, ее я пока разрулить не знаю как.
30.  
31.  
32.  
33. [b]man[/b]
34.  
35. Процессоры становятся многоядерными, надо ориентироваться соответственно на многопоточные алгоритмы сортировки. Но оставим эту тему в стороне - центральный процессор просто не обязан быть специализированным процессором. Тут такая штука - скажем введение схемы аппаратной сортировки в процессор, поднимет сложность его изготовления,  соответствено себестоимость к примеру на 20 у.e (наибольший рост цены в основном из-за возрастающего количества брака), и TDP на 3Вт. И зачем большинству потребителей спрашивается такой комбайны с большим энергопотреблением-тепловыделением-ценой, если специфика их применения ограничится небольшим рынком оптимизированного софта, выполняющего сотни сортировочных операций в секунду. А от количества сравнивателей врядли что изменится в лучшую сторону...

 

alpet

1. Ну скока можно повторять, что

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

man

Много простых сравнивателей уже есть - pcmp* в SSE - думай, как это можно прикрутить к сортировке.

 

semen

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

 

alpet

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