Оттестировал разные процессоры на пока еще не до конца оптимизированном коде. Думаю, после оптимизации он станет существенно быстрее. Но так как оптимизация будет инвариантна для всех процессоров, то относительный результат не сильно изменится.
Во-первых, развертывание циклов даже не в самом оптимальном варианте показало все же более серьезное ускорение, особенно на больших размерностях.
У AMD FX-4350 это порядка 30% для single (float) и 36% для double. Мобильный AMD A10-4600M показывает чуть худший результат: 20% и 33% соответственно. Рекордсмен среди процессоров от AMD, конечно Ryzen 5, у него 41% и 67%. Только надо учитывать, что это относительно производительности не развернутого цикла FPU (x87), который в Ryzen, как выяснил Иван (см. комментарии к прошлому посту), зарезан в 2 раза по отношению к Scalar SSE, тут все четко получилось.
Intel i3-3227U показывает 29% и 27%. Старшие Intel тут менее результативны: Intel i7-6700HQ 20% для обоих типов и Intel i5-8300H 18% и 17%.
Теперь сравнение производительности Scalar SSE для разных процессоров относительно AMD FX-4350.
Как видим, появился тест, в котором AMD Ryzen 5 3600 смог догнать интеловские процессоры. Правда, радость омрачает тот факт, что догнать он смог только мобильные процессоры.
Люблю я процессоры AMD, в первую очередь, конечно, за цены. Еще они первыми добавили поддержку PCIe 4.0, что тоже плюс, правда, не очень пока ясно с чем его кушать, этот плюс.
Но справедливости ради должен сказать, что по однопоточной производительности они все еще далеки до отчетливого лидерства. Но надо проверить и другие дисциплины.😉
Еще бросается в глаза тот факт, что на младших мобильных, что Intel, что AMD, в многозадачном режиме SSE приходится жить похуже, а вот старшие мобильные Intel гораздо лучше с этим справляются. Даже лучше, чем с FPU. На Ryzen многопоточный режим одинаково эффективен что на FPU, что на Scalar SSE, ну и банально: этот процессор однозначный лидер в многопоточной производительности тупо из-за числа ядер.
Совокупный рейтинг пока приводить не буду, сначала надо закончить с оптимизацией циклов.
Приятно когда моя теория подтвердилась Вашей практикой :)))
ОтветитьУдалитьИнтересно что у AMD тип данных сильно влияет на ускорение, а у Intel - нет, как я понимаю Intel как-то умудряется даже на неразвернутом цикле загружать из памяти в 2 регистра параллельно. Процессор от AMD быстро молотит числа, но ему все надо разжевывать, может это и к лучшему.
> Правда, радость омрачает тот факт, что догнать он смог только мобильные процессоры
У меня нет AMD, но есть i5-7267U (мобильный) и i7-8700K (одолжил десктоп у сына) с одинаковой архитектурой, но разной максимальной частотой (3.5 vs 4.7 GHz). Понятно что частота и кэш решают, но в целом кардинальных изменений я не увидел на своем тесте:
- Пока СЛАУ помещается в L3 (<=384 уравнений): нормированная по частоте производительность очень близкая (+/- 5% в разную сторону)
- 768: десктоп +20% даже после нормирования по частоте, так как СЛАУ все еще попадает целиком в его L3 кэш (12 MB vs 4 MB)
- 1536: десктоп +10% но только в абсолютных числах, если нормировать, то медленнее, процессор уже не узкое место
- 3072: мобильный быстрее на 3% - это уже думаю погрешность измерений.
- На больших СЛАУ (6144 уравнений): узкое место память, и если нормировать по ее пропускной способности, то опять же числа очень близки.
А на каких размерностях и каком типе данных Вы сравнивали производительность и сколько потоков?
Я бы наверное сравнивал так чтобы у всех процессоров либо СЛАУ попадала целиком в L2, либо в L3, либо размер существенно больше L3, иначе задача удобна для одного, но сильно большая для другого, и не понятно что мы сравниваем, так как размерность мы выбираем сами :)))) Думаю i3 будет куда лучше выглядеть если тестировать на СЛАУ из 192 элементов и отличие будет сравнимо с разницей по частоте.
Но это так мысли в слух, просто пытаюсь понять что этот график значит.
Еще судя по графику FX-4350 выдает абсолютно одинаковую производительность в однопоточном и многопоточном режимах (1.0), что как-то подозрительно. Или я не правильно понял график?
> этот процессор однозначный лидер в многопоточной производительности тупо из-за числа ядер.
Я думаю скорее из-за размера L3 и это можно легко это проверить: протестировать его с 2-3 потоками, думаю будет даже быстрее так как меньше войны за L3. Так как кэш дорогой и занимает кучу места на кристалле, то экономически не выгодно производить процессор с большим L3, но маленьким числом ядер, но никто не заставляет их все использовать :)
> А на каких размерностях и каком типе данных Вы сравнивали производительность и сколько потоков?
УдалитьНа всех размерностях, начиная от трех, увеличивая на каждой итерации теста в 2 раза, а количество СЛАУ подбираю так, что бы все они были решены примерно за одну секунду. И так для каждого типа данных. Но на типе single тест заканчивается на 384 переменных, так как для больших размерностей точность типа не достаточна для решения СЛАУ.
Далее сравнение производительности идет относительно "образцового" процессора, в данном случае AMD FX-4350, производительность которого принимается за 1. Для всех остальных это отношения скорости решения СЛАУ тестируемого процессора к скорости образцового (для каждого типа и размера).
Дальше можно было бы сравнивать производительность на каждом размере, и под конкретную задачу так и надо делать. Но для оценки интегральной производительности я беру для каждого процессора среднее отношение скоростей для каждого типа данных.
Например, по данной диаграмме видно, что Intel i7-6700HQ в среднем в 1.6 раза быстрее в однопотоке, чем AMD FX-4350 (это в среднем по всем протестированным размерностям, при этом данные с типом single я беру с весом 0.55, а double - 0.45 соответственно).
В однопоточном режиме поток был один, в многопоточном столько, сколько процессор имеет ядер.
> Я думаю скорее из-за размера L3 и это можно легко это проверить: протестировать его с 2-3 потоками
Если, например, протестировать его и i5-8300H на двух потоках, то они и покажут примерно одинаковую производительность. У Ryzen в самом деле будет выше производительность на больших размерах из-за кэша и большой скорости памяти, но так как я беру среднюю производительность по всем размерностям, это не сильно повлияет. То есть результат будет тот же, что и однопоточная производительность, плюс-минус.
Ryzen и так немного быстрее в однопоточном тесте на больших размерностях на типе double, но так как я усредняю результаты, это не сильно ему помогает.
Хитро Вы придумали, агрегированная оценка конечно лучше, чем то что я предлагал. Одно число куда удобнее сравнивать чем ворох чисел.
УдалитьА я решил -сходить конем- попробовать переписать алгоритм так, чтобы он был более дружественным к памяти и учитывал что есть кэш, и не все чтения одинаково полезны. Но сначала, я его упростил: убрал умножение строки на константу из прямого прохода, а в обратном стал учитывать что на главной диагонали может быть не единица. Это изменение не повлияло на скорость, но зато упростило переписывание прямого прохода.
И так, все упирается в r[i] += r0[i] * c, особенно на больших системах, эта операция ну жутко не эффективна с точки зрения памяти. Почему бы ее не усложнить, обрабатывая сразу n строк за раз? Тогда для n=4, выражение будет r[i] += r0[i] * c0 + r1[i] * c1 + r2[i] * c2 + r3[i] * c3. А это уже куда более дружелюбно к памяти.
Вроде все просто, на каждой итерации: выделяем 4 строки и пересчитываем, но сложность в том что для правильного выделения 2-й строки, нужно учитывать 1-ю и т.д., так что после каждого выделения, пересчитывать все строки все же нужно, но не до конца, а только максимум 4 столбца. Там еще есть несколько нюансов, но все решаемо, главное не запутаться и рисовать картинки на бумажке :))))
Почему именно 4 строки? Я пробовал разные значения и для 4-5 строк еще хватает регистров и кэша, а вот больше все начинает замедляться, разница между 4 и 5 не большая, а степень 2-ки как-то мне больше по душе.
Теперь собственно ускорение или замедление, в общем [мой, СЛАУ/с.]/[стандартный, СЛАУ/c.] для разных размерностей:
- 6: 0.84
- 12: 0.91
- 24: 0.96
- 48: 1.12
- 96: 1.49
- 192: 1.47
- 384: 1.62
- 768: 1.89
- 1436: 2.08
- 3072: 2.08
- 6144: 2.75
В реальности нужно просто переходить на стандартный алгоритм по раньше, но мне лень перетестировать, да и не думаю что это окажет существенное влияние.
Интересно, а есть более правильный с точки зрения кэша способ решения СЛАУ? Я вот что-то сходу ничего не нашел. Будет время, посмотрю как их решают в математических библиотеках.
Очень интересный и неожиданный подход. Я пока сходу понять, правда, его не могу. То есть ты сначала первые 3 строки приводишь к диагональному виду, не трогая нижних, а потом четвертую пересчитываешь сразу за четыре прохода как бы стандартного алгоритма? То есть нижние строки приводятся к диагональному виду отложенно?
УдалитьКак насчет точности такого варианта алгоритма? Не страдает ли она? Ведь по идее на каждом шаге прямого прохода нам нужно выбирать максимальный диагональный элемент, что бы обеспечить достаточную точность.
Ну и тут потенциально могут вылезти подводные камни. У тебя, как я понял, повышение производительности за счет более полного использования регистров и кэша. То есть в стандартном варианте в кэш попадает 2 строки, а у тебя, если я правильно понял, 4. И тут все зависит от используемой хэш-функции для кэширования и ассоциативности кэша. Функции там не очень сложные, так как надо все делать очень быстро. И вроде бы сейчас на всех процессорах 4-ассоциативный кэш, так что все хорошо. Но, тем не менее в некоторых специфичных случаях вроде могут быть конфликты. И тогда будет вытеснения из кэша одной строки при обращении к другой с потерей производительности. Хотя у тебя вроде по тестам все очень хорошо.
А так ускорение, конечно, впечатляет. Давай, что ли, сравним абсолютные цифры? Если, конечно, есть такая возможность. Сравнение не очень корректное, так как, видимо, мы на разных архитектурах тестируем. Но все же.
Вот тут картинка с абсолютной однопоточной производительностью, систем в секунду, для типа double на Scalar SSE, пока все еще неоптизированные циклы:
https://drive.google.com/file/d/1oOrJwYM-yspcXuE9uqlNKMe0pOzt0-P7/view?usp=sharing
Правда, для трех переменных для последних четырех процессоров данные не очень точные: памяти не хватает для точной оценки, поэтому в агрегированном рейтинге эта размерность не участвует для них.
(Part 1 out of 3)
Удалить> Я пока сходу понять, правда, его не могу.
Да, я мастер объяснять, меня ни на русском, ни на английском не всегда понимают...
В плане точности все хорошо, результат "практически" идентичен, и главные элементы выделяются те же самые, а "практически" потому что алгоритм может сложить числа в другом порядке, а от перестановки мест слагаемых... сумма может отличаться для чисел ограниченной точностью, но это так лирика. На реальных тестах все сходится.
Теперь алгоритм более детально:
Шаг самого внешнего цикла 4, тело цикла обрабатывает сразу 4 строки. Результат одной его итерации эквивалентен 4-м итерациям внешнего цикла стандартного алгоритма.
Рассмотрим самую 1-ю итерацию для СЛАУ из 8 уравнений.
На входе матрица 8x9:
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
aaaaaaaaa
Что если выполнить 4 итерации прямого прохода стандартного алгоритма с выделением главного элемента, но пересчитать только 4 левые колонки, плюс не превращать главную диагональ в единицу? Схематично:
bbbbbbbbb
0bbbaaaaa
00bbaaaaa
000baaaaa
0000aaaaa
0000aaaaa
0000aaaaa
0000aaaaa
Где "a" - оригинальный, не обработанный элемент, "b" - пересчитанный финальный. 1-я строка исключение, так как там нечего пересчитывать она может быть как a так и b, я выбрал b для наглядности, чтобы показать что нам ее трогать больше не надо.
Теперь надо превратить оставшиеся "a" в "b", для этого ко 2-й строке нужно добавить 1-ю умноженную на коэффициент, к 3-й уже 1-ю и 2-ю, к 4-й уже 3 строки, а к остальным все 4-ре с 1-й по 4-ю.
Осталось понять где хранить коэффициенты умножения? Посчитать то их не получится так как требуемые для расчета элементы уже превращены в нули. Получается их нужно сохранить во время пересчета 1-х 4-х столбцов, но где именно? Можно в отдельной структуре, но это дополнительная нагрузка на кэш, есть место лучше: вместо нулей (нули то мы и после можем проставить).
В этом случае "модернизированные" 4 прохода стандартного алгоритма, превратят матрицу в:
bbbbbbbbb
cbbbaaaaa
ccbbaaaaa
cccbaaaaa
ccccaaaaa
ccccaaaaa
ccccaaaaa
ccccaaaaa
Где "c" - коэффициенты умножения для превращения оставшихся a в b:
c[i, j] = -m[j,i]/m[i, i]
m[i,j] += m[i,0] * m[0,i] + m[i,1] * m[1,i] + m[i,2] * m[2,i] + m[i,3] * m[3,i]
(Это для основных строк, для 4-х первых формула будет покороче, но схема таже)
В итоге применяя формулу и зануляя больше не нужные "c" мы получаем:
bbbbbbbbb
0bbbbbbbb
00bbbbbbb
000bbbbbb
0000bbbbb
0000bbbbb
0000bbbbb
0000bbbbb
И можно запускать снова для следующих 4-х строк.
Надеюсь понятно объяснил.
(Part 2 out of 3)
Удалить> У тебя, как я понял, повышение производительности за счет более полного использования регистров и кэша.
Скорее более рационального: на больших системах кэша не хватает и на каждой итерации внешнего цикла мы по сути загружаем всю матрицу из памяти, чтобы всего лишь сделать одно умножение + сложение над каждым элементом. По сути мы кэш даже не используем: прочитали, положили в кэш, пока дошли до конца матрицы место кончилось, мы начало уже перетерли и опять по нвой. С моей оптимизацией алгоритм делает в 4 раза больше полезного на одну загрузку из памяти.
> в стандартном варианте в кэш попадает 2 строки, а у тебя, если я правильно понял, 4.
У меня 5: в стандартном текущая плюс ту что прибавляем умноженную на коэффициент, а у меня прибавляются 4 строки и того: 1 + 4 = 5 В L2 кэш вроде помещается даже для больших систем, а вот L1 страдает, но суммарно выходит быстрее.
> И вроде бы сейчас на всех процессорах 4-ассоциативный кэш, так что все хорошо
Я больше боролся за L3 кэш, а он аж 16-ассоциативный у моего процессора, конфликты конечно могут быть, но думаю здесь в пределах нормы.
(Part 3 out of 3)
УдалитьТеперь цифры...
У меня алгоритм написан на Java и я не особо предавал внимание маленьким размерностям, так что на 3 и 6 у меня совсем грустно.
Scalar AVX, стандартный метод:
(процентов на 10% медленнее Вашего i7-6700HQ если не смотреть на маленькие размерности)
- 3: 9830029.552
- 6: 4138780.639
- 12: 1109273.773
- 24: 227823.126
- 48: 38960.806
- 96: 5442.390
- 192: 711.695
- 384: 86.983
- 768: 9.874
- 1536: 1.090
AVX, стандартный метод:
- 3: 9733868.947
- 6: 3858885.153
- 12: 1099711.066
- 24: 271557.496
- 48: 51287.405
- 96: 6591.972
- 192: 1237.867
- 384: 172.373
- 768: 18.783
- 1536: 1.744
- 3072: 0.177
- 6144: 0.016
AVX, с расчетом по 4 строки за раз:
- 3: 9548155.055
- 6: 3226650.585
- 12: 998832.136
- 24: 260798.185
- 48: 57589.42
- 96: 9854.164
- 192: 1817.245
- 384: 279.905
- 768: 35.44
- 1536: 3.632
- 3072: 0.368
- 6144: 0.044
А у Вас ведь еще можно и циклы оптимизировать и векторизовать, сложно мне будет тягаться!
У меня цель простая: в теории, если учитывать только 3-й вложенный цикл, мой процессор за 1 секунду может решить СЛАУ примерно из 3476 уравнений за секунду, а мой алгоритм решает только из 2400, что всего 33% вычислительных ресурсов, я хочу большего :))))
P.S. Ryzen 5 и впрямь какой-то зверь, числомолотилка!
>> И вроде бы сейчас на всех процессорах 4-ассоциативный кэш, так что все хорошо
Удалить> Я больше боролся за L3 кэш...
Тупанул, конечно эти 4 горячие строки должны попадать целиком в L2 кэш, а не в L3, а он 4-ассоциативный, как Вы и писали.
Чуть-чуть реализовал описанные выше идеи более оптимально, плюс стал прибавлять по 5 строк за раз вместо 4-х и переходить на стандартный метод когда остается меньше 24 строк, новые цифры:
- 3: 9563253.511
- 6: 3889398.004
- 12: 1145168.793
- 24: 275287.737
- 48: 63758.437
- 96: 11355.633
- 192: 2119.275
- 384: 334.533
- 768: 41.969
- 1536: 4.478
- 3072: 0.495
- 6144: 0.052
Да, на больших размерностях очень хорошая производительность получается. Несмотря на то, что видимо, у тебя чуть помедленней процессор, чем тестированный мною Intel i7-6700HQ, судя по тому, что на 3 переменных производительность примерно в два раза ниже.
УдалитьПосмотрим, что получится у меня после оптимизации циклов.
> Будет время, посмотрю как их решают в математических библиотеках.
УдалитьЕсть подозрения, что большие размерности другими методами решают. Скорее всего, итерационными. Менее точно, зато быстрее. Зависимость O(n^3) не дает разогнаться.
Этот комментарий был удален автором.
ОтветитьУдалить