В данной статье авторы рассматривают переупорядочивание матрицы на основе раскраски графа для обеспечения ускорения алгоритма неполной LU-факторизации на GPU.
Ключевые слова: раскраска графа, параллельные вычисления, графический процессор, алгоритм Луби, алгоритм жадной раскраски, неполная LU-факторизация.
В настоящее время стали очень распространены параллельные компьютеры или электронно-вычислительные машины. Это связано с тем, что экономически намного выгоднее делать много ядер с низкой частотой, чем одно ядро с большой частотой. В связи с этим фактом возникло новое направление — параллельные вычисления. Они применяются в таких областях как data mining, графика, медицинская диагностика, физическое и финансовое моделирование. Все эти задачи объединяет одна общая деталь — огромный объём обрабатываемых данных. Эта деталь очень часто позволяет распараллелить обработку этих данных.
Существует множество различных способов получения параллельного алгоритма решения задачи (распараллеливание имеющегося последовательного алгоритма или разработка нового параллельного алгоритма). Возможно, для осуществления распараллеливания алгоритм решения задачи придется заменить или модифицировать (например, устранить некоторые зависимости между операциями). Одним из методов, который позволяет извлечь из задачи большего параллелизма является метод раскраски графа.
Представим задачу следующим образом: объекты — некие вычисления, между которыми надо разделить вычислительные ресурсы, способные работать параллельно друг другу. Какие-то вычисления могут выполняться в параллели друг другу, какие-то — нет. Соответственно, вершинная раскраска графа несовместимости вычислений и представляет собой искомое распределение.
Основная цель раскраски графа — назначить цвет каждому узлу в графе так, чтобы никакие два соседа не имели одинакового цвета и в то же время использовать как можно меньше цветов.
Применим инструмент раскраски графа для выявления дополнительного параллелизма в одном из самых популярных предобуславливателей — неполной LU-факторизации. Проведем эксперименты на следующих матрицах:
Таблица 1
Матрицы
|
№ |
Матрица |
n |
nnz |
|
1 |
ASIC_320ks |
321 671 |
1 316 085 |
|
2 |
FEM_30_thermal2 |
147 900 |
3 489 300 |
|
3 |
cage13 |
445 315 |
7 479 343 |
|
4 |
thermomech_dK |
204 316 |
2 846 228 |
|
5 |
atmosmodd |
1 270 432 |
8 814 880 |
где n — размерность матрицы, nnz — число ненулевых элементов. Матрицы поддаются в формате COO.
Пусть критерием остановки итерационного метода будет: максимальное число итераций больше, чем 2000 или относительная норма меньше, чем 1Е-07. Эксперименты выполнены на CUDA Toolkit 9.1 на Ubuntu 16.04 LTS, с Intel Core i5–4670 3.40 GHz CPU и Nvidia K40c GPU. Рассмотрим случай, когда предобуславливатель хранится в формате CSR.
Таблица 2
Результаты без применения раскраски графа
|
№ |
общее |
решение |
отн. норма |
# ит. |
# уровней |
решение (для #ит. = 1) |
|
1 |
0.18170 |
0.04138 |
6.33E-08 |
6.0 |
- |
0.00690 |
|
2 |
0.80449 |
0.50489 |
5.25E-08 |
4.0 |
- |
0.12622 |
|
3 |
0.07317 |
0.04262 |
2.52E-08 |
2.5 |
- |
0.01705 |
|
4 |
41.08228 |
41.0313 |
1.88E-04 |
2000.0 |
- |
0.02052 |
|
5 |
3.29116 |
3.26208 |
4.26E-08 |
76.0 |
- |
0.04292 |
Таблица 3
Результаты с применением раскраски графа
|
№ |
общее |
решение |
отн. норма |
# ит. |
# уровней |
решение (для #ит. = 1) |
# цветов |
ускорение |
|
1 |
0.1295 |
0.05690 |
9.35E-08 |
8.0 |
- |
0.00711 |
48 |
0.96965 |
|
2 |
0.0991 |
0.08110 |
7.21E-08 |
10.0 |
- |
0.00811 |
64 |
15.56381 |
|
3 |
0.1029 |
0.06744 |
5.51E-08 |
3.0 |
- |
0.02248 |
64 |
0.75836 |
|
4 |
17.21 |
17.19847 |
1.43E-04 |
2000.0 |
- |
0.00860 |
48 |
2.38575 |
|
5 |
2.69 |
2.66979 |
9.18E-08 |
105.5 |
- |
0.02531 |
46 |
1.69612 |
Мы получили среднее ускорение = 4.27474.
В таблицах 2–3 и далее: общее время работы программы (общее), время решения всех итераций (решение), количество итераций, необходимых для сходимости (# ит.), относительная норма (отн. норма), число уровней (# уровней), время решения одной итерации (решение (для #ит. = 1)), количество цветов (# цветов), ускорение версии программы с применением раскраски графа относительно версии без раскраски (ускорение).
Для проверки корректности полученных в ходе экспериментов результатов, сравним наши полученные данные с данными из статьи [1]. Эксперименты в статье выполнены на CUDA Toolkit 7.0 на Ubuntu 14.04 LTS, с Intel 6-core i7–3930K 3.20 GHz CPU и Nvidia K40c GPU.
Таблица 4
Результаты без применения раскраски графа
|
№ |
общее |
решение |
отн. норма |
# ит. |
# уровней |
решение (для #ит. = 1) |
|
1 |
- |
0.16 |
6.33E-08 |
6.0 |
- |
0.02667 |
|
2 |
- |
0.74 |
5.25E-08 |
4.0 |
- |
0.18500 |
|
3 |
- |
0.22 |
2.52E-08 |
2.5 |
- |
0.08800 |
|
4 |
- |
42.30 |
1.96E-04 |
2000.0 |
- |
0.02115 |
|
5 |
- |
3.06 |
9.62E-08 |
75.0 |
- |
0.04080 |
Таблица 5
Результаты с применением раскраски графа
|
№ |
общ. |
реш. |
отн. норма |
# ит. |
# уровней |
решение (для #ит. = 1) |
# цветов |
ускорение |
|
1 |
- |
0.18 |
9.09E-08 |
8.0 |
- |
0.02250 |
48 |
1.18519 |
|
2 |
- |
0.19 |
7.21E-08 |
10.0 |
- |
0.01900 |
64 |
9.73684 |
|
3 |
- |
0.24 |
5.51E-08 |
3.0 |
- |
0.08000 |
64 |
1.10000 |
|
4 |
- |
14.92 |
1.41E-04 |
2000.0 |
- |
0.00746 |
48 |
2.83512 |
|
5 |
- |
2.57 |
8.64E-08 |
105.0 |
- |
0.02448 |
46 |
1.66693 |
Среднее ускорение = 3.30481. Видно, что мы получили такие же относительную норму и число итераций, то есть со сходимостью все в порядке. А вот по времени есть расхождения, так как эксперименты все же проводились не на совсем одинаковых вычислительных устройствах. В целом, мы повторили результаты, а среднее ускорение получилось даже лучше.
Литература:
- M.Naumov, P.Castonguay, J. Cohen. Parallel Graph Coloring with Applications to the incomplete-LU factorization on the GPU. NVIDIA Research Technical Report — 2015.
- cuSPARSE: [Электронный ресурс]. Режим доступа: https://docs.nvidia.com/cuda/cusparse.
- cuSOLVER: [Электронный ресурс]. Режим доступа: https://docs.nvidia.com/cuda/cusolver.
- Introduction to Parallel Computing: [Электронный ресурс]. Режим доступа: https://computing.llnl.gov/tutorials/parallel_comp.
