Доброго всем дня и с Наступающим!!! Никогда до этого не занимался оптимизацией на низком уровне... Решил написать сюда и почитать мнения гуру, т.к. время выполнения программы просто зашкаливает, а своих идей нет... Есть простая процедура на С++: Код (Text): inline FLOATING_VAR Neuron::calculate() { //this will calculate output sum = 0; for (int i = 0; i < inputs; i++) sum+=sinapsData[i] * inputData[i]; //add polarization sum+=sinapsData[inputs]; axon = sigmoid(sum); return axon; } , где - FLOATING_VAR - это просто define float - sum, axon - переменные типа float, не определены - inputs - переменная int=1024 - sinapsData, inputData - массивы float размером 1025, заранее определены Эта процедура выполняется очень много раз в процессе работы программы (~10^6-8). Вопрос номер 1: Можно ли в этом коде хоть что-нибудь оптимизировать c т.з. скорости средствами Cpp? Насколько я понимаю - самое "узкое место" в этой процедуре - это цикл, в котором выполняются операции умножения. (for (int i = 0; i < inputs; i++) ...) Почитав соседний топик про SSE, решил наконец разобраться с этой технологией. Думал так: у меня есть 2 массива, размерностью 1024, которые нужно перемножить. Буду делать не в цикле по каждому элементу, а разобью массивы на группы по 16 элементов, чтобы влезло в регистры XMM. Затем все перемножу и сложу. К сожалению, моя реализация этого же кода под SSE работает в 5 (!!!) раз медленнее, чем приведенный выше код. Вот и решил разобраться, толи у меня руки не оттуда, толи мой компилятор такой умный, толи еще что-то. Отсюда вопрос номер 2: почему код, не оптимизированный, и работающий с сопроцессором, работает быстрее в 5 раз чем мой, через SSE. Знающие люди, подскажите! Ниже привожу листинги: Код (Text): 1) Листинг дизассемблированного кода процедуры (которая была выше) inline FLOATING_VAR Neuron::calculate() { 00401090 push ecx 00401091 push esi 00401092 push edi 00401093 mov esi,ecx //this will calculate output _asm int 3 00401095 int 3 sum = 0; 00401096 fldz for (int i = 0; i < inputs; i++) 00401098 mov edi,dword ptr [esi+18h] 0040109B fstp dword ptr [esi] 0040109D xor ecx,ecx 0040109F test edi,edi 004010A1 jle Neuron::calculate+33h (4010C3h) 004010A3 mov eax,dword ptr [esi+10h] 004010A6 mov edx,dword ptr [esi+14h] 004010A9 sub edx,eax 004010AB jmp Neuron::calculate+20h (4010B0h) 004010AD lea ecx,[ecx] sum+=sinapsData[i] * inputData[i]; 004010B0 fld dword ptr [edx+eax] 004010B3 add ecx,1 004010B6 fmul dword ptr [eax] 004010B8 add eax,4 004010BB cmp ecx,edi 004010BD fadd dword ptr [esi] 004010BF fstp dword ptr [esi] 004010C1 jl Neuron::calculate+20h (4010B0h) //add polarization sum+=sinapsData[inputs]; 004010C3 mov eax,dword ptr [esi+10h] 004010C6 fld dword ptr [eax+edi*4] 004010C9 fadd dword ptr [esi] 004010CB fstp dword ptr [esp+8] 004010CF fld dword ptr [esp+8] 004010D3 fst dword ptr [esi] axon = sigmoid(sum); --- return axon; } 2) листинг того, что я написал на асме (вставки в C++) с целью оптимизации по скорости, используя SSE: Не читайте эту чушь, уже переписал. Код (Text): inline FLOATING_VAR Neuron::calculate() { //this will calculate output _asm int 3 sum = 0; 00401097 fldz // split by groups for XMM regs int groups = inputs / 16; 00401099 mov eax,dword ptr [esi+18h] 0040109C fstp dword ptr [esi] FLOATING_VAR* sinapsd = sinapsData; 0040109E mov ecx,dword ptr [esi+10h] 004010A1 cdq 004010A2 and edx,0Fh 004010A5 add eax,edx FLOATING_VAR* inputd = inputData; 004010A7 mov edx,dword ptr [esi+14h] 004010AA sar eax,4 FLOATING_VAR sumd0[4]; FLOATING_VAR sumd1[4]; FLOATING_VAR sumd2[4]; FLOATING_VAR sumd3[4]; // mul for (int i = 0; i < groups; i++){ 004010AD test eax,eax 004010AF mov dword ptr [esp+58h],ecx 004010B3 mov dword ptr [esp+48h],edx 004010B7 jle Neuron::calculate+195h (401225h) //this will calculate output _asm int 3 004010BD mov ecx,eax 004010BF nop _asm { // 0 and 1 movups xmm0, sinapsd; // поместить 4 переменные с плавающей точкой в регистр xmm0 004010C0 movups xmm0,xmmword ptr [esp+58h] movups xmm1, inputd; // поместить 4 переменные с плавающей точкой в регистр xmm1 004010C5 movups xmm1,xmmword ptr [esp+48h] // sinapsd += 4 mov eax,dword ptr [sinapsd]; 004010CA mov eax,dword ptr [esp+58h] add eax,10h; 004010CE add eax,10h mov dword ptr [sinapsd],eax; 004010D1 mov dword ptr [esp+58h],eax // inputd += 4 mov eax,dword ptr [inputd]; 004010D5 mov eax,dword ptr [esp+48h] add eax,10h; 004010D9 add eax,10h mov dword ptr [inputd],eax; 004010DC mov dword ptr [esp+48h],eax // 2 and 3 movups xmm2, sinapsd; // поместить 4 переменные с плавающей точкой в регистр xmm2 004010E0 movups xmm2,xmmword ptr [esp+58h] movups xmm3, inputd; // поместить 4 переменные с плавающей точкой в регистр xmm3 004010E5 movups xmm3,xmmword ptr [esp+48h] // sinapsd += 4 mov eax,dword ptr [sinapsd]; 004010EA mov eax,dword ptr [esp+58h] add eax,10h; 004010EE add eax,10h mov dword ptr [sinapsd],eax; 004010F1 mov dword ptr [esp+58h],eax // inputd += 4 mov eax,dword ptr [inputd]; 004010F5 mov eax,dword ptr [esp+48h] add eax,10h; 004010F9 add eax,10h mov dword ptr [inputd],eax; 004010FC mov dword ptr [esp+48h],eax // 4 and 5 movups xmm4, sinapsd; // поместить 4 переменные с плавающей точкой в регистр xmm4 00401100 movups xmm4,xmmword ptr [esp+58h] movups xmm5, inputd; // поместить 4 переменные с плавающей точкой в регистр xmm5 00401105 movups xmm5,xmmword ptr [esp+48h] // sinapsd += 4 mov eax,dword ptr [sinapsd]; 0040110A mov eax,dword ptr [esp+58h] add eax,10h; 0040110E add eax,10h mov dword ptr [sinapsd],eax; 00401111 mov dword ptr [esp+58h],eax // inputd += 4 mov eax,dword ptr [inputd]; 00401115 mov eax,dword ptr [esp+48h] add eax,10h; 00401119 add eax,10h mov dword ptr [inputd],eax; 0040111C mov dword ptr [esp+48h],eax // 6 and 7 movups xmm6, sinapsd; // поместить 4 переменные с плавающей точкой в регистр xmm6 00401120 movups xmm6,xmmword ptr [esp+58h] movups xmm7, inputd; // поместить 4 переменные с плавающей точкой в регистр xmm7 00401125 movups xmm7,xmmword ptr [esp+48h] // sinapsd += 4 mov eax,dword ptr [sinapsd]; 0040112A mov eax,dword ptr [esp+58h] add eax,10h; 0040112E add eax,10h mov dword ptr [sinapsd],eax; 00401131 mov dword ptr [esp+58h],eax // inputd += 4 mov eax,dword ptr [inputd]; 00401135 mov eax,dword ptr [esp+48h] add eax,10h; 00401139 add eax,10h mov dword ptr [inputd],eax; 0040113C mov dword ptr [esp+48h],eax // now do mul mulps xmm1, xmm0; // перемножить пакеты плавающих точек: xmm1=xmm1*xmm0 00401140 mulps xmm1,xmm0 mulps xmm3, xmm2; // перемножить пакеты плавающих точек: xmm3=xmm3*xmm2 00401143 mulps xmm3,xmm2 mulps xmm5, xmm4; // перемножить пакеты плавающих точек: xmm5=xmm5*xmm4 00401146 mulps xmm5,xmm4 mulps xmm7, xmm6; // перемножить пакеты плавающих точек: xmm7=xmm7*xmm6 00401149 mulps xmm7,xmm6 // store results movups sumd0, xmm1; // выгрузить результаты из регистра xmm1 0040114C movups xmmword ptr [esp+8],xmm1 movups sumd1, xmm3; // выгрузить результаты из регистра xmm1 00401151 movups xmmword ptr [esp+18h],xmm3 movups sumd2, xmm5; // выгрузить результаты из регистра xmm1 00401156 movups xmmword ptr [esp+28h],xmm5 movups sumd3, xmm7; // выгрузить результаты из регистра xmm1 0040115B movups xmmword ptr [esp+38h],xmm7 }; // add to sum sum += sumd0[0];sum += sumd0[1];sum += sumd0[2];sum += sumd0[3]; sum += sumd1[0];sum += sumd1[1];sum += sumd1[2];sum += sumd1[3]; sum += sumd2[0];sum += sumd2[1];sum += sumd2[2];sum += sumd2[3]; sum += sumd3[0];sum += sumd3[1];sum += sumd3[2];sum += sumd3[3]; 00401160 fld dword ptr [esi] 00401162 sub ecx,1 00401165 fadd dword ptr [esp+8] 00401169 fstp dword ptr [esp+4] 0040116D fld dword ptr [esp+4] 00401171 fadd dword ptr [esp+0Ch] 00401175 fstp dword ptr [esp+4] 00401179 fld dword ptr [esp+4] 0040117D fadd dword ptr [esp+10h] 00401181 fstp dword ptr [esp+4] 00401185 fld dword ptr [esp+4] 00401189 fadd dword ptr [esp+14h] 0040118D fstp dword ptr [esp+4] 00401191 fld dword ptr [esp+4] 00401195 fadd dword ptr [esp+18h] 00401199 fstp dword ptr [esp+4] 0040119D fld dword ptr [esp+4] 004011A1 fadd dword ptr [esp+1Ch] 004011A5 fstp dword ptr [esp+4] 004011A9 fld dword ptr [esp+4] 004011AD fadd dword ptr [esp+20h] 004011B1 fstp dword ptr [esp+4] 004011B5 fld dword ptr [esp+4] 004011B9 fadd dword ptr [esp+24h] 004011BD fstp dword ptr [esp+4] 004011C1 fld dword ptr [esp+4] 004011C5 fadd dword ptr [esp+28h] 004011C9 fstp dword ptr [esp+4] 004011CD fld dword ptr [esp+4] 004011D1 fadd dword ptr [esp+2Ch] 004011D5 fstp dword ptr [esp+4] 004011D9 fld dword ptr [esp+4] 004011DD fadd dword ptr [esp+30h] 004011E1 fstp dword ptr [esp+4] 004011E5 fld dword ptr [esp+4] 004011E9 fadd dword ptr [esp+34h] 004011ED fstp dword ptr [esp+4] 004011F1 fld dword ptr [esp+4] 004011F5 fadd dword ptr [esp+38h] 004011F9 fstp dword ptr [esp+4] 004011FD fld dword ptr [esp+4] 00401201 fadd dword ptr [esp+3Ch] 00401205 fstp dword ptr [esp+4] 00401209 fld dword ptr [esp+4] 0040120D fadd dword ptr [esp+40h] 00401211 fstp dword ptr [esp+4] 00401215 fld dword ptr [esp+4] 00401219 fadd dword ptr [esp+44h] 0040121D fstp dword ptr [esi] 0040121F jne Neuron::calculate+30h (4010C0h) } //add polarization sum+=sinapsData[inputs]; 00401225 mov eax,dword ptr [esi+18h] 00401228 mov ecx,dword ptr [esi+10h] 0040122B fld dword ptr [ecx+eax*4] 0040122E fadd dword ptr [esi] 00401230 fstp dword ptr [esp+4] 00401234 fld dword ptr [esp+4] 00401238 fst dword ptr [esi] axon = sigmoid(sum); 0040123A fmul qword ptr [__real@bff0000000000000 (402180h)] 00401240 fstp dword ptr [esp+4] 00401244 fld dword ptr [esp+4] 00401248 call _CIexp (401E80h) 0040124D fstp dword ptr [esp+4] 00401251 fld dword ptr [esp+4] 00401255 fld1 00401257 fadd st(1),st 00401259 fdivrp st(1),st 0040125B fstp dword ptr [esp+4] 0040125F fld dword ptr [esp+4] 00401263 fst dword ptr [esi+4] 00401266 pop esi return axon; } Компилятор - MS VS2005. Процессор - Core2 QUAD. тестирую в 32, в боевую должно работать в 64, т.к. много памяти требуется. Спасибо всем.
Оптимизировать можно и на fpu и на SSE путем распараллеливания вычислений, т.е. нужно копить не одну сумму sum, а 4 независимые подсуммы и затем по окончании цикла сложить их в общую sum. А твоя SSE-реализация какая-то коряво-половинчатая, т.к. после векторных умножений не нужно ничего выгружать в память и складывать подсуммы на fpu (это дает доп.тормоза из-за store-to-load forwarding restriction-а, т.к. нельзя читать дворды из середины только что сохраненного 16-байтного числа). Нужно просто отвести один (или несколько) регистров под суммы и прибавлять к нему умноженные значения, накапливая таким образом 4 подсуммы в одном регистре, и только по окончании всего цикла сложить между собой эти подсуммы или на SSE или на fpu (если цикл большой, то штрафом на STLF можно и пренебречь)
Не совсем понимаю. Речь идет о распараллеливании на каком уровне? Спасиб. Да, какую-то чушь написал вначале. Переделал. Теперь быстро считает)) Не могу только найти команду, которая бы один XMM регистр складывала целиком (т.е. все 4 float числа одного регистра сложить). Код (Text): sum = 0; // split by groups for XMM regs int groups = inputs / 16; FLOATING_VAR sumd[4]; _asm { mov edx, [esi + inputData]; mov ebx, [esi + sinapsData]; }; // do SSE mul for (int i = 0; i < groups; i++){ _asm { // load data to XMM movups xmm0, [ebx]; // поместить 4 переменные с плавающей точкой в регистр xmm0 movups xmm1, [edx]; // поместить 4 переменные с плавающей точкой в регистр xmm1 movups xmm2, [ebx+10h]; // поместить 4 переменные с плавающей точкой в регистр xmm2 movups xmm3, [edx+10h]; // поместить 4 переменные с плавающей точкой в регистр xmm3 movups xmm4, [ebx+20h]; // поместить 4 переменные с плавающей точкой в регистр xmm4 movups xmm5, [edx+20h]; // поместить 4 переменные с плавающей точкой в регистр xmm5 movups xmm6, [ebx+30h]; // поместить 4 переменные с плавающей точкой в регистр xmm6 movups xmm7, [edx+30h]; // поместить 4 переменные с плавающей точкой в регистр xmm7 // XMM mul mulps xmm1, xmm0; // перемножить пакеты плавающих точек: xmm1=xmm1*xmm0 mulps xmm3, xmm2; // перемножить пакеты плавающих точек: xmm3=xmm3*xmm2 mulps xmm5, xmm4; // перемножить пакеты плавающих точек: xmm5=xmm5*xmm4 mulps xmm7, xmm6; // перемножить пакеты плавающих точек: xmm7=xmm7*xmm6 // XMM add 0 = (1 + 3) + (5 + 7) addps xmm1, xmm3; addps xmm5, xmm7; addps xmm1, xmm5; // Вот здесь бы сложить все 4 переменных float регистра XMM1. // Не знаю как, поэтому выгружаем в память // store results movups sumd, xmm1; // increment registers add ebx, 40h add edx, 40h }; // add to sum sum += sumd[0]; sum += sumd[1]; sum += sumd[2]; sum += sumd[3]; } Можно ли еще оптимизировать этот код по скорости?
Как вариант, можно вообще отказаться от использования FPU Идея: работать с двоичными дробями, используя команды целочисленного сложения/умножения/деления Ключевые слова: масштаб, целочисленная арифметика, дробная арифметика, коррекция после умножения, коррекция перед делением Пример: возвести в квадрат x, x = [-200, 200] для 16-битных слов: целочисленный масштаб M=32767/200 = 2^7 Масштаб результата My = M*M/2^16 = 2^-2, оценочный масштаб M = M(200*200) = 32767/40000 = 2^-1, коррекция на 1 бит (разница в масштабах) Возведем в квадрат 123.456: Код (Text): mov ax, 3DBAh ; 123.456 * 2^7 imul ax shld dx, ax, 1 ;здесь в dx - результат 1DC4 ;результат = 1DC4h*2 = 15240 Относительная ошибка = (15241,383936 - 15240)/15241,383936 = 0,0091% Работает все это очень быстро, возвращает малую ошибку и это при 16-битной разрядности (double использует 64-битную мантиссу)
Условия задачи не позволяют заранее рассчитать: MasMul[]= sinapsData * inputData ? Какого рода числа в этих массивах? Абсолютно случайные?
То что надо. Спасибо. Идея хорошая, буду копать. Область значений чисел в массиве не определена. Там могут быть как очень близкие к нулю по модулю числа, так и большие. Придется всеравно таскать экспоненту за собой. А что такое MasMul в примере? Если это максимум - то нет. В одном массиве числа изначально случайные. Известно только, что они от 0 до 1. Во втором тоже случайные. Значения - любые вещественные числа.
Span Насчет диапазонов. Обрати внимание, что у тебя сложение. При сложении двух чисел, сильно отличающихся по порядку, точность одного из них практически не будет иметь значения. Если разница в экспоненте 2^10, то 10 младших бит меньшего из слагаемых в сложении участвовать не будут и будут отброшены. Так что надо думать и считать.
Span На уровне оптимизации кода - устранения зависимой операции sum+=..., путем разбивки ее на 4 независимых sumd[0]+=.., sumd[1]+=.. и т.д. Т.к. от перестановки мест слагаемых сумма не меняется, то можно независимо копить 4 суммы - в sumd[0] копим сумму [0]+[4]+[8]+.., в sumd[1] соотв-но [1]+[5]+[9]+.. и т.д. Затем после завершения цикла складываем части и получаем общую сумму. Для вещественных fpu и SSE операций такая разбивка дает заметный прирост скорости, т.к. латентность fadd и addps\addpd достаточно большая - порядка 5-7 тактов, но независимые сложения за счет конвееризации могут выполняться каждый такт, т.е. практически параллельно Можно. Во-первых, опбеспечить выравнивание массивов на 16 и заменить тормозные movups на быстрые movaps. Во-вторых, заменить загрузку вторых операндов и умножение reg*reg на прямое умножение reg*mem. В-третьих, прислушаться к совету и производить сложение частей не внутри цикла, а после его завершения
Код (Text): mov edx,[inputs] shl edx,2 mov ecx,edx neg ecx lea eax,[sinapsData+edx] lea edx,[inputData+edx] xorps xmm0,xmm0 movss xmm0,[eax] calc:movaps xmm1,[eax+ecx] mulps xmm1,[edx+ecx] addps xmm0,xmm1 add ecx,16 jne calc movhlps xmm1,xmm0 addps xmm0,xmm1 movss xmm1,xmm0 shufps xmm0,xmm0,1 addss xmm0,xmm1 sub esp,4 movss [esp],xmm0 call sigmoid mov [axon],eax inputs должно быть кратно 4
murder Спасибо за код. Сижу разбираюсь с ним. Насколько я понял, в такой реализации операнд (адрес) для movaps всегда будет % 16.
Спасибо. Очень помогло. Даже не верится что считаться стало так быстро. Переписал с учетом этих советов, получилось вот что: Код (Text): PUBLIC neuron_calculate .CODE ; RCX - pointer to 1st FLOAT array ; RDX - pointer to 2nd FLOAT array ; R8 - pointer to output FLOAT var ; R9 - Array size neuron_calculate PROC ; iterations = inputs / 32 shr R9, 5 ; XMM ; 0 - 7 - first operands ; 8 - 15 - SUMs xorps xmm8, xmm8 xorps xmm9, xmm9 xorps xmm10, xmm10 xorps xmm11, xmm11 xorps xmm12, xmm12 xorps xmm13, xmm13 xorps xmm14, xmm14 xorps xmm15, xmm15 mul_loop: cmp R9, 0 je mul_end ;load data to XMM movaps xmm0, [rdx]; // поместить 4 переменные с плавающей точкой в регистры xmm movaps xmm1, [rdx+10h]; movaps xmm2, [rdx+20h]; movaps xmm3, [rdx+30h]; movaps xmm4, [rdx+40h]; movaps xmm5, [rdx+50h]; movaps xmm6, [rdx+60h]; movaps xmm7, [rdx+70h]; ; XMM mul mulps xmm0, [rcx]; // перемножить пакеты переменных: xmm=xmm*[MEM] mulps xmm1, [rcx+10h]; mulps xmm2, [rcx+20h]; mulps xmm3, [rcx+30h]; mulps xmm4, [rcx+40h]; mulps xmm5, [rcx+50h]; mulps xmm6, [rcx+60h]; mulps xmm7, [rcx+70h]; ; add addps xmm8, xmm0; // добавить результат к накапливаемым частичным суммам addps xmm9, xmm1; addps xmm10, xmm2; addps xmm11, xmm3; addps xmm12, xmm4; addps xmm13, xmm5; addps xmm14, xmm6; addps xmm15, xmm7; ; inc regs add rcx, 80h; add rdx, 80h; dec R9 ; goto start jmp mul_loop mul_end: ; calc result addps xmm8, xmm9; addps xmm10, xmm11; addps xmm12, xmm13; addps xmm14, xmm15; addps xmm8, xmm10; addps xmm12, xmm14; addps xmm8, xmm12; haddps xmm8, xmm8 haddps xmm8, xmm8 movss DWORD PTR[R8], xmm8 ret neuron_calculate ENDP END Имеет ли здесь смысл перемешать вручную команды (загрузки, умножения, сложения) в теле цикла??? Цель - избавиться от зависимости при выполнении. Хаотичные перемещения не дали результата.
Имеет смысл посмотреть ABI: Код (Text): ; R12:R15 | Nonvolatile | preserved by callee ; XMM6:XMM15 | Nonvolatile | preserved by callee
Т.Е. мне их (Nonvolatile) лучше не трогать в теле ф-и?? А чем мне это грозит, если ф-ю вызывает моя же программа??
О-о-о-о rdx, xmm15, haddps... А у меня AMD Athlon XP 2500 1) Сделай адресацию как у меня - через один регистр. 2) Если массивы большие попробуй подход AMD (Блочная предвыборка + movntps/sfence)
Спасибо. Узнал много нового. Хотя думал, что MASM все сделает за меня (сохранение значений используемых Nonvolatile регистров, +- RSP). А чем мне грозит отсутствие пролога/эпилога? Что, например, если я оставлю стек в покое в вызываемой процедуре (SPILL for args)? Я не заметил каких-либо изменений.
Ничем не грозит. AMD советует для эпилога использовать leave. А вот Enter для пролога не рекомендуется.
