Распараллеливание решения задач с использованием раскраски графа | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 6 марта, печатный экземпляр отправим 10 марта.

Опубликовать статью в журнале

Авторы: , ,

Рубрика: Информационные технологии

Опубликовано в Молодой учёный №5 (347) январь 2021 г.

Дата публикации: 31.01.2021

Статья просмотрена: 10 раз

Библиографическое описание:

Гильфанов, Л. Л. Распараллеливание решения задач с использованием раскраски графа / Л. Л. Гильфанов, С. В. Мигранов, А. А. Бикбов. — Текст : непосредственный // Молодой ученый. — 2021. — № 5 (347). — С. 4-6. — URL: https://moluch.ru/archive/347/78208/ (дата обращения: 25.02.2021).



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

Литература:

  1. M.Naumov, P.Castonguay, J. Cohen. Parallel Graph Coloring with Applications to the incomplete-LU factorization on the GPU. NVIDIA Research Technical Report — 2015.
  2. cuSPARSE: [Электронный ресурс]. Режим доступа: https://docs.nvidia.com/cuda/cusparse.
  3. cuSOLVER: [Электронный ресурс]. Режим доступа: https://docs.nvidia.com/cuda/cusolver.
  4. Introduction to Parallel Computing: [Электронный ресурс]. Режим доступа: https://computing.llnl.gov/tutorials/parallel_comp.
Основные термины (генерируются автоматически): раскраска графа, GPU, CPU, CUDA, LTS, относительная норма, решение, COO, CSR, время решения.


Ключевые слова

параллельные вычисления, графический процессор, раскраска графа, алгоритм Луби, алгоритм жадной раскраски, неполная LU-факторизация
Задать вопрос