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

Авторы

  • С.Н. Чадов

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

параллельные вычисления
разреженные СЛАУ
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.