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

Скачать статью Optimize Data Structures and Memory Access Patterns to Improve Data Locality [Eng., PDF 782KB]

Аннотация

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

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

Введение

Классическим примером, иллюстрирующим проблему неэффективной локальности данных и ее влияние, является реализация алгоритма перемножения двух матриц. Сначала рассмотрим однопоточную версию алгоритма, которая перемножает две квадратные матрицы А и В и записывает результат в матрицу С по формуле: C[i][j] = Summ(A[i][k] * B[k][j]). Каждая матрица хранится в виде массиве и имеет достаточно большой размер (NxN):

Это простой пример ресурсоемкого алгоритма, который по ряду характеристик сходен со многими другими алгоритмами: 1) - он реализован с использованием вложенных циклов, 2) - он работает с большими объемами данных. Кроме того, можно выделить еще одно свойство, которое, однако, является менее очевидным, – итерации внешнего цикла независимы, поэтому идеально подходят для распараллеливания. Ниже приведена параллельная версия реализации алгоритма, реализованная с помощью Intel® Cilk™ Plus (мы просто заменили for на cilk_for из Intel® Cilk™ Plus и использовали Intel® Compiler, который поддерживает расширение языка Intel® Cilk™ Plus):

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

Ниже представлен пример, в котором анализ на высоком уровне не помогает в поиске причины возникновения проблемы. Когда мы запускаем анализ параллельности (Concurrency) в Intel® VTune™ Amplifier XE, мы видим, что проблема существует: малый уровень параллелизма во время выполнения критической функции (parallel_mm), однако анализ не объясняет, почему так происходит:

Мы получили бы идентичный результат, запустив анализ параллельности на Intel® Parallel Amplifier. Однако использование Intel VTune Amplifier XE (Intel Parallel Amplifier Extreme Edition) дает нам еще одно средство для анализа статистики производительности – шкалу времени. Шкала времени показывает рабочие потоки приложения и их поведение с течением времени. В нашем случае, при работе с программой перемножения матриц, Intel® VTune™ Amplifier XE выявил три рабочих потока, созданных исполняющей системой Intel® Cilk™ Plus в дополнение к основному потоку (обозначены как “Cilk Worker” на шкале времени), а также обозначил распределение времени работы CPU по рабочим потокам (показаны коричневым цветом на шкале). Опираясь на данные, собранные во время анализа параллельности, мы можем сказать, что время нагрузки CPU рабочими потоками очень мало, хотя время работы CPU во время выполнения работы достаточно большое.

Следующий шаг в нахождении причины плохого параллелизма – запуск низкоуровневого профилировщика, поддерживаемого на Intel VTune Amplifier XE:

Intel VTune Amplifier XE поддерживает несколько типов низкоуровневого анализа, основанных на EBS (Event-based Sampling): Lightweight Hotspots, а также еще несколько способов, объединенных в категорию “Advanced”. Цель EBS-анализа – сбор аппаратных событий с помощью проверки значений PMU-регистров, которые могут быть запрограммированы так, чтобы они увеличивали свое значение, когда встречается определенное аппаратное событие (например, ошибочное прогнозирование ветви, «непопадание» в кэш и т.д.). CPU может генерировать множество различных событий, и анализ одного из них или группы таких событий может быть недостаточным для определения причины плохой производительности. Зачастую для ответа на вопрос о производительности необходимо использовать правильные сочетания событий и определенные формулы. Если вы используете низкоуровневые профилировщики впервые и/или не знаете тип возникшей проблемы, рекомендуется использовать тип анализа “General Exploration”. “General Exploration” – заранее настроенный инструмент анализа, который собирает несколько аппаратных событий и использует некоторые формулы, которые могут помочь в обнаружении типа проблемы в приложении. Данный инструмент собирает аппаратные события, показывает данные вычислений формул и основные числа, которые могут указывать на тип проблемы производительности. Все события и формулы детально описаны во вкладке Help в Intel VTune Amplifier XE; также короткие описания можно прочитать во всплывающих подсказках.

Запуск “General Exploration” для программы перемножения матриц выявил ряд «узких мест» производительности (ячейки, обозначенные розовым цветом):

  1. CPI Rate: Показывает, сколько циклов CPU было в среднем потрачено на команду. В идеале это значение должно быть меньше или равно единице, но в нашем случае оно больше пяти.
  2. Retire Stalls: Показывает отношение числа циклов, в которых ни одна микрооперация не завершена, к общему количеству циклов. При отсутствии длинных операций и цепей зависимости, это число должно быть больше или равно единице, но в нашем случае оно ~0.8.
  3. LLC Miss: Показывает отношение числа циклов, в которых возник «промах» LLC (кэша последнего уровня), к общему количеству циклов. Любой запрос памяти, который получил “промах” LLC, должен быть обработан локальным или удаленным DRAM, что влечет за собой значительные задержки. В идеале, это число должно быть очень близким к нулю.
  4. Execution Stalls: Показывает отношение числа циклов, в которых ни одна микрооперация не была выполнена, к общему количеству циклов. Причиной Execution Stalls является ожидание ограниченных вычислительных ресурсов.

На основе полученных данных можно сделать вывод о том, что CPU тратит много времени на ожидание данных, получаемых из локальных или удаленных DRAM, из-за большого числа «промахов» LCC. Если мы дважды щелкнем мышкой по функции, Intel VTune Amplifier XE покажет нам исходную функцию и распределение аппаратных событий по строкам исходного кода. В нашем случае, большинство событий были получены во время выполнения внутреннего цикла:

Рассмотрим модель доступа к данным, реализованную в функции parallel_mm с i = 0 и j = 0:

В каждой итерации внутреннего цикла используется элемент матрицы А, который находится рядом с элементом, использованным в прошлой итерации. Такой способ доступа эффективно использует локальность данных. Способ доступа для матрицы В, однако, не является эффективным, так как каждая итерация программы нуждается в доступе к j-му элементу k-ого столбца, где k – внутренний счетчик цикла. Это и есть главная причина плохой производительности программы, так как такая реализация влечет большое количество «непопаданий» в кэш.

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

Поменяв местами два внутренних цикла, можно значительно улучшить локальность данных (i=0, k=0):

В данной реализации, для каждого значения i (счетчик внешнего цикла) мы высчитываем всю строку матрицы С и работаем только с последовательными элементами матриц А и В. Это изменение значительно улучшает производительность, увеличивая CPI и минимизируя количество «промахов» LLC:

Рекомендации

Intel® VTune Amplifier XE располагает большим количеством полезных функций для определения «узких мест» производительности в программе. В то время как высокоуровневые анализаторы полезны для алгоритмической оптимизации, низкоуровневые анализаторы фокусируются на анализе поведения аппаратного обеспечения во время выполнения приложения. Современные CPU становятся все более и более сложными, поэтому нужно быть профессионалом, чтобы выполнять низкоуровневый анализ производительности. Тем не менее, Intel VTune Amplifier XE делает все возможное, чтобы упростить выполнение низкоуровневого анализа, делая его доступным для рядовых пользователей. Когда высокоуровневый анализ не может помочь с выявлением проблемы, запуск анализа General Exploration на Intel VTune Amplifier XE может дать подсказку, что делать дальше, и поможет локализовать проблему.

В предыдущем разделе мы рассмотрели лишь одну проблему локальности данных, при этом изменение алгоритма помогло нам улучшить локальность данных и производительность программы. Однако, помимо этого, плохая локальность данных может быть результатом плохой реализации структуры данных. В этом случае для улучшения локальности данных придется менять местоположения данных. Для обнаружения данного типа проблемы рассматриваются те же симптомы, выявляемые Intel VTune Amplifier XE: слабый уровень параллелизма, малое CPI и большое число «промахов» кэша.

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

Руководство по применению

Анализ производительности – это повторяющийся процесс. При использовании одного из типов анализа Intel VTune Amplifier XE следует перезапускать программу после изменения кода. Intel VTune Amplifier XE предоставляет функцию автоматического сравнения, что позволяет сравнивать два варианта и таким образом отслеживать прогресс.

В этой статье мы обсудили анализатор “General Exploration”. Его основная задача – помочь начать работу с низкоуровневыми анализаторами. Существуют и другие, более конкретные, анализаторы (“Memory Access,” “Cycles и uOps” и т.д.), которыми вы можете воспользоваться на следующем этапе или в случае, когда вы знаете, какой тип «узкого места» производительности вы исследуете, а также, если вы нуждаетесь в более конкретных деталях.

Дополнительные ресурсы

Для получения подробной информации о возможностях оптимизации компилятора обратитесь к нашему Уведомлению об оптимизации.