» » Распараллеливание алгоритма Штрассена на Intel® Xeon Phi(TM)

 

Распараллеливание алгоритма Штрассена на Intel® Xeon Phi(TM)

Автор: admin от 21-12-2015, 11:45, посмотрело: 491

Сопроцессоры Intel Xeon Phi(TM) представляют собой PCI Express устройство и имеют x86 архитектуру, обеспечивая высокую пиковую производительности — до 1,2 терафлопс (триллион операций с плавающей запятой в секунду) двойной точности на сопроцессор. Xeon Phi(TM) может обеспечивать одновременную работу до 244 потоков, и это нужно учитывать при программировании для достижения максимальной эффективности.

Недавно мы вместе с компанией Intel проводили небольшое исследование эффективности реализации алгоритма Штрассена для сопроцессора Intel Xeon Phi(TM). Кому интересны тонкости работы с этим устройством и просто любящих параллельное программирование, прошу под кат.

Распараллеливание алгоритма Штрассена на Intel® Xeon Phi(TM)



Общее количество операций стандартного алгоритма умножения квадратных матриц размера n (сложений и умножений):

Распараллеливание алгоритма Штрассена на Intel® Xeon Phi(TM)

Алгоритм Штрассена (1969), который относится к быстрым алгоритмам умножения матриц требует:

Распараллеливание алгоритма Штрассена на Intel® Xeon Phi(TM)

Таким образом, алгоритм Штрассена имеет меньшую асимптотическую сложность и потенциально быстрее на больших размерах матриц. Но рекурсивная природа данного алгоритма представляет определенную сложность для эффективного распараллеливания на современных вычислительных системах и использования данных из памяти.

В данной работе рассматривается комбинированный подход, в котором при достижении порогового значения из алгоритма Штрассена вызывается стандартный алгоритм умножения матриц (в качестве стандартного алгоритма мы использовали Intel MKL DGEMM). Это связано с тем, что при маленьких размерах матриц (десятки или сотни, в зависимости от архитектуры процессора) алгоритм Штрассена начинает проигрывать стандартному алгоритму и по количеству операций, и за счет большего числа кэш-промахов. Теоретические оценки для порогового значения размера матриц для перехода на стандартный алгоритм (без учета кэширования и конвейерной обработки) дает различные оценки — 8 у Хайема и 12 у Хасс-Ледермана, на практике пороговое значение зависит от архитектуры вычислительной системы и должно оцениваться экспериментально. Для нашей системы с Intel Xeon Phi(TM) 7120D наиболее эффективным оказалось значение 1024.

Результаты вычислительных экспериментов сравнивались с функцией DGEMM из библиотеки Intel MKL. Рассматривалось умножение квадратных матриц размера Распараллеливание алгоритма Штрассена на Intel® Xeon Phi(TM), где Распараллеливание алгоритма Штрассена на Intel® Xeon Phi(TM) и Распараллеливание алгоритма Штрассена на Intel® Xeon Phi(TM). Под M здесь понимается пороговое значение размера матриц, после которого вызывается стандартный алгоритм. Умножение двух матриц записывается как Распараллеливание алгоритма Штрассена на Intel® Xeon Phi(TM), где A, B и C матрицы размера Распараллеливание алгоритма Штрассена на Intel® Xeon Phi(TM). Метод Штрассена для умножения матриц основан на рекурсивном делении каждой перемножаемой матрицы на 4 подматрицы и выполнении операций над ними. Требование к размеру матриц (Распараллеливание алгоритма Штрассена на Intel® Xeon Phi(TM) и Распараллеливание алгоритма Штрассена на Intel® Xeon Phi(TM)) необходимо, чтобы была возможность разбить каждую матрицу на 4 подматрицы на требуемую глубину рекурсии.

Метод Штрассена описывается следующей формулой:

Распараллеливание алгоритма Штрассена на Intel® Xeon Phi(TM)


где

Распараллеливание алгоритма Штрассена на Intel® Xeon Phi(TM)


Ниже показано, как можно выделить 4 группы операций, в каждой из них все операции могут быть выполнены параллельно.

Распараллеливание алгоритма Штрассена на Intel® Xeon Phi(TM)


В реализации распараллеливания нет ничего сложного. Использовалось OpenMP и механизм задач (omp task), распределение нагрузки между задачами показано на рисунке. Первые группы операций были совмещены в одну, так получается меньше точек синхронизации, так как это очень дорогая операция.

Распараллеливание алгоритма Штрассена на Intel® Xeon Phi(TM)


Для замера времени использовался стандартный подход с «разогревающим» запуском и усреднением времени нескольких запусков. В качестве таймера используется функция Intel MKL dsecnd.


После реализации распараллеливания мы провели ряд тестов. Тесты проводились в нативном режиме на Intel Xeon Phi(TM) 7120D, 16 Гб.


Чтобы не усложнять статью, все тесты будут проводиться на размере матриц 8192x8192 (данный размер является почти предельным по потреблению памяти для распараллеленного алгоритма Штрассена — около 10GB — и является достаточно большим, чтобы ощутить эффект меньшей асимптотической сложности алгоритма).


































Количество потоков1481660120180240
Штрассен, с114.8929.915.758.853.683.584.228.17
MKL DGEMM, c131.7934.3817.2792.611.902.452.54

На небольшом количестве потоков алгоритм Штрассена оказался быстрее Intel MKL DGEMM. Также было замечено, что на большом количестве потоков наблюдается падение производительности (задача почти не масштабируется больше 60 потоков). Для эффективного использования ресурсов Intel Xeon Phi(TM) в многопоточном приложении, рекомендуют использовать число потоков, кратное NP-1, где NP — количество процессоров в устройстве (в нашем случае 61). Подробнее можно почитать здесь.

Возникла мысль, что помочь дальнейшему масштабированию может использование параллелизма внутри вызываемого из Штрассена DGEMM. Для управления количеством потоков в MKL есть несколько функций: mkl_set_num_threads, mkl_set_num_threads_local, mkl_domain_set_num_threads. При попытке использовать mkl_set_num_threads мы обнаружили, что данная функция не влияет на количество потоков в MKL DGEMM, вызываемой из алгоритма Штрассена (на количество потоков в MKL за пределами Штрассена данная функция влияла). Вложенный параллелизм при этом был включен (OMP_NESTED=true).

Как выяснилось, MKL активно сопротивляется вложенному параллелизму. MKL использует переменную окружения MKL_DYNAMIC, которая по умолчанию равна true. Данная переменная позволяет MKL уменьшать количество потоков, которое задает пользователь, в частности при вызове функций MKL из параллельной области будет принудительно установлено количество потоков, равное 1. Чтобы разрешить параллелизм в MKL DGEMM, мы использовали функцию mkl_set_dynamic(0).





































Общее количество потоковШтрассен, сMKL DGEMM, с
Количество потоков в MKL DGEMM
124
603.683.895.192.61
1203.583.503.821.90
2408.174.233.592.54

Результаты алгоритма Штрассена для 120 потоков при использовании многопоточного MKL DGEMM стали немного лучше, но серьезного выигрыша мы не получили.

Следующим нашим шагом было изучение привязки программных потоков OpenMP к физическим и логическим ядрам (binding). На Xeon Phi для управления привязкой потоков к ядрам служат переменные окружения KMP_AFFINITY и KMP_PLACE_THREADS. Хорошее описание нашли здесь.

Самым важным среди параметров KMP_AFFINITY является type, который управляет очередностью назначения потоков на ядра (см. рис. ниже).

Распараллеливание алгоритма Штрассена на Intel® Xeon Phi(TM)


Были использованы следующие значения KMP_AFFINITY:

KMP_AFFINITY = granularity=fine,balanced




































Общее количество потоковШтрассен, сMKL DGEMM, с
Количество потоков в MKL DGEMM
124
603.674.075.532.64
1203.543.513.951.51
2407.114.333.411.15


KMP_AFFINITY = granularity=fine,compact




































Общее количество потоковШтрассен, сMKL DGEMM, с
Количество потоков в MKL DGEMM
124
609.299.9610.274.58
1206.236.796.042.31
2409.325.214.211.15

По умолчанию, переменная KMP_AFFINITY= granularity=core,balanced. При тестировании выяснилось, что лучшие параметры для умножения матриц KMP_AFFINITY= granularity=fine,balanced, причем на результаты MKL DGEMM данные параметр влияет не так сильно, как на алгоритм Штрассена, где по сравнению с KMP_AFFINITY= granularity=fine,compact наблюдается двукратное сокращение времени работы. Также заметим, что изменение переменной окружения KMP_AFFINITY с его значения по умолчанию (KMP_AFFINITY= granularity=core,balanced) сократило время работы MKL DGEMM с минимальных 1.90 с до 1.15 с (примерно в 1,5 раза). Результаты MKL DGEMM с compact и balanced отличаются предсказуемым образом, например при 120 потоках вариант с compact использует 30 ядер по 4 потока, а balanced — 60 по 2, за счет большего количества ядер и получается почти двукратное ускорение в варианте balanced.

Еще мы попробовали профилировать программу на Xeon Phi, как это сделать можно почитать здесь. Чтобы профилировать только алгоритм умножения мы использовали возможности VTune API.

В итоге мы не смогли догнать MKL DGEMM на максимальном количестве потоков, но немного больше узнали про программирование такого мощного вычислителя, как Intel Xeon Phi(TM).

Источник: Хабрахабр

Категория: Программирование

Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

Добавление комментария

Имя:*
E-Mail:
Комментарий:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера
Введите два слова, показанных на изображении: *