Как найти пиковую производительность процессора

Оценка и оптимизация производительности вычислений на многоядерных системах

Данная публикация является переводом первой части статьи Characterization and Optimization Methodology Applied to Stencil Computations инженеров компании Intel. Эта часть посвящена анализу производительности и построению roofline модели на примере довольно распространенного вычислительного ядра, которая позволяет оценить перспективы оптимизации приложения на данной платформе.

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

• масштабируемое распараллеливание (collaborative thread blocking)
• увеличение пропускной способности памяти (cache blocking, переиспользование регистров)
• увеличение производительности процессора (векторизация, переразбиение циклов).

В третьей части статьи будет описан алгоритм, позволяющий автоматически подобрать оптимальные параметры запуска и построения приложения. Эти параметры обычно связаны с изменениями исходного кода программы (например, loop blocking значения), с параметрами для компилятора (например, фактор развертки цикла) и характеристиками вычислительной системы (например, размеры кэшей). Получившийся алгоритм оказался быстрее, чем традиционные тяжеловесные техники поиска. Начиная с простейшей реализации и до самой оптимизированной, было получено 6-кратное улучшение производительности на процессоре Intel Xeon E5-2697v2 и примерно 3-кратное на сопроцессорах Intel Xeon Phi первого поколения. В дополнение к этому, приведенная методология автоматического тюнинга выбирает оптимальные параметры запуска для любого набора входных данных.

Рисунок 1. Roofline модель Iso3DFD для Ivy Bridge 2S E5-2697 v2. Красная и светло-зеленые линии обозначают верхний теоретический и достижимый предел на текущей платформе соответственно. Горизонтальная синяя линия отражает максимально достижимые значения пропускной способности памяти принимая во внимание определенный дисбаланс сложений и умножений (#ADD;#MUL) и усредненные с помощью Stream triad бенчмарка (горизонтальная коричневая линия). Вертикальная темно-зеленая линия соответствует арифметической интенсивности для ядра Iso3DFD алгоритма. Пересечения с остальными линиями дают соответствующие достижимые пределы.

Краткий обзор

Статья описывает характеризацию (прим. переводчика — характеризация — выявление характерных признаков) и методологию оптимизации 3D алгоритма конечных разностей (3DFD), который используется для решения акустического волнового уравнения с константной или переменной плотностью изотропной среды (Iso3DFD). Начиная с простейшей реализации 3DFD, мы опишем методологию для оценки наилучшей производительности, которая может быть получена для данного алгоритма, с помощью его характеризации на конкретной вычислительной системе.

Введение

Метод конечных разностей во временной области – широко применяемая техника моделирования волн, например, для анализа волновых явлений и сейсморазведки. Этот метод популярен при использовании таких техник сейсмического анализа, как обратная временная миграция (reverse time migration) и полноволновая инверсия (full waveform inversion). Разновидности метода включают рассмотрение волн как акустических или упругих, а среда распространения может являться анизотропной, при этом плотность может также варьироваться.

Как известно, выбор конкретной численной схемы для аппроксимации частных производных имеет сильное влияние на производительность реализации [1]. В частности, это влияет на арифметическую интенсивность (число операций с плавающей запятой на каждое пересланное машинное слово) 3DFD алгоритма. Данная арифметическая интенсивность может быть далее связана с ожидаемой производительностью, используя методологию roofline моделирования [2]. Эта методология позволяет оценить уровень производительности реализации относительно максимально достижимой на конкретной вычислительной системе. То есть, roofline модель устанавливает рамки роста производительности, которая может быть достигнута с помощью оптимизации исходного кода программы. После того, как производительность реализации достигла определенного уровня, дальнейший рост производительности может быть получен только с помощью изменения самого алгоритма.

Для любого данного компьютера, его спецификация определяет

пиковые

значения для количества операций с плавающей запятой (FLOP/s) и для пересылок данных из памяти или в память (пропускная способность памяти). Соответствующие максимально

достижимые

показатели могут быть получены путем запуска стандартных бенчмарков как LINPACK [3] и STREAM triad [4].

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

Рисунок 2. Roofline модель Iso3DFD для сопроцессора Xeon Phi 7120P. Красная и светло-зеленые линии обозначают верхний теоретический и достижимый предел на текущей платформе соответственно. Горизонтальная синяя линия отражает максимально достижимые значения пропускной способности памяти, принимая во внимание определенный дисбаланс сложений и умножений (#ADD;#MUL) и усредненные с помощью Stream triad бенчмарка (горизонтальная коричневая линия). Вертикальная темно-зеленая линия соответствует арифметической интенсивности для ядра Iso3DFD алгоритма. Пересечения с остальными линиями дают соответствующие достижимые пределы.

Оценка производительности

Наше ядро алгоритма Iso3DFD решает акустическое изотропное волновое уравнение 16 порядка дискретизации по пространству и 2 порядка дискретизации по времени. Стандартная реализация данного 3DFD ядра обычно достигает менее чем 10% от пиковой производительности вычислительной системы на операциях с плавающей запятой в секунду (FLOP/s). Мы рассмотрим способ получения roofline модели [2] для вычислительного ядра Iso3DFD на CPU и сопроцессоре Xeon Phi. Для нахождения максимальной производительности данного приложения нам необходимо найти:

• Пиковое значение производительности и пропускной способности памяти (теоретические): 2420 GFLOP/s в одинарной точности и 352 GB/s для Intel Xeon Phi 7120A; 1036 GFLOP/s в одинарной точности и 119 GB/s для 2 процессоров Intel Xeon E5-2697v2 с 1866 MHz DDR3 памятью.
• Значения полученные на Linpack (или GEMM) and STREAM triad бенчмарках дают нам соответствующие показатели максимальной производительности на платформе: 2178 GFLOP/s и 200 GB/s для Intel Xeon Phi 7120A; 930 GFLOP/s и 100 GB/s для 2 процессоров Intel Xeon E5-2697v2 с 1866 MHz DDR3 памятью.
• Арифметическая интенсивность приложения рассчитывается на базе количества сложений и умножений (ADD, MUL) чисел с плавающей запятой и количества байт пересланных из памяти и определенной количеством загрузок и записей в память (LOAD, STORE).

Последний пункт следует из предположения, что вычислительная система имеет кэш с бесконечной пропускной способностью памяти и размером, а также имеет нулевую задержку на доступ к данным (latency). Это определяет своего рода безупречную подсистему памяти, где любой массив загружается полностью даже в том случае, если требуется всего 1 элемент.

Несколько других факторов также могут влиять на производительность всего приложения, использующая 3DFD ядро – выбор граничных условий, IO схема при обращении во времени, а также технология или модель параллельного программирования. Однако, в приведенном здесь анализе мы не рассматриваем граничные условия и IO. Параллельная реализация решения данной задачи использует метод domain decomposition для распределенных систем с использованием MPI стандарта вместе с параллелизмом по потокам на вычислительном узле с использованием OpenMP. В данной работе рассматривается вычисления в подобласти на одном узле вычислительной системы.

Арифметическая интенсивность платформы

Наша тестовая система состоит из двух CPU Xeon E5-2697 (2S-E5) с 12 ядрами на один CPU, каждый запущен с частотой 2.7 ГГц без турбо режима. Данные процессоры поддерживают AVX расширение набора инструкций с 256-битной шириной векторных регистров. Данные инструкции могут выполнять вычисления с 8 числами с плавающей запятой в одинарной точности (32 бита) одновременно (за один такт CPU). Таким образом, теоретическую пиковую производительность можно посчитать как 2.7 (GHz) x 8 (SP FP) x 2 (ADD/MULL) x 12 (cores) x 2 (CPUs) = 1036,8 GFLOP/s. Пиковая пропускная способность рассчитывается с помощью частоты памяти (1866 ГГц), количества каналов памяти [4], количества байт пересылаемых в один такт (8), что дает 1866 x 4 x 8 x 2(CPUs) = 119 GB/s для двухпроцессорного узла 2S-E5. Также, нам необходимо оценить реально достижимые значения пропускной способности и производительности для характеризации поведения приложения. В качестве первого приближения допустим, что производительность любого реального приложения может быть ограничена пропускной способностью памяти (totally bandwidth bound), что в данной работе оценивается с помощью Stream triad или быстродействием процессора (totally FLOP/s bound или compute bound или CPU bound), что показывает бенчмарк Linpack. Выбор именно этих двух бенчмарков является чисто гипотетическим, но мы можем утверждать, что если они и далеки от идеальных оценок, то уж точно они лучше подходят в качестве приближения, чем пиковые теоретические значения вычислительной системы.

На 2S-E5 системе Linpack дает 930 GFLOP/s, а Stream triad 100 GB/s. Далее мы можем посчитать арифметическую интенсивность (AI) для теоретических и реальных максимальных показателей соответственно, как:
AI (theoretical, CPU) = 1036,8 / 119 = 8,7 FLOP/byte
AI (achievable, CPU) = 930 / 100 = 9,3 FLOP/byte

С данными значениями мы можем характеризовать любое вычислительное ядро следующим образом: если арифметическая интенсивность ядра больше (меньше) чем 9,3 FLOP/byte мы можем сказать, что это ядро ограничено быстродействием процессора — CPU bound (пропускной способностью памяти – memory bound).

Аналогичные расчеты на Linpack и Stream triad для Xeon Phi дают 2178 GFLOP/s и 200 GB/s соответственно. Теоретические пиковые оценки — 2420 GFLOP/s и 352 GB/s. Таким образом, арифметическая интенсивность будет равна:
AI (theoretical, Phi) = 2420,5 / 352 = 6,87 FLOP/byte
AI (achievable, Phi) = 2178 / 200 = 10,89 FLOP/byte

Арифметическая интенсивность вычислительного ядра

Roofline модель также требует вычисления арифметической интенсивности данного приложения. Она может быть получена через подсчет количества арифметических операций и доступов в память путем визуальной инспекции кода или с помощью специальных средств имеющих доступ к счетчикам вычислительной системы. В рамках стандартного вычислительного ядра схемы конечных разностей [5] мы можем найти 4 загрузки (coeff, prev, next, vel), 1 запись (next), 51 сложение (вычисления индексов не берутся в расчет) и 27 умножений (рисунок 3).

for(int bz=HALF_LENGTH; bz<n3; bz+=n3_Tblock)
    for(int by=HALF_LENGTH; by<n2; by+=n2_Tblock)
        for(int bx=HALF_LENGTH; bx<n1; bx+=n1_Tblock) {
            int izEnd = MIN(bz+n3_Tblock, n3);
            int iyEnd = MIN(by+n2_Tblock, n2);
            int ixEnd = MIN(n1_Tblock, n1-bx);
            int ix;
            for(int iz=bz; iz<izEnd; iz++) {
                for(int iy=by; iy<iyEnd; iy++) {
                    float* next = ptr_next_base + iz*n1n2 + iy*n1 + bx;
                    float* prev = ptr_prev_base + iz*n1n2 + iy*n1 + bx;
                    float* vel = ptr_vel_base + iz*n1n2 + iy*n1 + bx;
                    for(int ix=0; ix<ixEnd; ix++) {
                        float value = 0.0;
                        value += prev[ix]*coeff[0];
                        for(int ir=1; ir<=HALF_LENGTH; ir++) {
                            value += coeff[ir] * (prev[ix + ir] + prev[ix - ir])
                                ;
                            value += coeff[ir] * (prev[ix + ir*n1] + prev[ix -
                                ir*n1]);
                            value += coeff[ir] * (prev[ix + ir*n1n2] + prev[ix -
                                ir*n1n2]);
                        }
                        next[ix] = 2.0f* prev[ix] - next[ix] + value*vel[ix];
                    }
                }}}

Рисунок 3. Исходный код вычислительного ядра с cache blocking

Арифметическая интенсивность может быть рассчитана по формуле:

AI = (#ADD + #MUL) / ((#LOAD + #STORE) x word size) (1)

Это дает арифметическую интенсивность, равную 3,9 FLOP/byte, которую мы умножим на теоретическую пропускную способность каждой платформы для получения первой оценки максимально достижимой производительности для данного алгоритма. Получим 1372,8 GFLOP/s на Xeon Phi и 461,1 GFLOP/s на 2S-E5. Однако теоретическое пиковое значение производительности предполагает параллельное использование двух конвейеров (один для ADD, другой для MUL), что невозможно в данном вычислительном ядре из-за дисбаланса между сложениями и умножениями, таким образом, данный код не сможем достичь этого оцененного максимального значения. А это значит, что достижимое максимальное значение следует усреднить с помощью:

(#ADD + #MUL) / (2 x max(add, mul)), (2)

что отражает отношение общего возможного количества операций при 16 операциях с плавающей запятой на такт (ops/cycle) и максимально количества сложений и умножений, которые исполняются при 8 ops/cycle, предполагая использование одной 256-битной AVX SIMD вычислительной единицы. Это даст теоретическую оценку пиковой производительности, учитывающую дисбаланс сложений и умножений.
Рисунки 1 и 2 показывают Roofline модель с верхними границами в 354,9 GFLOP/s и 1049,8 GFLOP/s для 2S-E5 и Xeon Phi соответственно, полученных с помощью этой усредненной версией арифметической интенсивности.
Более реалистичная roofline модель может быть получена при использовании пропускной способности Stream triad бенчамарка умноженной на арифметическую интенсивность вычислительного ядра (390 GFLOP/s и 780 GFLOP/s соответственно). Еще более реалистичную модель можно получить, если учесть некоторый дисбаланс сложений и умножений (с помощью (2)), что показано красной пунктирной линией. Новая верхняя граница будет равна около 298 GFLOP/s для 2S-E5 и 596 GFLOP/s для Xeon Phi. Так как наша модель основана на безупречной модели кэш-памяти, мы предполагаем, что получившиеся значения все еще являются грубой оценкой максимально достижимых значений производительности. Как продемонстрировано в [2], можно улучшить получившийся roofline добавлением некоторых новых сущностей в характеризацию вычислительной системы, как, например, влияние и ограничения кэш памяти.

Продолжение следует…

Список литературы

1. D. Imbert, K. Immadouedine, P. Thierry, H. Chauris, and L. Borges, “Tips and tricks for finite difference and i/o-less fwi,” in Expanded Abstracts. Soc. Expl. Geophys., 2011, pp. 3174–3178.
2. S. Williams, A. Waterman, and D. Patterson, “Roofline: an insightful visual performance model for multicore architectures,” Communications of the ACM — A Direct Path to Dependable Software, vol. 52, pp. 65–76, April 2009.
3. J. Dongarra, P. Luszczek, and A. Petitet, “The linpack benchmark: past, present and future,” Concurrency and Computation: Practice and Experience, vol. 15, no. 9, pp. 803–820, 2003, doi:10.1002/cpe.728.
4. J. D. McCalpin, “Stream: Sustainable memory bandwidth in high performance computers,” University of Virginia, Charlottesville, Virginia, Tech. Rep., 1991-2007, a continually updated technical report. www.cs.virginia.edu/stream
5. L. Borges, “Experiences in developing seismic imaging code for Intel Xeon Phi coprocessor.”, 2012. software.intel.com/en-us/blogs/2012/10/26/experiences-in-developing-seismic-imaging-code-for-intel-xeon-phi-coprocessor
6. J. H. Holland, “Genetic algorithms and the optimal allocation of trials,” SIAM Journal of Computing, vol. 2, no. 2, pp. 88–105, 1973.

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

Существуют
два способа оценки пиковой производительности
компьютера. Один из них опирается на
число команд, выполняемых компьютером
в единицу времени. Единицей измерения,
как правило, является MIPS (Million Instructions
Per Second). Производительность, выраженная
в MIPS, говорит о скорости выполнения
компьютером своих же инструкций. Но,
во-первых, заранее не ясно, в какое
количество инструкций отобразится
конкретная программа, а, во-вторых,
каждая программа обладает своей
спецификой, и число команд от программы
к программе может меняться очень сильно.
В связи с этим данная характеристика
дает лишь самое общее представление о
производительности компьютера.

Другой
способ измерения производительности
заключается в определении числа
вещественных операций, выполняемых
компьютером в единицу времени. Единицей
измерения является Flops (Floating point operations
per second) – число операций с плавающей
точкой, производимых компьютером за
одну секунду. Такой способ является
более приемлемым для пользователя,
поскольку последний знает вычислительную
сложность своей программы и, пользуясь
этой характеристикой, может получить
нижнюю оценку времени ее выполнения.

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

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

Для
того, чтобы оценить эффективность работы
вычислительной системы на реальных
задачах, был разработан фиксированный
набор тестов. Наиболее известным из них
является LINPACK – программа, предназначенная
для решения системы линейных алгебраических
уравнений с плотной матрицей с выбором
главного элемента по строке. LINPACK
используется для формирования списка
Top500 – пятисот самых мощных компьютеров
мира.

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

Наиболее
распространенными тестами, построенными
по этому принципу, являются: набор из
24 Ливерморских циклов (The Livermore Fortran
Kernels, LFK) и пакет NAS Parallel Benchmarks (NPB), в состав
которого входят две группы тестов,
отражающих различные стороны реальных
программ вычислительной гидродинамики.

Организация ЭВМ и периферийные устройства

Смотрите также