Удаление всей арифметики на загрузку не влияет вообще )). Независимо от длины массивов. Изменяла длину больших массивов (src, res). Оставила от цикла следующее: Вариант А Code (Text): start: movaps xmm0, [eax] movaps xmm1, [ebx] add eax,16 add ebx,16 movaps [edi],xmm0 add edi,16 cmp ebx,edx jb start mov ebx, ptr_in cmp edi,limit cmovae edi, begin_res cmp edi,res jne start Вариант Б Code (Text): start: add ebx,16 movaps [edi],xmm0 add edi,16 cmp ebx,edx jb start mov ebx, ptr_in cmp edi,limit cmovae edi, begin_res cmp edi,res jne start Загрузка в процентах следующая: длина массива А Б 32768 2 1...2 65536 4 2 200000 11..12 7 400000 22..23 15...16 С арифметикой результат как для варианта А (плюс-минус полпроцента) При комментировании только этих команд Code (Text): movaps xmm0, [eax] movaps xmm1, [ebx] при длине 400000 загрузка 21-22 а только этих Code (Text): addps xmm0,[edi] movaps [edi],xmm0 при длине 400000 загрузка 6-7 Длину меньшего массива ставила 1024, 2048, 4096. Загрузка уменьшается с увеличением длины. Например, для 400000: 1024: 22...23 2048: 11 4096: 6 В случае с изменением длины длинных массивов вроде понятно: чем длиннее - тем больше операций. Для короткого массива - я в недоумении, т.к. изменение его длины не должно влиять на к-во операций (длинный массив делится на куски, равные длине короткого). Т.е. уменьшается к-во циклов. С этой точки зрения получается, что во всем виноват вот этот фрагмент: Code (Text): cmp ebx,edx jb start но это вроде не совсем согласуется с тем что выше... (еще перепроверю потом) Да, это проект в Visual Studio. Память массивам раздаю через aligned_malloc и некоторым через new (где лень мешала поисправлять на aligned_malloc). В memset не думаю что есть необходимость - массив все равно обрабатывается периодически один и тот же... Начальный всплеск загрузки иногда есть, но я его не учитываю. Кстати. Эта функция вызывается несколько раз, причем короткий массив один и тот же, а длинные каждый раз другие... О да, это она Эх... Слепить что ли длл в матлабе и использовать в своем коде? 8-)
ettaine А разве поэлементное умножение не составляет всего лишь несколько процентов трудоемкости от общей задачи свертки, которая требует два-три FFT, прогоняющие вектора log n раз?
ConstZ Спасибо за ссылку! почитал и почти все из этого интуитивно применял, что касается группировки. Только вот лезть в память несколько раз вместо копирования про запас в регистр на это рука никогда не подымится... А где можно почитать или услышать рекомендации про 1) смешение SSE2 с MMX, в частности, что делать с emms, куда ее притулить? 2) SSE2 и многоядерность, может ли быть в камне два ALU и один FPU
ettaine Спасибо за проведенный опыт. Вроде бы как получается что основная загрузка идет за счет записи в память (movaps [edi],xmmN) и есть четкая зависимость между размером массива-приемника (sic!) - ? Вроде бы как получается при достижении всей памяти какого-то значения (размер кэша? Он вроде ~512KБайт) происходит существенный прирост: 65536 4 2 200000 11..12 7 Если это так (можно уточнить экспериментом с просто записью в _один_ массив с минимально возможным числом команд), то, видимо, нужно стремиться к этим (т.е. которые для размера массива <=65536) значениям - дальнейшая оптимизация просто невозможна. Это был быстрый ответ, надо подумать еще... Я немного посмотрел статью по ссылке ConstZ - там вроде бы про оптимизацию записи нет ничего... По идее можно удвоить число элементов (если точность устраивает) используя 64-х битные элементы вместо 128-ми битных или же как-то реорганизовать данные чтобы одномоментно размер текущих массивов умещался в кэш (видимо часть его, так как есть еще и другие процессы).
ettaine Попробуйте писать результаты в отдельный массив. Code (Text): addps xmm0,[edi] movaps [edi],xmm0 - нехорошая идея, потому, что "Постоянно" обновляется линейка кэша, идет то запись, то чтение. Предвыборка от этого сильно страдает и вылезает латентнось доступа к памяти. Предположим, все данные в L2, тогда время выполнения этих команд будет складыватся из: addps xmm0,[edi] - загрузки данных из L2 + latency сложения movaps [edi],xmm0 - тут (если не ошибаюсь у Intel-a запись идет в L2) идет запись в L2 линейки кэша (64b) на следующей итерации: addps xmm0,[edi] - читаем 16b из той же линейки, придется ждать когда она обновится и потом еще прочитается... Возможно я несовсем прав и кэш контроллер пытается это как-то разрулить, но ему явно плохо. Если же [edi] вылезает из L2, все становится еще хуже. Если вам необходимо чтобы результаты писались в тот же массив, пишите небольшими блоками во временный, а потом в исходный. Кстати, посмотрите _http://download.intel.com/technology/itj/2004/volume08issue01/art02_compilers/vol8iss1_art02.pdf может, это то что вам надо. Измерение ресурсоемкости функции в % что-то говорит только вам, в дальнейшем пишите хотя бы время выполнения N вызовов ф-ии в тактах и модель процессора. Кроме Intel Manuals, рекомендую почитать Агнера Фога - agner.org и "Техника оптимизации программ.." Крис Касперски(немного устарела но многое разжевано и на русском).
1) emms в конце ф-ии. А зачем вам мешать mmx и sse? (такое бывает очень редко) 2) Что вы понимаете под камнем? если ядро, то в каждом ядре современного x86 процессора несколько исполнительных устройств, относящихся как к ALU и FPU. Многоядерные процессоры исполнительные блоки не разделят. А вот с HT как раз раз делят. про внутренне устройство можно прочитать в "Intel® 64 and IA-32 Architectures Optimization Reference Manual"
ettaine Ты бы для начала со своим алгоритмом разобралась, а то в твоих отрывочных сумбурных мыслях вслух - одни нестыковки Во-первых, говоришь у тебя буфер res - кольцевой, но размерчики 100000 и т.д. почему-то постоянно указываешь некратные размеру входного ptr_in. Как у тебя limit устанавливается не понятно, поэтому в результае можно предположить, что ты просто выскакиваешь за пределы буфера res при cmp + cmovae Во-вторых, проверки длины массива src в цикле нет, из чего видимо следует, что размеры src и res равны, но тут смущает отрывочная фраза "первых два массива влазят в кэш, третий нет" В-третьих, с одной стороны говоришь, что позиция res "при каждом вызове смещается на размер ptr_in", а с другой стороны "функция вызывается несколько раз, причем короткий массив один и тот же, а длинные каждый раз другие...". Как это понимать ? И цифирьки у тебя весьма странные получаются. "Для короткого массива - я в недоумении" - это вобще явный признак косяка в алгоритме. Для длинных массивов тоже "интересный" результат - практически пропорциональный рост с размером массива, хотя пара массивов по 32тыс. явно должна умещаться в L2, а по 400тыс. явно нет и поэтому, по крайней мере, должны возникать доп.тормоза на сброс измененного массива res в ОЗУ, а это как мин. 30% на доп.поток обмена данными с ОЗУ. Это при условии, что при каждом вызове массивы другие и соотв-но при любом размере грузятся из ОЗУ, а если бы они использовались повторно, то доп.разница между 32 и 400тыс. достигала бы десятка и более раз. В итоге вся эта пропорциональность говорит либо о наличии каких-то больших доп.тормозов, либо о том что "загрузка процессора" измеряется как-то не так... PS: Большие тормоза могут быть при использовании неинициализированных массивов, выделяемых через VirtualAlloc. В винде и в MSVC все массивы размером более ~512К выделяются VirtualAlloc'ом и соотв-но при первом обращении к каждой 4К странице возникает page fault для ее инициализации. Хотя массивы в 32тыс. это всего 128К и должны выделяться из общей кучи, тем не менее если их каждый раз освобождать и выделять заново, то виндовый менеджер может делать decommit страниц при освобождении (все таки 256К это не мелочь) и повторный commit при выделении
LiveM Ес-но. Во-первых, запись производится не сразу в кэш, а сначала в store-буферы и только спустя N-е кол-во тактов (порядка длины конвеера) данные сбрасываются из буферов в кэш. Это делается для того, чтобы при спекулятивном исполнении ветвлений и изменении порядка команд гарантированно дождаться подтверждения и отставки всех команд, предшествоваших записи. Во-вторых, для того чтобы можно было одновременно читать из кэша и записывать в него, его делают состоящим из нескольких "банков" данных, причем таким образом, чтобы соседние dword или qword-ы каждой линейки кэша принадлежали разным банкам. Поэтому конфликт между чтением и записью возникает только либо при чтении\записи по одному и тому же адресу (в одну переменную), либо по адресам, различающимся на размер линейки кэша. Конечно, с учетом того, что реальная запись в кэш идет с задержкой, все эти конфликты трудно предугадать. Но ясно, что 1) чем меньше разных массивов используется при обработке, тем лучше и 2) желательно адреса одновременно обрабатываемых массивов выравнивать на размер линейки (64 байта), тогда, например, для рассматриваемого случая чтение данных из всех трех массивов будет каждый раз производиться из одного банка кэша и соотв-но вероятность того, что запись будет именно в этот банк - меньше (чем если бы при чтении юзались 3 разных банка)
leo Спасибо за коментарий! Про буфера записи и ассоциативность кэша представление имею, но действительно, в данном случае конфликт не возникает, это я словил интересный "глюк" и ошибочно принял его за конфликт кэша. Сейчас пытаюсь разобраться. не всегда. например, в данном случае будет конфликт Code (Text): addps xmm0,xmmword ptr [eax] mov dword ptr [eax], reg так же Intel® 64 and IA-32 Architectures Optimization Reference Manual. Chapter 7.2 про HARDWARE PREFETCHING По п2. противоречит A Fog по этому поводу пишет Хотя к первоначальному вопросу это пожалуй не относится, но все же считаю что в большинстве случаев читать и писать лучше в разные массивы. Прошу поправить, если ошибаюсь. p.s. все что выше, писал относительно Core2
LiveM С какой стати ?! Не будет тут никакого конфликта Это вообще тут причем ? Или ты думаешь для load свой префетч, а для store - свой Префетч работает с линейками кэша и ему пофиг читаешь ты или пишешь, т.к. если ты даже только записываешь, он обязан сначала загрузить (прочитать) линейку из памяти или вышестоящего кэша и только потом в нее записать. Поэтому твое предложение использовать еще один массив для записи результата через movaps эквивалентен тому, что вместо 2-х больших массивов будут читаться 3, т.к. прежде чем записать что-то в 3-й массив процессор обязан его прочитать из памяти в кэш. Поэтому если уж использовать отд.массив, то писать в него нужно не через movaps, а через movntdq Ничего не противоречит. Если все три вх.массива выравнены на 64, то в каждом цикле все 3 чтения производятся из одного и того же банка, поэтому в каждом цикле есть еще 3 свободных банка, в которые может производиться запись результата (запись, как я говорил идет с задержкой). Если же все 3 чтения производятся из разных банков, то вероятность нарваться на банк, занятый записью ес-но выше. Однако, из-за того, что запись производится с задержкой, предугадать все эти хитрости с конфликами банков практически невозможно, поэтому и заморачиваться с этим не стоит. Тем более, что в данном сл. на одну запись приходится 3 чтения и еще с десяток операций, поэтому возможный пропуск 1 такта из-за конфликта практической роли не играет
(sorry, что поднимаю - тема старая, но интересная. ) Несколько наблюдений. 1. использование SSE ONLY может привести к жуткому падению производительности. В частности, К7-К8 (AMD естественно) просто помрут на SSE. Используйте MMX. Если позволяет алгоритм. 2. не забывайте о количестве конвейеров SSE. У Core их 3. Т.е., теоретически можно получить IPC 3. Я получил 2.7-2.9; linpack - порядка 2.7 для х86 и 2.9 для х64. (почему так - см. ниже) Почему я вспомнл о '3'? Да просто потому, что _каждый_тик_ надо поставлять ТРИ инструкции. Выражусь несколько иначе - Вы должны представить 3 инструкции (три НЕЗАВИСИМЫЕ) инструкции, чтобы они выполнились за 1 тик. 3. независимость. Параллельно выполняются независимые инструкции. Если есть зависимость в регистрах, то начинается 'секс'. Итак, из п2 и 3 следует, что алгоритм должен использовать операции с независимыми регистрами и этих операций надо аж 3 штуки за раз. 4. предвыборка. Точнее загрузка. Не используйте операции выполнения с загрузкой из памяти. _вначале_ загружайте регистр, а уж затем его используйте. Между загрузкой регистра и его использованием надо делать БольшуюЗадержку на загрузку из кеши. С учетом кол-ва конвейеров это будет ОченьМного инструкций. 5. Вывод. Максимально распараллеливайте вычисления. Например, алгоритм 'сумма числ в памяти' напрашивается в виде цикла 'reg+[mem]'. Однако, если разрезать его на цикл ('reg0+[mem]' 'reg1+[mem]' ...) и потом сложить эти регистры reg(i), то процедура будет работать быстрее. Почему? А потому, что алгоритм будет выглядить так: reg0<-mem0 reg1<-mem1 reg2<-mem2 reg4=reg4+reg0 reg3<-mem3 reg5=reg5+reg1 reg6=reg6+reg2 reg0<-mem0 reg7=reg7+reg3 reg1<-mem1 reg2<-mem2 Между загрузкой регистра и его использованием проходит 3 инструкции. Та-же задержка и при новом использовании этого-же регистра. 6. И из неприятного. Как видно, регистров SSE фатально не хватает. По используйте MMX. Хоть и мелкие, но подходят для промежуточный констант. В режиме х64 кол-во SSE регистров удваивается, поэтому (и только поэтому, IMHO) в х64 SSE может быть быстрее. Для упомянутого linpack написаны разнличающиеся алгоритмы по х86 и х64 редакциям. Для х86 4 параллельных вычислений, для х64 их число в 2 раза больше и поэтому IPC больше (значительно меньше взаимные конфликты использования регистров). Ну и, чтоб небыло чистой говорильни, фрагмент linpack для медитации. Code (Text): movaps xmm7, oword ptr [eax+40h] movaps xmm6, oword ptr [ebx] movaps xmm5, xmm6 mulpd xmm6, xmm4 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+10h] mulpd xmm4, xmm6 addpd xmm1, xmm4 movaps xmm4, oword ptr [eax+10h] mulpd xmm5, xmm4 addpd xmm2, xmm5 mulpd xmm6, xmm4 addpd xmm3, xmm6 movaps xmm4, oword ptr [eax+20h] movaps xmm6, oword ptr [ebx+20h] movaps xmm5, xmm6 mulpd xmm6, xmm4 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+30h] mulpd xmm4, xmm6 addpd xmm1, xmm4 movaps xmm4, oword ptr [eax+30h] mulpd xmm5, xmm4 addpd xmm2, xmm5 mulpd xmm6, xmm4 addpd xmm3, xmm6 movaps xmm4, oword ptr [eax+80h] movaps xmm6, oword ptr [ebx+40h] movaps xmm5, xmm6 mulpd xmm6, xmm7 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+50h] mulpd xmm7, xmm6 addpd xmm1, xmm7 movaps xmm7, oword ptr [eax+50h] mulpd xmm5, xmm7 addpd xmm2, xmm5 mulpd xmm6, xmm7 addpd xmm3, xmm6 movaps xmm7, oword ptr [eax+60h] movaps xmm6, oword ptr [ebx+60h] movaps xmm5, xmm6 mulpd xmm6, xmm7 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+70h] mulpd xmm7, xmm6 addpd xmm1, xmm7 movaps xmm7, oword ptr [eax+70h] mulpd xmm5, xmm7 addpd xmm2, xmm5 mulpd xmm6, xmm7 addpd xmm3, xmm6 movaps xmm7, oword ptr [eax+0C0h] movaps xmm6, oword ptr [ebx+80h] movaps xmm5, xmm6 mulpd xmm6, xmm4 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+90h] mulpd xmm4, xmm6 addpd xmm1, xmm4 movaps xmm4, oword ptr [eax+90h] mulpd xmm5, xmm4 addpd xmm2, xmm5 mulpd xmm6, xmm4 addpd xmm3, xmm6 movaps xmm4, oword ptr [eax+0A0h] movaps xmm6, oword ptr [ebx+0A0h] movaps xmm5, xmm6 mulpd xmm6, xmm4 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+0B0h] mulpd xmm4, xmm6 addpd xmm1, xmm4 movaps xmm4, oword ptr [eax+0B0h] mulpd xmm5, xmm4 addpd xmm2, xmm5 mulpd xmm6, xmm4 addpd xmm3, xmm6 movaps xmm4, oword ptr [eax+100h] movaps xmm6, oword ptr [ebx+0C0h] movaps xmm5, xmm6 mulpd xmm6, xmm7 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+0D0h] mulpd xmm7, xmm6 addpd xmm1, xmm7 movaps xmm7, oword ptr [eax+0D0h] mulpd xmm5, xmm7 addpd xmm2, xmm5 mulpd xmm6, xmm7 addpd xmm3, xmm6 movaps xmm7, oword ptr [eax+0E0h] movaps xmm6, oword ptr [ebx+0E0h] movaps xmm5, xmm6 mulpd xmm6, xmm7 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+0F0h] mulpd xmm7, xmm6 addpd xmm1, xmm7 movaps xmm7, oword ptr [eax+0F0h] mulpd xmm5, xmm7 addpd xmm2, xmm5 mulpd xmm6, xmm7 addpd xmm3, xmm6 movaps xmm7, oword ptr [eax+140h] movaps xmm6, oword ptr [ebx+100h] movaps xmm5, xmm6 mulpd xmm6, xmm4 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+110h] mulpd xmm4, xmm6 addpd xmm1, xmm4 movaps xmm4, oword ptr [eax+110h] mulpd xmm5, xmm4 addpd xmm2, xmm5 mulpd xmm6, xmm4 addpd xmm3, xmm6 movaps xmm4, oword ptr [eax+120h] movaps xmm6, oword ptr [ebx+120h] movaps xmm5, xmm6 mulpd xmm6, xmm4 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+130h] mulpd xmm4, xmm6 addpd xmm1, xmm4 movaps xmm4, oword ptr [eax+130h] mulpd xmm5, xmm4 addpd xmm2, xmm5 mulpd xmm6, xmm4 addpd xmm3, xmm6 movaps xmm4, oword ptr [eax+180h] movaps xmm6, oword ptr [ebx+140h] movaps xmm5, xmm6 mulpd xmm6, xmm7 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+150h] mulpd xmm7, xmm6 addpd xmm1, xmm7 movaps xmm7, oword ptr [eax+150h] mulpd xmm5, xmm7 addpd xmm2, xmm5 mulpd xmm6, xmm7 addpd xmm3, xmm6 movaps xmm7, oword ptr [eax+160h] movaps xmm6, oword ptr [ebx+160h] movaps xmm5, xmm6 mulpd xmm6, xmm7 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+170h] mulpd xmm7, xmm6 addpd xmm1, xmm7 movaps xmm7, oword ptr [eax+170h] mulpd xmm5, xmm7 addpd xmm2, xmm5 mulpd xmm6, xmm7 addpd xmm3, xmm6 movaps xmm7, oword ptr [eax+1C0h] movaps xmm6, oword ptr [ebx+180h] movaps xmm5, xmm6 mulpd xmm6, xmm4 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+190h] mulpd xmm4, xmm6 addpd xmm1, xmm4 movaps xmm4, oword ptr [eax+190h] mulpd xmm5, xmm4 addpd xmm2, xmm5 mulpd xmm6, xmm4 addpd xmm3, xmm6 movaps xmm4, oword ptr [eax+1A0h] movaps xmm6, oword ptr [ebx+1A0h] movaps xmm5, xmm6 mulpd xmm6, xmm4 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+1B0h] mulpd xmm4, xmm6 addpd xmm1, xmm4 movaps xmm4, oword ptr [eax+1B0h] mulpd xmm5, xmm4 addpd xmm2, xmm5 mulpd xmm6, xmm4 addpd xmm3, xmm6 movaps xmm4, oword ptr [eax+200h] movaps xmm6, oword ptr [ebx+1C0h] movaps xmm5, xmm6 mulpd xmm6, xmm7 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+1D0h] mulpd xmm7, xmm6 addpd xmm1, xmm7 movaps xmm7, oword ptr [eax+1D0h] mulpd xmm5, xmm7 addpd xmm2, xmm5 mulpd xmm6, xmm7 addpd xmm3, xmm6 movaps xmm7, oword ptr [eax+1E0h] movaps xmm6, oword ptr [ebx+1E0h] movaps xmm5, xmm6 mulpd xmm6, xmm7 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+1F0h] mulpd xmm7, xmm6 addpd xmm1, xmm7 movaps xmm7, oword ptr [eax+1F0h] mulpd xmm5, xmm7 addpd xmm2, xmm5 mulpd xmm6, xmm7 addpd xmm3, xmm6 movaps xmm7, oword ptr [eax+240h] movaps xmm6, oword ptr [ebx+200h] movaps xmm5, xmm6 mulpd xmm6, xmm4 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+210h] mulpd xmm4, xmm6 addpd xmm1, xmm4 movaps xmm4, oword ptr [eax+210h] mulpd xmm5, xmm4 addpd xmm2, xmm5 mulpd xmm6, xmm4 addpd xmm3, xmm6 movaps xmm4, oword ptr [eax+220h] movaps xmm6, oword ptr [ebx+220h] movaps xmm5, xmm6 mulpd xmm6, xmm4 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+230h] mulpd xmm4, xmm6 addpd xmm1, xmm4 movaps xmm4, oword ptr [eax+230h] mulpd xmm5, xmm4 addpd xmm2, xmm5 mulpd xmm6, xmm4 addpd xmm3, xmm6 movaps xmm4, oword ptr [eax+280h] movaps xmm6, oword ptr [ebx+240h] movaps xmm5, xmm6 mulpd xmm6, xmm7 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+250h] mulpd xmm7, xmm6 addpd xmm1, xmm7 movaps xmm7, oword ptr [eax+250h] mulpd xmm5, xmm7 addpd xmm2, xmm5 mulpd xmm6, xmm7 addpd xmm3, xmm6 movaps xmm7, oword ptr [eax+260h] movaps xmm6, oword ptr [ebx+260h] movaps xmm5, xmm6 mulpd xmm6, xmm7 addpd xmm0, xmm6 movaps xmm6, oword ptr [ebx+270h] mulpd xmm7, xmm6 addpd xmm1, xmm7 movaps xmm7, oword ptr [eax+270h] mulpd xmm5, xmm7 addpd xmm2, xmm5 mulpd xmm6, xmm7