Комментарии 17
Высказанные мной тут идеи в какой-то мере применимы до окна 19 включительно, но я пока не готов их проверять в коде :) Особенно с учетом "параллельного" алгоритма из соседней ветки комментариев и частичной применимости тех же идей к нему — слишком много вариантов, которые надо воплотить в коде.
Надо заметить, что все это применимо только к 1D-фильтру (зато в 1D первый шаг оптимизации должен быть применим и к алгоритму Хуанга — надо будет только обновлять гистограмму по два элемента подряд, и вычислять помимо медианного индекса еще индекс предыдущего элемента, что делается фактически автоматом).
Если именно про векторизацию и Хуанга — алгоритм не очень хороший для векторизации. Для малых размерностей элементов (<=8 битных), на первый взгляд, можно без особых проблем все сделать просто через N гистограмм — но ускорения в N раз не будет. Для больших размерностей, где размер гистограммы оказывается большим — остается разве что оптимизировать какие-то детали алгоритма. Лучше сначала оптимизировать сам алгоритм, благо что научный народ уже этим занимается и нам остается просто подсмотреть у них :)
Не сравнивали AVX-512 с другими SIMD — SSE/AVX2? Вот например:
habr.com/ru/post/204682
То есть можно догадаться, что в идеале AVX-512 должен быть в 2 раза быстрее AVX2, поскольку вектор в 2 раза шире. Но все эти сдвиги и перетасовки данных не добавляют ли нагрузки?
Также интересно, на каком железе вы тестируете. И будет ли оно работать IceLake-U — вроде как там поддерживаются не все подмножества AVX-512.
Но вопрос про железо остаётся в силе.
Идея из той статьи вполне применима, и вообще более "правильна" с точки зрения SIMD (делать одну операцию над несколькими данными, а не пытаться ускорять работу единственной операции). Назову ее "параллельный вариант". Портировал на AVX512 (единственное, что в отличие от варианта из статьи, для загрузки линий сети используется примитив от Боба, а не многократное чтение из памяти — так проще было делать и автоматически получается обработка краев), подставил частичную сеть для 7 линий, прогнал через бенчмарк и… оно быстрее в 1.64x раза, чем мой лучший результат. Посыпаю голову пеплом, ухожу в монастырь :)
Может быть, на больших окнах результат будет несколько другой. у Боба сеть работает параллельно, а у тов. ErmIg — последовательно и сложность будет расти гораздо быстрее. С другой стороны, 16 результатов на выходе против двух — это весомый аргумент, с которым тяжело бороться. Как выдастся свободное время, я еще подумаю, нельзя ли скомбинировать оба варианта.
Насечет AVX2: казалось бы AVX-512 должен быть в 2 раза быстрее; даже больше, чем в 2 раза — у него система команд богаче (одни масочные операции чего стоят). Но у AVX-512 есть неприятная особенность, что процессор при их использовании может начать тормозить. Я добавил вариант того же "параллельного" алгоритма ErmIg для AVX2, и он всего в 1.36x раз медленнее.
Про железо: я использую Xeon на архитектуре Skylake. Все подмножества AVX-512 не поддерживает никто — Intel клепает их быстрее, чем успевает делать под них процессоры. В моем коде используется только подмножество F, которое работает на всех процессорах, заявляющих про AVX-512.
Идея из той статьи вполне применима, и вообще более «правильна» с точки зрения SIMD (делать одну операцию над несколькими данными, а не пытаться ускорять работу единственной операции).Ну да, это удобно ещё и в том смысле, что логически векторный код не отличается от скалярного. В реализации ErmIg основная сортирующая функция вообще почти не меняется, благо интринсики спрятаны на более низком уровне.
Я добавил вариант того же «параллельного» алгоритма ErmIg для AVX2, и он всего в 1.36x раз медленнее.Понятно. ErmIg получил почти такую же разницу между AVX2 и SSE2 — 1.33.
Похоже это общая закономерность SIMD-оптимизаций, наибольший прирост даёт SSE (хотя тоже не всегда пропорционально размеру вектора), а c AVX+ темп снижается.
Если увеличить размер фильтра (хотя бы до 5x5), то ускорение от AVX2 и AVX-512BW значительно увеличиться.
Собственно в Simd есть реализация медианного фильтра с окном 3х3 и 5х5, с которыми там можно поиграться во встроенных тестах.
Для окна 5x5 AVX2 дает ускорение практически в 100 раз, AVX-512BW почти в 130 раз.
Я тут еще подумал и пришел к выводу, что те же идеи из статьи в какой-то мере можно применить и к 2D-фильтрации, и даже более того — там они будут гораздо натуральнее выглядеть, без необходимости крутить местами элементы в регистрах. Как будет время, попробую, чтобы не быть голословным.
Потому уже начиная с AVX2 узким местом становится именно загрузка данных, а не сами операции с ними.
Это очень круто :) Но иногда есть смысл оптимизировать дальше, даже если уже уперлись в скорость L3 — например, при композиции нескольких локальных операций можно обрабатывать данные по кусочкам, меняя оверхед многократной обработки краев на роскошь работы в L1/L2
Поигрался, получилось вроде неплохо. Я обновил статью применительно как раз к фильтру 5x5 из вашей библиотеки.
А вот частоту при использовании AVX512 — понижают («не так повышают»). Ну и больше шансов получить память как узкое место.
То есть можно догадаться, что в идеале AVX-512 должен быть в 2 раза быстрее AVX2, поскольку вектор в 2 раза шире. Но все эти сдвиги и перетасовки данных не добавляют ли нагрузки?в идеале вы хотите упереться в быстродействие памяти, которое не зависит от ширины регистра. Если такое быстродействие недостижимо, вы всё равно не получите двойного прироста за счет одного лишь удвоения ширины регистра, т.к. молотя AVX512 процессор начинает сбавлять частоты. Плюс, как ответили некоторые другие комментаторы, количество некоторых вычислительных блоков процессора ограничено, и может возникнуть ситуация, что вы одинаково упретесь в него. Вот и получается что оптимистический прогноз — порядка 30% прироста от AVX512 относительно AVX2. Единственное что может дать более существенное ускорение — использование эзотерических подмножеств команд, но только в тех случаях, где они хорошо накладываются на алгоритм
Быстрая медианная фильтрация с использованием AVX-512