Влияние команд чтения-записи на производительность (+цикл +SSE)

Доброго времени суток.
Есть такой вот код:

Код (Text):

1.         mov eax, src               
2.         mov ebx, ptr_in            
3.         mov edx, limit_in
4.         mov edi, res               
5. start:
6.         movaps xmm0, [eax]           
7.         movaps xmm1, [ebx]         
8.  
9. // .....здесь десяток SSE-команд (movaps, shufps, mulps, addps), все внутри проца
10.  
11.         addps xmm0,[edi]
12.         movaps [edi],xmm0
13.  
14.         add eax,16                  // +4 elements
15.         add edi,16
16.         add ebx,16
17.         cmp ebx,edx
18.         jb start
19.        
20.         mov ebx, ptr_in
21.  
22.         cmp edi,limit
23.         cmovae edi, begin_res
24.         cmp edi,res
25.         jne start

Размеры массивов (к-во элементов типа float) примерно следующие:
ptr_in - 512...4096
src, res - от 100000 до 300000 (первый все время проходится от начала до конца, второй - типа кольцевой буфер, начальная позиция в нем при каждом вызове смещается на размер ptr_in)

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

Код (Text):

1.         addps xmm0,[edi]
2.         movaps [edi],xmm0

то загрузка процессора уменьшается примерно вдвое (если любую одну из них - примерно на четверть).
А если выбросить одну из этих (оставив те что с [edi])

Код (Text):

1.         movaps xmm0, [eax]           
2.         movaps xmm1, [ebx]

то загрузка не меняется вообще...
А если выбросить все четыре, то загрузка выше, чем если выбросить только первых две... 8-)

Что же такого магического есть в первых двух командах, что они так влияют на производительность?

Первое что пришло в голову:
- первых два массива влазят в кэш, третий нет: кэш 2Мб, 8-канальный - вроде нет причин не влазить res, если влазит src, во всяком случае при 100000 эл.(ок. полмегабайта)
- потеря производительности при обращении к невыровненным данным: выровняла все по границе 16, а потом и 64 байт, не помогло (точнее, помогло очень незначительно)
- из-за того что друг за другом идут операции чтения и записи (что-то такое читала в Intel Optimization reference manual, правда мало что поняла): переставляла addps xmm0,[edi] внутрь куска SSE-команд (в середину примерно), не помогло

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

В каком направлении копать?

Инглиш мой (как и асм) оставляет желать лучшего, так что я честно пыталась разобраться в Intel Optimization reference manual, но толку пока мало... Возникли пока такие вопросы:
Может ли тут быть полезной команда PREFETCH (пока не совсем понимаю как ее эффективно прицепить)?
Есть ли смысл обрабатывать в одном проходе цикла больше данных (не по 2, а по 4 или 8 элементов, а потом все вместе их записывать в res)? Но тогда мне ХММ-регистров будет не хватать, и код раздуется...
Тот ли это случай, когда будет полезной команда MOVNTPS (простая замена movaps [edi],xmm0 на MOVNTPS, наоборот, ухудшает производительность)?

Спасибо.

 

Memory/Register read/write stall?

зависит от

PREFETCH не поможет.

 

Попробуйте (тупое) вот так:

Что примерно делает алгоритм? Может есть возможность высокоуровневой оптимизации.

 

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

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

типа
mov mmx0.[esi+16*0]
mov mmx1.[esi+16*1]
mov mmx2.[esi+16*2]
mov mmx3.[esi+16*3]

16*0 я тоже всегда пишу, компилер это игнорирует в качестве комментария, потом гораздо меньше думать при отладке. Если значение в памати используется один раз, то можно не грузить а сразу обработать типа
pxor mmx0,[esi], а если много раз, то лучше под него отвести отдельные регистр.

 

вот пример чужого кода, тенденция на лицо, регистрам лучше общаться с памятью большими шоблами.

Код (Text):

1.     __asm__ __volatile__ (
2.         "movdqa   (%%esi), %%xmm0\n"
3.         "movdqa 16(%%esi), %%xmm1\n"
4.         "movdqa 32(%%esi), %%xmm2\n"
5.         "movdqa 48(%%esi), %%xmm3\n"
6.         "movdqa 64(%%esi), %%xmm4\n"
7.         "movdqa 80(%%esi), %%xmm5\n"
8.         "movdqa 96(%%esi), %%xmm6\n"
9.         "movdqa 112(%%esi), %%xmm7\n"
10.  
11.         "psubw    %%xmm2, %%xmm0\n"
12.         "psubw    %%xmm3, %%xmm1\n"
13.         "psubw    %%xmm6, %%xmm4\n"
14.         "psubw    %%xmm7, %%xmm5\n"
15.  
16.         "psllw   $1,%%xmm2\n"
17.         "psllw   $1,%%xmm3\n"
18.         "psllw   $1,%%xmm6\n"
19.         "psllw   $1,%%xmm7\n"
20.  
21.         "paddw    %%xmm0, %%xmm2\n"
22.         "paddw    %%xmm1, %%xmm3\n"
23.         "paddw    %%xmm4, %%xmm6\n"
24.         "paddw    %%xmm5, %%xmm7\n"
25.  
26.         "psubw    %%xmm4, %%xmm0\n"
27.         "psubw    %%xmm5, %%xmm1\n"
28.         "psubw    %%xmm6, %%xmm2\n"
29.         "psubw    %%xmm7, %%xmm3\n"
30.  
31.         "psllw   $1,%%xmm4\n"
32.         "psllw   $1,%%xmm5\n"
33.         "psllw   $1,%%xmm6\n"
34.         "psllw   $1,%%xmm7\n"
35.  
36.         "paddw    %%xmm0, %%xmm4\n"
37.         "paddw    %%xmm1, %%xmm5\n"
38.         "paddw    %%xmm2, %%xmm6\n"
39.         "paddw    %%xmm3, %%xmm7\n"
40.  
41.         "movdqa   %%xmm6,   (%%esi)\n"
42.         "movdqa   %%xmm7, 16(%%esi)\n"
43.         "movdqa   %%xmm4, 32(%%esi)\n"
44.         "movdqa   %%xmm5, 48(%%esi)\n"
45.         "movdqa   %%xmm2, 64(%%esi)\n"
46.         "movdqa   %%xmm3, 80(%%esi)\n"
47.         "movdqa   %%xmm0, 96(%%esi)\n"
48.         "movdqa   %%xmm1, 112(%%esi)\n"
49.     : : "S"(p) : "memory");

 

еще хочу задать вопрос знающим товарищам. Щас пишу свою первую многоядерную прогу.

Насколько SIMD дружит с многопроцессорностьью? может быть такое, что ALU в процессоре два, а FPU который проводит MMX один и получатся тормоза?

 

Про это где можно почитать? Искала в Intel Optimization reference manual по ключевому слову stall - вроде не нашла... Самое похожее - это Partial register stall (когда перезаписывается только часть регистра - у меня такого нет) и еще загадочные Assembly/Compiler coding rule 51 и 52, которые я не совсем поняла (особенно про loop-carried dependence chain)

Если допустить, что регистров мне все-таки хватит, тоже будет зависеть? Я думала, за счет записывания одновременно кучки результатов чего-то можно выиграть...

Да я их уже пробовала разнести (см. мой первый пост). Ваш вариант, к сожалению, тоже не помог...

Комплексное умножение двух массивов с записью в третий (комплексные числа записаны в стиле Re1 Im1 Re2 Im2...). Без асмовой вставки со всей возможной оптимизацией у компиляторов MS и Intel выходит чуть хуже по производительности 8-) Правда, не пробовала "SSE and SSE2 Intrinsics" от MS и еще не исключаю, что они умеют и лучше оптимизировать, просто у меня не получается их заставить

Ну да, я наверное таки разверну цикл хотя бы вдвое... Если б еще ХММ-регистров было побольше...

Спасибо всем за комментарии.

 

ettaine

Что подразумевается под "загрузкой процессора" ?
Вообще-то, оптимизация по скорости как раз и предполагает 100% загрузку процессора, который должен не простаивать в ожидании чего-то, а работать на полную катушку. Поэтому сравнивать разные варианты кода нужно по времени выполнения (QueryPerformanceCounter) или количесnву тактов (rdtsc), а не по какой-то "мифической" загрузке процессора

 

В принципе, я не совсем корректно выразилась (точнее, совсем некорректно ). Дело в том, что этот кусок кода вызывается не постоянно в смысле "непрерывно" , а периодически (с периодом десятки...сотни миллисекунд), и должен выполниться как можно быстрее. Т.е СРЕДНЯЯ загрузка процессора должна быть минимальной (пиковая - да, по возможности 100%, хотя возможен и может даже более предпочтителен вариант равномерной загрузки).
Просто есть тестовая программа, в которую подгружается моя длл, и которая сама мне показывает загрузку , из-за чего я и не меряла производительность непосредственно в своем коде. Может она и мифическая, но есть аналог, у которого эта мифическая загрузка меньше 8-), так что в качестве ориентира сойдет.

Но QueryPerformanceCounter/rdtsc я наверное действительно попробую.

 

А если их хранить в тригонометрической форме - это не может упростить?

 

Вряд ли, учитывая что у меня там куда ни ткни - быстрое преобразование Фурье ...
Кроме того, проблема, как я понимаю, совсем не в части вычислений, а именно в командах чтения-записи.
Я повторюсь, удаление ОДНОЙ команды movaps [edi],xmm0 уменьшает загрузку на четверть...

Тем временем я развернула цикл для вычисления 2 значений за проход вместо одного, вынесла все movaps-shufps, относящиеся к массиву ptr_in, в отдельный внешний цикл (учитывая, что этот массив используется М раз, где М порядка сотни), перепробовала N комбинаций по-разному упорядочивая команды внутри цикла, в частности максимально разнесла последовательные обращения к [edi]...
Результат - НОЛЬ. Загрузка в точности как и была...

Попробовала с горя PREFETCH - действительно не помог
Может, я неправильно понимаю смысл этой команды, но по идее если есть вот такая последовательность:
prefetch [edi]
// кучка movaps, mulps,addps
addps xmm0,[edi]
addps xmm1,[edi+16]
то вроде как во время выполнения кучки арифметических операций ничто не мешает процессору параллельно запихнуть себе в кеш строку по адресу [edi] и позже успешно ей воспользоваться... Тем не менее, добавление prefetch, наоборот, увеличивает загрузку...

 

На современных компах (старше PIII) рулит хардварный префетч, поэтому при последовательном доступе к данным команда PREFETCH ничего не дает

 

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

 

ettaine
Мадемуазель, а зачем Вам эта квалифицированная и во многом бессмысленная работа? Вроде есть там всякие BLAS-ATLAS-CUDA для высокопроизводительной линейной алгебры?

Для FFT есть FFTW с готовой сборокой под Win и Nix в том числе и под синглы.

 

ettaine
Префетч помочь должен в любом случае, в AMD manual есть рассказ как они разгоняли MemCpy. Когда першли на SIMD копирование из памяти сильно ускорилось, а когда добавили префетч, то еще больше ускорили. Жаль что я в этом ничего не понимаю, хотя пишу на SSE2 много.

 

persicum
А у меня, месье, может быть, хобби такое
CUDA не катит - нужен реалтайм (сама не пробовала, но на одном форуме ребята писали что может быть задержка порядка сотни мс).
BLAS не содержит функции поэлементного умножения векторов (есть только вектор на константу или матрицу).
Проблема FFT пока не стоит: FFTW думали использовать но передумали узнав стоимость лицензии для коммерческого использования (это так, на перспективу ), возможно будем использовать Intel MKL или IPP, но пока что скорость FFT не так критична, как того куска о котором весь этот разговор.
Про ATLAS раньше не слышала. По инфе на их главной странице пока поняла, что это реализация функций BLAS (см. выше) и некоторых LAPACK (решение систем линейных уравнений). Собственно, то и другое есть в Intel MKL, и по списку функций я там не нашла такой примитивной вещи как поэлементное перемножение комплексных векторов 8-)
Тем не менее, хочу вас поблагодарить, т.к. при контрольном просматривании хелпа к MKL я обнаружила там раздел Vector Mathematical Functions, который ранее от моих глаз загадочным образом ускользал (я искала нужные мне функции только в разделе BLAS). Так что попробую еще и так... Хотя есть смутное сомнение, что проблема все же с тем, что у меня массивов многовато...

C prefetch пока неясно... на Интеле он пока точно не помогает, почитаю еще мануал про оптимизацию для АМД.

 

ettaine

А можно проделать небольшой опыт?

Возьмите ваш первый цикл и оставьте в нем только вытаскивание значений из памяти и запись, ну может 1-2 фейковых использований исходных значений - типа почти пустой цикл:

Код (Text):

1. start:
2.         movaps xmm0, [eax]           
3.         movaps xmm1, [ebx]         
4.  
5. // ... что-нить типа xor xmm0,xmm1 - 1-2 инструкции.
6.  
7.         addps xmm0,[edi]
8.         movaps [edi],xmm0
9.  
10.         add eax,16                  // +4 elements
11.         add edi,16
12.         add ebx,16
13.         cmp ebx,edx
14.         jb start

Таким образом это будет некий замер N1 производительности. Уменьшите размер массивов (особенно приемника) в ~16раз (ваша идея собственно). Что будет? Уменьшайте еще если есть изменения. Идея - максимально локализовать проблему.

 

Мда, а что такое все эти массивы? Как получается эта память? Судя по камменту "//" это вставка из VC? Да, нельзя ли перед замером на всякий случай встряхнуть этот массивчег типа memset'ом?

 

Мда, вот незадача... BLAS level 1 действительно не содержит поэлементного умножения векторов. Наверное, предполагается сначала сделать из первого вектора диагональную матрицу с кучей нулей, а уж потом умножить матрицу на вектор =))). Кстати, FFT и поэлементное умножение уж очень напомнило мне свертку, которой я уже долгое время увлекаюсь в качестве хобби. Как же теперь бедным математикам проводить СВЕРТКУ o:, если такой нужной фичи там нет?

 

Кста, такая фишка есть в матлабе, а именно x.*y