Вероятно, наиболее простым примером, может послужить алгоритм параллельного суммирования значений элементов массива. В таком случае каждый поток суммировал бы свой набор элементов. Этот алгоритм мог бы выглядеть следующим образом:
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.