SIMD и ручная векторизация (доп. семинар для первого курса по языку C и алгоритмам)
Вставка
- Опубліковано 17 чер 2024
- Специальные выпуски о комбинаторике.
Дополнительный семинар, когда сессия уже (почти) сдана, а семестр ещё далеко -- самое время поговорить об отвлеченных вещах. Например о векторизации.
Мы рассмотрим базовую поддержку векторных инструкций современными процессорами, эффект векторизации на производительность простых примеров, а дальше пойдём к более сложным примерам.
В частности -- к сортирующим сетям.
Лектор: Константин Владимиров
Дата лекции: 2 мая 2022 года
Съёмка: Евгений Богданов.
Звук: Юлий Тарасов.
Слайды ко всем лекциям по комбинаторике: sourceforge.net/projects/cpp-...
Исходный код к лекции: github.com/tilir/c-graduate/t...
Задачник для первого курса: olymp1.vdi.mipt.ru
Timeline:
00:00 Векторные возможности CPU
07:50 Хедера для интринсиков и методы работы с ними
14:53 Распечатка, сохранение и загрузка регистров
24:42 Простая арифметика
29:00 Первый пример: find
36:16 Больше интринсиков и blend
42:00 Второй пример: argmin
57:14 Перестановки
01:00:17 Третий пример: copy_if_less
01:13:12 Сортирующие сети
01:22:16 Битонические последовательности
01:32:38 Сортировка внутри векторного регистра
01:37:25 Вращения и сдвиги
01:43:12 Медианные фильтры и завершение
Errata:
* Тут пока пусто
Благодарю за лекции, давно не студент, но ваши лекции просто великолепны.
Спасибо большое. Очень классная лекция. Да все лекции классные
Невероятно крутая лекция!
🤣🤣... вперед с нашими молотилками ...🤣😂🤣👏
1:34:28 Скорее всего, опечатка для регистра idx, его 3-ий и 2-ой lanes должны быть (2,3), а не (3,4)
Где Вы рассказываете про маски с перестановками в copy_if_less, может имеет смысл пару слов сказать про таблично заданные функции (вычисления с памятью). Наверняка, многих "замыкает" на этом месте.
На i5-9400F avx512f, соответственно и на виртуалке avx512f нет( на ноуте 2016 года (естественно) тоже нет((
придется через mm256i пробовать
Проще, наверное, сказать, что порядок расположения байт в регистре всегда одинаков - младшие разряды справа, как на бумаге. А в ОЗУ зависит от архитектуры. Другое дело, что называть прямым порядком: L-E, поскольку младший байт в младшем адресе; или S-E, поскольку младший байт справа как при записи на бумаге.
Добрый день! У Вас замечательнейшая подача информации, однако для меня она пока что слишком сложная) Не могли бы Вы мне подсказать в какой последовательности смотреть Ваши лекции?
Начните с бакалаврского курса. Это самое лёгкое что есть и там всё очень систематично.
Константин, спасибо!
Я лично не до конца понял как организовать гарантированно переносимую программу. Получается, чтобы достучаться до intrinsics, скажем, avx2 , я должен сказать компилятору -mavx2. Но как я понимаю, с такой опцией компилятор имеет право автоматически использовать avx инструкции для floating point optimization по всему коду. Т.е. получается, что как только я включаю в gcc mavx2 я теряю переносимость? по крайней мере для всех функций скомпилированных с этой опцией?
Не подскажите есть ли способ обойти эту проблему кроме как дублировать код в разные файлы, компилируемые с разными опциями?
Да вы теряете переносимость. Есть функция __cpuid которой можно проверять поддержку во время исполнения и переключать на оптимизированный или базовый вариант.
@@tilir Cpuid это ясно. Но мне же надо собрать большую программу. В которой должна быть ветка кода, где гарантировано не включены инструкции avx. Т.е. получается обойтись без разных вариантов компиляции невозможно?
я влетел в эту проблему в одном из больших продуктов. По ряду причин недопускалось использование разных опций компиляции для разных файлов. И пришлось обойтись без векторных оптимизаций :)
Я пока не понимаю в чём проблема. Выносим векторизованные части в один модуль. Ставим там прагму. В рантайме решаем будем ли оттуда вызывать.
Чтоб работало на AMD надо другие функции использовать? или при поддержке SSE процессором можно просто запускать тот-же самый бинарик?
Я же в начале лекции рассказывал волшебные слова. Z-регистры это AVX512f. На AMD часто бывает, включается точно так же, весь выложенный код будет продолжать работать.
@@tilir Хм пересмотрел первые 10 минут -- это только программно можно проверять наличие регистров? и march=tigerlake это ж вроде только для Intel? сорри, я слабо понимаю но вот моя проблема в общих чертах: допустим написал я программу и на обложке диска пишу "системные требования" -- как мне указать какие процессоры поддерживаются? с Интел вроде понятно, а что искать на AMD? просто SSE3 поддержку например? Извиняюсь за витиеватый формат вопроса -- если бы я мог поставить его точно, я б спросил Гугл =)
@@XuryFromCanada если вы указываете march=tigerlake, то на обложке диска вы пишете tigerlake без вариантов. А вот если вы arch не указываете, а в коде просто прагмой включаете например AVX2 (и компилятор тогда верит что они на машине где вы это будете запускать будут) то на обложке диска вы пишете: нужны AVX2. И т.д.
Как Вы думаете откуда произошел этот базовый набор SIMD операций?
Я впервые увидел в CRAY1
ChatGPT мне говорит, что действительно базовые SIMD команды пошли с Cray1
Вы пробовали написать без бранчей ? Ну что то типа
for(auto [v, i] : arr | enumerate)
result = comparator(v, needle) * i;
? Насколько лучше компилятор с этим разбирается тогда? Или просто без бранчей становится быстрее возможно. Просто очень хочется, чтобы компиляторы этим занимались
Ну вы же сами можете попробовать. Так как вы написали работать не будет т.к. результат будет сбрасывать в ноль. Но можно сделать вот так:
for (i = 0; i < n; i++)
k = i * (a[i] < a[k]) + k * (a[i] >= a[k]);
Специально залил этот вариант, он методически интересный:
github.com/tilir/c-graduate/blob/master/simd/bench-argmin-branchless.c
Замеры у меня на машине:
Обычный: 3.949768
Без бранчей: 4.645893
Векторизованный: 0.074639
Резюме: убирание бранча не слишком помогло =)
@@tilir ну я так, для примера что то скинул)) Так то я максимально далёк от ассемблера и симд, но очень напомнило мышление при попытке без рекурсии в pack expanding совершить какое то действие, типа найти элемент
template
consteval size_t find_if_impl(typevec, std::index_sequence) {
size_t index = npos;
(void)std::initializer_list{
(static_cast(Pred(type{})) && index == npos && (index = Is))...};
return index;
}
По сути при нахождении максимума там можно попробовать что нибудь с массивом из двух элементов и вставкой в него без бранча, но думаю в большинстве случаев это будет просто вручную сделанной оптимизацией, которую компилятор уже умеет делать
Мой опыт с компиляторами показывает, что не надо пытаться их одурачить на ровном месте, они за это мстят. Чем яснее и точнее выражена ваша мысль, тем, на самом деле, больше шансов что она попадёт в категорию "о мы знаем как это соптимизировать!".
Разумеется в consteval функциях можно делать что угодно, я про рантайм.
Доброе утро, подскажите пожалуйста, если рассматривать простенькую векторизацию, как в примере с find, имеет ли смысл разворачивать цикл вручную, т.е. какова вероятность, что с интринсиками компилятор развернёт/не развернёт цикл даже с пакетом O2?
С векторизацией обычно компилятору анроллить легче а не сложнее. Но если сомневаетесь -- воткните прагму.
@@tilir спасибо, а подскажите ещё пожалуйста, есть ли какая-то скрытая семантика в использовании атрибута для выравнивания вместо _Alignas?
@@user-nt1re9ym4i никакой, я просто написал не думая. Разумеется _Alignas это стандартное средство.
@@tilir ещё раз спасибо, лекция просто отличная!
Что Вы скажете по поводу библиотеки C++20 eve? На ней можно писать платформо-независимый SIMD код...
Очень люблю эту библиотеку. А вы обратили внимание что лекция для первокурсников и я все примеры привожу на языке C?
@@tilir да на С без макросов и void* не получается :D
Тема масок раскрыта недостаточно. Насколько я помню, в avx512 маску можно на любую операцию повесить. Также не раскрыта тема gather/scatter memory access (-:
Хотел добавить gathering load/store но не нашёл убедительного примера. Может у тебя есть?
Насчёт масок вроде идею рассказал и пример показал, а уж куда вешать люди сами найдут по доке ))
@@tilir маски можно применить, чтобы векторизовать хвост цикла, который у тебя в примере остаётся скалярным. По поводу gather/scatter пока конструктивных мыслей нет. Возможно, что-нибудь в духе векторизации работы со связными списками, деревьями, etc?
Вот эту лекцию для первокурсников? Сурово.
Для физтехов отлично зашла.
"...шеснадцать иголок, четыре ствола, всё небо в попугаях..." - а можно сделать такой язык программирования, что бы в нём было всё, что есть в C++, но чтобы в нём небыло мёртвых попугаев, никаких иголок, а стволы были где-то далеко и не правда... и чтобы им можно было удобно и быстро пользоваться? ....и да, ещё, чтобы его можно было легко изучить?
Для явного SIMD программирования есть свои специализированные языки. Посмотрите, например, в сторону ISPC.