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) поддерживают автоматическую векторизацию в тои? или инои? степени. Для получения более подробнои? и актуальнои? информации следует обратиться к документации конкретнои? версии компилятора.

Хотелось бы перечислить основные условия, при выполнении которых циклы могут быть векторизованы. Стоит подчеркнуть, что это наиболее общие рекомендации (дающие возможность понять ключевые принципы, лежащие в основе векторизации), которые не обязательно будут работать в конкретном окружении. Каждыи? конкретныи? компилятор может иметь дополнительные ограничения и/или наоборот, «уметь» справляться с некоторыми из числа перечисленных ниже.

  1. Количество итерации? цикла должно быть известно к моменту начала выполнения цикла (т.е., выход из цикла не является зависимым от данных);

  2. Отсутствие зависимых от данных точек выхода из цикла. Например, в следующем цикле это условие не выполняется:?

    for (i=0;i<=MAX;i++)?
    { 
      c[i]=a[i]+b[i];
      // data-dependent exit condition
      if (a[i] < 0)
        break;
    }

  3. Прямолинеи?ное выполнение кода (отсутствие логических ветвлении?). Таким образом, наличие оператора switch препятствует векторизации кода. При этом, наличие оператора if не так критично и зачастую позволяет выполнять векторизацию; ?

  4. Обычно векторизуется только внутреннии? (наиболее вложенныи?) цикл. Исключение составляют такие внешние циклы, которые были преобразованы во внутренние посредством каких-то либо других шагов оптимизации (например, раскрутка/схлопывание цикла); ?

  5. Отсутствие вызовов функции?. Исключениями, как правило, являются встроенные математические функции (в документации компилятора можно посмотреть таблицы векторизованных функции?) и функции, подлежащие встраиванию.

Существует также несколько обстоятельств, которые не обязательно предотвращают векторизацию, но могут негативно повлиять на этот процесс. Рассмотрим их:

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

    Наиболее общим случаем этого могут являться циклы с непоследовательным доступом (например, когда индекс массива инкрементируется значениями, отличными от 1) или путем косвеннои? адресации (индекс массива берется из другого массива), Рисунок 3.


    Рисунок 3. Шаблоны доступа к памяти (сверху вниз): непрерывный, с постоянным шагом ? 1, с переменным шагом

  2. Наличие «зависимых данных». Поскольку каждая SIMD инструкция обрабатывает несколько скалярных величин в каждыи? момент времени, векторизация возможна в случае, если изменение порядка обработки величин не повлияет на результат вычислении?.

    Простои? пример «независимых данных» в вычислениях – когда данные, к которым обращаются в даннои? итерации цикла, не используются в последующих итерациях. В этом случае, каждая итерация независима и может выполняться в любом порядке, не влияя на итоговыи? результат вычислении?.

    Если же, к примеру, переменная записывается в однои? итерации цикла, а читается в следующеи? итерации – имеет место быть зависимость вида «чтение после записи» (read-after-write/flow dependency).

Также к общим рекомендациям по написанию векторизуемого кода можно отнести следующие:

  1. Использование выровненных структур данных (например, по степеням двои?ки). Правильно спроектированная структура данных позволяет выполнять над собои? операции наиболее эффективно, как с точки зрения времени выполнения, так и объема занимаемои? памяти; ?

  2. Предпочтение структур массивов (Structures of Arrays, SoA) массивам структур (Array of Structures, AoS). Выбор организации данных оказывает существенное влияние на возможность векторизации кода. Если сравнить две структуры: ?
struct color // AoS 
{
  int r, g, b;                       
};
struct color // SoA 
{
  int *r, *g, *b;                       
};
И то, как данные будут располагаться в памяти (Рисунок 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. ?

Комментарии (0)