Сложение очень-очень длинных чисел

"Уговорить" P4-1800 15.2.4 выполнять ADC с перекрытием никак не удается.

При развороте большую часть MOV удается распараллелить с ADC, но сами ADC все равно выполняются последовательно, поэтому общую задержку менее ~1050-1100 тиков получить не удается (т.е. ~8 тактов на сложение = latency ADC). Перепробовал все варианты расположения mov и, ради экперимента, вообще закоментировал все mov, оставив одни ADC - нет не желают они перекрываться и все тут. Видимо Intel-ы чего-то напутали: или в мануале опечатка или блок динамического исполнения "недоделанный". В мануале для ADC throughput = 3, а на деле получается ~8 = latency. (По определению: "Throughput - the number of clock cycles required to wait before the issue ports are free to accept the same instruction again").



Вывод простой: ADC на P4 - это "тормозной отстой"

 

leo > "Уговорить" P4-1800 15.2.4 выполнять ADC с перекрытием никак не удается."

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

 

leo >

Да зачем intel'у путать в доках, причем от версии к версии..

Есть такое понятие, как заваисимость по данным.

Пока данные для операции не готовы, выполняться она не будет.

ADC ждёт результатов выполнения предыдущего ADC.

Именно поэтому в данном случае и получается, что throughput не 3, а "как бы" 8.

 

S_T_A_S_

Насчет зависимости я конечно понимаю и не зря подчеркнул цитату "to accept the same instruction again". Вопрос в том, как понимать "the same" - как "точно такую же" или "похожую, аналогичную". Последовательные инструкции ADC всегда являются зависимыми и если вторая вынуждена всегда ждать первую, то интелам не стоило бы морочить людям голову и указывть throughput = 3 вместо 8, если под "the same" в данном случае имеется ввиду такая же ADC. Если же под throughput понимается просто освобождение порта для принятия другой инструкции - тогда понятно.



И потом, у меня теплилась надежда на то, что все-таки флаг CF играет особую роль, т.к. используется в ADC\SBB и поэтому устаналивается не только в EFLAGS, откуда его потом долго извлекать (сутя по latency ADC,SBB,SETC), а еще и в некий дополнительный бит или темп-регистр. И тогда, если бы P4 был бы "поумнее", вторая ADC могла бы работать быстрее, беря на лету это значение CF не связываясь с EFLAGS. Но к сожалению, это оказалось бесплодными фантазиями.



PS: Посмотрел, что пишет Агнер Фог (pentopt.pdf), так у него для ADC на P4 приводится throughput = latency = 6 для r,r и 8 для r,m. Все ясно и понятно.

 

leo

Возможно если между первой ADC и второй вставить инитрукцию, которая "разобьет" зависимость между ними, то тогда и только тогда будет throughput = 3?

 

leo >

Код (Text):

1.      „Для неведомого все имена, что одно.
2.      Видеть в чудесном чудесное - вот ключ ко всем тайнам мира.“

>

Как-то один очень уважаемый мною человек сказал мне, что athlon способен выполнить 9 nop за такт.

Только по прошествии большого количества времени я (надеюсь) понял, что он хотел мне сказать.



В 2х словах смысл такой:

Существует как непроверенная информация, так и официальная документация!

 

S_T_A_S_

Все-таки я не понимаю, что ты хочешь сказать. Я вроде бы свою мысль уже пояснил: если 3 - это время освобождения порта для приема (не обязательно начала исполнения) следующей инструкции, то ясно. НО если следующая ADC всегда вынуждена ждать завершения предыдущей ADC, то реальный темп выполнения последовательных ADC будет >= 8 тактов. Правильно ?



Что касается уважаемого Агнера, то он приводит другую, более понятную величину reciprocal throughput:

This value indicates the number of clock cycles from the execution of an instruction begins to a subsequent independent instruction can begin to execute in the same execution subunit. Как видим, эта величина больше соответствует тому, что мы хотим знать об ADC, чем величина throughput приводимая Intel.

 

Хмм.. И все-же разбивание зависимости влияет:



RDTSCTimer timer;

timer.StartCount();

__asm

{

mov ecx, 100000

mov ebx, 1

xor eax, eax

.align 16

loop_:

adc eax, ebx

adc eax, ebx

adc eax, ebx

adc eax, ebx

adc eax, ebx

adc eax, ebx

adc eax, ebx

adc eax, ebx

adc eax, ebx

adc eax, ebx

adc eax, ebx

adc eax, ebx

adc eax, ebx

adc eax, ebx

adc eax, ebx

adc eax, ebx

dec ecx

jnz loop_

}

__int64 time = timer.GetTime();

printf("processor ticks without break: %I64i\n", time);



timer.StartCount();

__asm

{

mov ecx, 100000

mov ebx, 1

xor eax, eax

.align 16

loop2_:

mov edx, 0xffffffff

adc eax, ebx

shl edx, 1

adc eax, ebx

shl edx, 1

adc eax, ebx

shl edx, 1

adc eax, ebx

shl edx, 1

adc eax, ebx

shl edx, 1

adc eax, ebx

shl edx, 1

adc eax, ebx

shl edx, 1

adc eax, ebx

shl edx, 1

adc eax, ebx

shl edx, 1

adc eax, ebx

shl edx, 1

adc eax, ebx

shl edx, 1

adc eax, ebx

shl edx, 1

adc eax, ebx

shl edx, 1

adc eax, ebx

shl edx, 1

adc eax, ebx

shl edx, 1

adc eax, ebx

dec ecx

jnz loop2_

}

time = timer.GetTime();

printf("processor ticks with break: %I64i\n", time);



Что выдает на моем P4Mobile-1700 F15 M2 S4:

processor ticks without break: 11953340

processor ticks with break: 9814656



Т.е. с разбиением 6 тиков на adc и сдвиг



на P4-2800 F15 M2 S9:

processor ticks without break: 11448676

processor ticks with break: 6386308



Т.е. с разбиением 4 тика на adc и сдвиг



на Dual P2-300 F6 M3 S3:

processor ticks without break: 3921358

processor ticks with break: 4022432

- 2.5 тика

 

semen

Да, результат интересный в познавательном плане.

Вот только перенос при такой разбивке теряется и к задаче сложения это видимо никак не "прицепишь".



PS: С P2,P3 (Family 6) все понятно, там и ADC 2-3 такта.

 

leo >

Ну почему же всегда? CF можно учитывать другим способом, и добавить инструкции убирающие зависимость по данным (см. пример semenа)





>

Вот здесь ключевое слово "хотим". Такая уж психология у людей - из 2х вариантов ответа выбирается не тот, который правильный, а тот что по душе. Захотим - у нас и the same будет значить "похожую, аналогичную"





>

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

Если же знать формат, знать о (не)возможности складывать 2 пары чисел параллельно - тогда можно перейти от слов "видимо" к "очевидно"..



ЗЫ: про "любой формат" мне можно не напоминать, я пытался делать предположения, а они оказались частным случаем. А как можно сочинять свой формат не зная толком как он потом будет использоваться, не пойму

 

S_T_A_S_

Ты все о своем. Почему "обычные"-то числа нельзя складывать. Есть же int16, int32, int64, так почему бы и int512 не использовать. Gray прав - вроде бы все уже выжали из "обычного" сложения. Если интересно, то можно и другие форматы рассмотреть или параллельное сложение двух пар чисел.



Хотя до кучи вот еще вариантик - с использованием циклического сдвига RCL, который работает несколько быстрее SETC:

Код (Text):

1.     shr ecx,2
2.     xor edx,edx
3.     xor ebp,ebp
4. align 16
5. @@loop:
6.     mov eax,[esi]
7.     mov edi,[ebx]
8.     or  edx,ebp
9.     add edi,eax
10.     rcl ebp,1
11.     and edx,1
12.     add edi,edx
13.     mov [ebx],edi
14.     rcl edx,1
15.     .............
16.         ;разворот цикла на 4: +3 повтора со смещением 4, 8 и 12
17.     .............
18.     lea esi,[esi+16] ;add esi,16 - без разницы
19.     lea ebx,[ebx+16]
20.     sub ecx,1        ;dec ecx - хуже
21.     jnz @@loop}

Также возможна "статистическая" модификация с заменой rcl edx,1 на jc:

Код (Text):

1.     mov eax,[esi]
2.     mov edi,[ebx]
3.     add edi,eax
4.     rcl ebp,1
5.     and edx,1
6.     add edi,edx
7.     mov [ebx],edi
8.     jc  @@carry1
9.     mov edx,ebp
10. @@carry1:

Результаты на P4-1800 (15.2.7):

Код (Text):

1. Gray.............1428
2. leo_rcl..........1008
3. leo_rcl_jc.......816,900,[b]828,828[/b]... - разные цифры для проходов 2,3 и 4-8 для данных Data1 Gray
4. ...............................видимо из-за наличия переходов по jc

 

leo

Ну я о познавательном плане и заботился... к тому что интел не соврал про throughput = 3... и если в этой задаче не получится использовать быстрый adc - в другой получится...

 

semen

Ясно, спасибо

 

Учел замечания semen и S_T_A_S_ по возможности перекрытия ADC за счет добавления инструкций, учитывающих перенос и устраняющих зависимость ADC. На P4 15.2.7 получаются превосходные результаты при развороте цикла на 4 сложения:

Код (Text):

1. macro leo_ADC_fast4{
2.     shr ecx,2
3.     clc
4. align 16
5. .loop:
6.     mov     eax,[esi]
7.     mov     edi,[ebx]
8.     mov     ebp,eax
9.     adc     eax,edi         ;ADC[0] <--- EAX
10.     ;устраняем зависимость
11.     add     ebp,edi         ;"основной" перенос
12.     inc     ebp             ;контроль "редкого" случая x[i]+y[i] = $FFFFFFFF
13.     jz      .carry1
14. .ret1:
15.     mov     edx,[esi+4]
16.     mov     edi,[ebx+4]
17.     mov     ebp,edx
18.     adc     edx,edi         ;ADC[4] <--- EDX
19.     ;устраняем зависимость
20.     add     ebp,edi
21.     inc     ebp
22.     jz      .carry2
23. .ret2:
24.     mov     [ebx],eax       ;---> MOV[0] EAX
25.     mov     eax,[esi+8]
26.     mov     edi,[ebx+8]
27.     mov     ebp,eax
28.     adc     eax,edi         ;ADC[8] <--- EAX
29.     ;устраняем зависимость
30.     add     ebp,edi
31.     inc     ebp
32.     jz      .carry3
33. .ret3:
34.     mov     [ebx+4],edx     ;---> MOV[4] EDX
35.     mov     edx,[esi+12]
36.     mov     edi,[ebx+12]
37.     adc     edx,edi         ;ADC[12] <--- EDX
38.     ;здесь остается ждать результата
39.     mov     [ebx+8],eax     ;---> MOV[8] EAX
40.     mov     [ebx+12],edx    ;---> MOV[12] EDX
41.  
42.     lea     esi,[esi+16]
43.     lea     ebx,[ebx+16]
44.     dec     ecx
45.     jnz     .loop
46.  
47.     jmp     .end
48. .carry1:
49.     ;--- коррекция CF ---
50.     ;здесь ebp = x+y+1 = 0 => либо eax = 0 (был перенос и будет),
51.     ;                         либо eax = -1 = $FFFFFFFF (не было переноса и не будет)
52.     cmp eax,-1 ;CF установится если eax = 0, т.е. eax ниже $FFFFFFFF
53.     jmp .ret1
54. .carry2:
55.     cmp edx,-1
56.     jmp .ret2
57. .carry3:
58.     cmp eax,-1
59.     jmp .ret3
60. .end:
61. };==========================================

Можно учет переноса по JZ вставить в тело цикла, но при этом результаты получаются несколько хуже

Код (Text):

1.     add     ebp,edi
2.     inc     ebp
3.     ;db $3E     ;префикс выполнения прыжка, при нескольких проходах ничего не дает
4.     jnz     .ret1
5.     cmp     eax,-1
6. .ret1:
7.     .......

Вот результаты на P4-1800 (15.2.7)

Код (Text):

1. Gray...............1428
2. Gray_SSE2...........940
3. leo_JZ..............832  
4. leo_ADC_fast4......732,776,728,[b]676,676[/b]... ;рез-ты проходов 2,3.. по Data1 Gray
5. leo_ADC_fast4jnz...756,772,772,[b]692,692[/b]... ;- " -

Кстати на P4 15.2.4 этот же код дает заметно худшие результаты, а предварительный разворот на 8 сложений тоже получается чуть хуже => остаются какие-то зависимости от расположения инструкций, длины тела цикла и т.п.

 

leo, ты меня поражаешь! Я уж думал, что все из процессора уже выжали, а ты своим leo_ADC_fast4 показал, что сие вовсе не так.



leo >"На P4 15.2.7 получаются превосходные результаты при развороте цикла на 4 сложения..."



На P4 15.2.9 результаты столь же превосходны, завтра протестирую на других процессорах.



P.S. Воистину nop так же неисчерпаем как и pop

 

leo, поигрался я с твоим удивительным leo_ADC_fast4 в перестановки инструкций (на P4 15.2.9). Удалось еще немного ускорить :



macro leo_ADC_fast4_m{

shr ecx,2

clc

;align 2

.loop:

mov eax,[esi]

mov edi,[ebx]

mov ebp,eax

adc eax,edi

add ebp,edi

inc ebp

jnz .ret1

cmp eax,-1

.ret1:

mov edx,[esi+4]

mov edi,[ebx+4]

mov ebp,edx

adc edx,edi

add ebp,edi

inc ebp

jnz .ret2

cmp edx,-1

.ret2:

mov [ebx],eax

mov eax,[esi+8]

mov edi,[ebx+8]

mov ebp,eax

mov [ebx+4],edx

adc eax,edi

add ebp,edi

inc ebp

mov [ebx+8],eax

jnz .ret3

cmp eax,-1

.ret3:

mov edx,[esi+12]

mov edi,[ebx+12]

adc edx,edi

mov [ebx+12],edx

lea esi,[esi+16]

lea ebx,[ebx+16]

dec ecx

jnz .loop



.end:

};==========================================



;____________________Data1_____Data1_____Data2____Data1____Data2____Da ta1____Data2____Data1

;____________________Comp1_____Comp2_____Comp2____Comp3____Comp3____Co mp4____Comp4____Comp5

;Gray_SSE2;____________940_______880______880_________________________ ____________________

;leo_JZ_pop2;__________824_______916_____1008______625_____958_______6 25_____1026______625

;leo_JZ_pop;___________948_______920_____1204_____1034____1432______10 34_____1432_____1034

;leo_JZ;_______________824_______924_____1064______657____1307_______6 57_____1432______780

;gray_pop;____________1092______1100_____1164_____1400____1414______14 00_____1415_____1400

;svin_test2;__________1216______1176_____1120_____1459____1473______14 59_____1473_____1459

;leo_setc;____________1224______1212_____1232_____1044____1044______10 44_____1044_____1044

;leo;_________________1232______1228_____1228______738_____738_______7 66______766______739

;leo_setc2;___________1300______1272_____1412______796_____796_______7 96______796______796

;svin_test_gray;______1220______1284_____1280_____1401____1413______14 01_____1413_____1401

;svin_test;___________1220______1292_____1272_____1400____1412______14 04_____1412_____1400

;Gray;________________1428______1400_____1400_____1033____1033______10 33_____1033_____1033

;leo2;________________1428______1400_____1400_____1118____1118______11 18_____1118_____1118

;The_Svin;____________1432______1420_____1420_____1119____1119______11 19_____1119_____1119

;gray_popall;_________1588______1624_____1624______371_____371_______3 57______357______371

;leo_ADC_fast4;________692______1248_____1256_____1200____1211______12 00_____1211_____1200

;leo_ADC_fast4_m;______676______1244_____1248_____1124____1136______11 24_____1136_____1124

;

;

;Comp1 - Processor= x86 Family 15 Model 2 Stepping 9 GenuineIntel ~2664 Mhz (Windows XP) DDR (Notebook Dell Lattitude 100, Windows XP)

;Comp2 - Processor= x86 Family 15 Model 2 Stepping 4 GenuineIntel ~2254 Mhz (Windows XP)

;Comp3 - Processor= x86 Family 6 Model 8 Stepping 3 GenuineIntel ~601 Mhz (Windows 2000)

;Comp4 - Processor= x86 Family 6 Model 11 Stepping 1 GenuineIntel ~601 Mhz) (Windows 2000 Server).

;Comp5 - Processor= x86 Family 6 Model 11 Stepping 4 GenuineIntel ~1327 Mhz (Windows XP) Notebook Toshiba Satellite



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



На младших моделях самый шустрый gray_popall. Иль я упустил какой-то из развернутых вариантов?



P.S. Чудны твои пути, Intel! Ну кто бы мог подумать, что 2*N сложений можно сделать быстрее чем N.

 

Gray

> "Удивительно и немного обидно, что этот вариант быстрошустр только на старших моделях процессора"

В случае с P3 и вообще P6-family это понятно - у них сама ADC достаточно шустрая. А вот интересно почему на P4 15.2.4 не получается перекрытия ADC - все теже 9-10 тактов на сложение. Может для этой модели попробовать увеличить число сложений в цикле ? Или все-таки Агнер частично прав насчет throughput (не с потолка же он взял свои цифры) ?



> "Иль я упустил какой-то из развернутых вариантов?"

Наверное, упустил простой безымянный разворот на 32 сложения за цикл (leo: Окт 28, 2004 22:55:36). По сути это практически тоже самое, что и твой вариант с POPA. Но он, на мой взгляд показывает, что выигрыш на P3 достигается не за счет POPА, а за счет "хорошего" расположения инструкций (что, кстати, вполне соответствует "учению" Агнера).

 

Вот оптимизированный вариант разворота для P3.

Для 16,32 сложений на цикл получается пошустрее чем gray_popall.

Код (Text):

1. macro P3_ADC_unroll countdeg {
2. <font color="gray];countdeg = 3,4,5,6 = log2(count)</font><!--color-->
3. count = 1 shl countdeg <font color="gray] ;число сложений в цикле = 8,16,32,64</font><!--color-->
4.         shr ecx,countdeg
5.         clc
6. align 16
7. @@:
8.     <font color="gray];два первых сложения</font><!--color-->
9.         mov eax,[esi]         ;a  0
10.         mov ebx,[esi+4]       ;b  4
11.         mov edx,[esi+8]       ;d  8
12.         adc eax,[edi]
13.         mov [edi],eax
14.         adc ebx,[edi+4]
15.     <font color="gray];повтор блоков по 6 сложений</font><!--color-->
16. reps = (count-2)/6
17.     repeat reps
18. ofs = (%-1)*24 <font color="gray];смещение в каждом блоке увеличивается на 6*4=24</font><!--color-->
19.         mov eax,[esi+12+ofs]  ;a
20.         mov [edi+4+ofs],ebx
21.         adc edx,[edi+8+ofs]
22.         mov ebx,[esi+16+ofs]  ;b
23.         mov [edi+8+ofs],edx
24.         adc eax,[edi+12+ofs]
25.  
26.         mov edx,[esi+20+ofs]  ;d
27.         mov [edi+12+ofs],eax
28.         adc ebx,[edi+16+ofs]
29.         mov eax,[esi+24+ofs]  ;a
30.         mov [edi+16+ofs],ebx
31.         adc edx,[edi+20+ofs]
32.  
33.         mov ebx,[esi+28+ofs]  ;b
34.         mov [edi+20+ofs],edx
35.         adc eax,[edi+24+ofs]
36.     <font color="gray];если последнее сложение для count = 8,32,128</font><!--color-->
37.     if  %*6 = count-2
38.         mov [edi+24+ofs],eax
39.         adc ebx,[edi+28+ofs]
40.         mov [edi+28+ofs],ebx  <font color="gray];сохраняем результат</font><!--color-->
41.     else
42.     <font color="gray];если не последнее, то грузим след.значение, а рез-т ADC не сохраняем</font><!--color-->
43.         mov edx,[esi+32+ofs]  ;d
44.         mov [edi+24+ofs],eax
45.         adc ebx,[edi+28+ofs]
46.     end if
47.     end repeat
48.  
49.     <font color="gray];для count = 16 и 64 остаются еще 2 сложения</font><!--color-->
50.     if  (count-2) mod 6  > 0
51.     ofs2 = reps*24
52.         mov eax,[esi+12+ofs2]  ;a
53.         mov [edi+4+ofs2],ebx
54.         adc edx,[edi+8+ofs2]
55.         mov [edi+8+ofs2],edx
56.         adc eax,[edi+12+ofs2]
57.         mov [edi+12+ofs2],eax
58.     end if
59.  
60.         lea esi,[esi+count*4]
61.         lea edi,[edi+count*4]
62.         dec ecx
63.         jnz @B
64. };======================================================
65. macro P3_ADC_unroll_8{P3_ADC_unroll 3}
66. macro P3_ADC_unroll_16{P3_ADC_unroll 4}
67. macro P3_ADC_unroll_32{P3_ADC_unroll 5}
68. macro P3_ADC_unroll_64{P3_ADC_unroll 6}
69. };======================================================
70.  
71. Результаты на [u]P3-650 (6.8.1)[/u]
72. gray_popall......................[b]371[/b]
73. P3_ADC_unroll_8..................389
74. P3_ADC_unroll_16.................[b]340[/b]
75. P3_ADC_unroll_32.................[b]311[/b]
76. P3_ADC_unroll_64.................313 - видимо "насыщение" ~ 2.4 такта на сложение

Вывод: по-видимому гипотеза о "массовом чтении" не подтверждается. Рулит обычное распараллеливание: циклическая последовательность операций adc(r,m) mov(r,m) mov(m,r) для P3 по всей видимости является "оптимальной" - согласованной по latency и по использованию разных портов.

Возможно даже схема оптимального декодирования 4-1-1 моп за такт по Агнеру рулила бы, да вот только длина каждой инструкции 3 байта, поэтому неизбежны разбивки инструкций границами 16 байтных ifetch блоков, а с ними и изменение порядка декодирования и соответствующие penalty. В принципе можно поизвращаться и в каждом втором ADC заменить [edi+ofs] на [edi+ebp+ofs] при ebp=0. Может попробую ради спортивного интереса и проверки учения Агнера.

 

Вот поизвращался с выравниванием длины 5 инструкций на 16 байт (замена [edi+ofs] на [edi+ebp+ofs] при ebp = 0). Разницы никакой. Оказывается тот же Агнер учит, что mov(m,r) на P3 это 2 микрооп (а не 1), так что схема 4-1-1 не действует. Хотя при явном (без repeat) развороте цикла 32 сложений удается уменьшить число тиков с 311 до 303 за счет перестановки местами mov(r,m) и mov(m,r) на границах 16 байт (для ускорения декодирования по Агнеру). Но это мелочь, не стоящая свечь. Так что теория действует, но конкретный код оставляет мало простора для ее реализации.



Кстати попробовал заменить все mov r,[esi+disp] на вариант с POP r - получилось значительно хуже (для 32 сложений 412 тиков вместо 311). У Агнера и на это можно найти ответ: POP это 2 мопа - mov и приращение esp на 4, которое выполняется на одном из АЛУ и => отнимает такт у ADC.

 

Кстати еще о тонкостях "при ловле блох". В используемом test.asm от Gray начало макроса соответствует смещению xCh. Поэтому если луп выравнен align 16, то перед ним хорошо умещаются до 4 байт подготовительных инструкций. Если больше, то в итоге получаем длинную цепочку нопов перед лупом которые по крайней мере на P3 ухудшают результат на ~ 5 тиков. Поэтому можно считать, что в упомянутом выше эксперименте с добавлением [edi+ebp+ofs] выигрыш чуть больше, но он съедается за счет добавления перед лупом xor ebp,ebp и как следствие вставкой длинной цепочки нопов. Вот такая "блин", наука..



PS: Если вынести обнуление ebp в начало тестовой проги, то как раз получается 298 тиков (= 303-5). А 5 тиков это время декодирования на P3 xor и цепочки нопов на общей длиной в 16 байт.