Реализация алгоритма решения несимметричных систем линейных уравнений на графических процессорах

Авторы

  • С.Н. Чадов

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

параллельные вычисления
разреженные СЛАУ
GPGPU
CUDA
BiCG-STAB
графические процессоры

Аннотация

Рассматриваются вопросы численного решения разреженных систем линейных алгебраических уравнений на графических процессорах общего назначения. Системы решаются на основе варианта алгоритма BiCG-STAB. Приводится описание алгоритма, излагаются несколько форматов представления разреженных матриц с учетом особенностей архитектуры графических процессоров NVIDIA. Производительность предложенной реализации на трех различных графических процессорах сравнивается с производительностью аналогичного алгоритма на центральных процессорах. Обсуждается зависимость производительности от разных факторов. Предлагаются направления дальнейшего совершенствования алгоритмов.

Новые вычислительные технологии

Загрузки

Опубликован

2009-09-06

Выпуск

Том 10 (2009): Выпуск 3.

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

С.Н. Чадов

Ивановский государственный энергетический университет (ИГЭУ),
факультет информатики и вычислительной техники
Рабфаковская ул., 34, 153003, Иваново
• аспирант

Библиографические ссылки

  1. Krüger J., Westermann R. Linear algebra operators for gpu implementation of numerical algorithms // ACM Transactions on Graphics. 2003. 22, N 3. 908-916.
  2. Bolz J., Farmer I., Grinspun E., Schröder P. Sparse matrix solvers on the gpu: conjugate gradients and multigrid // ACM Transactions on Graphics. 2003. 22, N 3. 917-924.
  3. Buatois L. et al. Concurrent number cruncher: a gpu implementation of a general sparse linear solver // International Journal of Parallel, Emergent and Distributed Systems (to appear).
  4. Barrett R. et al. Templates for the solution of linear systems: building blocks for iterative methods. Philadelphia: SIAM, 1994.
  5. Grote M., Huckle T. Parallel preconditioning with sparse approximate inverses // SIAM Journal on Scientic Computing. 1997. 18, N 3. 838-853.
  6. NVIDIA. CUDA Programming Guide, 2.1 edition. 2009.
  7. Baskaran M., Bordawekar R. Optimizing sparse matrix-vector multiplication on GPUs. IBM Tech. Rep. 2009.
  8. Bell N., Garland M. Efficient sparse matrix-vector multiplication on cuda. NVIDIA Tech. Rep. 2008.
Получено редакцией: 2020-11-11
Принято в выпуск: 2020-11-30
Опубликовано: 2020-12-06
 Цитировать как   
Чадов С.Н. Реализация алгоритма решения несимметричных систем линейных уравнений на графических процессорах // Вычислительные методы и программирование. 2009. 10, № 3. 321–326.

TEX CODE:

Chadov S. , (2009) “Implementation of a nonsymmetric linear solver on GPU,” Numerical Methods and Programming, vol. 10, no. 3, pp. 321–326.

TEX CODE:

S. Chadov, “Implementation of a nonsymmetric linear solver on GPU,” Numerical Methods and Programming 10, no. 3 (2009): 321–326

TEX CODE:

Chadov S. Implementation of a nonsymmetric linear solver on GPU. Numerical Methods and Programming. 2009;10(3):321–326.(In Russ.).

TEX CODE:

Рекомендованные статьи

Отображение проблем вычислительной математики на архитектуру вычислительных систем
В.В. Воеводин
Численное моделирование и компьютерный алгоритм процесса сегрегации легирующих примесей на границе волны окисления в полупроводниковых подложках
Г.А. Тарнавский, С.И. Шпак, М.С. Обрехт
Численное моделирование задачи динамики роста пленки окисла в полупроводниковых подложках на основе геометрического подхода и метода Дила-Гроува
А.Л. Александров, Г.А. Тарнавский, С.И. Шпак, А.И. Гулидов, М.С. Обрехт
Электронные образовательные средства: новые идеи
В.В. Воеводин, Вл.В. Воеводин
Система поддержки метакомпьютерных расчетов X-Com: архитектура и технология работы
М.П. Филамофитский
Об одной задаче компьютерной томографии в волновом приближении
А.В. Гончарский, С.Ю. Романов
Обратная задача акустической диагностики трехмерных сред
А.В. Гончарский, С.Ю. Романов, С.А. Харченко
Опыт параллелизации вычислений при расчете отрывных течений на основе трехмерных нестационарных формулировок
Д.К. Зайцев, Е.М. Смирнов, Н.А. Щур, П.Е. Смирнов, С.А. Якубов
Параллельные вычисления в задачах моделирования климата и прогноза погоды
Е.М. Володин, М.А. Толстых
Опыт использования параллельных алгоритмов в спектральной модели среднесрочного прогноза погоды Гидрометцентра России
Е.Д. Астахова, Ю.В. Алферов
Диагностика трехмерных сред методами синтезированной апертуры
Г.М. Агаян, Н.С. Виноградов, А.В. Гончарский, С.Л. Овчинников, С.Ю. Романов
Численное моделирование усиления ударных волн в пузырьковом шнуре на суперЭВМ
В.А. Вшивков, В.Д. Корнеев, Г.Г. Лазарева
Параллельный глобальный поиск равновесных ситуаций в биматричных играх
И.Л. Васильев, К.Б. Климентова, А.В. Орлов
Применение параллельных алгоритмов для решения задачи фильтрации жидкости в трещиновато-пористом пласте к скважинам со сложной траекторией
Д.А. Губайдуллин, Р.В. Садовников
Интегрирование трехмерных уравнений невязкого газа на неструктурированной сетке с применением распределенных вычислений
Н.М. Евстигнеев
Математическое моделирование: основные сегменты, их особенности и проблемы
Г.А. Тарнавский, А.В. Алиев
Алгоритмы распараллеливания на сгущающихся сетках в задачах трехфазной фильтрации жидкостей
Д.А. Губайдуллин, А.И. Никифоров, А.В. Цепаев
Разработка и реализация алгоритмов численного решения задач механики жидкости и газа
К.Н. Волков
Моделирование экстремальных явлений в атмосфере и океане как задача высокопроизводительных вычислений
А.В. Бухановский, С.В. Иванов, С.В. Ковальчук, Л.И. Лопатухин, О.И. Зильберштейн, С.К. Попов, М.М. Чумаков
Применение параллельного предобусловливателя CPR к задаче фильтрации вязкой сжимаемой жидкости в пористой среде
К.Ю. Богачев, И.Г. Горелов
О пространственной аппроксимации методом подсеток для задачи фильтрации вязкой сжимаемой жидкости в пористой среде
К.Ю. Богачев, Н.С. Мельниченко
Об одном подходе к решению обратных задач вычислительной диагностики на высокопроизводительных ЭВМ
А.В. Гончарский
Организация параллельных вычислений при решении обратной задачи волновой диагностики
С.Л. Овчинников, С.Ю. Романов
Оценка минимальных требований к аппаратуре и топологии при построении высокоскоростных коммуникационных сетей для суперкомпьютеров с общей памятью
А.А. Корж, Д.В. Макагон
Использование графических процессоров и технологии CUDA для задач молекулярной динамики
А.С. Боярченков, С.И. Поташников
Комбинированная MPI+threads параллельная реализация метода блоков для моделирования тепловых процессов в структурно-неоднородных средах
Д.Б. Волков-Богородский, Г.Б. Сушко, С.А. Харченко
Решение уравнения Больцмана на графических процессорах
Ю.Ю. Клосс, Ф.Г. Черемисин, П.В. Шувалов
Библиотека шаблонов итерационных методов подпространств Крылова для численного решения задач механики сплошных сред на гибридной вычислительной системе
Д.А. Губайдуллин, А.И. Никифоров, Р.В. Садовников
Комплекс программ параллельной декомпозиции сеток
Е.Н. Головченко
Построение параллельных алгоритмов для решения задач гравитационной газовой динамики
Б.П. Рыбакин, Н.И. Шидер
Некоторые технологические аспекты применения высокопроизводительных вычислений на графических процессорах в прикладных программных системах
М.Р. Галимов, Е.В. Биряльцев
Суперкомпьютерное образование: третья составляющая суперкомпьютерных технологий
Вл.В. Воеводин, В.П. Гергель
Применение HPC-технологий для решения пространственных задач мультифизики
В.А. Васильев, А.Ю. Ницкий, М.В. Крапошин, А.В. Юскин
Об одной задаче ультразвуковой томографии
А.В. Гончарский, С.Ю. Романов
Синтез волноведущих систем на основе фотонных кристаллов
Ю.С. Дементьева
Об особенностях использования архитектуры гетерогенного кластера для решения задач механики сплошных сред
Д.А. Губайдуллин, А.И. Никифоров, Р.В. Садовников
Об одном подходе к мониторингу, анализу и визуализации потока заданий на кластерной системе
А.В. Адинец, П.А. Брызгалов, Вад.В. Воеводин, С.А. Жуматий, Д.А. Никитенко
Оптимизация торговых стратегий с помощью параллельных эволюционных вычислений на графических процессорах
О.Г. Монахов
Использование гетерогенных вычислительных систем для решения задач фильтрации жидкости методами декомпозиции области
А.В. Цепаев
Особенности проведения экзафлопс-расчетов в физике плазмы
В.А. Вшивков, А.В. Снытников
Трехмерное моделирование двухфазных систем типа жидкость-пар методом решеточных уравнений Больцмана на GPU
А.Л. Куперштох
Применение графических процессоров для численного моделирования течения вязкой несжимаемой жидкости в областях сложной конфигурации методом погруженной границы
Е.В. Мортиков
Суперкомпьютерные технологии в разработке методов решения обратных задач в УЗИ-томографии
А.В. Гончарский, С.Ю. Романов
Математическое моделирование радиационной эмиссии электронов на гибридных суперкомпьютерах
М.Е. Жуковский, Р.В. Усков
Высокопроизводительные вычисления в моделировании динамики и сейсмичности систем тектонических плит
Л.А. Мельникова, В.Л. Розенберг
Разработка высокоэффективных масштабируемых программ в задаче ультразвуковой томографии
Вад.В. Воеводин, С.Л. Овчинников, С.Ю. Романов
Безградиентная параллельная оптимизация геометрии кластера Bi 3+ 5 и его люминесцентные свойства
А.Н. Романов, В.Б. Сулимов, И.В. Офёркин, А.В. Сулимов, Е.Д. Масленников
Квантово-химическая оценка фторкислотности как метод определения условий стабилизации субвалентных форм висмута во фторидных стеклах
О.А. Кондакова, А.Н. Романов, В.Б. Сулимов, Е.Д. Масленников
Трехмерное моделирование методом LBE на гибридных GPU-кластерах распада бинарной смеси жидкого диэлектрика с растворенным газом на систему парогазовых каналов
А.Л. Куперштох
Моделирование многокомпонентных гидродинамических течений с использованием адаптивных сеток
М.Е. Поварницын, А.С. Захаренков, П.Р. Левашов, К.В. Хищенко
Организация параллельных вычислений для моделирования сейсмических волн с использованием аддитивного метода Шварца
М.А. Белоносов, С.А. Соловьёв, В.А. Чеверда, К. Костов, Г.В. Решетова
Реализация метода решеточных уравнений Больцмана для расчетов на GPU-кластере
Д.А. Бикулов, Д.С. Сенин, Д.С. Демин, А.В. Дмитриев, Н.Е. Грачев
Ab initio молекулярная динамика: перспективы использования многопроцессорных и гибридных суперЭВМ
П.А. Жиляев, В.В. Стегайлов
Адаптация метода прямого статистического моделирования для вычислений на ГПУ
А.В. Кашковский, А.А. Шершнёв, М.С. Иванов
Программная система «ВИГОЛТ» для решения задач оптимизации, возникающих в транспортной логистике
Д.С. Бухаров, А.Л. Казаков
Моделирование трехмерных течений методом расщепления с использованием параллельной архитектуры ГПУ
С.Б. Березин, В.М. Пасконов, Н.А. Сахарных
Построение коллизии для 75-шаговой версии хеш-функции SHA-1 с использованием ГПУ-кластеров
Е.А. Гречников, А.В. Адинец
Параллельный программный комплекс NOISETTE для крупномасштабных расчетов задач аэродинамики и аэроакустики
И.В. Абалакин, А.В. Горобец, А.П. Дубень, Т.К. Козубская, П.А. Бахвалов
HOPLANG: развитие языка обработки потоков данных мониторинга
А.В. Адинец, П.А. Брызгалов, Вад.В. Воеводин, С.А. Жуматий, Д.А. Никитенко, К.С. Стефанов
Job Digest: подход к исследованию динамических свойств задач на суперкомпьютерных системах
А.В. Адинец, П.А. Брызгалов, Вад.В. Воеводин, С.А. Жуматий, Д.А. Никитенко, К.С. Стефанов
Математическое моделирование условий формирования заморов в мелководных водоемах на многопроцессорной вычислительной системе
А.И. Сухинов, А.В. Никитина, А.Е. Чистяков, И.С. Семенов
Методы деформирования сеток в сопряженных задачах
C.П. Копысов, И.М. Кузьмин
Использование графических ускорителей и вычислительных сопроцессоров при решении задачи фильтрации
К.Ю. Богачев, А.С. Богатый, А.Р. Лапин
О распараллеливании вычислений в вихревом методе решения задач аэродинамики
А.А. Апаринов, А.В. Сетуха
Трехмерное моделирование динамики деформируемых капель эмульсии методом граничных элементов и быстрым методом мультиполей на гетерогенных вычислительных системах
О.А. Абрамова, Ю.А. Иткулова, Н.А. Гумеров, И.Ш. Ахатов
О применимости послойных моделей в решении трехмерных задач ультразвуковой томографии
Г.М. Агаян, Вад.В. Воеводин, С.Ю. Романов
Эвристические алгоритмы отображения параллельных MPI-программ на мультикластерные вычислительные и GRID-системы
М.Г. Курносов, А.А. Пазников
Автоматизация поиска ошибок и неэффективностей в параллельных программах
А.С. Антонов, Вад.В. Воеводин, С.А. Жуматий, Д.А. Никитенко, К.С. Стефанов, П.А. Швец
Параллельные алгоритмы решения уравнения Пуассона при дискретизации по шаблону «косой крест» в областях с обратной ступенькой
А.М. Рязанов, С.А. Финогенов
Система автоматизированного поиска ошибок и неэффективностей в параллельных программах
Д.Ю. Андреев, А.С. Антонов, Вад.В. Воеводин, С.А. Жуматий, Д.А. Никитенко, К.С. Стефанов, П.А. Швец
Балансировка нагрузки в ГПУ-реализации поиска в ширину на графе
М.А. Черноскутов, Д.Г. Ермаков
Параллельная реализация алгоритма градиентного бустинга деревьев решений
П.Н. Дружков
Применение планировщика для эффективного обмена данными на суперкомпьютерах гибридной архитектуры с массивно-параллельными ускорителями
П.Б. Богданов, А.А. Ефремов, С.А. Суков, А.В. Горобец
Параллельная CUDA-реализация алгоритма сопоставления стереоизображений
В.А. Фурсов, Е.В. Гошин, А.П. Котов
Разработка пакета программ для трехмерного численного моделирования многофазных многокомпонентных течений в атомной энергетике
С.В. Дьяченко
Моделирование динамики пузырьков в трехмерных потенциальных течениях на гетерогенных вычислительных системах быстрым методом мультиполей и методом граничных элементов
Ю.А. Иткулова, О.А. Абрамова, Н.А. Гумеров, И.Ш. Ахатов
Автоматическое определение и описание сетевой инфраструктуры суперкомпьютеров
Вад.В. Воеводин, К.С. Стефанов
Об одном подходе к сравнению масштабируемости параллельных программ
А.М. Теплов
Параллельное формирование предобусловливателя, основанного на аппроксимации обращения Шермана-Моррисона
Н.С. Недожогин, C.П. Копысов, А.К. Новиков
Открытая энциклопедия свойств алгоритмов AlgoWiki: от мобильных платформ до экзафлопсных суперкомпьютерных систем
Вл.В. Воеводин
Стохастическая модификация сферической блоковой модели динамики и сейсмичности литосферы
Л.А. Мельникова, В.Л. Розенберг
Суперкомпьютерное молекулярное моделирование термодинамического равновесия в микросистемах газ-металл
В.О. Подрыга, С.В. Поляков, Д.В. Пузырьков
О реализации вихревых методов моделирования двумерных течений несжимаемой среды с использованием технологии CUDA
С.Р. Гречкин-Погребняков, К.С. Кузьмина, И.К. Марчевский
Эффективная реализация метода решеточных уравнений Больцмана для гибридных суперкомпьютерных систем
Д.А. Бикулов
Гибридный эвристический параллельный метод глобальной оптимизации
К.В. Пушкарев, В.Д. Кошур
Параллельная оптимизация метода решения системы уравнений полярона с использованием алгоритма разбиений
А.В. Волохова, Е.В. Земляная, В.С. Рихвицкий
Параллельная реализация быстрого метода решения уравнений агрегационно-фрагментационной кинетики типа уравнений Смолуховского
С.А. Матвеев
Пакет параллельной декомпозиции больших сеток GridSpiderPar
Е.Н. Головченко, М.В. Якобовский
Новые подходы к построению высокоэффективных параллельных алгоритмов для численного решения краевых задач на структурированных сетках
В.М. Волохов, С.И. Мартыненко, П.Д. Токталиев, Л.С. Яновский, А.В. Волохов
Анализ производительности гидродинамических расчетов на GPU- и CPU-кластерах
А.В. Сентябов, А.А. Гаврилов, М.А. Кривов, А.А. Дектерев, М.Н. Притула
Обратные задачи послойной ультразвуковой томографии с данными на цилиндрической поверхности
А.В. Гончарский, С.Ю. Романов, С.Ю. Серёжников
Применение NVidia CUDA для ускорения обработки сейсмических данных при помощи разложения по волновым пакетам
В.В. Никитин, А.А. Дучков, Ф. Андерссон
Параллельные вычисления на гибридной вычислительной системе в задачах двухфазной фильтрации
А.И. Никифоров, Р.В. Садовников
Параллельные вычисления в гидрогеологическом расчетном коде GeRa: организация и эффективность
И.В. Капырин, И.Н. Коньшин, Г.В. Копытов, В.К. Крамаренко
Метод балансировки нагрузки вычислений с использованием кривых Гильберта применительно к параллельному алгоритму решения уравнений мелкой воды
А.В. Чаплыгин, Н.А. Дианский, А.В. Гусев
Всесторонний анализ качества работы больших суперкомпьютерных комплексов
В.В. Воеводин
Параллельный предобусловливатель на основе степенного разложения обратной матрицы для решения разреженных линейных систем на графических процессорах
А.В. Юлдашев, Н.В. Репин, В.В. Спеле
Возможности многоядерных процессоров MALT в задачах обработки изображений
Н.Г. Михеев, В.А. Антонюк, С.Г. Елизаров, Г.А. Лукьянченко
Параллельные алгоритмы решения задачи динамики изменения рельефа дна в прибрежных системах
В.В. Сидорякина, А.И. Сухинов, А.Е. Чистяков, Е.А. Проценко, C.B. Проценко
Опыт применения механизма областей для поэтапного распараллеливания программных комплексов с помощью системы SAPFOR
А. С. Колганов
Исследование эффективности распараллеливания расчета движения подвижных тел и свободных поверхностей во FlowVision на компьютерах с распределенной памятью
А.А. Аксенов, А.А. Дядькин, С.А. Харченко
Параллельная молекулярная динамика с суммированием Эвальда и интегрированием на графических процессорах
А.С. Боярченков, С.И. Поташников
Интегрирование уравнения Пуассона с использованием графического процессора технологии CUDA
Н.М. Евстигнеев
Алгоритмы оптимизации вычислений методом ПСМ на параллельных вычислительных кластерах
П.В. Ващенков, А.В. Кашковский, М.С. Иванов
Модель параллельной программы для оценки времени ее исполнения
В. А. Антонюк, Н. Г. Михеев
Преобразование последовательных Fortran-программ для их распараллеливания на гибридные кластеры в системе SAPFOR
А. С. Колганов, Г. Д. Гусев
О реализации параллельного алгоритма глобальной оптимизации с использованием набора инструментов Intel oneAPI
И. Г. Лебедев, К. А. Баркалов, Я. В. Силенко
Параллельная реализация алгоритма восстановления сейсмического источника по серии статистически идентичных моделей среды с применением Fortran Coarray
В. В. Койнов
Создание переносимого программного комплекса для мониторинга и анализа производительности суперкомпьютерных приложений
В. В. Воеводин, К. С. Стефанов
Валидационные расчеты задач гемодинамики с использованием программного комплекса FlowVision в режиме распараллеливания
М. Д. Калугина, В. С. Каширин, А. И. Лобанов
Поиск аномалий в больших временных рядах на кластере с GPU узлами
М. Л. Цымблер, Я. А. Краева
Экономичные алгоритмы решения обратных задач гравиметрии и магнитометрии на графических процессорах
Е. Н. Акимова, В. Е. Мисилов, А. И. Третьяков
Реализация преобразования удаления приватных переменных в последовательных Fortran-программах для их эффективного распараллеливания на вычислительные кластеры в системе SAPFOR
А. С. Колганов, Г. Д. Гусев
Сравнение подходов к динамической адаптации расчетной сетки на распределенной вычислительной системе
А. А. Бай, С. К. Григорьев