17 сентября 2015 в Москве состоялась очередная ежегодная конференция Intel Software Conference. Программа конференции включала общие выступления (вступительное слово, обзор технологий компании для разработчиков, истории успеха клиентов Intel) и две параллельные сессии: первая была посвящена оптимизации кода и параллельным вычислениям, вторая касалась вопросов мобильной разработки и медиа.
По итогам посещения первой сессии, наибольший интерес у меня вызвал доклад на тему «Векторизуем код с Intel Advisor XE». Помимо демонстрации возможностей инструмента по оптимизации кода, рассматривались общие вопросы векторизации, давались рекомендации к написанию векторизуемого кода, а также разбирались примеры конструкций, препятствующих автоматической векторизации, и давались советы по их устранению. Но давайте обо всём по порядку.
Предыстория
Эта небольшая история началась с того, что один мой коллега как-то подошел и сказал: «Послушай, а ведь скоро пройдет очередная Intel software conference, почему бы нам не посетить её?». Он был там несколько раз ранее, отзывался всегда положительно. Сказано — сделано, регистрация бесплатная, а о посещении этого мероприятия посреди трудовой недели удалось договориться с руководством (за что — отдельное спасибо).
Кстати сказать, когда я обмолвился о предстоящем походе на конференцию своему старому другу (бывшему однокурснику, одногруппнику и коллеге в одном лице), он тоже, пользуясь случаем, решил «вырваться» из рутины рабочих будней, благо загрузка на рабочем фронте позволяла это сделать. И хотя он связывался с организаторами уже после того, как официальная регистрация на сайте была закрыта, надо отдать им должное — никаких проблем не возникло, в тот же день пришел положительный ответ.
Общее впечатление
На меня конференция произвела двоякое впечатление. Посетителей было не так чтобы очень много (виной тому вполне могли быть будни, люди заняты на основной работе), как мне показалось, в основном это были представители старшего поколения (среди посетителей мы встретили одного из уважаемых сотрудников родного университета, Вам привет, Борис Михайлович!).
Вступительное слово держал Greg Anderson (Director, Worldwide Software Sales Intel Software and Services Group, Portland, Oregon, USA), который рассказал на своем родном языке в целом о линейке средств разработки компании Intel, об их видении будущего технологий оптимизации и о некоторых деталях, новых фичах их свежих продуктов. Всегда полезно послушать носителя языка, а тут к тому же самым любознательным выпала возможность задать интересующие их вопросы напрямую.
Всю программу пересказывать не имеет смысла, она доступна на официальном сайте конференции.
«Коротко о главном»
Обсуждая с коллегами и друзьями данное мероприятие, выяснил, что тема векторизации кода достаточно многим интересна, но мало кто хорошо помнит детали. По итогам посещения конференции был написан небольшой отчет, который может быть использован в качестве краткого ликбеза.
Векторизация является частным случаем параллельных вычислений модели SIMD (Single Instruction Multiple Data). По сути это означает выполнение одной команды, обрабатывающей некоторое количество скалярных данных (в отличие от скалярных операций по модели SISD, Single Instruction Single Data, которые обрабатывают один элемент данных в каждый момент времени). Разные процессорные архитектуры поддерживают разные SIMD-расширения и/или SIMD-инструкции.
Подобный подход позволяет обеспечить существенный выигрыш в скорости выполнения вычислений определенного вида. В качестве простейшего классического примера часто приводят сложение двух массивов целых чисел, которое можно записать следующим образом (здесь и далее по тексту определения переменных опущены):
for (i=0;i<=MAX;i++)
c[i]=a[i]+b[i];Без векторизации (при рассмотрении одного регистра SSE2 размером в 128bit, что соответствует четырем 32bit целых) значительная часть регистра остается незанятой (Рисунок 1).
Рисунок 1. Иллюстрация процесса сложения двух массивов (без векторизации)
С включенной векторизацией компилятор может использовать дополнительные 32bit элементы для выполнения четырёх сложений в рамках одной операции (Рисунок 2).
Рисунок 2. Иллюстрация векторизованного сложения двух массивов
В общем случае это может приводить к ощутимому приросту производительности. Тем не менее, конкретные результаты могут сильно различаться в зависимости от исходного кода. компилятора, процессора.
Современные версии популярных компиляторов (например, Microsoft Visual C++ 14.0, GCC 5.3, Clang 3.7, ICC) поддерживают автоматическую векторизацию в той или иной степени. Для получения более подробной и актуальной информации следует обратиться к документации конкретной версии компилятора.
Хотелось бы перечислить основные условия, при выполнении которых циклы могут быть векторизованы. Стоит подчеркнуть, что это наиболее общие рекомендации (дающие возможность понять ключевые принципы, лежащие в основе векторизации), которые не обязательно будут работать в конкретном окружении. Каждый конкретный компилятор может иметь дополнительные ограничения и/или наоборот, «уметь» справляться с некоторыми из числа перечисленных ниже.
- Количество итераций цикла должно быть известно к моменту начала выполнения цикла (т.е., выход из цикла не является зависимым от данных);
- Отсутствие зависимых от данных точек выхода из цикла. Например, в следующем цикле это условие не выполняется:
for (i=0;i<=MAX;i++) { c[i]=a[i]+b[i]; // data-dependent exit condition if (a[i] < 0) break; } - Прямолинейное выполнение кода (отсутствие логических ветвлений). Таким образом, наличие оператора switch препятствует векторизации кода. При этом, наличие оператора if не так критично и зачастую позволяет выполнять векторизацию;
- Обычно векторизуется только внутренний (наиболее вложенный) цикл. Исключение составляют такие внешние циклы, которые были преобразованы во внутренние посредством каких-то либо других шагов оптимизации (например, раскрутка/схлопывание цикла);
- Отсутствие вызовов функций. Исключениями, как правило, являются встроенные математические функции (в документации компилятора можно посмотреть таблицы векторизованных функций) и функции, подлежащие встраиванию.
Существует также несколько обстоятельств, которые не обязательно предотвращают векторизацию, но могут негативно повлиять на этот процесс. Рассмотрим их:
- Обращения к участкам памяти, не являющимся непрерывными. В качестве примера, можно рассмотреть 4 расположенных рядом целых числа, которые могут быть загружены в регистр при помощи одной SSE инструкции. Если эти 4 числа не расположены в непрерывном участке памяти, для их загрузки может потребоваться большее количество операций, что определенно менее эффективно. В таких случаях векторизация возможна, но компилятор может счесть её не имеющей смысла.
Наиболее общим случаем этого могут являться циклы с непоследовательным доступом (например, когда индекс массива инкрементируется значениями, отличными от 1) или путем косвенной адресации (индекс массива берется из другого массива), Рисунок 3.
Рисунок 3. Шаблоны доступа к памяти (сверху вниз): непрерывный, с постоянным шагом ≠ 1, с переменным шагом
- Наличие «зависимых данных». Поскольку каждая SIMD инструкция обрабатывает несколько скалярных величин в каждый момент времени, векторизация возможна в случае, если изменение порядка обработки величин не повлияет на результат вычислений.
Простой пример «независимых данных» в вычислениях – когда данные, к которым обращаются в данной итерации цикла, не используются в последующих итерациях. В этом случае, каждая итерация независима и может выполняться в любом порядке, не влияя на итоговый результат вычислений.
Если же, к примеру, переменная записывается в одной итерации цикла, а читается в следующей итерации – имеет место быть зависимость вида «чтение после записи» (read-after-write/flow dependency).
Также к общим рекомендациям по написанию векторизуемого кода можно отнести следующие:
- Использование выровненных структур данных (например, по степеням двойки). Правильно спроектированная структура данных позволяет выполнять над собой операции наиболее эффективно, как с точки зрения времени выполнения, так и объема занимаемой памяти;
- Предпочтение структур массивов (Structures of Arrays, SoA) массивам структур (Array of Structures, AoS). Выбор организации данных оказывает существенное влияние на возможность векторизации кода. Если сравнить две структуры:
|
|
И то, как данные будут располагаться в памяти (Рисунок 4):
Рисунок 4. Графическое представление расположения данных в памяти
становится очевидным, что вариант SoA является более «дружественным» способом хранения данных для выполнения операций векторизации (поскольку обеспечивает хорошую локальность данных, а значит возможность эффективной векторизации за счет выполнения операций над смежными значениями).
Следует также отметить, что применимость описанных методик может быть ограниченной, так как реальная польза может быть извлечена только при тщательном анализе создаваемого кода.
Подводя итоги
В целом, впечатления от посещения конференции остались положительные. Но складывается ощущение, что из года в год программа меняется незначительно, поэтому я бы резюмировал так: при наличии возможности один раз посетить её точно необходимо тем, кто интересуется продукцией/технологиями компании Intel.
Будь я студентом, то при любой возможности (а их в этот период жизни, в среднем, больше, чем, например, при фулл-тайм занятости), посещал бы эту конференцию для расширения кругозора и формирования интересных знакомств.
То же самое можно рекомендовать людям, чья профессиональная деятельность тесно связана с высокопроизводительными вычислениями и/или глубокой оптимизацией кода — здесь можно встретить единомышленников, послушать истории успеха и получить ответы на интересующие вопросы, что называется, «из первых уст».
Спасибо организаторам и докладчикам!
Список источников:
1. A Guide to Vectorization with Intel® C++ Compilers, Intel Corporation, 2010;
2. Optimizing software in C++, A.Fog, Technical University of Denmark, 2015;
3. «Векторизуем код с Intel Advisor XE», К.Рогожин, Intel Software Conference, 2015.
Автор: Acronis
