Адаптация программного обеспечения для эффективного использования всех доступных процессоров наиболее критична в свете намечающегося многоядерного будущего современной вычислительной техники. Кроме всех прочих препятствий, которые могут быть встречены на этом пути, существуют проблемы, связанные с совместным использованием конечной пропускной способности существующих платформ и процессоров. Правильное использование событий производительности процессора Intel Core2 позволит определить точную причину, останавливающую приложение на пути к полноценному использованию всех доступных в системе ядер.
Прежде чем начать изучение проблем масштабируемости программного обеспечения в среде параллельных вычислений, нам необходимо определиться со значением самого термина. Идеальная масштабируемость означает, что полное время выполнения задачи будет линейно уменьшаться с увеличением количества ядер, используемых приложением. Однако в соответствии с законом Амдаля для параллельного исполнения алгоритма, полное время выполнения программы может быть сокращено только на отрезке оптимизированного соответствующим образом кода. Таким образом, первый пункт в нашем поиске заключается в определении достигнутой степени параллелизма алгоритмов.
События производительности процессора на основе микроархитектуры Intel Core2 предоставляют нам удобные метрики для этих целей. Каждое ядро имеет Блок Мониторинга Производительности (Performance Monitoring Unit или PMU), а событие CPU_CLK_UNHALTED.CORE позволяет определить число рабочих циклов на каждом ядре. Если для сбора информации используется VTune™ Performance Analyzer, то это число суммируется для всех ядер, исполнявших интересующий нас процесс. То есть это число есть количество эффективных циклов потраченных на исполнение приложения. Назовем это число «effective_cycles».
Полезной особенностью PMU является возможность сравнивать на каждом цикле значение события с некоторым заданным числом (cmask) и определять, является ли оно большим или равным (inv=0) или же оно меньше этого числа (inv=1). Если такое условие задано, PMU будет считать циклы только в случае его соблюдения. Однако, это возможно только для счетчиков общего назначения. Фиксированные счетчики, например, для событий CPU_CLK_UNHALTED.CORE, INST_RETIRED.ANY и CPU_CLK_UNHALTED.REF, не могут подвергаться этой операции. Если значение события CPU_CLK_UNHALTED.CORE_P (обобщенная версия счетчика рабочих циклов) сравнивать с числом 2 с условием «менее чем» (inv=1), то счетчик будет считать все циклы. Если это число просуммировать для всех процессов и поделить на количество ядер в системе, мы получим полное время исполнения процесса. Назовем это число «total_cycles».
Для обеспечения корректности полученных значений необходимо, что бы функция Speed Stepping была отключена в BIOS и ОС, иначе незагруженные ядра могут работать на пониженной частоте, что исказит полученное значение полного времени. Отношение effective_cycles/total_cycles будет равняться числу использовавшихся ядер для отлично масштабируемого кода, и равняться 1 для абсолютно последовательного кода. Причем результат не зависит от того, какая часть из всех ядер системы была задействована во время исполнения. Однако ценность этой техники может быть нивелирована, если в коде встречаются пожирающие процессорное время циклы активного ожидания, так что циклы ожидания должны быть реализованы корректно. Для более детального анализа рекомендуется использовать Intel Thread Profiler.
Отклонения от идеальной масштабируемости могут быть обусловлены особенностями структуры кода и синхронизационной логики, но также они могут быть вызваны высокой конкуренцией за общие ресурсы системы. Целью данной статьи как раз и является системный поиск подобных проблем и их решение.
Первым делом необходимо определить список ресурсов, к которым возможна высокая конкуренция при параллельных вычислениях. Сюда относятся:
Последний компонент списка имеет несколько иное влияние на производительность, чем все остальные, так как синхронизация потоков (threads) и процессов зависит от блокируемого доступа к линиям КЭШа. Различие это наиболее очевидно с той точки зрения, что более быстрый / более объемный кэш не всегда способен обойти влияние падения масштабируемости, как в случае с другими элементами этого списка.
Для этих ограничений есть два основных сценария масштабирования приложения, которые будут рассмотрены ниже, разбиение фиксированного объема работы между ядрами и линейное увеличение количества работы, выполняемой всеми ядрами. Эти два сценария имеют несколько разный смысл, если говорить о проблемах масштабируемости, и, следовательно, различаются по искомым признакам.
Чтобы понять какой вклад в падение производительности вносит трафик по шине, необходимо определить, какой, собственно, трафик проходит по шине во время выполнения программы (суммарный и по отдельным компонентам) и какова пиковая пропускная способность платформы используемой при анализе. Пиковая пропускная способность платформы зависит от большого числа сторонних факторов. Это и конфигурация аппаратных блоков предвыборки данных (hardware prefetchers), и количество, тип и расположение в слотах планок оперативной памяти, и частота системной шины, частота процессора, и условия, позволяющие достигнуть когерентности КЭШей. Поэтому ни одна метрика не может считаться определяющей пропускную способность платформы на основе Intel Core 2. Единственный приемлемый метод определить ее – провести синтетический тест пропускной способности. Одиночный длительный цикл алгоритма TRIAD похоже наилучшим образом подходит для этих целей. Так как предел пропускной способности для многоядерного расчета скорее всего будет отличен от одноядерного, вышеозначенный тест должен поддерживать параллельный счет либо за счет потоков, либо за счет разбиения на отдельные процессы.
Предел пропускной способности системы влияет на производительность несколько иначе, чем большинство замедляющих факторов. Влияние большинства растет линейно с ростом их определяющей метрики, как в случае кэш-промахов на последнем уровне КЭШа, где влияние на производительность определяется как соответствующее количество событий ожидания. В этом же случае производительность падает, как бы натыкаясь на барьер, который не заметен до тех пор, пока приложение не исчерпает все ресурсы платформы. То есть зависимость производительности от использования пропускной способности системы скорее ступенчатая, чем линейная, как в случае с другими событиями. Так, например, время доступа к памяти нелинейно возрастает, так как достигнут предел пропускной способности. Пронаблюдать за этим эффектом можно замеряя задержку доступа к шине при увеличении количество одновременно рассчитываемых триад. Задержка доступа к шине может быть измерена событиями производительности в счетном режиме (в противоположность сэмплированию) как отношение:
В большинстве случаев компонент ifetch (instruction fetch, выборка инструкции) маловажен, особенно в ситуации с пиковой пропускной способностью, а, следовательно, может быть проигнорирован.
Существует множество источников, вносящих свой вклад в трафик по системной шине. События производительности процессоров Intel Core 2 позволяют использовать множество методик для определения как полной, так и индивидуальной загрузки шины этими компонентами. Насыщенность системной шины определить очень просто. Она может быть представлена как часть циклов шины использовавшихся для передачи данных:
Или напрямую, как количество байт переданных по шине в составе кэш-линий:
Удобной метрикой в этом случае является просто количество кэш-линий на цикл, так как аппетит N параллельных версий данного приложения / потока составит N раз от этого значения. Так что если предел платформы определен в этих значениях, наиболее вероятная загруженность шины при параллельном счете может быть легко определена во время анализа единичного потока.
События BUS_TRANS_* можно использовать иерархически, чтобы вычленить компоненты, использующие шину. Их краткое описание представлено в нижеследующей таблице, а также они очень подробно разобраны в онлайн справке VTune Performance Analyzer.
Существует множество стандартных способов сократить трафик по шине, которые могут быть применены в случае достижения предела платформы. Сюда можно отнести следующие методы:
Вышесказанное ни в коем случае не претендует на роль исчерпывающего списка возможных вариантов, это скорее список самых очевидных. Любой, кто на самом деле пытался, скажет, что последнее вообще проще сказать, чем сделать.
Извиняюсь за многобукав и некоторую сумбурность, но материал действительно несколько суховат. Перевод делал еще в прошлом году, так что извиняюсь за некоторую потерю актуальности.
Продолжение статьи: часть 2, часть 3, часть 4
Что есть масштабируемость?
Прежде чем начать изучение проблем масштабируемости программного обеспечения в среде параллельных вычислений, нам необходимо определиться со значением самого термина. Идеальная масштабируемость означает, что полное время выполнения задачи будет линейно уменьшаться с увеличением количества ядер, используемых приложением. Однако в соответствии с законом Амдаля для параллельного исполнения алгоритма, полное время выполнения программы может быть сокращено только на отрезке оптимизированного соответствующим образом кода. Таким образом, первый пункт в нашем поиске заключается в определении достигнутой степени параллелизма алгоритмов.
События производительности процессора на основе микроархитектуры Intel Core2 предоставляют нам удобные метрики для этих целей. Каждое ядро имеет Блок Мониторинга Производительности (Performance Monitoring Unit или PMU), а событие CPU_CLK_UNHALTED.CORE позволяет определить число рабочих циклов на каждом ядре. Если для сбора информации используется VTune™ Performance Analyzer, то это число суммируется для всех ядер, исполнявших интересующий нас процесс. То есть это число есть количество эффективных циклов потраченных на исполнение приложения. Назовем это число «effective_cycles».
Полезной особенностью PMU является возможность сравнивать на каждом цикле значение события с некоторым заданным числом (cmask) и определять, является ли оно большим или равным (inv=0) или же оно меньше этого числа (inv=1). Если такое условие задано, PMU будет считать циклы только в случае его соблюдения. Однако, это возможно только для счетчиков общего назначения. Фиксированные счетчики, например, для событий CPU_CLK_UNHALTED.CORE, INST_RETIRED.ANY и CPU_CLK_UNHALTED.REF, не могут подвергаться этой операции. Если значение события CPU_CLK_UNHALTED.CORE_P (обобщенная версия счетчика рабочих циклов) сравнивать с числом 2 с условием «менее чем» (inv=1), то счетчик будет считать все циклы. Если это число просуммировать для всех процессов и поделить на количество ядер в системе, мы получим полное время исполнения процесса. Назовем это число «total_cycles».
Для обеспечения корректности полученных значений необходимо, что бы функция Speed Stepping была отключена в BIOS и ОС, иначе незагруженные ядра могут работать на пониженной частоте, что исказит полученное значение полного времени. Отношение effective_cycles/total_cycles будет равняться числу использовавшихся ядер для отлично масштабируемого кода, и равняться 1 для абсолютно последовательного кода. Причем результат не зависит от того, какая часть из всех ядер системы была задействована во время исполнения. Однако ценность этой техники может быть нивелирована, если в коде встречаются пожирающие процессорное время циклы активного ожидания, так что циклы ожидания должны быть реализованы корректно. Для более детального анализа рекомендуется использовать Intel Thread Profiler.
Отклонения от идеальной масштабируемости могут быть обусловлены особенностями структуры кода и синхронизационной логики, но также они могут быть вызваны высокой конкуренцией за общие ресурсы системы. Целью данной статьи как раз и является системный поиск подобных проблем и их решение.
Ограниченность ресурсов
Первым делом необходимо определить список ресурсов, к которым возможна высокая конкуренция при параллельных вычислениях. Сюда относятся:
- Пропускная способность системы
- Пропускная способность памяти
- Пропускная способность взаимодействия между сокетами
- Загруженность дисковой подсистемы
- Объем общего КЭШа
- Объем буфера трансляции адресов данных (DTLB)
- Индивидуальный доступ к линиям КЭШа
- Общие элементы в линии
- Общие линии без общих элементов (ложное совместное использование)
Последний компонент списка имеет несколько иное влияние на производительность, чем все остальные, так как синхронизация потоков (threads) и процессов зависит от блокируемого доступа к линиям КЭШа. Различие это наиболее очевидно с той точки зрения, что более быстрый / более объемный кэш не всегда способен обойти влияние падения масштабируемости, как в случае с другими элементами этого списка.
Для этих ограничений есть два основных сценария масштабирования приложения, которые будут рассмотрены ниже, разбиение фиксированного объема работы между ядрами и линейное увеличение количества работы, выполняемой всеми ядрами. Эти два сценария имеют несколько разный смысл, если говорить о проблемах масштабируемости, и, следовательно, различаются по искомым признакам.
Пропускная способность
Чтобы понять какой вклад в падение производительности вносит трафик по шине, необходимо определить, какой, собственно, трафик проходит по шине во время выполнения программы (суммарный и по отдельным компонентам) и какова пиковая пропускная способность платформы используемой при анализе. Пиковая пропускная способность платформы зависит от большого числа сторонних факторов. Это и конфигурация аппаратных блоков предвыборки данных (hardware prefetchers), и количество, тип и расположение в слотах планок оперативной памяти, и частота системной шины, частота процессора, и условия, позволяющие достигнуть когерентности КЭШей. Поэтому ни одна метрика не может считаться определяющей пропускную способность платформы на основе Intel Core 2. Единственный приемлемый метод определить ее – провести синтетический тест пропускной способности. Одиночный длительный цикл алгоритма TRIAD похоже наилучшим образом подходит для этих целей. Так как предел пропускной способности для многоядерного расчета скорее всего будет отличен от одноядерного, вышеозначенный тест должен поддерживать параллельный счет либо за счет потоков, либо за счет разбиения на отдельные процессы.
Предел пропускной способности системы влияет на производительность несколько иначе, чем большинство замедляющих факторов. Влияние большинства растет линейно с ростом их определяющей метрики, как в случае кэш-промахов на последнем уровне КЭШа, где влияние на производительность определяется как соответствующее количество событий ожидания. В этом же случае производительность падает, как бы натыкаясь на барьер, который не заметен до тех пор, пока приложение не исчерпает все ресурсы платформы. То есть зависимость производительности от использования пропускной способности системы скорее ступенчатая, чем линейная, как в случае с другими событиями. Так, например, время доступа к памяти нелинейно возрастает, так как достигнут предел пропускной способности. Пронаблюдать за этим эффектом можно замеряя задержку доступа к шине при увеличении количество одновременно рассчитываемых триад. Задержка доступа к шине может быть измерена событиями производительности в счетном режиме (в противоположность сэмплированию) как отношение:
Bus Latency = BUS_REQUEST_OUSTANDING.SELF/(BUS_TRANS_BRD.SELF - BUS_TRANS_IFETCH.SELF)В большинстве случаев компонент ifetch (instruction fetch, выборка инструкции) маловажен, особенно в ситуации с пиковой пропускной способностью, а, следовательно, может быть проигнорирован.
Существует множество источников, вносящих свой вклад в трафик по системной шине. События производительности процессоров Intel Core 2 позволяют использовать множество методик для определения как полной, так и индивидуальной загрузки шины этими компонентами. Насыщенность системной шины определить очень просто. Она может быть представлена как часть циклов шины использовавшихся для передачи данных:
BUS_DRDY_CLOCKS.ALL_AGENTS/CPU_CLK_UNHALTED.BUSИли напрямую, как количество байт переданных по шине в составе кэш-линий:
Cacheline_Bandwidth (байт/с) ~ 64*BUS_TRANS_BURST.ALL_AGENTS*core_freq / CPU_CLK_UNHALTED.COREУдобной метрикой в этом случае является просто количество кэш-линий на цикл, так как аппетит N параллельных версий данного приложения / потока составит N раз от этого значения. Так что если предел платформы определен в этих значениях, наиболее вероятная загруженность шины при параллельном счете может быть легко определена во время анализа единичного потока.
События BUS_TRANS_* можно использовать иерархически, чтобы вычленить компоненты, использующие шину. Их краткое описание представлено в нижеследующей таблице, а также они очень подробно разобраны в онлайн справке VTune Performance Analyzer.
| Событие | Описание |
| BUS_TRANS_ANY | Все транзакции по шине: Mem, IO, Def, Partial |
| BUS_TRANS_MEM | Все кэш-линии, частичные и недействительные |
| BUS_TRANS_BURST | Все кэш-линии: Brd, RFO, WB, Совмещеная Запись |
| BUS_TRANS_BRD | Все чтения кэш-линий: Data, Ifetch |
| BUS_TRANS_IFETCH | Все кэш-линии инструкций |
| BUS_TRANS_RFO | Всего кэш-линий при запросе на монопольное использование |
| BUS_TRANS_WRB | Все записи кэш-линий (модифицированные кэш-линии) |
Существует множество стандартных способов сократить трафик по шине, которые могут быть применены в случае достижения предела платформы. Сюда можно отнести следующие методы:
- Использовать все байты всех кэш-линий, пока они пребывают в КЭШе
- Необходимо расположить элементы структур в порядке убывания их размера, чтобы избежать выравнивания их компилятором
- Определять структуры по фактическому использованию, а не в угоду объектной ориентации или тематической связности
- Пересекать ведущие размерности массивов следует в самом внутреннем из вложенных циклов
- По возможности укладывать компоненты структур в кэш-линию
- Помещать рядом совместно используемые компоненты структур
- Использовать инструкции потоковой выгрузки мимо КЭШа для больших циклов присваивания
- Не делать предвыборку неиспользуемых кэш-линий
- По возможности необходимо совмещать циклы, упирающиеся в пропускную способность, с циклами, упирающимися в производительность процессора
Обычно этого легко достичь, если количество итераций у циклов равно, но в принципе осуществимо и при разном количестве итераций - Старайтесь разбивать данные блоками, чтобы максимально их использовать, пока они в КЭШе.
Вышесказанное ни в коем случае не претендует на роль исчерпывающего списка возможных вариантов, это скорее список самых очевидных. Любой, кто на самом деле пытался, скажет, что последнее вообще проще сказать, чем сделать.
Извиняюсь за многобукав и некоторую сумбурность, но материал действительно несколько суховат. Перевод делал еще в прошлом году, так что извиняюсь за некоторую потерю актуальности.
Продолжение статьи: часть 2, часть 3, часть 4
