Продолжение статьи: часть 1, часть 3, часть 4
Пункты 1.1 и 1.2 освещают одну из самых основных проблем: использование только части адресного пространства в кэш-линии. А это не только увеличивает трафик по шине, но и снижает эффективность процессорных КЭШей. Если за время нахождения в КЭШе используется только часть кэш-линии, то приложение значительно снижает размер своего КЭШа. Пункт 1.1 ссылается на практику компиляторов располагать элементы структур в памяти согласно их размеру. Так, если первым элементом структуры является «char», за ним следует 4-х байтовый «int», то компилятор добавит между этими элементами еще 3 байта, чтобы расположить их по 4-х байтной сетке.
Пункт 1.2 кажется говорит сам за себя, однако это один из самых главных источников высокого трафика по шине. Существует множество путей обнаружения этой проблемы. В приложениях с преобладанием циклов эффективность можно грубо прикинуть, посчитав сколько раз исполняются основные циклы и сколько байт данных они используют каждую итерацию посредством статического анализа ассемблерного листинга. В результате получаем максимальное количество байт, используемое в цикле. Измерив количество кэш-линий проходящих по шине во время циклов и умножив это число на 64, получим трафик по шине, инициируемый в циклах. Теперь, если разделить число байт потребляемое в цикле (из анализа листинга) на общее число байт, передаваемых по шине, получим грубую оценку эффективности использования шины.
Чтобы узнать сколько раз выполняется цикл, усредните число событий INST_RETIRED.ANY_P по командам цикла. Это будет количество исполнений базисного блока. Само событие не равномерно распределяется по базисному блоку; однако полное количество будет верно для «достаточно большой» области. Общее количество для приложения верно, но «длинные» команды покажут гораздо большее число этого события, чем команды немедленно прежде или после их в пределах того же самого блока. В цикле с доминирующим потоком через несколько базисных блоков событие должно быть усреднено по всем его базисным блокам, предполагая, что из статистического анализа ассемблерного листинга можно продемонстрировать, что фактически они все выполняются равное число раз. С собранными данными это можно сделать в VTune Analyzer. Просто подсветите все команды в цикле, чтобы отобразить сумму по ним. Посчитайте число команд в подсвеченной области. Умножьте сумму INST_RETIRED.ANY_P на значение «Выборка После Значения» (Sampling After Value, SAV) и разделите на число команд. Это и будет полное количество итераций цикла.
Эта методика позволяет также определить усредненное количество итераций внутреннего цикла, необходимо разделить количество выполнений внутреннего цикла на количество выполнений базисных блоков перед или после цикла. Результат крайне неточен, если количество итераций внутреннего цикла будет намного больше 100, но весьма точен для малых циклов. Однако, в то время как методика неточна для большого количества итераций, в целом полезно знать, что итераций много.
Простой контроль загрузки и выгрузки в память поможет оценить общек количество байтов, использованных за итерацию. Есть, конечно, риск завысить эту оценку из-за идентичных указателей, особенно рассматривая множество циклов.
Общее количество использованных кэш-линий измеряется событием BUS_TRANS_BURST.SELF.
Вскоре будет доступна другая статья, с более детальным рассмотрением анализа доступа к данным.
В случаях, где только малая часть данных, переданных по шине, фактически используется в часто исполняемых циклах, есть несколько способов улучшить использование шины и, таким образом, производительность одного потока или нескольких параллельных. Наиболее очевидное решение — разбить данные согласно их фактическому использованию, организовывая их в параллельные массивы или связные списки структур. В общем случае, только некоторое подмножество данных каждой структуры используется многократно, большая же часть используется лишь иногда. В большом приложении полностью реорганизовать формат данных может быть чрезвычайно трудно. В таком случае, часто используемые данные можно скопировать в удобный, упакованный массив структур, содержащий только часто используемые элементы. Это позволит часто исполняемым циклам программы генерировать минимальный трафик по шине при выполнении. Более агрессивная оптимизация включила бы «разворачивание» формата данных по 2, в случае чисел с плавающей запятой двойной точности, или по 4, если все данные – целые (int) или с плавающей запятой одинарной точности (float). Это откроет путь для чрезвычайно эффективного использования набора инструкций Intel Streaming SIMD Extension 3 (SSE3), так как инструкции упаковки данных в этом случае не потребуются. Возможно даже было бы неплохо добавить несколько элементов-пустышек в конце массива, чтобы гарантировать размер массива равный четному множителю 2 или 4.
Может оказаться, что лучше использовать структуры массивов, а не массивы структур, если доминирующим шаблоном доступа является последовательный доступ по массиву списку, поскольку это гарантирует, что все байты кэш-линий будут использованы.
Компиляторы избегают генерировать инструкции потоковой выгрузки мимо КЭШа в случаях, когда количество итераций цикла присваивания данных неизвестно. Например, в простой функции TRIAD, представленной ниже, значение len не известно на момент трансляции.
Большинство трансляторов будет использовать обычные инструкции выгрузки или упакованные инструкции выгрузки SSE для массива «a». Это вызовет запрос на монопольное использование кэш-линии, что удваивает полосу пропускания, необходимую для этого массива. Если же массив не требуется немедленно или слишком велик, чтобы поместиться в КЭШе целиком, то трафик можно сократить вдвое. В примере выше, если количество итераций “len” умноженное на 8, больше чем размер КЭШа последнего уровня (LLC), деленный на 3, то первая кэш-линия для массива «a» будет выгружена из КЭШа еще до окончания цикла. Чтобы гарантировать, что компилятор Intel сгенерирует оптимальный код для большого количества итераций, нужно выровнять массивы по 16 байт и затем изменить цикл, добавив две директивы pragma сразу перед ним.
Также очень важна чрезмерная предварительная выборка кэш-линий. Плохо закодированные программные предвыборки могут усилить трафик по шине. Убедитесь, что вы не делаете предвыборку кэш-линий, которые потом не будут использоваться. Интервал предвыборки также должен быть достаточно большим, чтобы фактически загрузить строку в кэш до ее использования. Команды загрузки, которые ссылаются на кэш-линии все еще подгружаемые программной предвыборкой, инкрементируют счетчик события LOAD_HIT_PRE. Таким образом, это весьма просто обнаружить.
В ядре процессоров Intel Core 2 есть 4 аппаратных блока предвыборки. Два для работы с кэшем второго уровня (L2) способом, аналогичным ранее виденным в процессорах Pentium 4. Еще 2 дополнительных аппаратных блока предвыборки, работают с кэшем данных первого уровня (L1): это блок потоковой предвыборки и блок предвыборки, который ищет шаговые шаблоны, связанные с определенными адресами инструкций (IP). Как правило, в системе включены два блока предвыборки для КЭШа L2 и блок предвыборки IP L1D, но не блок потоковой предвыборки L1D. В целях анализа может быть полезно отключить эти блоки. Обычно это можно сделать в настройках параметров BIOS, в подразделе «cpu options» (опции процессора). Искать следует по ключевым словам «prefetch» и «adjency» – обычно эти пункты и надо менять.
Чтобы определить, какие аппаратные блоки предвыборки включены, можно использовать события производительности. Событие L2_LD.SELF.PREFETCH считает кэш-линии загруженные в КЭШ L2, блоком предвыборки L2. Появление события L1D_PREFETCH.REQUESTS говорит о включенных блоках предвыборки КЭШа данных L1.
Чтобы определить число неиспользуемых кэш-линий, запрашиваемых аппаратным блоком предвыборки, запустите программу 2 раза, с включенными и с выключенными блоками предвыборки. Измерьте общее количество кэш-линий, которые переданы с событием BUS_TRANS_BURST.SELF. Если есть существенное различие между этими двумя значениями, используйте VTune Analyzer, чтобы точно определить где это происходит в исходном коде. Частые причины тому:
Аппаратная предвыборка обычно управляется внутренним циклом, таким образом, в первом случае предварительно загруженные строки будут за пределом адресации внутреннего цикла, и не будут использоваться следующей итерацией внешнего цикла. Во втором случае блок предвыборки может попытаться загрузить уже использованные строки, то есть будет абсолютно бесполезен. Эта ситуация очень распространена в итерационных решателях и в большинстве случаев может быть исправлена простым изменением направления внутреннего цикла и некоторых требуемых указателей. В обоих случаях, вероятно, будет потребляться множество кэш-линий, запрашиваемых инструкциями загрузки и выгрузки. Это можно проверить с помощью события MEM_LOAD_RETIRED.L2_LINE_MISS, считающего только загрузки, и события L2_LD.SELF.DEMAND, считающее и загрузки и выгрузки в кэш-линии, включая также запросы, сделанные блоками предвыборки L1.
Разбиение данных на блоки — стандартное решение при недостатке пропускной способности, оно обычно предлагается без какого-либо намека на то, как же его фактически реализовать. Легче сказать, чем сделать. Однако, есть некоторая зависимость между декомпозицией данных и разбиением на блоки, и этим можно воспользоваться в некоторых случаях. Декомпозицию данных можно выполнить таким образом, чтобы получилось два уровня иерархии. Внешний уровень предполагает разбиение «один набор данных на ядро», и в тоже время на один процесс или поток, в зависимости от применяемой декомпозиции процесса счета, openmp это, явная организация поточной обработки или MPI, например. «Набор данных на ядро» можно делить дальше, согласно той же стратегии, подразделяя на “виртуальных узлы”, чей размер определяется размером КЭШа последнего уровня. Эту стратегию следует рассматривать на ранних этапах проектирования алгоритма, поскольку она может значительно увеличить возможности масштабирования.
Чрезмерная загруженность совместно используемого диска для программы означает, что время, проводимое программой в ожидании доступа к дисковой подсистеме, с числом используемых ядер начинает преобладать во времени исполнения самого приложения. Это легко заметить в режиме просмотра модулей в VTune Performance Analyzer, просто сравнивая, какая часть времени исполнения проходит в дисковом драйвере с увеличением числа ядер. Для хорошо масштабирующегося приложения (фиксированный или линейно увеличивающийся объем работы) эта часть должна быть постоянной. Конечно, на это стоит обращать внимание, только если (возросшее) время доступа к диску существенно.
Вариации в поведении означают, что несколько компонент мешают друг другу при доступе к диску. Это может случиться, например, из-за различных операций, вызывающих ошибочные движения дисковых головок, что мешает последовательному доступу, являющемуся самым эффективным.
В случаях, где доступ к диску не фиксирован, почти всегда лучше организовывать его очередность во времени, оставляя остальные ядра занятыми другими делами. Таким образом, разбросав фазы доступа к диску для отдельных потоков или процессов можно избежать чрезмерную загруженность дисковой подсистемы.
Эффективность использования кэш-линий
Пункты 1.1 и 1.2 освещают одну из самых основных проблем: использование только части адресного пространства в кэш-линии. А это не только увеличивает трафик по шине, но и снижает эффективность процессорных КЭШей. Если за время нахождения в КЭШе используется только часть кэш-линии, то приложение значительно снижает размер своего КЭШа. Пункт 1.1 ссылается на практику компиляторов располагать элементы структур в памяти согласно их размеру. Так, если первым элементом структуры является «char», за ним следует 4-х байтовый «int», то компилятор добавит между этими элементами еще 3 байта, чтобы расположить их по 4-х байтной сетке.
Пункт 1.2 кажется говорит сам за себя, однако это один из самых главных источников высокого трафика по шине. Существует множество путей обнаружения этой проблемы. В приложениях с преобладанием циклов эффективность можно грубо прикинуть, посчитав сколько раз исполняются основные циклы и сколько байт данных они используют каждую итерацию посредством статического анализа ассемблерного листинга. В результате получаем максимальное количество байт, используемое в цикле. Измерив количество кэш-линий проходящих по шине во время циклов и умножив это число на 64, получим трафик по шине, инициируемый в циклах. Теперь, если разделить число байт потребляемое в цикле (из анализа листинга) на общее число байт, передаваемых по шине, получим грубую оценку эффективности использования шины.
Чтобы узнать сколько раз выполняется цикл, усредните число событий INST_RETIRED.ANY_P по командам цикла. Это будет количество исполнений базисного блока. Само событие не равномерно распределяется по базисному блоку; однако полное количество будет верно для «достаточно большой» области. Общее количество для приложения верно, но «длинные» команды покажут гораздо большее число этого события, чем команды немедленно прежде или после их в пределах того же самого блока. В цикле с доминирующим потоком через несколько базисных блоков событие должно быть усреднено по всем его базисным блокам, предполагая, что из статистического анализа ассемблерного листинга можно продемонстрировать, что фактически они все выполняются равное число раз. С собранными данными это можно сделать в VTune Analyzer. Просто подсветите все команды в цикле, чтобы отобразить сумму по ним. Посчитайте число команд в подсвеченной области. Умножьте сумму INST_RETIRED.ANY_P на значение «Выборка После Значения» (Sampling After Value, SAV) и разделите на число команд. Это и будет полное количество итераций цикла.
Эта методика позволяет также определить усредненное количество итераций внутреннего цикла, необходимо разделить количество выполнений внутреннего цикла на количество выполнений базисных блоков перед или после цикла. Результат крайне неточен, если количество итераций внутреннего цикла будет намного больше 100, но весьма точен для малых циклов. Однако, в то время как методика неточна для большого количества итераций, в целом полезно знать, что итераций много.
Простой контроль загрузки и выгрузки в память поможет оценить общек количество байтов, использованных за итерацию. Есть, конечно, риск завысить эту оценку из-за идентичных указателей, особенно рассматривая множество циклов.
Общее количество использованных кэш-линий измеряется событием BUS_TRANS_BURST.SELF.
Вскоре будет доступна другая статья, с более детальным рассмотрением анализа доступа к данным.
В случаях, где только малая часть данных, переданных по шине, фактически используется в часто исполняемых циклах, есть несколько способов улучшить использование шины и, таким образом, производительность одного потока или нескольких параллельных. Наиболее очевидное решение — разбить данные согласно их фактическому использованию, организовывая их в параллельные массивы или связные списки структур. В общем случае, только некоторое подмножество данных каждой структуры используется многократно, большая же часть используется лишь иногда. В большом приложении полностью реорганизовать формат данных может быть чрезвычайно трудно. В таком случае, часто используемые данные можно скопировать в удобный, упакованный массив структур, содержащий только часто используемые элементы. Это позволит часто исполняемым циклам программы генерировать минимальный трафик по шине при выполнении. Более агрессивная оптимизация включила бы «разворачивание» формата данных по 2, в случае чисел с плавающей запятой двойной точности, или по 4, если все данные – целые (int) или с плавающей запятой одинарной точности (float). Это откроет путь для чрезвычайно эффективного использования набора инструкций Intel Streaming SIMD Extension 3 (SSE3), так как инструкции упаковки данных в этом случае не потребуются. Возможно даже было бы неплохо добавить несколько элементов-пустышек в конце массива, чтобы гарантировать размер массива равный четному множителю 2 или 4.
Может оказаться, что лучше использовать структуры массивов, а не массивы структур, если доминирующим шаблоном доступа является последовательный доступ по массиву списку, поскольку это гарантирует, что все байты кэш-линий будут использованы.
Выгрузка мимо КЭШа
Компиляторы избегают генерировать инструкции потоковой выгрузки мимо КЭШа в случаях, когда количество итераций цикла присваивания данных неизвестно. Например, в простой функции TRIAD, представленной ниже, значение len не известно на момент трансляции.
double TRIAD(int len, double a1, double * a, double *b, double*c, double*d){
int i;
for(i=0; i<len; i++) a[i] = b[i] + a1*d[i];
return;
}
Большинство трансляторов будет использовать обычные инструкции выгрузки или упакованные инструкции выгрузки SSE для массива «a». Это вызовет запрос на монопольное использование кэш-линии, что удваивает полосу пропускания, необходимую для этого массива. Если же массив не требуется немедленно или слишком велик, чтобы поместиться в КЭШе целиком, то трафик можно сократить вдвое. В примере выше, если количество итераций “len” умноженное на 8, больше чем размер КЭШа последнего уровня (LLC), деленный на 3, то первая кэш-линия для массива «a» будет выгружена из КЭШа еще до окончания цикла. Чтобы гарантировать, что компилятор Intel сгенерирует оптимальный код для большого количества итераций, нужно выровнять массивы по 16 байт и затем изменить цикл, добавив две директивы pragma сразу перед ним.
#pragm vector aligned
#pragma vector nontemporal
for(i=0; i<len; i++)
a[i] = b[i] + a1*d[i];
Также очень важна чрезмерная предварительная выборка кэш-линий. Плохо закодированные программные предвыборки могут усилить трафик по шине. Убедитесь, что вы не делаете предвыборку кэш-линий, которые потом не будут использоваться. Интервал предвыборки также должен быть достаточно большим, чтобы фактически загрузить строку в кэш до ее использования. Команды загрузки, которые ссылаются на кэш-линии все еще подгружаемые программной предвыборкой, инкрементируют счетчик события LOAD_HIT_PRE. Таким образом, это весьма просто обнаружить.
В ядре процессоров Intel Core 2 есть 4 аппаратных блока предвыборки. Два для работы с кэшем второго уровня (L2) способом, аналогичным ранее виденным в процессорах Pentium 4. Еще 2 дополнительных аппаратных блока предвыборки, работают с кэшем данных первого уровня (L1): это блок потоковой предвыборки и блок предвыборки, который ищет шаговые шаблоны, связанные с определенными адресами инструкций (IP). Как правило, в системе включены два блока предвыборки для КЭШа L2 и блок предвыборки IP L1D, но не блок потоковой предвыборки L1D. В целях анализа может быть полезно отключить эти блоки. Обычно это можно сделать в настройках параметров BIOS, в подразделе «cpu options» (опции процессора). Искать следует по ключевым словам «prefetch» и «adjency» – обычно эти пункты и надо менять.
Чтобы определить, какие аппаратные блоки предвыборки включены, можно использовать события производительности. Событие L2_LD.SELF.PREFETCH считает кэш-линии загруженные в КЭШ L2, блоком предвыборки L2. Появление события L1D_PREFETCH.REQUESTS говорит о включенных блоках предвыборки КЭШа данных L1.
Чтобы определить число неиспользуемых кэш-линий, запрашиваемых аппаратным блоком предвыборки, запустите программу 2 раза, с включенными и с выключенными блоками предвыборки. Измерьте общее количество кэш-линий, которые переданы с событием BUS_TRANS_BURST.SELF. Если есть существенное различие между этими двумя значениями, используйте VTune Analyzer, чтобы точно определить где это происходит в исходном коде. Частые причины тому:
- вложенные циклы с малым количествами итераций и большими шагами во внешних циклах;
- вложенные циклы с противоположными направлениями движения по данным (внешний цикл идет вперед с большим шагом, внутренний цикл идет назад с маленьким шагом).
Аппаратная предвыборка обычно управляется внутренним циклом, таким образом, в первом случае предварительно загруженные строки будут за пределом адресации внутреннего цикла, и не будут использоваться следующей итерацией внешнего цикла. Во втором случае блок предвыборки может попытаться загрузить уже использованные строки, то есть будет абсолютно бесполезен. Эта ситуация очень распространена в итерационных решателях и в большинстве случаев может быть исправлена простым изменением направления внутреннего цикла и некоторых требуемых указателей. В обоих случаях, вероятно, будет потребляться множество кэш-линий, запрашиваемых инструкциями загрузки и выгрузки. Это можно проверить с помощью события MEM_LOAD_RETIRED.L2_LINE_MISS, считающего только загрузки, и события L2_LD.SELF.DEMAND, считающее и загрузки и выгрузки в кэш-линии, включая также запросы, сделанные блоками предвыборки L1.
Разбиение данных на блоки — стандартное решение при недостатке пропускной способности, оно обычно предлагается без какого-либо намека на то, как же его фактически реализовать. Легче сказать, чем сделать. Однако, есть некоторая зависимость между декомпозицией данных и разбиением на блоки, и этим можно воспользоваться в некоторых случаях. Декомпозицию данных можно выполнить таким образом, чтобы получилось два уровня иерархии. Внешний уровень предполагает разбиение «один набор данных на ядро», и в тоже время на один процесс или поток, в зависимости от применяемой декомпозиции процесса счета, openmp это, явная организация поточной обработки или MPI, например. «Набор данных на ядро» можно делить дальше, согласно той же стратегии, подразделяя на “виртуальных узлы”, чей размер определяется размером КЭШа последнего уровня. Эту стратегию следует рассматривать на ранних этапах проектирования алгоритма, поскольку она может значительно увеличить возможности масштабирования.
Чрезмерная загруженность дисковой подсистемы
Чрезмерная загруженность совместно используемого диска для программы означает, что время, проводимое программой в ожидании доступа к дисковой подсистеме, с числом используемых ядер начинает преобладать во времени исполнения самого приложения. Это легко заметить в режиме просмотра модулей в VTune Performance Analyzer, просто сравнивая, какая часть времени исполнения проходит в дисковом драйвере с увеличением числа ядер. Для хорошо масштабирующегося приложения (фиксированный или линейно увеличивающийся объем работы) эта часть должна быть постоянной. Конечно, на это стоит обращать внимание, только если (возросшее) время доступа к диску существенно.
Вариации в поведении означают, что несколько компонент мешают друг другу при доступе к диску. Это может случиться, например, из-за различных операций, вызывающих ошибочные движения дисковых головок, что мешает последовательному доступу, являющемуся самым эффективным.
В случаях, где доступ к диску не фиксирован, почти всегда лучше организовывать его очередность во времени, оставляя остальные ядра занятыми другими делами. Таким образом, разбросав фазы доступа к диску для отдельных потоков или процессов можно избежать чрезмерную загруженность дисковой подсистемы.
