Приводим данные и код в порядок: данные и разметка, часть 2

В этой серии из двух статей о производительности и памяти описываются базовые принципы и приводятся советы для разработчиков по повышению производительности программного обеспечения. Эти статьи затрагивают, в частности, работу памяти и компоновку. В первой части было рассказано об использовании регистров и о применении алгоритмов блокирования для повышения многократного использования данных. В этой части статьи сначала описывается компоновка данных для обычного распараллеливания — программирования для общей памяти с потоками, а затем распределенные вычисления по сетям MPI. В статье описываются понятия, связанные с распараллеливанием: векторизация (инструкции SIMD) и работа с общей памятью (многопоточная архитектура), а также вычисления с распределенной памятью. И наконец, в этой статье сравниваются компоновки данных «массив структур» (AOS) и «структура массивов» (SOA).

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

Программирование общей памяти с потоками

Давайте начнем с программирования общей памяти с потоками. Все потоки вместе обращаются к одной и той же памяти в пределах процесса. Существует множество моделей управления потоками. Наиболее известные среди них потоки Posix* и потоки Windows*. В работе, связанной с правильным созданием потоков и управлением ими, могут возникать ошибки. В современных программах, состоящих из множества модулей и создаваемых крупными командами разработчиков, часто возникают ошибки в параллельном программировании с использованием многопоточных вычислений. Разработано несколько пакетов для упрощения создания потоков, управления ими и наиболее эффективного использования параллельных потоков. Два самых популярных пакета — это OpenMP* и Intel Threading Building Blocks. Третья модель управления потоками — Intel Cilk Plus — не получила настолько широкого распространения, как OpenMP и Threading Building blocks. Все эти модели управления потоками создают пул потоков, который многократно используется каждой из параллельных операций и параллельных областей. В OpenMP есть преимущество — ступенчатое распараллеливание с помощью использования директив. При этом директивы OpenMP можно зачастую добавлять к существующим программам в пошаговом процессе и с минимальными изменениями кода. Если позволить библиотеке времени выполнения управлять обслуживанием потоков, это существенно упростит разработку многопоточных программ. Также предоставляется единая модель управления потоками, которой должны придерживаться все разработчики кода, что снижает вероятность возникновения некоторых распространенных ошибок. Оптимизированная библиотека управления потоками используется всеми разработчиками.

Принципы параллельного программирования, упомянутые во вводной части, состоят в том, чтобы размещать данные как можно ближе к месту, где они будут использоваться, и избегать перемещения данных. В многопоточном программировании в модели по умолчанию данные являются общими для всего процесса, к ним могут обращаться все потоки. Во вводных статьях по управлению потоками подчеркивается, насколько просто можно применить OpenMP к циклам do (Fortran*) или циклам for ©. Такие методы обычно значительно ускоряются при выполнении кода на двух или четырех ядрах. Зачастую эти методы наращиваются до 64 потоков или более. Впрочем, не менее часто дополнительные потоки не используются, причем в некоторых таких случаях это обусловлено неподходящей компоновкой данных. Дело в создании архитектуры, пригодной для параллельного кода.

Важно изучать возможности распараллеливания на более высоком уровне в стеке вызовов кода, чем первоначально предполагается разработчиком или средствами разработки. Если разработчик считает, что какие-либо задачи или данные можно обрабатывать параллельно, то попробуйте ответить на следующие вопросы (в свете закона Амдала): «Можно ли начать применять параллельные операции выше в стеке вызовов перед переходом к этому месту?», «Если я это сделаю, то увеличится ли параллельная область кода, что приведет к ускорению работы при задействовании большего числа потоков?».

Следует внимательно обдумать и размещение данных, и то, к каким данным может быть предоставлен общий доступ посредством сообщений. Компоновка данных должна предусматривать размещение данных там, где они используются больше всего, а оттуда их можно отправлять другим системам. Для приложений, представленных в таблице или в физическом домене с заданными разделами, программы MPI часто добавляют строку «фантомных» ячеек вокруг подчиненной таблицы или подчиненного домена. В «фантомных» ячейках сохраняются значения данных, отправленные процессом MPI, обновляющим эти ячейки. В многопоточных программах «фантомные» ячейки обычно не используются, но при снижении длины границы раздела для передачи сообщений желательно уменьшить границы разделов, использующих общую память. При этом снижается необходимость в блокировке потоков (или важных разделов) и вероятность образования конфликтов кэша, связанных с владением кэшем.

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

Рисунок 1. Скорость доступа к памяти, относительные задержки при доступе к данным

Если один поток выделяет и инициализирует данные, то эти данные обычно помещаются в память, ближайшую к процессору, в котором выполняется поток, выделяющий и инициализирующий память (рис. 1). Можно повысить производительность, если заставить каждый поток выделять и давать первую ссылку на память, которая в наибольшей степени будет использоваться этим потоком. Обычно этого достаточно для того, чтобы поток был запущен в области памяти, ближайшей к процессору. Если поток создан и активен, то ОС обычно оставляет его в этом же процессоре. Иногда бывает выгодно явным образом привязать поток к определенному ядру, чтобы избежать переноса потока между ядрами. Если данные имеют определенную компоновку, то может быть выгодно назначить или привязать потоки к определенным ядрам в соответствии с этой компоновкой. Библиотека выполнения Intel OpenMP (в составе Intel Parallel Studio XE 2016) содержит явные атрибуты сопоставления, эффективно работающие на сопроцессорах Intel Xeon Phi.

Это атрибуты Compact, Scatter и Balanced.

1. Атрибут Compact сопоставляет последовательные или соседние потоки с симметричными многопоточными множествами (SMT) на одном ядре перед назначением потоков другим ядрам. Это идеальное решение для ситуаций, когда потоки обращаются к данным, общим для потоков с последовательной нумерацией (т. е. соседних потоков).
2. Атрибут Scatter назначает по одному потоку каждому ядру, затем возвращается к первоначальному ядру для планирования других потоков в SMT.
3. Атрибут Balanced равномерно назначает потоки с последовательными или соседними идентификаторами одному и тому же ядру. Это рекомендуемый начальный атрибут для оптимизации сопоставления потоков в документации компилятора Intel 16.0 C++. Параметр Balanced доступен только для семейства продуктов Intel Xeon Phi. Для обычных ЦП он недействителен. Когда все SMT на платформе Xeon Phi задействованы, атрибуты Balanced и Compact работают одинаково. Если же на платформе Xeon Phi задействованы лишь некоторые SMT, то метод Compact будет заполнять все SMT на первых ядрах, а некоторые ядра останутся свободными (в идеале).

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

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

Представьте ситуацию, когда каждый поток увеличивает значение собственного счетчика, но сам счетчик при этом является одномерным массивом. Каждый поток увеличивает значение своего счетчика. Для увеличения значения счетчика ядро должно владеть строкой кэша. Например, поток A процессора 0 становится владельцем строки кэша и увеличивает значение счетчика iCount[A]. Одновременно поток A+1 процессора 1 увеличивает значение счетчика iCount[A+1]. Для этого ядро процессора 1 становится владельцем строки кэша и поток A+1 обновляет значение счетчика. Поскольку значение в строке кэша изменяется, эта строка аннулируется для процессора 0. В следующей итерации процессор 0 становится владельцем строки кэша и изменяет значение iCount[A], что, в свою очередь, аннулирует эту строку кэша для процессора 1. Когда поток в процессоре 1 будет готов к записи, цикл повторяется. Значительное количество циклов процессора тратится на поддержку согласованности кэша, поскольку аннулирование строк кэша, восстановление контроля и синхронизация с памятью влияют на производительность.

Наилучшее решение — не аннулировать кэш. Например, при входе в цикл каждый поток может прочитывать свой счетчик и сохранять его в локальной переменной в своем стеке (при чтении кэш не аннулируется). Когда работа завершена, поток может скопировать свое локальное значение обратно в постоянное расположение (см. рис. 2). Еще одно альтернативное решение — использовать заполнение данных, чтобы данные предпочтительно использовались одним определенным потоком в своей собственной строке кэша.

int iCount[nThreads] ;
      .
      .
      .
      for (some interval){
       //some work . . . 
       iCount[myThreadId]++ // may result in false sharing
     }

int iCount[nThreads*16] ;// memory padding to avoid false sharing
      .
      .
      .
      for (some interval){
       //some work . . . 
       iCount[myThreadId*16]++ //no false sharing, unused memory
     }

int iCount[nThreads] ; // make temporary local copy

      .
      .
      .
      // every thread creates its own local variable local_count
      int local_Count = iCount[myThreadID] ;
      for (some interval){
       //some work . . . 
       local_Count++ ; //no false sharing
     }
     iCount[myThreadId] = local_Count ; //preserve values
     // potential false sharing at the end, 
     // but outside of inner work loop much improved
     // better just preserve local_Count for each thread

Рисунок 2

Ложный общий доступ может возникнуть и при назначении скалярных значений в соседние области памяти. Этот случай показан в приведенном ниже фрагменте кода.

int data1, data2 ; // data1 and data2 may be placed in memory 
                   //such that false sharing could occur 
declspec(align(64)) int data3;  // data3 and data4 will be 
declspec(align(64)) int data4;  // on separate cache lines, 
                                // no false sharing

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

Выравнивание данных

Производительность программ является оптимальной, когда данные, обрабатываемые инструкциями SIMD (AVX512, AVX, SSE4), выравниваются по границам строки кэша. Потеря производительности при доступе к невыровненным данным различается в зависимости от семейства процессоров. Работа сопроцессоров Intel Xeon Phi особенно сильно затрагивается выравниванием данных. На платформе Intel Xeon Phi выравнивание данных имеет огромное значение. Эта разница не столь велика на других платформах Intel Xeon, но производительность все же заметно возрастает, когда данные выровнены по границам строки кэша. Поэтому разработчикам программ рекомендуется всегда выравнивать данные по 64-байтовым границам. В системах Linux* и Mac OS X* для этого даже не нужно менять код, достаточно лишь использовать соответствующий параметр в командной строке компилятора Intel: /align:rec64byte.

Для динамически выделяемой памяти в C можно заменить malloc() на _mm_alloc(datasize,64). Если используется _mm_alloc(), то следует использовать _mm_free() вместо free(). Подробная статья, посвященная выравниванию данных, находится здесь.

Также ознакомьтесь с документацией к компилятору. Чтобы показать влияние выравнивания данных на две матрицы одинакового размера, мы создали и запустили блочный код умножения матриц, использованный в первой части этой статьи. В первом случае матрица А была выровнена. Во втором случае матрица А была намеренно смещена на 24 байта (три значения типа Double). При этом производительность (использовался компилятор Intel 16.0) упала на 56–63 % для матриц размером от 1200 х 1200 до 4000 х 4000. В первой части я привел таблицу с производительностью упорядочения циклов в разных компиляторах. Когда одна матрица была смещена, компилятор Intel перестал давать прирост производительности. Разработчикам рекомендуется прочесть документацию к компиляторам, чтобы узнать о выравнивании данных и о доступных параметрах, чтобы компилятор мог с наибольшей эффективностью воспользоваться выровненными данными. Код для измерения производительности матрицы, смещенной по отношению к строке кэша, входит в состав кода для первой части статьи.

Дополнительные сведения вы найдете в документации к компилятору.

Чтобы показать влияние выравнивания данных на две матрицы одинакового размера, мы создали и запустили блочный код умножения матриц, использованный в первой части этой статьи. Первая матрица была выровнена. Вторая матрица была намеренно смещена на 24 байта (три значения типа Double). При этом производительность (использовался компилятор Intel 16.0) упала на 56–63 % для матриц размером от 1200 х 1200 до 4000 х 4000.

Массив структур или структура массивов

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

struct {
   uint r, g, b, w ; // a possible 2D color rgb pixel layout
} MyAoS[N] ;

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

struct {
   uint r[N] ;
   uint g[N] ;
   uint b[N] ;
   uint w[N] ;
} MySoA ;

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

Анализ Memory Access Pattern (MAP) в Intel (Vectorization) Advisor 2016 выявляет циклы с последовательным, непоследовательным и нерегулярным доступом.

В столбце Strides Distribution предоставляется совокупная статистика о том, насколько часто используется каждая модель в заданном цикле. На приведенном выше рисунке две трети горизонтальной полосы закрашены синим (это последовательный доступ к памяти), а правая треть закрашена красным (это непоследовательный доступ). Для кода с компоновкой «массив структур» Advisor также может получить «рекомендацию» для преобразования массива структур в структуру массивов.

Анализы моделей доступа и локальности памяти упрощены в Advisor MAP, они дополнительно предоставляют метрику использования памяти и сопоставляют диагностику каждого «шага» (то есть модель доступа) с определенными именами объектов и массивов C++ или Fortran*. Дополнительные сведения о Intel Advisor см. на сайтах здесь и здесь.

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

В компиляторе Intel, начиная с версии 2016 Update 1, преобразование «массив структур» -> «структура массивов» упрощено за счет применения шаблонов компоновки данных Intel SIMD (Intel SDLT). С помощью шаблонов SDLT можно просто переопределить контейнер массива структур следующим образом.

SDLT_PRIMITIVE(Point3s, x, y, z)
sdlt::soa1d_container<Point3s> inputDataSet(count);  

Это позволит обращаться к экземплярам Point3s по модели структуры массивов. Подробнее о SDLT см. здесь.

Существует несколько статей, посвященных использованию массивов структур и структур массивов. В частности, рекомендуется ознакомиться со следующими статьями (англ.):

• Comparing Arrays of Structures and Structures of Arrays Data Layouts for a Compute-Intensive Loop
• How to Manipulate Data Structure to Optimize Memory Use on 32-Bit Intel Architecture
• Structure of Arrays vs Array of Structures in cuda

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

Заключение

Подведем итоги. Вот основные принципы, которые следует соблюдать в отношении производительности и компоновки данных. Структурируйте код таким образом, чтобы свести к минимуму перемещение данных. Многократно используйте данные, пока они находятся в регистрах и в кэше (это также дает возможность меньше перемещать их). Можно ограничить перемещение данных с помощью блокирования циклов. Это особенно важно для программ с двухмерной или трехмерной компоновкой. Проанализируйте компоновку на предмет распараллеливания: как задачи и данные распределяются для параллельных вычислений. Правильные методики разграничения доменов повышают эффективность и обмена сообщениями (MPI), и программирования с общей памятью. В структуре массивов обычно перемещается меньше данных, чем в массиве структур, и выше скорость. Избегайте ложного общего доступа, создавайте действительно локальные переменные или применяйте заполнение, чтобы несколько потоков не ссылались на значения в одной и той же строке кэша. И наконец, настройте выравнивание данных так, чтобы они начинались в строке кэша.

Полный код можно загрузить здесь.

Если вы еще не читали первую часть этой статьи, то она находится здесь.

Примените описанные методики и оцените, насколько повысится производительность кода.

Автор: Intel

Источник