elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Узкое место или немного о SIMD
elizarov

В серии предыдущих статей я показывал различные аспекты производительности кода на примере простого цикла, последовательно суммирующего целые числа из массива. Достаточно изучить пропускную способность этого кода при работе в нескольких потоках или при разном размере массива, чтобы понять, что основное узкое место в нем это работа с памятью. Это на первый взгляд контринтутивный вывод, ибо работа с память происходит там последовательно, и именно на такую, последовательную работу с памятью, оптимизированы архитектуры современных процессоров.

Я очень хорошо помню момент, когда массовые процессоры стали обрастать оптимизациями именно для последовательной работы с большими массивами данных. В этом не было никакой инновации в том смысле, что специализированные системы для работы над большими массивами данных существовали уже очень давно. Первые векторные процессоры появились уже в 1970-x. Однако, процессоры которые легли в основу массовых персональных компьютеров, появившиеся примерно в то же время, были с самого начала и долго оставались исключительно скалярными. И это было более чем обоснованно, если учесть класс задач, который приходилось решать первым персональным компьютерам: работа с текстами, таблицами, бухгалтерией и т.п. Однако, в 1990-х начался лавинообразный рост мультимедийной информации: цифровой звук, цифровые изображения, цифровое видео. Всё это стало доступным широким массам и появился повышенный спрос на работу с мультимедийной информации на персональных компьютерах которые не были к этому готовы с точки зрения своей архитектуры. Ответом на этом в 1997-году стал выпуск процессора Pentium MMX (Multimedia Extensions). С тех пор, основное развитие процессоров для персональных компьютеров происходило именно в направлении их оптимизации для работы с мультимедийной информацией. Вот и получается, что современный процессор может легко распаковывать HD видео в режиме реального времени, а при работе над дискретной задачей, например, сбора ДНК, где требуется работа с огромными конечными автоматами занимающими память под завязку, большую часть времени он простаивает, ожидая получения данных из памяти.

Будет ли узкое место вашего кода в памяти или в вычислениях в общем случае зависит от очень многих деталей. Если делать более сложные вычисления, чем простое сложение целых чисел, то при последовательной работе с памятью очень быстро обнаруживается узкое место в АЛУ вашего процессора. Для обхода этого узкого места и предназначены различные наборы SIMD инструкций. Именно благодаря им возможна эффективная работа со все большими объемами мультимедийной информации.

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

UPDATE: Наглядный пример в числах, показывающий как при увеличении сложности вычислений память перестает быть узким местом, можно посмотреть в следующей заметке.


  • 1
Есть ли в "типичных бизнес-приложениях" сортировка?

Бузусловно есть. Только типичные бизнес-приложения обычно сортируют не массивы чисел, а массивы объектов. Да обычно это и не самая популярная операция. Среди классических алгоритмов и структур данных чаще встречаются хэши.

Edited at 2012-03-21 07:58 pm (UTC)

Ну вот, кстати, посчитать хэш-функцию или два ключа посравнивать - вполне себе упражнение для SSE.

Да и с сортировкой не все так просто, сортировать (большие) массивы (больших) объектов - неэффективно, куча лишнего времени уйдет на обмен, да и из кэшей вывалишься. А для сортировки массива указателей вида {key,pointer} SIMD может внезапно оказаться полезным.

Конечно SSE содержит массу полезных инструкций и не только для SIMD. Однако, в части SIMD, про которую я завел разговор в своей заметке, трудность для типичных бизнес-приложениях в том, что там редко есть эти самые "Multiple Data" к которым можно применить "Single Instruction". Наверное можно убыстрить расчет хэш-функции, например, для строк используя векторные инструкции, но учитывая что результаты такого расчета обычно кэшируются, практически заметного эффекта от этого все-равно не будет.

Дело же в первую очередь не в том, в каких задачах какие инструкции можно применить, а в том, для каких задача это даст заметный выигрыш в производительности. Декодирование видео, работа с изображениями, или обсчет физики часто может быть ускорен в разы при правильном использовании SIMD инструкций современных процессоров. Но в задачах где естественным образом нет векторов чисел, а идет работа с другими структурами данных (хэш-таблицы, деревья, и т.п.) их использованием не добиться сколь либо заметного эффекта.

Ну, если автор "бизнес-приложения" использует готовые контейнеры и алгоритмы (ну там std::hash_map или std::sort), у него места приложения для SIMD крайне мало. Ну вот в лучшем случае оператор сравнения ключей или еще что-то такое. Это раз.

Два: для эффективного использования SIMD нужны другие структуры данных, пока у пользователя 'Array of Structures' (в терминологии Intel) - странно было бы ожидать чего-то хорошего.

Как я наглядно показал тут, использование готовых контейнеров типа std::vector само по себе не является препятствием для генерации компилятором эффективного кода. В том числе, не мешает компилятору векторизовать код (применить SIMD инструкции, если он это умеет). И хотя свой собственный std::hash_map можно сделать быстрей стандартного, но не благодаря SIMD.

А про структуры данных в целом это как раз в точку. В том то всё и дело, что в бизнес приложениях обычно даже не просто 'Array of Structures' а 'Array of Pointers'. Об использовании же SIMD-friendly 'Structure of Arrays' в типичных бизнес-приложениях даже речи быть не может, в силу того, что они как-правило объектно-ориентированные как по духу стоящей перед ними задачи, так и по стилю написания кода.

Не-не, C++ очень не SIMD-friendly, даже если компилятор это формально умеет.
Потому что
а) выравнивание
б) pointer aliasing
И веселее всего pointer aliasing на this, даже restrict негде написать, вот тут я про это писал: http://blog.lexa.ru/2011/10/07/o_semantike_c_prodolzhenie.html (это не про SIMD, но проблема та же самая).

OO-же не является препятствием само по себе. Препятствием является то, что в нетривиальных случаях (более нетривиальных, чем вектор или список) структуры данных надо исходно дизайнить думая о производительности (занимаясь той самой Premature Optimization, которая root of известно что), а если этого нет, то передизайнивать может быть очень дорого.
А дизайнить так - дорого, ибо дизайнеров таких мало.

Ну последнее замечание не только к SIMD относится. Структуры данных важны для производительности так же как и алгоритмы. Мы весь QDS дизайнили вокруг быстрых структур данных. Получился не только сложный код, но и сложный API, поэтому потом поверх него сделали новый объектно-ориентированный dxFeed API.

По опыту QDS скажу чтобы приходилось много раз переступать через принципы ОО (нарушать инкапсуляцию и правильное разбиение на объекты), чтобы получить высокопроизводительные структуры данных. Следование принципам ОО при дизайне приводит к более понятному и простому в поддержке, но менее производительному коду.

Ромка, а я правильно понимаю, что относительная эффективность ArrayList (да и GC в модели с поколениями) во многом - следствие все-таки оптимизаций по последовательной работе с памятью? Или это таки не существенно?

Конечно. Современные архитектуры заточены именно под последовательную работу с памятью в первую очередь для оптимизации работы с "мультимедия", хотя сейчас это слово уже не модно — теперь говорят "векторные вычисления" подчеркивая более широкий класс задач, который можно решать на такой архитектуре. Именно поэтому массив это самая-самая быстрая структура данных на современной технике. ArrayList рвет LinkedList как тузик грелку именно сейчас.

20 лет назад такой огромной разницы в производительности между ними не было. Все классические книги по алгоритмам (тот же Кнут) в первую очередь всегда уделяли внимание списочным структурам (я даже не говорю про LISP, где они были поставлены во главу угла), а вектора были узко-специализированной прерогативой "физиков".


  • 1
?

Log in

No account? Create an account