Продолжение статьи: часть 1, часть 2, часть 3
Вероятно, наиболее простым примером, может послужить алгоритм параллельного суммирования значений элементов массива. В таком случае каждый поток суммировал бы свой набор элементов. Этот алгоритм мог бы выглядеть следующим образом:
Если указатель «sum» объявлен как простой массив с индексом, являющимся идентификатором потока, то мы можем столкнуться с конкуренцией параллельных потоков за кэш-линию, содержащую элемент массива. Вообще говоря, компилятор мог бы суммировать значения массива в регистре-аккумуляторе (снимая необходимость в переменной «sum»), и, таким образом, избежать проблемы, что, собственно, и делает компилятор Intel.
Однако не все компиляторы столь сообразительны. Если функция объявлена так:
то компилятору запрещено перенести «sum» в регистровую память, что гарантирует сражение за КЭШ-линию. Обозначенные выше события польются рекой.
В качестве второго примера возьмем очень простой трижды вложенный цикл перестановок в массиве, превосходно подходящий для нашего обсуждения.
Взглянув на код, становится очевидно, что индексные массивы i, j, k и массив tmp вероятнее всего окажутся в одной кэш-линии, за которую потоки и будут бороться на каждой итерации каждого цикла. Они специально объявлены как volatile, чтобы запретить компилятору разместить их в регистрах, что в принципе допускается стандартом языка. Стандарт языка вообще много чего позволяет делать с доступом к данным в целях оптимизации. Если не применить к ним что-либо вроде volatile, компилятор сам не станет задумываться о том, что эта функция должна выполняться несколькими потоками.
Текущий компилятор Intel (10.0) для архитектуры Intel 64 создаст исполняемый файл полностью свободный от ложного совместного использования кэш-линии при оптимизации O3, если объявление volatile будет удалено из вышеупомянутой функции. Ни один из локальных циклов, ни одна из временных переменных никогда не будет выгружена в память, существуя только в регистрах. Появление неблокируемого ложного совместного использования линии вообще очень сильно зависит от компилятора. Вариаций на эту тему становится неисчислимо много, когда программист начинает использовать оптимизации вроде inline-функций, разбивку функций на части и так далее.
Допустим, мы собрали данные при помощи VTune Analyzer, далее смотрим зависимости между количествами события. Количество EXT_SNOOP.ALL_AGENTS_HITM приблизительно равно BUS_HITM_DRV. Обратим внимание на то, как ведет себя приложение от запуска к запуску, что происходит с событиями. MEM_LOAD_RETIRED.L2_MISS намного больше чем MEM_LOAD_RETIRED.L2_LINE_MISS. Количество MEM_LOAD_RETIRED.L2_LINE_MISS намного меньше, чем количество кэш-линий, переданных на шине, судя по BUS_TRANS_BURST.SELF. Наибольший вклад вносят запросы на монопольное использование (RFO), измеряемые событием BUS_TRANS_RFO.SELF. Оцениваем вклад RFO в трафик по шине, измеренный BUS_TRANS_BURST.SELF.
Остаток оценивается в общих чтениях, измеряемых BUS_TRANS_BRD.SELF. Событие L2_LD.SELF полезно для выяснения состояния кэш-линии, особенно если влияние аппаратных блоков предвыборки очень сильно.
Следовательно, для того, чтобы определить, имеет ли место конкуренция за кэш-линии, разумно было бы собрать данные при однопоточном счете, чтобы определить базовые значения, а уже потом – при многопоточном. Чтобы идентифицировать ложное совместное использование линии, вероятно, лучше всего смотреть на MEM_LOAD_RETIRED.L2_MISS, сравнивая количества и расположение пиков этого события при просмотре исходного кода в VTune Analyzer. Обычно все сразу становится понятно, если при этом также обратить внимание на EXT_SNOOPS.ALL_AGENTS.HITM.
Поиск конфликтов блокировки доступа также довольно прост. Событие L2_LOCK.SELF.E_STATE происходит всякий раз, когда блокировка доступа (кроме инструкции xchg) используются для создания мьютекс-блокировки. Если блокированный элемент была изменен, тогда произойдет также событие L2_LOCK.SELF.M_STATE. Из-за блока предвыборки IP событие MEM_LOAD_RETIRE.L2_LINE_MISS не эффективно для нашего поиска. В таком случае, пики MEM_LOAD_RETIRED.L2_MISS совместно с L2_LD.LOCK.E_STATE при просмотре исходного кода в VTune Analyzer проясняют картину происшествия. EXT_SNOOP.HITM.ALL_AGENTS опять же присутствует в этих случаях.
Конкуренция за блокированную кэш-линию часто обусловлена использованием API синхронизации. Рассмотренный выше примитивный анализ собранных данных вероятно покажет, что приложение тратит произвольную часть времени в цикле ожидания синхронизации. В таком случае необходимо найти, где вызывается этот API, чтобы понять, можно ли изменением кода уменьшить последовательность выполнения, вызванную блокировками переменных. Местоположение этих «бутылочных горлышек» можно быстро определить, используя граф вызовов в VTune Analyzer или Intel Thread Profiler.
В то время как конкуренция за кэш-линии характерна для модели параллелизации с общей памятью, чрезмерное падение масштабируемости также возможно из-за злоупотребления синхронизацией операций в MPI. Синхронная передача сообщений, MPI_Wait, и глобальные операции MPI (MPI_Allreduce например) могут аналогичным образом сказаться на производительности, как и в описанных выше случаях. Intel Trace Analyzer and Collector создан как раз для поиска подобных проблем MPI. Использование этой программы просто необходимо для достижения наилучшего масштабирования MPI в среде больших кластеров на основе процессоров Intel Core 2.
У процессора Intel Core 2 довольно развитая иерархия события производительности, которая очень эффективна при анализе проблем низкой скорости исполнения. Множество причин плохого масштабирования в многоядерной среде могут быть быстро и легко идентифицировано с помощью Intel VTune Performance Analyzer. Для разрешения более сложных проблем поточной синхронизации существует Intel Thread Profiler. Для MPI рекомендуется использовать Intel Trace Analyzer and Collector.
Вероятно, наиболее простым примером, может послужить алгоритм параллельного суммирования значений элементов массива. В таком случае каждый поток суммировал бы свой набор элементов. Этот алгоритм мог бы выглядеть следующим образом:
int sum(int* data, int* sum, int size, int tid)
{
int i;
for(i=0; i < size; i++)
*sum += data[i]*data[i];
return *sum;
}
Если указатель «sum» объявлен как простой массив с индексом, являющимся идентификатором потока, то мы можем столкнуться с конкуренцией параллельных потоков за кэш-линию, содержащую элемент массива. Вообще говоря, компилятор мог бы суммировать значения массива в регистре-аккумуляторе (снимая необходимость в переменной «sum»), и, таким образом, избежать проблемы, что, собственно, и делает компилятор Intel.
Однако не все компиляторы столь сообразительны. Если функция объявлена так:
int sum(int* data, volatile int* sum, int size, int tid)то компилятору запрещено перенести «sum» в регистровую память, что гарантирует сражение за КЭШ-линию. Обозначенные выше события польются рекой.
В качестве второго примера возьмем очень простой трижды вложенный цикл перестановок в массиве, превосходно подходящий для нашего обсуждения.
#define MAXTHR 4
#define ITERS 1000
#define SIZE 1000
int aa[MAXTHR][SIZE];
volatile int i[MAXTHR], j[MAXTHR], k[MAXTHR], n[MAXTHR], tmp[MAXTHR];
int sort(int *a, int size, int tid) //a = aa[tid][0]
{
n[tid] = 0;
for (k[tid]=0; k[tid] < ITERS/2; k[tid]++){
for (i[tid] = 0; i[tid] < size-1; i[tid]++){
for (j[tid] = i[tid]+1; j[tid] < size; j[tid]++){
if (a[i[tid]] > a[j[tid]]){
tmp[tid] = a[i[tid]];
a[i[tid]] = a[j[tid]];
a[j[tid]] = tmp[tid];
n[tid]++;
} } }
for (i[tid] = 0; i[tid] < size-1; i[tid]++){
for (j[tid] = i[tid]+1; j[tid] < size; j[tid]++){
if (a[i[tid]] < a[j[tid]]){
tmp[tid] = a[i[tid]];
a[i[tid]] = a[j[tid]];
a[j[tid]] = tmp[tid];
n[tid]++;
} } }
}
return n[tid];
}
Взглянув на код, становится очевидно, что индексные массивы i, j, k и массив tmp вероятнее всего окажутся в одной кэш-линии, за которую потоки и будут бороться на каждой итерации каждого цикла. Они специально объявлены как volatile, чтобы запретить компилятору разместить их в регистрах, что в принципе допускается стандартом языка. Стандарт языка вообще много чего позволяет делать с доступом к данным в целях оптимизации. Если не применить к ним что-либо вроде volatile, компилятор сам не станет задумываться о том, что эта функция должна выполняться несколькими потоками.
Текущий компилятор Intel (10.0) для архитектуры Intel 64 создаст исполняемый файл полностью свободный от ложного совместного использования кэш-линии при оптимизации O3, если объявление volatile будет удалено из вышеупомянутой функции. Ни один из локальных циклов, ни одна из временных переменных никогда не будет выгружена в память, существуя только в регистрах. Появление неблокируемого ложного совместного использования линии вообще очень сильно зависит от компилятора. Вариаций на эту тему становится неисчислимо много, когда программист начинает использовать оптимизации вроде inline-функций, разбивку функций на части и так далее.
Допустим, мы собрали данные при помощи VTune Analyzer, далее смотрим зависимости между количествами события. Количество EXT_SNOOP.ALL_AGENTS_HITM приблизительно равно BUS_HITM_DRV. Обратим внимание на то, как ведет себя приложение от запуска к запуску, что происходит с событиями. MEM_LOAD_RETIRED.L2_MISS намного больше чем MEM_LOAD_RETIRED.L2_LINE_MISS. Количество MEM_LOAD_RETIRED.L2_LINE_MISS намного меньше, чем количество кэш-линий, переданных на шине, судя по BUS_TRANS_BURST.SELF. Наибольший вклад вносят запросы на монопольное использование (RFO), измеряемые событием BUS_TRANS_RFO.SELF. Оцениваем вклад RFO в трафик по шине, измеренный BUS_TRANS_BURST.SELF.
Остаток оценивается в общих чтениях, измеряемых BUS_TRANS_BRD.SELF. Событие L2_LD.SELF полезно для выяснения состояния кэш-линии, особенно если влияние аппаратных блоков предвыборки очень сильно.
Следовательно, для того, чтобы определить, имеет ли место конкуренция за кэш-линии, разумно было бы собрать данные при однопоточном счете, чтобы определить базовые значения, а уже потом – при многопоточном. Чтобы идентифицировать ложное совместное использование линии, вероятно, лучше всего смотреть на MEM_LOAD_RETIRED.L2_MISS, сравнивая количества и расположение пиков этого события при просмотре исходного кода в VTune Analyzer. Обычно все сразу становится понятно, если при этом также обратить внимание на EXT_SNOOPS.ALL_AGENTS.HITM.
Поиск конфликтов блокировки доступа также довольно прост. Событие L2_LOCK.SELF.E_STATE происходит всякий раз, когда блокировка доступа (кроме инструкции xchg) используются для создания мьютекс-блокировки. Если блокированный элемент была изменен, тогда произойдет также событие L2_LOCK.SELF.M_STATE. Из-за блока предвыборки IP событие MEM_LOAD_RETIRE.L2_LINE_MISS не эффективно для нашего поиска. В таком случае, пики MEM_LOAD_RETIRED.L2_MISS совместно с L2_LD.LOCK.E_STATE при просмотре исходного кода в VTune Analyzer проясняют картину происшествия. EXT_SNOOP.HITM.ALL_AGENTS опять же присутствует в этих случаях.
Конкуренция за блокированную кэш-линию часто обусловлена использованием API синхронизации. Рассмотренный выше примитивный анализ собранных данных вероятно покажет, что приложение тратит произвольную часть времени в цикле ожидания синхронизации. В таком случае необходимо найти, где вызывается этот API, чтобы понять, можно ли изменением кода уменьшить последовательность выполнения, вызванную блокировками переменных. Местоположение этих «бутылочных горлышек» можно быстро определить, используя граф вызовов в VTune Analyzer или Intel Thread Profiler.
В то время как конкуренция за кэш-линии характерна для модели параллелизации с общей памятью, чрезмерное падение масштабируемости также возможно из-за злоупотребления синхронизацией операций в MPI. Синхронная передача сообщений, MPI_Wait, и глобальные операции MPI (MPI_Allreduce например) могут аналогичным образом сказаться на производительности, как и в описанных выше случаях. Intel Trace Analyzer and Collector создан как раз для поиска подобных проблем MPI. Использование этой программы просто необходимо для достижения наилучшего масштабирования MPI в среде больших кластеров на основе процессоров Intel Core 2.
Заключение
У процессора Intel Core 2 довольно развитая иерархия события производительности, которая очень эффективна при анализе проблем низкой скорости исполнения. Множество причин плохого масштабирования в многоядерной среде могут быть быстро и легко идентифицировано с помощью Intel VTune Performance Analyzer. Для разрешения более сложных проблем поточной синхронизации существует Intel Thread Profiler. Для MPI рекомендуется использовать Intel Trace Analyzer and Collector.
