Начал реализовывать. В принципе, на что рассчитывал? FPU (x87) осуществляет операции, расширяя предварительно операнды в памяти до 80 бит, в то время как Scalar SSE этого вроде бы не делает, выполняя операции точно в размер типа.
Соответственно, на типе single (float) в 32 бита теоретически можем получить ускорение в 2.5 раза. Заменяем команды FPU на соответствующие команды Scalar SSE и получаем... ту же самую производительность, по крайней мере на AMD FX-4350. То есть производительность FPU и Scalar SSE отличается на плюс/минус погрешность измерения.
Хм... Крайне странно. Попробую что ли развернуть циклы?
Лирическое отступление про развертывание. Оптимизация здесь достигается за счет того, что не сбрасывается конвейер и полностью используются суперскалярные возможности процессора. В полной мере воспользоваться преимуществом развертывания легко на коротких циклах.
Тем не менее, на современных процессорах влияние развертывания на производительность заметно меньше, в первую очередь за счет очень качественного механизма предсказания переходов, а также использования теневых регистров.
И еще меньше оно становится, если параллельно используются два совершенно независимых устройства, в нашем случае блоки целочисленных операции и операций с плавающей точкой.
Ведь пока выполняется относительно длинная операция с плавающей точкой, мы можем параллельно выполнить пару коротких целочисленных операций, практически без потери производительности.
Еще один нюанс связан с количеством итераций цикла. Если количество итераций заранее известно, то можно цикл развернуть максимально оптимальным способом. Если же такой информации нет и пишется универсальный цикл, то при развертывании придется за счет дополнительных условий пожертвовать производительностью коротких циклов.
Теперь вернемся к решению СЛАУ на Scalar SSE. Документация AMD говорит о том, что при использовании SSE можно рассчитывать на увеличение производительности до 4 раз.
От чего это зависит? По моим соображениям, от количества АЛУ в блоке SSE. То есть 4-х кратного ускорения можно достигнуть, если у нас есть 4 сумматора, например. Но только на операциях сложения.
В случае наличия по два мультипликатора и сумматора можно достичь двукратного ускорения. Или 4-х кратного, если у нас есть данные, которые позволяют параллельно выполнить два умножения и два сложения.
При таком построение блока SSE возможно получить существенный выигрыш и от раскрытия цикла Scalar SSE в случае суперскалярной архитектуры.
В принципе, возможно и другое аппаратное решение: одно АЛУ, которое выполняет действие над всем регистром SSE, в результате которого получается сразу четыре результата (для типа single). В этом случае раскрытие цикла на Scalar SSE не даст слишком большого выигрыша.
В общем, раскрываю цикл и получаю выигрыш... та-дам!.. максимум в пару десятков процентов. Причем на маленьких размерностях закономерно производительность падает.
Понятно, результат пока предварительный, на разных процессорах может быть разным, чуть позже тесты покажут.
В общем, такое ощущение, что Scalar SSE ничего не знает про суперскалярность! 😉 Или я просто не умею его готовить?
Ниже пример кода, реализующего внутренний цикл, на этот раз, правда, для типа double. В принципе, ничем от single не отличается, кроме размера операндов. Результаты тоже аналогичны.
procedure MakeDoubleNextRowsPASM;
asm
// R8 - P, R9w - n, R10w - index
lea EBX, [R10d+1]; // BX - i
cmp BX, R9w;
jae @exit;
@Loop1:
mov RCX, [R8 + RBX*8]; // RCX - S
lea EDX, [R10d+1];
movsd XMM0, [RCX+R10*8];
mov ax, R9w; // --
sub ax, R10w; // --
@Loop2:
cmp ax, 4;
jb @Loop2_2;
movsd XMM1, XMM0;
movsd XMM2, [RCX+RDX*8];
movsd XMM3, XMM0;
mulsd XMM1, [R11+RDX*8];
movsd XMM5, XMM0;
movsd XMM4, [RCX+RDX*8+8];
subsd XMM2, XMM1;
mulsd XMM3, [R11+RDX*8+8];
movsd XMM7, XMM0;
movsd XMM6, [RCX+RDX*8+16];
movsd [RCX+RDX*8], XMM2;
subsd XMM4, XMM3;
mulsd XMM5, [R11+RDX*8+16];
movsd [RCX+RDX*8+8], XMM4;
subsd XMM6, XMM5;
mulsd XMM7, [R11+RDX*8+24];
movsd XMM8, [RCX+RDX*8+24];
movsd [RCX+RDX*8+16], XMM6;
subsd XMM8, XMM7;
sub ax, 4
movsd [RCX+RDX*8+24], XMM8;
add dx, 4;
jmp @Loop2_Fin;
@Loop2_2:
cmp ax, 2;
jb @Loop2_1;
movsd XMM1, XMM0;
movsd XMM2, [RCX+RDX*8];
movsd XMM3, XMM0;
mulsd XMM1, [R11+RDX*8];
movsd XMM4, [RCX+RDX*8+8];
subsd XMM2, XMM1;
mulsd XMM3, [R11+RDX*8+8];
movsd [RCX+RDX*8], XMM2;
subsd XMM4, XMM3;
sub ax, 2;
movsd [RCX+RDX*8+8], XMM4;
add dx, 2;
jmp @Loop2_Fin;
@loop2_1:
movapd XMM1, XMM0;
mulsd XMM1, [R11+RDX*8];
movsd XMM2, [RCX+RDX*8];
subsd XMM2, XMM1;
movsd [RCX+RDX*8], XMM2;
inc DX; //--
@Loop2_Fin:
cmp DX, R9W;
jbe @Loop2;
inc BX;
cmp BX, R9w;
jb @Loop1;
@exit:
end;
Отлично, продолжение сериала про СЛАУ :))))) Извините за мою портянку.
ОтветитьУдалить> Оптимизация здесь достигается за счет того, что не сбрасывается конвейер и полностью используются суперскалярные возможности процессора
Плюс экономится на инкременте счетчика и проверки условия выхода, а вот возможностей там не так много в плане математики, скажем у моего процессора всего 2 АЛУ. А вот SIMD - это другое дело, каждый АЛУ может 4 double обработать за раз, но это уже не про суперскалярность, а про векторизацию.
> одно АЛУ, которое выполняет действие над всем регистром SSE
Именно так и устроен процессор, он не умеет склеивать скалярные операции в одну, скажем у AMD FX-4350 2 128-битных АЛУ, он может выполнять за такт:
1. 2 SSE умножения, сложения или умножение + сложение, но ему все равно полностью или частично загружены регистры.
2. 1 AVX операцию склеивая АЛУ в один 256-битный
И того 8 double или 16 float за такт используя SIMD, но никак не 8 scalar SSD инструкций, а только 2: по одной на каждый АЛУ
> Тем не менее, на современных процессорах влияние развертывания на производительность заметно меньше ... максимум в пару десятков процентов.
У меня цифры сравнимы с Вашими: СЛАУ из 384 уравнений решается на 25% быстрее с развернутым циклом на scalar AVX, но пара 10-ов процентов - это тоже не плохо, к тому же SIMD не возможен без инфраструктуры разворота цикла, в любом случае нужно досчитывать хвост используя скалярные инструкции, а раз компилятор научен разворачивать циклы, то почему бы и не получить эти десятки или даже единицы процентов,
> В общем, такое ощущение, что Scalar SSE ничего не знает про суперскалярность!
Думаю просто решение СЛАУ упирается не в математику, а в скорость загрузки данных. Решил проверить это на синтетическом тесте обрабатывающем массивы уже загруженные в L1 (1024 элемента, double). Время перевел в такты моего процессора i5-7267U, up to 3.50 GHz. 1/3.50 = 0.29 нс/цикл. Вот в этих попугаях я и считал.
1. a[i] += b[i] * c (2 загрузки, 1 сохранение, 1 умножение, 1 сложение):
- no loop unroll, scalar AVX: 2.43 такта/тело цикла
- loop unrolled, scalar AVX: 1.76 такта/тело цикла
- AVX: 0.46 такта/тело цикла
- идеальный AVX: ~0.25 такта/тело цикла, или 1 такт на AVX цикл, судя по описанию процессор как раз позволяет 2 загрузки, 1 сохранение, 1 умножение, 1 сложение для 256-bit регистра за такт.
AVX почти в 2 раза медленнее идеала, наверное 2 загрузки и одно сохранение в L1 каждый такт - это пока еще слишком круто.
2. a[i] += a[i] * c + b[i] * d (те же 2 загрузки и 1 сохранение, но 2 умножения и 2 сложения):
- no loop unroll, scalar AVX: 2.90 такта/тело цикла
- loop unrolled, scalar AVX: 2.42 такта/тело цикла
- AVX: 0.68 такта/тело цикла
- идеальный AVX: ~0.5 такта/тело цикла, нужно в 2 раза больше сложений и умножений чем в 1-м тесте.
Все еще меньше чем идеал, но явно что-то выполняется параллельно на FPU, иначе вычисления требовали бы (2 сложения + 2 умножения) / 4 (4 double в AVX) = 1 такт/тело цикла, а судя по тесту, только 0.68
И продолжение, я превысил лимит в 4096 символа в комментарии :)))))))
ОтветитьУдалитьНесколько идей как можно код улучшить (или ухудшить) ассемблер:
1. Сейчас циклы завязаны в узел: я бы избавился от @Loop2_Fin и переходил на начало текущего цикла вместо перехода на верх 1-го развернутого. По сути вам нужно 3 подряд идущих независимых циклов: по 4, по 2, по 1 элементу. Это должно улучшить работу на маленьких системах.
2. Условия в Loop1 цикле написаны оптимально: проверка перед циклом и после тела цикла - это позволяет избежать 2-го перехода при выходе из цикла, а вот внутренние циклы проверяют условие выхода внутри цикла, в результате 2 перехода при выходе, а они ведь самая горячая часть в программе.
3. Вместо пересчета 2-х счетчиков (индекса и числа оставшихся элементов) оптимальнее будет перед каждым циклом подсчитать максимальное допустимый индекс массива и выходить из цикла если текущий индекс превышает лимит.
4. Если умножить константу умножения на -1, то movsd + subsd можно заменить на addsd ("movsd XMM2, [RCX+RDX*8]; subsd XMM2, XMM1; movsd [RCX+RDX*8], XMM2;" -> "addsd XMM1, [RCX+RDX*8]; movsd [RCX+RDX*8], XMM1;"), но надо смотреть быстрее ли это.
5. Не уверен что ручное переименование регистров нужно, для современных процессоров имя регистра задает только поток данных, так сказать связывает инструкции между собой, а физический регистр назначается процессором из списка свободных (Register renaming), также не уверен что пересортировка команд что-то решает. Попробуйте просто скопировать тело цикла как есть и подправить только смещения. Это должно быть проще читать и изменять, но опять же надо тестировать.
По 1-3 пунктам, если вдруг, что-то плохо написал, то вот псевдокод:
for (var i = 0; i < n; i++) {
...
}
предлагаю развертывать примерно так:
var i = 0;
var limit4 = n - 4;
if (i <= limit4) {
do {
...
i += 4;
} while (i <= limit4);
}
var limit2 = n - 2;
if (i <= limit2) {
do {
...
i += 2;
} while (i <= limit2);
}
if (i < n) {
do {
...
i++;
} while (i < n);
}
Я намерено оставил последнее условие циклом, чтобы сохранить их независимость: можно легко закомментировать любой из развернутых циклов и программа все еще останется корректной, но это так лирика.
P. S. Мне https://www.agner.org/optimize/microarchitecture.pdf и https://www.agner.org/optimize/instruction_tables.pdf понравились для быстрого поиска информации по разным процессорам. Так сказать отфильтрованные рекламные материалы.
Ваши исследования, прям глоток свежего воздуха в рутине работы, все воскресенье просидел обдумывая и анализируя результаты по влиянию кэшей, и попытках оптимизации. Еще раз извиняюсь за много слов.
Опечатался: "а вот внутренние циклы проверяют условие выхода внутри цикла", понятно что внутри, а как еще то? Хотел сказать: сейчас внутри цикла перед телом, а оптимальнее: перед циклом и внутри после тела.
Удалить> 1. Сейчас циклы завязаны в узел: ...
УдалитьДа, ты прав. Это будет существенно лучше, спасибо за подсказку. Но на самом деле, если уж оптимизировать до конца, нужен только один цикл, с максимальным развертыванием. Все остальное доделывается максимум за одну итерацию более коротких циклов. Поэтому достаточно условия. Ну, и если реализовать этот пункт, то совершенно справедливый п. 2 обойдется автоматически.
> 3. Вместо пересчета 2-х счетчиков ...
О да, тут порядок надо навести. Правда, выигрыша по производительности тут не будет, так как операции выполняются скорее всего параллельно друг другу, но это снизит нагрузку на ядро, что хорошо по другим соображениям.
> 4. Если умножить константу умножения на -1, ...
Да, тут надо проверять. Умножение на -1 заменяется на XOR, что достаточно быстро. Наверное, быстрее, чем считать из памяти.
> 5. Не уверен что ручное переименование регистров нужно...
Да, неплохо бы чекнуть.
> не уверен что пересортировка команд что-то решает.
Я тут сам вдруг с перепугу что-то перестраховался. Интересно будет проверить, влияет на самом деле, или нет.
Спасибо за замечания и за ссылки на информацию. Интересно посмотреть, как и что реализовано.
Пока проведу тесты как есть, а потом попробую оптимизировать с учетом нашего обсуждения.
> Поэтому достаточно условия.
УдалитьАга, Вы правы, оставлять их циклами - это расточительно. Можно еще заморочиться и использовать switch без break для добивания хвоста, как компиляторы, но это еще больше копирования кода:
switch (n-i) {
case 3:
// loop body
case 2:
// loop body
case 1:
// loop body
case 0:
// no op
}
А в это будет косвенный переход сразу на нужный кусок развернутого хвоста цикла.
Еще посмотрел более детально, что java JIT компилятор вытворяет:
1. Разворачивает цикл по 8 итераций. Интересно почему 8? Может как-то завязано на длину конвейера, или скорость кэша, не знаю, но это еще один потенциальный параметр для проверки :))))
2. Разворот более хитрый, в псевдокоде:
// 1 тело цикла использующий regA регистр для индекса
mov regB regA
// 7 тел цикла используют regB
add regA, 8
// условие выхода по regA
Я сначала думал 2 разных регистра для индекса - это артефакт автоматической оптимизации, но потом понял, что таким образом увеличение индекса и проверка условия отвязываются от основного тела цикла. Интересно, это как-то существенно заметно на производительности? Поди доли процента.
У меня тут вот еще какая мысль в голову пришла: я получил после развертывания цикла пару десятков процентов выигрыша Scalar SSE над FPU. Но FPU-то не развернутый! Если его развернуть, то, видимо, у Scalar SSE выигрыша над FPU не будет совсем...
УдалитьНепонятная ситуация. С одной стороны, на простых вычислениях Scalar SSE программировать легче, с другой - у FPU выше точность, плюс есть аппаратно реализованные всякие разные математические функции.
> 1. Разворачивает цикл по 8 итераций.
По всей видимости, по той же причине, что я развернул цикл на 4 итерации. Видимо, из расчета на то, что какой-нибудь процессор сможет 8 операций выполнить суперскалярно. )
Если писать универсальный код, то, кмк, ловить такие вещи бессмысленно. Надо делать то, что поддерживает все процессоры. Кстати, перемешивание кода - из того же разряда. Если внеочередное исполнение на каком-то процессоре имеет ограничения, то, перемешав код вручную, я возможно, помог ему достичь большей производительности, никак не повлияв на скорость исполнения на других, более умных в этом отношении процессорах.
> Если его развернуть, то, видимо, у Scalar SSE выигрыша над FPU не будет совсем
УдалитьДа, думаю Вы правы, я почему-то считал что x87 - это прям вообще отдельный зверь в процессоре, но на деле все на том же ALU что и SSE. Но все же x87 считают устаревшим и не развивают, будет ли он таким быстрым как scalar SSE в будущем история умалчивает.
> Если писать универсальный код, то, кмк, ловить такие вещи бессмысленно.
В этом как раз и фишка Java, компилятору не нужно генерировать универсальный ассемблер, а можно во время выполнения компилировать под текущую архитектуру, да еще и учитывать реальную длину цикла и в рантайме его перекомпилировать если есть необходимость. Код конечно мрак, я мало что понял, вот где-то здесь HotSpot решает нужно ли разворачивать дальше по каким-то эвристикам: https://github.com/openjdk/jdk/blob/master/src/hotspot/share/opto/loopTransform.cpp#L887
Но в целом вроде логика примерно такая: счетчик и переход - это зло и с одной стороны нужно делать цикл как можно больше, но декодирование команд - тоже занимает время и часто именно оно узкое место, поэтому процессоры их кэшируют, и если цикл сильно развернуть, то кэша не хватает, и процессор страдает. Поэтому надо искать золотую середину.
Что-то не дает мне покоя x87 vs SSE :))) Решил изучить одну из pdf что я приводил выше, ту где куча таблиц по всем инструкциям и архитектурам. Анализировал 2 колонки: Execution pipes и Reciprocal throughput, еще конечно Latency полезна - но я решил ее проигнорировать, в ней отличия если и есть, то не в разы, считаем что мы можем развернуть цикл так, что конвейер загрузиться максимально и именно один из блоков выполнения будет узким местом.
УдалитьСравнил mulsd, subsd vs fmul и fsubr для Piledriver (FX-4350, A10-4600M), Ivy Bridge (i3-3227U), Skylake (i7-6700HQ, i5-8300H), Zen 2 (Ryzen 5 3600).
x87:
- У всех кроме Zen 2: 1 сложение, 1 умножение за такт, сложение + умножение вроде тоже возможно, но это не точно.
- Zen 2: умножение и сложение выполняются только на блоке P0 и того максимум 1 операция за такт.
Scalar SSE (число операций без учета векторизации, на деле в 2-8 раз больше в зависимости от типа данных и SSE vs AVX):
- Piledriver: 2 универсальных 128-bit блока: 2 сложения, 2 умножения или сложение + умножение за такт
- Ivy Bridge: 1 256-bit блок сложения, 1 умножения: сложение + умножение за такт
- Skylake: 2 универсальных 256-bit блока: 2 сложения, 2 умножения или сложение + умножение за такт
- Zen 2: 2 256-bit блока сложения, 2 блока умножения и того до 2-х сложений + 2-х умножений за такт
И того:
- Математика на SSE вроде должна быть быстрее, особенно на Ryzen 5, если удасться загрузить конвейер по полной
- Но думаю на решении СЛАУ мы это не увидим, так как упремся в пропускную способность памяти. Максимум что нам нужно от математики это 1 умножение + сложение на 2 загрузки из L1, на это x87 хватает, возможно за исключением Ryzen. В нем, если судить по pdf, x87 использует только один блок в сравнении с другими архитектурами, может это как раз и объясняет что он медленнее i5 в однопоточных тестах
P.S. Нужно что-то более CPU-емкое придумать, типа расчета какой-нибудь криптографически стойкой хэш суммы :))))
>И того:
УдалитьДа, походу так и есть. Но, думаю, и на СЛАУ мы это все же как-то заметим. Уже из свойств процессора понятно, как он будет себя вести. Тем не менее у разных процессоров разные тайминги, поэтому реальный результат интересен для сравнения разных вариантов реализации.
>Zen 2: умножение и сложение выполняются только на блоке P0 и того максимум 1 операция за такт.
>Но все же x87 считают устаревшим и не развивают...
AMD не то что не развивает x87, оно его прямо душит!
>P.S. Нужно что-то более CPU-емкое придумать, типа расчета какой-нибудь криптографически стойкой хэш суммы :))))
Да, можно потестить и чисто регистровую производительность, но это уже такой прям жирный сферический конь получается. Не понятно, какой алгоритм только взять для тестирования. Гаусс хорош тем, что он практически вечен. А криптографический хэш чуть ли не каждый год меняется. Только реализуешь - а он уже устарел. Ну и кроме того, обычно под актуальный криптографический алгоритм есть спец. команды в процессорах.
Еще как вариант вариант картинку масштабировать скажем бикубической интерполяцией. Вроде математики должно быть больше чем в решении СЛАУ, но сложность линейная к размеру памяти, так что возможно опять в память уткнемся.
Удалить