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

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

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

Авторы: , ,

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

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

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

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

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

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



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

Похожие статьи

Занятие «Раскраски графов» факультативного курса «Элементы...

Классической задачей о раскраске графа, с помощью которой хорошо демонстрируется суть проблемы, является задача о раскраске политической карты

Там же можно найти подробно изложенное решение задач. При решении задач могут использоваться и специализированные...

Ускорение расчета динамического напряженно-деформированного...

Для создания переносимых решений, которые можно применять на разных вычислительных архитектурах GPU, CPU, FPGA, MIC, можно воспользоваться

Замер времени выполнения версии алгоритма расчета правых частей уравнений, реализованного на OpenCL, показал, что...

Применение графических процессоров с технологией CUDA...

Рис. 1. График, изображающий прогресс производительности CPU и GPU [3]. Рост производительности перешел на видеокарты, и если в ближайшее время не произойдет глобальных изменений в развитии центральных процессоров, к 2025 году GPU станет в 1000...

Алгоритм Лерча — Гроссмана и его реализация на центральном...

Для решения первого вопроса применяются методы пространственной интерполяции, а второго методы, основанные на теории графов. В данной статье приводится описание применения алгоритма нахождения оптимального карьера Лерча-Гроссмана, основанное на теории графов.

Особенности тестирования программного обеспечения...

Используется автоматный подход к решению задачи. На первом шаге способа тестирования

На втором шаге данного способа тестирования разрабатывается граф причинно-следственных связей.

Каждый узел графа может находиться в состоянии 0 (состояние отсутствует) или 1...

Параллельная реализация алгоритма для описания термоупругих...

Программа написана на языке Си с применением технологии CUDA (Compute Unified Device Architecture) для распараллеливания вычислений, позволяющей использовать

Для анализа результатов счета в контрольных точках по времени решение передается с GPU на CPU, и по...

Девиантное поведение подростков | Статья в журнале...

Автор: Юсупова Кристина Алексеевна. Рубрика: Психология. Опубликовано в Молодой учёный №21 (416) май 2022 г. Статья просмотрена: < 10 раз.

Параллельный вычислительный алгоритм для анализа...

Параллельный вычислительный алгоритм для решения системы уравнений жидкого

Для решения системы уравнений второго порядка (2) разработан численный алгоритм.

–описание событий start и stop для замера времени выполнения программы на GPU, начало замера...

Проблемы вычислений с высокой точностью при использовании...

Функции, скомпилированные для GPU, будут использовать математическую библиотеку NVIDIA CUDA, тогда как для вычислений на CPU будут

В то время как программная реализация NVIDIA CUDA также, как и SSE, использует только наборы инструкций, оперирующие числами с...

Похожие статьи

Занятие «Раскраски графов» факультативного курса «Элементы...

Классической задачей о раскраске графа, с помощью которой хорошо демонстрируется суть проблемы, является задача о раскраске политической карты

Там же можно найти подробно изложенное решение задач. При решении задач могут использоваться и специализированные...

Ускорение расчета динамического напряженно-деформированного...

Для создания переносимых решений, которые можно применять на разных вычислительных архитектурах GPU, CPU, FPGA, MIC, можно воспользоваться

Замер времени выполнения версии алгоритма расчета правых частей уравнений, реализованного на OpenCL, показал, что...

Применение графических процессоров с технологией CUDA...

Рис. 1. График, изображающий прогресс производительности CPU и GPU [3]. Рост производительности перешел на видеокарты, и если в ближайшее время не произойдет глобальных изменений в развитии центральных процессоров, к 2025 году GPU станет в 1000...

Алгоритм Лерча — Гроссмана и его реализация на центральном...

Для решения первого вопроса применяются методы пространственной интерполяции, а второго методы, основанные на теории графов. В данной статье приводится описание применения алгоритма нахождения оптимального карьера Лерча-Гроссмана, основанное на теории графов.

Особенности тестирования программного обеспечения...

Используется автоматный подход к решению задачи. На первом шаге способа тестирования

На втором шаге данного способа тестирования разрабатывается граф причинно-следственных связей.

Каждый узел графа может находиться в состоянии 0 (состояние отсутствует) или 1...

Параллельная реализация алгоритма для описания термоупругих...

Программа написана на языке Си с применением технологии CUDA (Compute Unified Device Architecture) для распараллеливания вычислений, позволяющей использовать

Для анализа результатов счета в контрольных точках по времени решение передается с GPU на CPU, и по...

Девиантное поведение подростков | Статья в журнале...

Автор: Юсупова Кристина Алексеевна. Рубрика: Психология. Опубликовано в Молодой учёный №21 (416) май 2022 г. Статья просмотрена: < 10 раз.

Параллельный вычислительный алгоритм для анализа...

Параллельный вычислительный алгоритм для решения системы уравнений жидкого

Для решения системы уравнений второго порядка (2) разработан численный алгоритм.

–описание событий start и stop для замера времени выполнения программы на GPU, начало замера...

Проблемы вычислений с высокой точностью при использовании...

Функции, скомпилированные для GPU, будут использовать математическую библиотеку NVIDIA CUDA, тогда как для вычислений на CPU будут

В то время как программная реализация NVIDIA CUDA также, как и SSE, использует только наборы инструкций, оперирующие числами с...

Задать вопрос