Анализ и моделирование производительности трафаретных вычислений на мультипроцессоре Константин Калгин Институт Вычислительной Математики и Математической Геофизики лаборатория Синтеза Параллельных Программы

Трафаретные вычисления Stencil computations Явная разностная схема Синхронный клеточный автомат

Типичный график эффективности (размер задачи не изменяется) E p = T 1 / (T p * p) Накладные расходы (коммуникации, сеть) Суперлинейное ускорение «Попадаем» в кэш Слишком малый домен Большие накладные расходы III «Пожелания»

Постановка задачи Проанализировать и построить модель производительности трафаретных вычислений для ccNUMA архитектур в случае, когда домен помещается в кэш ( зона II) T = T seq + T bar + T comm Тестирование : Intel Westmere (2 x 6 ядер ) nks30t, SL_q Intel SandyBridge (2 x 8 ядер ) mvs1p1 Вычислительные схемы 2D: 5- и 9- точечные невзвешенные и взвешенные средние float и double

Общие условия замера времени На каждом ядре запускается счёт это выравнивает частоту ядер ( TurboBoost) Перед замерами времени 0.5 с процессор работает вхолостую это выравнивает частоту (SpeedStep) Время измеряется в тактах rdtsc наиболее точный таймер имеет минимальные накладные расходы В качестве результата берётся среднее по 1000 запускам отсеиваются значения на 50% превосходящие минимум это позволяет минимизировать влияния системных прерываний Компиляция : icpc -O3 -march=native -fno-inline -unroll0

Последовательная реализация A - время вызова процедуры, реализующей итерацию B - время, затрачиваемое на переход с одной строки домена на другую ( двумерная область ) С - время обработки одного узла домена T seq (x,y) = A + By + Cxy ~10ns ~2ns ~0.5-2ns

Барьер Замер времени : последовательная реализация + барьер, без коммуникаций/копирований Типы барьера : OpenMP (#pragma omp barrier) Ожидания на volatile переменных Локальная синхронизация ( не барьер ) + ещё много вариантов ( иерархический, атомарные операции, потоковая запись ) тестируется на студентах в рамках курса « Эфф. прогр. мультипроцессоров » 500 | | | 250 ns

Latency,Westmare, Intel Свой кэш Свой сокет Чужой сокет

Границы (5nbh,a=0,float) private shared private shared y y x 60 | ns 3 | ns 0.8 | ns 60 | ns 0.4 | 1.5 L | 0.8 L2-L3 x xx

Заключение Построенная модель позволяет описывать время исполнения последовательной реализации с точностью 2-3% Традиционно используемый барьер встроенный в OpenMP достаточно медленный и даёт существенный вклад на малых доменах (L1), полученная реализация работает в пять ( L1) и в два ( L2/L3) раз быстрее Построена модель времени межъядерного взаимодействия на границах доменов, выявлены оптимальные способы деления счетной области (shared/private) Дальнейшие планы Расширить модель до MPI версии ( между узлами ) Автоматизировать получение оптимального деления на домены Сравнить производительность с типовыми реализациями OpenMP/MPI