Сборник докладов кемерово 2017 the ministry of education and science of the russian federation federal State Budgetary Educational Institution «Kemerovo State University»


АНАЛИЗ ЭФФЕКТИВНОСТИ ВЕКТОРИЗАЦИИ АЛГОРИТМА УМНОЖЕНИЯ МАТРИЦ



страница4/14
Дата14.08.2018
Размер2.09 Mb.
#44474
ТипСборник
1   2   3   4   5   6   7   8   9   ...   14

АНАЛИЗ ЭФФЕКТИВНОСТИ ВЕКТОРИЗАЦИИ АЛГОРИТМА УМНОЖЕНИЯ МАТРИЦ*
Цель данной работы заключается в выполнении экспериментального анализа эффективности подсистем автоматической векторизации циклов в открытых компиляторах GCC C/C++ и LLVM/Clang и определении классов трудновекторизуемых циклов. В качестве тестового набора циклов использован пакет Extended Test Suite for Vectorizing Compilers [2, 3]. Особое внимание в работе уделено гнезду из трех циклов, в котором выполняются арифметические операции над элементами двумерных массивов. Такие виды циклов характерны для подпрограмм библиотек линейной алгебры BLAS уровня 3 [1]. В работе рассматривается отображение такого гнезда циклов на архитектуру с короткими векторными регистрами Intel AVX. В качестве представителя целевого гнезда циклов использован алгоритм умножения матриц по определению (DGEMM).

Анализ эффективности подсистем автоматической векторизации циклов в открытых компиляторах. Для оценки эффективности подсистем векторизации в компиляторах GCC C/C++ и LLVM/Clang в работе использовался пакет Extended Test Suite for Vectorizing Compilers (ETSVC), содержащий основные классы циклов, встречающихся в научных приложениях на языке C. Циклы разделены на категории: анализ зависимостей по данным (36 циклов), анализ потока управления и трансформация циклов (52 цикла), распознавание идиоматических конструкций (редукции, рекуррентности и т.п., 27 циклов), полнота понимания языка программирования (23 цикла). Кроме этого, в набор включены 13 контрольных циклов – тривиальные циклы, с векторизацией которых должен справиться каждый векторизующий компилятор.

Циклы оперируют с одномерными и двумерными глобальными массивами, начальные адреса которых выравнены на заданную границу (по умолчанию 16 байт). Одномерные массивы содержат 125·1024/sizeof(TYPE) элементов заданного типа TYPE, а двумерные – 256 элементов по каждому измерению. Глобальные массивы в пакете ETSVC были выравнены на границу 32 байта. Эксперименты выполнены для массивов с элементами типов double, float, int и short int.

Эксперименты проводились на системе, представляющей собой cервер на базе двух процессоров Intel Xeon E5-2620 v4 (архитектура Intel 64, микроархитектура Broadwell, 8 ядер, Hyper-Threading включен, поддержка набора векторных инструкций AVX 2.0), 64 Гбайта оперативной памяти DDR4, операционная система GNU/Linux CentOS 7.3 x86-64 (ядро linux 3.10.0-514.2.2.el7). Анализировалась работа следующих открытых компиляторов: GCC С/C++ 6.3.0, LLVM/Clang 3.9.1.

Для данных типа double были получены следующие результаты. Для GCC С/C++ общее количество векторизованных циклов составляет 79. При этом 34 из них были векторизованы только им. LLVM/Clang векторизовал 51 цикл, 6 из которых смог векторизовать только он. Количество невекторизованных циклов ни одним из компиляторов составило 66. Результаты векторизации для массивов с элементами типов float, int и short int аналогичны double для обоих компиляторов.

Максимальное ускорение, полученное при векторизации компилятором GCC С/C++, составило 4.06, 8.1, 12.01 и 24.48 для типов double, float, int и short int, соответственно. Компилятором LLVM/Clang получены следующие значения максимального ускорения: 5.12 (double), 10.22 (float), 4.55 (int) и 14.57 (short int). Ускорение измерялось как отношение времени выполнения скалярного кода к времени выполнения векторизованного. При этом учитывались только значения ускорения, большие 1.15.

Векторизация алгоритма умножения матриц. Распространенным шаблоном вычислений в библиотеках подпрограмм линейной алгебры (BLAS) является гнездо из трех циклов (i = 0 ... M – 1; j = 0 ... N – 1; k = 0 ... K – 1), в котором выполняются арифметические операции над элементами двумерных массивов. Здесь i, j, k – индуктивные переменные, являющиеся счетчиками циклов. Такое гнездо характеризуется наличием инструкций обработки элементов массивов только в самом внутреннем вложенном цикле и пространством итераций, образующим прямоугольный параллелепипед с размерностями M, N, K.

Типичным представителем гнезда из трех циклов является алгоритм умножения матриц GEMM, выполняющий вычисления вида: A = αBC + βA, где A, B и C – двумерные массивы с размерностями M × N, M × K и K × M, соответственно, а α и β – скалярные коэффициенты. Для алгоритма умножения матриц по определению α = β = 1. Если M = N = K, А, B и C – квадратные матрицы. Частным случаем GEMM является алгоритм DGEMM, оперирующий матрицами, элементами которых являются числа с плавающей запятой двойной точности (тип данных double).

Алгоритм умножения матриц DGEMM можно реализовать в виде двух последовательных версий (см. рис. 1). В первой версии циклы выполняются в порядке ijk, а во второй – в порядке ikj. На рис. 1 порядок следования циклов представлен в виде кортежей из трех индуктивных переменных <i, j, k> и <i, k, j>. Каждая из этих версий может быть векторизована тремя способами: 1) только по самому внутреннему вложенному циклу; 2) по среднему вложенному циклу и 3) по обоим этим циклам. На рис. 1 в кортежах индуктивная переменная векторизуемого цикла помечена символом «→». Шаг S выполнения итераций для векторизуемых циклов равен количеству элементов типа данных double, помещающихся в векторный регистр целевой архитектуры вычислительной системы.

Рисунок 1. Скалярные и векторизованные версии алгоритма умножения матриц DGEMM по определению для двумерных массивов A[M][N], B[M][K] и C[K][N] (S – количество элементов массивов, помещающихся в векторный регистр)
Проведено экспериментальное исследование эффективности предложенных версий алгоритма умножения матриц. Исследование проводилось на двух ВС с общей памятью. Первая ВС укомплектована двумя процессорами Intel Xeon CPU E5-2620 v3 (микроархитектура Haswell), а вторая – двумя процессорами Intel Xeon E5-2620 v4 (микроархитектура Broadwell). Обе ВС имеют 64 Гбайта ОЗУ. Для сокращения влияния сторонних факторов на выполнение тестов в ходе экспериментов учитывались особенности NUMA-архитектуры. Запуск процесса, выполняющего тест, производился на том же самом NUMA-узле, на котором происходило выделение памяти.

Графики зависимости ускорения различных реализаций теста DGEMM от количества строк и столбцов N используемых матриц приведены на рис. 2 для микроархитектуры Haswell и на рис. 3 для Broadwell. В работе [1] представлены реализации приведенных версий алгоритма DGEMM. Наибольшее ускорение получено версией 1 (рис. 2а, 3а), достигнув максимального значения при размере массивов 64 × 64 элемента типа double для микроархитектуры Haswell (S = 4.67), и при 256 × 256 элементов для Broadwell (S = 8.79). В этой версии выполнена векторизация циклов j и k. Отличительной особенностью данной реализации является работа с транспонированной матрицей C. Это позволило уменьшить количество кэш-промахов при выполнении загрузки данных из L1 кэша (8684 кэш-промахов при N = 64, микроархитектура Haswell, и 2115816 кэш-промахов при N = 256, микроархитектура Broadwell), а также сократить число операций загрузки и сохранения данных из/в память (86038/1034 load/store операций при N = 64, микроархитектура Haswell, и 5308466/16396 load/store операций при N = 256, микроархитектура Broadwell). Детальный отчет, содержащий значения счетчиков производительности основных версий алгоритма умножения матриц, приведен в табл. 2 для микроархитектуры Haswell и в табл. 3 для Broadwell.


Таблица 1. Значения счетчиков производительности для микроархитектуры Intel Haswell (N = 64)

Версия DGEMM

Ускорение

L1d -load-misses

LLC-load-misses

mem-loads

mem-stores

cycles

instructions

CPI

branch-instructions

branch-misses

<i, j, k>: 1 (рис. 4а)

4.67

8684

0

86038

1034

93663

240100

0.39

17501

72

<i, j, k>: 2 (рис. 4а)

4.57

9884

0

100368

1034

97662

203236

0.48

8797

71

<i, j, k>: 3 (рис. 4а)

3.16

19336

0

198678

2060

213945

600612

0.36

66653

1095

<i, k, j>: 1 (рис. 4б)

4.65

8730

0

86038

16394

91136

222693

0.41

17501

72

<i, k, j>: 2 (рис. 4б)

3.66

9643

0

135190

65546

144023

549349

0.26

69725

72

<i, k, j>: 3 (рис. 4б)

1.83

9282

0

328728

65547

483118

1169893

0.41

83037

78

Таблица 2. Значения счетчиков производительности для микроархитектуры Intel Broadwell


(N = 256)

Версия DGEMM

Ускорение

L1d -load-misses

LLC-load-misses

mem-
loads

mem-stores

cycles

instructions

CPI

branch-instructions

branch-misses

<i, j, k>: 1 (рис. 3а)

8.79

2115816

0

5308466

16396

9850108

14059112

0.7

1065249

267

<i, j, k>: 2 (рис. 3а)

6.46

2143096

0

6324281

16396

13456733

12682856

1.06

532769

275

<i, j, k>: 3 (рис. 3а)

3.38

4263691

3456

12615758

32780

25802907

37914476

0.68

4210981

16901

<i, k, j>: 1 (рис. 3б)

8.36

2118641

0

5308466

1048588

10355924

13780585

0.75

1065249

270

<i, k, j>: 2 (рис. 3б)

6.77

2098595

1826

8454194

4194316

12790121

33949289

0.38

4260129

520

<i, k, j>: 3 (рис. 3б)

2.72

2178667

185

20987997

4194317

32114941

74548847

0.43

5259559

16657




S

N

а)

S

N

б)

Рисунок 2. Ускорение выполнения теста на микроархитектуре Broadwell:

а) версия : 1 – с непоследовательным доступом к элементам матрицы C; 2 – с использованием команды vbroadcastsd; 3 – ;

б) версия : 1 – c использованием команды vbroadcastsd; 2 – ; 3 – c непоследовательным доступом к элементам матрицы C.




S

N

a)

S

N

б)







Рисунок 3. Ускорение выполнения теста на микроархитектуре Haswell:

а) версия : 1 – с непоследовательным доступом к элементам матрицы C; 2 – с использованием команды vbroadcastsd; 3 – ;

б) версия : 1 – c использованием команды vbroadcastsd; 2 – ; 3 – c непоследовательным доступом к элементам матрицы C.
*Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проекты 16-07-00992, 15-07-00653) и Программы Президиума РАН № 27 «Фундаментальные проблемы решения сложных практических задач с помощью суперкомпьютеров».
Литература


  1. Исходный код разработанных тестов DGEMM [Электронный ресурс]. URL: https://github.com/Ikulagin/vect_bench (дата обращения: 20.07.2017).

  2. Basic Linear Algebra Subprograms Technical (BLAST) Forum Standard // URL: http://www.netlib.org/blas/blast-forum/blas-report.pdf (дата обращения 15.07.2017).

  3. Extended Test Suite for Vectorizing Compilers. [Электронный ресурс]. URL: http://polaris.cs.uiuc.edu/~maleki1/TSVC.tar.gz (дата обращения 13.07.2017).

Попов Д. В., Юго-Западный государственный университет,

Кафедра вычислительной техники, аспирант

Ватутин Э. И., Юго-Западный государственный университет,

Кафедра вычислительной техники, доцент
АНАЛИЗ ЭФФЕКТИВНОСТИ ПРИМЕНЕНИЯ ТЕХНОЛОГИЙ GPGPU ПРИ РЕАЛИЗАЦИИ ЭВРИСТИЧЕСКИХ АЛГОРИТМОВ В ЗАДАЧАХ НА ГРАФАХ*
Задачи дискретной комбинаторной оптимизации делятся на два больших класса: класс сложности P и класс сложности NP. К классу сложности P относят задачи, для решения которых известны алгоритмы, обеспечивающие получение оптимального решения за полиномиальное время, а к классу NP – те задачи, для которых такие алгоритмы не известны или доказана невозможность их построения. На практике для решения задач класса NP и задач большой размерности класса P применяются эвристические методы. Они не гарантируют нахождения решения (и его оптимальности), но имеют гораздо меньшую временную сложность. Среди эвристических методов выделяют итерационные, выполняющие построение ограниченного конечного множества решений с заданным ограничением и выбирающие лучшее из них. Для некоторых методов становится возможным применение технологий параллельных вычислений для получения множества решений, среди которых будет выбрано лучшее.

CUDA и OpenCL представляют собой два разных интерфейса для программирования графических процессоров. OpenCL – это открытый стандарт, который можно использовать для программирования процессоров, графических процессоров и других устройств от разных производителей, а CUDA – только для графических процессоров NVIDIA. Хотя OpenCL является кроссплатформенной технологией, поддержка различных типов устройств может негативно влиять на производительность ввиду необходимости поддержки универсальности и отсутствия специализации под конкретную аппаратную платформу.

В данной работе основное внимание уделено сравнению производительности CUDA и OpenCL при реализации некоторых итерационных эвристических алгоритмов в задачах на графах.

В качестве тестовой задачи была взята широко известная задача поиска кратчайшего пути в графе , где – множество вершин графа, – количество вершин в графе, – множество дуг, а – количество дуг. Тогда плотность графа . Каждой дуге приписана длина . Целевой функцией будет являться длина пути , где – множество образующих путь дуг [1].

Для тестирования были выбраны метод случайного (англ. Random Search, сокр. RS) и взвешенного случайного перебора (англ. Weighted Random Search, сокр. WRS), метод муравьиной колонии (англ. Ant Colony, сокр. AC) [2, 3]. Во время поиска решения методом муравьиной колонии после каждой итерации необходимо выполнять обновление матрицы феромона, которая является общей структурой данных, с которой различным потокам необходимо параллельно осуществлять операции чтения и записи данных с использованием одного из известных механизмов блокировки (мьютексов, критических секций и т.п.), что снижает эффективность параллельной программной реализации. Однако и в данном случае имеется возможность параллельно строить решения, которые находят «муравьи». Для сравнения эффективности перечисленных выше методов были разработаны параллельные версии данных алгоритмов (англ. Parallel, сокр. P в имени метода).

Целью организованного вычислительного эксперимента был анализ среднего времени нахождения решения , где K=1000 – объем выборки тестовых примеров,  время нахождения решения для -ого элемента выборки, при равном количестве запущенных потоков на GPU.

Эксперимент проводился с использованием CPU Intel Core i3-4330 и GPU Nvidia GTX 750 Ti. Поиск решений проводился для графов с количеством вершин 50 и плотностью графа в диапазоне от 0,01 до 1.

Ниже приведены результаты вычислительного эксперимента для количества запускаемых потоков на GPU С=256. При этом, ядра CUDA имели конфигурацию 16 блоков по 16 потоков в каждом.



Рисунок 1. Зависимости времени получения решения от плотности графа для алгоритма муравьиной колонии

На рисунке 1 представлены результаты эксперимента для метода муравьиной колонии. Как можно увидеть, использование технологии CUDA позволяет добиться уменьшения временных затрат для данного до 4,3 раз, а использование OpenCL – до 2,7 раза. При этом, средний выигрыш во времени нахождения решения за счет использования технологии CUDA по сравнению с OpenCL составляет 1,7 раза.



Рисунок 2. Зависимости времени получения решения от плотности графа для взвешенного случайного перебора
Результаты эксперимента для случайного и взвешенного случайного переборов представлены на рисунке 2 и 3. При реализации метода взвешенного случайного перебора CUDA дает выигрыш в среднем в 1,47 раза по сравнению с OpenCL. А для метода случайного перебора выигрыш может достигать 1,85 раза при плотности графа d=0,75, и составляет 1,6 раза в среднем.

Рисунок 3. Зависимости времени получения решения от плотности графа для случайного перебора
При увеличении количества потоков до 1024 среднее отставание OpenCL от CUDA остается на уровне 1,4 раза в среднем для методов случайного и случайного взвешенного перебора, а для метода муравьиной колонии достигает в среднем 3,5 раз. Так, для алгоритма муравьиной колонии при плотности графа d = 0,7 использование GPU с поддержкой технологии OpenCL обеспечивает выигрыш по сравнению с реализацией на CPU примерно в 3,1 раза (против 16,2 для технологии CUDA).

Полученные данные позволяют сделать вывод о том, что использование технологии CUDA дает больший выигрыш в скорости выполнения, по сравнению с технологией OpenCL. Однако, технология CUDA может применяться только на видеокартах производства фирмы Nvidia, в то время как OpenCL является кроссплатформенной технологией.

*Работа была частично поддержана РФФИ (грант № 17-07-00317) и советом по грантам Президента РФ (грант МК-9445.2016.8).


Каталог: upload -> iblock -> 5e9
iblock -> Часы-смартфон
iblock -> Руководство пользователя для телефона Apple iPhone 6
iblock -> Руководство по эксплуатации Методика калибровки Технические характеристики. Минимальный радиус кривизны поверхностей контролируемых изделий, 6мм
iblock -> Технические требования
iblock -> Технологические карты
iblock -> Оптимизация процесса восстановления измененных и уничтоженных маркировочных обозначений на блоках двигателей транспортных средств
iblock -> Инструкция по эксплуатации Температурный gsm извещатель Grinson T7 Благодарим Вас за выбор температурного gsm извещателя Grinson T7
5e9 -> Рабочая программа дисциплины общая и неорганическая химия


Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9   ...   14




База данных защищена авторским правом ©vossta.ru 2022
обратиться к администрации

    Главная страница