company_banner

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

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


Эти статьи предназначены для разработчиков среднего уровня. Предполагается, что читатель стремится оптимизировать производительность программ с помощью распространенных возможностей программирования на языках C++ и Fortran*. Использование ассемблера и встроенных функций мы оставляем более опытным пользователям. Автор рекомендует желающим получить более подробные материалы, чтобы ознакомиться с архитектурой наборов инструкций процессоров и с многочисленными исследовательскими журналами, в которых публикуются великолепные статьи по анализу и проектированию структур данных.

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

Размещение данных


Рассмотрим три уровня, на которых могут находиться данные. Ближайшее место к исполняемым блокам — регистры процессора. Данные в регистрах можно обрабатывать: применять к ним умножение и сложение, использовать их в сравнениях и логических операциях. В многоядерном процессоре у каждого ядра обычно есть собственный кэш первого уровня (L1). Можно очень быстро перемещать данные из кэша первого уровня в регистр. Может быть несколько уровней кэша, но обычно кэш последнего уровня (LLC) является общим для всех ядер процессора. Устройство промежуточных уровней кэша различается для разных моделей процессоров; эти уровни могут быть как общими для всех ядер, так и отдельными для каждого ядра. На платформах Intel поддерживается согласованная работа кэша в пределах одной платформы (даже при наличии нескольких процессоров). Перемещение данных из кэша в регистр осуществляется быстрее, чем получение данных из основной памяти.

Схематическое расположение данных, близость к регистрам процессора и относительное время доступа показаны на рис. 1. Чем ближе блок находится к регистру, тем быстрее перемещение и тем короче задержка при поступлении данных в регистр для выполнения. Кэш — самая быстрая память с наименьшими задержками. Следующая по скорости — основная память. Может быть несколько уровней памяти, хотя о многоуровневом устройстве памяти мы поговорим во второй части этой статьи. Если страницы памяти размещаются в виртуальной памяти файла подкачки на жестком диске или твердотельном накопителе, скорость существенно снижается. Традиционная архитектура MPI с отправкой и получением данных по сети (Ethernet, Infiniband и т. д.) обладает большими задержками, чем получение данных в локальной системе. Скорость при перемещении данных из удаленной системы с доступом по MPI может различаться в зависимости от используемого способа подключения: Ethernet, Infiniband, Intel True Scale или Intel Omni Scale.


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

Ближайшее место к исполняемым блокам — регистры процессора. В силу количества регистров и задержек, связанных с загрузкой данных в регистры, а также из-за размера очереди операций с памятью невозможно использовать каждое значение в регистрах однократно и подавать данные достаточно быстро, чтобы все исполняемые блоки были полностью заняты. Если данные находятся близко к исполняемому блоку, желательно многократно использовать эти данные перед тем, как они будут вытеснены из кэша или удалены из регистра. Некоторые переменные существуют только в виде переменных регистров и никогда не хранятся в основной памяти. Компилятор превосходно распознает, когда лучше использовать переменную только в регистре, поэтому не рекомендуется использовать ключевое слово register в C/C++. Компиляторы сами достаточно хорошо распознают возможности оптимизации и могут игнорировать ключевое слово register.

Разработчик должен проанализировать код, понять, как используются данные и сколько времени они должны существовать. Спросите себя: «Нужно ли создавать временную переменную?», «Нужно ли создавать временный массив?», «Нужно ли хранить столько временных переменных?». В процессе повышения производительности нужно собрать метрику производительности и сосредоточить усилия на приближении данных к модулям или ветвям кода, в которых на выполнение кода тратится значительное время. В число популярных программ для получения данных производительности входит Intel VTune Amplifier XE, gprof и Tau*.

Использование и многократное использование данных


Для понимания этого этапа отлично подходит пример с умножением матриц. Умножение матриц A = A + B*C для трех квадратных матриц n х n можно представить тремя простыми вложенными циклами for, как показано ниже.

for (i=0;i<n; i++)                      // line 136
   for (j = 0; j<n; j++)                // line 137
     for (k=0;k<n; k++)                 // line 138
         A[i][j] += B[i][k]* C[k][j] ;  // line 139

Основная проблема с таким порядком заключается в том, что он содержит операцию приведения матрицы (строки 138 и 139). Левая часть строки 139 — одиночное значение. Компилятор частично развернет цикл в строке 138, чтобы в наибольшей степени заполнить регистры SIMD и образовать 4 или 8 произведений из элементов B и C, необходимо сложить эти произведения в одно значение. Сложение 4 или 8 произведений в одну позицию — это операция приведения, которая не использует производительность параллельных вычислений и не использует все регистры SIMD с наибольшей эффективностью. Можно повысить производительность параллельной обработки, если свести к минимуму или вовсе исключить операции приведения. Если в левой части строки внутри цикла находится одно значение, это указывает на возможное приведение. Путь доступа к данным для одной итерации строки 137 показан ниже на рис. 2 (i,j=2).


Рисунок 2. Упорядочение; единственное значение в матрице A

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

for (i=0;i<n; i++)                    // line 136
   for (k = 0; k<n; k++)              // line 137new
     for (j=0;j<n; j++)               // line 138new
       a[i][j] += b[i][k]* c[k][j] ;  // line 139

После этого происходит смежное обращение к элементам А и С.


Рисунок 3. Обновленный порядок со смежным доступом

Первоначальный порядок ijk — это метод скалярного умножения. Скалярное умножение двух векторов используется для вычисления значения каждого элемента матрицы А. Порядок ikj — это операция saxpy (A*X+Y одинарной точности) или daxpy (A*X+Y двойной точности). Произведение одного вектора на константу прибавляется к другому вектору. И скалярное произведение, и операции A*X+Y являются процедурами BLAS уровня 1. При порядке ikj не требуется приведение. Подмножество строки матрицы C умножается на скалярное значение матрицы B и прибавляется к подмножеству строки матрицы A (компилятор определит размер подмножеств в зависимости от размера используемых регистров SIMD — SSE4, AVX или AVX512). Доступ к памяти для одной итерации цикла 137new показан выше на рис. 3 (вновь i,j=2).

Исключение приведения в скалярном умножении — значительное повышение производительности. При уровне оптимизации O2 и компилятор Intel, и gcc* создают векторизованный код, использующий регистры SIMD и исполняемые блоки. Кроме того, компилятор Intel автоматически меняет местами циклы j и k. Убедиться в этом можно в отчете компилятора об оптимизации, который можно получить с помощью параметра компилятора opt-report (-qopt-report в Linux*). Отчет об оптимизации по умолчанию выводится в файл filename.optrpt. В этом случае отчет об оптимизации содержит следующие фрагменты текста.

LOOP BEGIN at mm.c(136,4)
   remark #25444: Loopnest Interchanged: ( 1 2 3 ) --> ( 1 3 2 )

Отчет также показывает, что переупорядоченный цикл был векторизован.

LOOP BEGIN at mm.c(137,7)
    remark #15301: PERMUTED LOOP WAS VECTORIZED
 LOOP END

Компилятор gcc (версия 4.1.2-55) не переупорядочивает циклы автоматически. Об изменении порядка должен позаботиться разработчик.

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

В последнем варианте кода циклы j и k переупорядочены, а также применена блокировка. Код работает на подмножествах матриц или блоках размером blockSize. В этом простом примере blockSize является кратным n кода.

for (i = 0; i < n; i+=blockSize)
   for (k=0; k<n ; k+= blockSize)   
      for (j = 0 ; j < n; j+=blockSize)      
         for (iInner = i; iInner<i+blockSize; iInner++)     
            for (kInner = k ; kInner<k+blockSize; kInner++)
               for (jInner = j ; jInner<j+blockSize ; jInner++)
                 a[iInner,jInner] += b[iInner,kInner] *
                    c[kInner, jInner]

В этой модели обращение к данным одной итерации цикла j может выглядеть так.


Рисунок 4. Представление блочной модели

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

В приведенной ниже таблице показано соотношение производительности, измеренное в системе с разными компиляторами. Обратите внимание, что компилятор Intel автоматически меняет местами циклы в строках 137 и 138. Поэтому показатели компилятора Intel практически не отличаются для порядков ijk и ikj. Благодаря этому базовая производительность компилятора Intel также гораздо выше, поэтому итоговое увеличение скорости по сравнению с базовой кажется меньше.
Порядок Размер матрицы/блока Gcc* 4.1.2 -O2, повышение скорости/производительности по сравнению с базовым показателем Компилятор Intel 16.1 -O2, повышение скорости/производительности по сравнению с базовым показателем
ijk 1600 1 (базовый уровень) 12,32
ikj 1600 6,25 12,33
Блок ikj 1600/8 6,44 8,44
ijk 4000 1 (базовый уровень) 6,39
ikj 4000 6,04 6,38
Блок ikj 4000/8 8,42 10,53
Таблица 1. Соотношение производительности компиляторов gcc* и Intel

Показанный пример кода несложен, оба компилятора создадут инструкции SIMD. Это устаревший компилятор gcc, здесь он используется не для сравнения производительности компиляторов, а для демонстрации влияния порядка операций и приведения, даже когда данные, подлежащие приведению, обрабатываются параллельно. Многие циклы являются более сложными, в них компилятор не сможет распознать возможности для распараллеливания. Поэтому разработчикам рекомендуется изучать части кода, на выполнение которых тратится больше всего времени, просмотреть отчеты компилятора, чтобы понять, применил ли компилятор оптимизацию, или же ее нужно применить самостоятельно. Также обратите внимание на важность блокирования данных, если объем данных становится слишком большим. Для меньшей из двух матриц производительность не повышается. Для более крупных матриц производительность значительно возрастает. Поэтому перед применением блокирования разработчикам следует учесть относительный размер данных и кэша. При добавлении нескольких вложенных циклов и соответствующих границ разработчики могут добиться увеличения производительности от 2 до 10 раз по сравнению с первоначальным кодом. Это значительный прирост производительности, достигающийся при вполне разумном объеме усилий.

Использование оптимизированных библиотек


Как известно, нет предела совершенству. Блочный код по-прежнему работает не с самой большой скоростью: можно его ускорить с помощью процедур BLAS DGEMM уровня 3 из оптимизированных библиотек LAPACK, таких как Intel Math Kernel Library (Intel MKL). Для обычной линейной алгебры и преобразований Фурье современные библиотеки, такие как Intel Math Kernel Library, обеспечивают еще более эффективную оптимизацию по сравнению с простым блокированием и переупорядочением. Разработчикам рекомендуется применять такие оптимизированные библиотеки во всех возможных случаях.

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


Рисунок 5. Двухмерное представление блочной модели

Простой девятиточечный шаблон использует показанные ниже выделенные блоки для обновления значений в центральном блоке. Девять значений используются для обновления одной позиции. При обновлении соседнего элемента шесть из этих значений будут использованы снова. Если код работает в показанном порядке, то поведение будет подобно показанному на соседнем рисунке, для обновления трех позиций используется 15 значений. Далее это соотношение постепенно приближается к 1:3.

Если поместить данные в двухмерные блоки, как показано на рис. 5, то для обновления шести позиций используется 20 значений, помещаемых в регистры блоками по два; при этом соотношение приблизится к 1:2.

Рекомендую читателям ознакомиться с конечно-разностными техниками в превосходной статье Восемь методов оптимизации трехмерного конечно-разностного (3DFD) изотропного кода (ISO) Седрика Андреолли (Cedric Andreolli). В этой статье описывается не только блокирование, но и другие методики оптимизации памяти.

Заключение


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

Во второй части я расскажу о распараллеливании нагрузки на несколько ядер, а не только на регистры SIMD. Помимо этого, мы обсудим ложный общий доступ и массивы структур.
Intel
132.66
Company
Share post

Comments 27

    0
    Очень правильно сравнивать последний C++ Compiler с древним GCC 4.1.
    А что насчёт GCC 5.0? Clang? Стало страшно?
      +3
      В втором предложении после таблички написано
      «Это устаревший компилятор gcc, здесь он используется не для сравнения производительности компиляторов»
      0
      Спасибо, очень полезная информация. Лишний раз убеждаюсь, что в эти дебри лучше не лезь, а полагаться на BLAS-библиотеки.

      Однако не всегда данные и алгоритмы можно свести с операциями над матрицами и тут уже библиотеки не помогут. Когда-то я занимался стохастическим моделированием, основная проблема была в асинхронности операций. Т.е. кусок данных в двумерном/трехмерном массиве выбирался случайным образом и только после его обработки можно было бы переходить к следующей порцие данных, поэтому параллельно обрабатывать весь массив нельзя, а кэш процессора постоянно обновляется. :( Тут бы пригодилась какая-то страничная организация кэша.
        +1
        Имхо, делать оптимизации учитывающие особенности архитектуры процессора, которые [скорее всего?] скрыты стандартом языка в с++ коде — просто ужасно.
          +3
          Это не ужасно, это мир High Performance Computing.
            +3
            Глупо было бы не воспользоваться деталями архитектуры и выжать максимум производительности там, где это оправдано и даёт существенную выгоду.
            Это реальность не только High Performance Computing, но и многих интерактивных приложений типа игр.
            Оставьте ваш юношеский романтизм и идеализм :-)
              0
              Всё-таки, я считаю, лучше тогда уж писать на ассемблере или пользоваться библиотеками, на нем написанными. В примере с матрицами, скорее всего, лучший результат дал бы алгоритм Штрассена (но применительно к разностным уравнениям вопросов нет =)
                0
                Человек не сможет оптимизировать на ассемблере лучше компилятора.
                Компилятор знает и длины инструкций, размеры кэша и прочие параметры.
                Грамотно написанная функция на C++ транслируется в лучший ассемблерный код.
                  0
                  Человек не сможет оптимизировать на ассемблере лучше компилятора.

                  Какое категоричное заявление!
                  А ничего, что люди, писавшие компилятор решали общую задачу, которая значительно сложнее чем те частные случаи, которые стоит писать на ассемблере? Не приходило в голову, что вылизать до идеала (например, с помощью того же Intel VTune Amplifier'а) 100 — 150 строк значительно проще, чем написать компилятор, который будет генерировать сопоставимый по производительности код?
                  Не задумывался на тем что люди вообще делают с помощью Intel VTune? Зачем они его покупают?
                    0
                    Если компилятор не может что-то соптимизировать — это проблемы компилятора :)
                    Я согласен, что есть кейсы, когда требуется решение, а компилятор не может его дать — приходится писать разработчикам, попутно используя собственный код на ассемблере.
                    Я и сам периодически использую VTune — как раз чтобы посмотреть, что сгенерировалось, и как можно улучшить оригинальный код на Си, чтобы сгенерировалось что-то лучше. Чаще всего редактирование именно Си-кода позволяет достичь нужных результатов.
                    –2
                    1) Какие ваши доказательства?©
                    Человек может задать любую последовательность инструкций. Компилятор крайне ограничен.
                    2) Человек знает куда больше, включая контекст. Компилятору сейчас максимум конкретную микроархитектуру можно задать, но размер L2/LLC везде разный.
                    3) см п.1
                      0
                      это если:
                      а. человек — профессионал, который гарантированно не допустит ошибку, не пропустит возможность оптимизации и отлично знает особенности архитектуры
                      в. существует достаточное количество выделенных на проект часов, чтобы писать его на асме, под каждую отдельно взятую целевую платформу и архитектуру.
                    0
                    Если бы лучше было писать на ассемблере, никто бы не изобретал С или С++. Не стоит вдаваться в крайности, лучше использовать каждый инструмент гибко там, где это необходимо. Писать всё подряд на ассемблере неоправдано по времени. Правильный подход такой: С++, профилирование программы, определение «узких мест», оптимизация одним из возможных способов. И да, самые быстрые библиотеки для линейной алгебры написаны на C++ с небольшим добавлением intrinsics
                  0
                  Не менее чем делать треугольную крышку для квадратной банки.
                  0
                  А где же кодстайл хоть какой-то? То есть пробелы после операторов, то нет
                    0
                    Читаю очередную статью про оптимизацию, и возникает странное чувство что люди их читают и сознательно делают все наоборот.
                    Запускаем практически любую игрушку (онлайн с клиентом на ПК), и уже на экране ввода логина-пароля комп начинает взлетать на вентиляторах :).
                    По ощущениям, половина этих игрописателей, не знают даже про оптимизацию на уровне циклов и подпрограмм. Вынесение 1й формулы за тело цикла может дать прирост производительности сравнимый со всем описанным в статье. Отимизировать надо в первую очередь алгоритмы и код.

                    p.s. Это критика не статьи, а современных тенденций в программировании, когда сначала лажают в коде со словами «компилятор сам соптимизирует», а потом удивляются «а чё оно тормозит?».
                      0
                      Про онлайн не скажу, не имел опыта, но во многих игрушках для меня сейчас более загадочно то, что все по прежнему (похоже) пишут под однопроцесорные калькуляторы с считанными байтами оперативки. Куча игр, в которых весь игровой уровень можно впихнуть в десяток килобайт и при этом загрузки каждого приходится ждать ооочень ощутимое время. Особенно доставляет при линейном порядке прохождения.
                      Какая оптимизация того, чего мы не видим, если никто не задумывается о том, что отлично видно?
                        0
                        По моему наоборот. Если бы писали под «калькуляторы», то на современном железе все летало бы. А так тормозит даже то, где тормозить нечему абсолютно (выше пример с экраном логина).
                          0
                          И, в основном связано это с тем убеждением, что время программиста афигеть какое дорогое чтоб еще и с оптимизацией заморачиваться, а современное железо все стерпит. (тормозит тетрис — докупите еще 16 Гб памяти :))
                            0
                            Это что это за игрушки такие?
                              –1
                              Сходу вспоминаются Nuclear throne, например, или Enter the gungeon. Там уровни генерятся, но вполне последовательно. Что мешает делать это параллельно игре в низкоприоритетном треде непонятно.
                              Broforce вообще линеен, уровни побольше, но тоже должны читаться в момент даже без лишних заморочек. Это что сразу вспомнил.
                              Собственно в любой игре, в которой имеется ограниченное количество проходов в другие локации — предзагрузка не проблема. Хотя ГТА, Ведьмак или Minecraft отлично демонстрируют, что и с неограниченным количеством это тоже вполне решаемо.
                                –1
                                Я то думал вы о каких-то ААА играх, где я проблем с выжимкой последних флопсов из железа не припомню. Этот то шлак инди конечно, может тормозить и тупить на ровном месте. Broforce вон на консоли так портировали, что аж 15 фпс бывает. Люди не особо способные делают, плюс технология частенько мешает. Тот же юнити довольно тормозная штука.
                                  0
                                  Ну шлаком бы я их не назвал. Весьма неплохие игрушки. По мне так с точки зрения собственно игрового процесса многие ААА как раз коммерческий шлак, но это дело вкуса.
                                  ААА? Да любые практически обвиняют в лагах и тормозах. Некоторые вроде Бэтмена даже снимали временно с продажи из-за того что играть невозможно.
                                    0
                                    Ну если говорить о том, о чем изначально речь «не знают даже про оптимизацию на уровне циклов и подпрограмм», то это к крупным проектам никак не относится. Там все это прекрасно знают и, собственно, являются авторами многих как раз оптимизации, потому что именно ААА студии и их R&D отделы двигают эту отрасль.

                                    Бетмен же — консольные версии там работали отлично, где я и играл. А ПК версию делали как получится, поэтому и получилось как получилось. ПК все еще не является приоритетной платформой во многих случаях.
                          0
                          А еще есть страшный враг векторизации который называется «указатели». иногда компилятор не может доказать что массивы не пересекаются и отказывается генерировать хороший код.
                            0
                            При уровне оптимизации O2 и компилятор Intel, и gcc* создают векторизованный код, использующий регистры SIMD

                            А разве не надо явно указывать -msse -msse2?
                              0
                              Так когда же наконец у вас там выйдут процессора с поддержкой AVX512?

                              Only users with full accounts can post comments. Log in, please.