Матрично-векторное умножение многократной точности на графическом процессоре

Автор: Исупов Константин Сергеевич, Князьков Владимир Сергеевич

Журнал: Программные системы: теория и приложения @programmnye-sistemy

Рубрика: Программное и аппаратное обеспечение для супер ЭВМ

Статья в выпуске: 3 (46) т.11, 2020 года.

Бесплатный доступ

Мы рассматриваем параллельную реализацию матрично-векторного умножения (GEMV, уровень 2 BLAS) для графических процессоров (GPU) с использованием арифметики многократной точности на основе системы остаточных классов. В нашей реализации GEMV покомпонентные операции с многоразрядными векторами и матрицами разбиваются на части, каждая из которых выполняется отдельным CUDA ядром. Это исключает ветвление логики исполнения и позволяет добиться более полного использования ресурсов GPU. Эффективная структура данных для хранения многоразрядных массивов обеспечивает объединение доступов параллельных потоков к глобальной памяти GPU в транзакции. Для предложенной реализации GEMV выполнен анализ ошибок округления и получены оценки точности. Представлены экспериментальные результаты, показывающие высокую эффективность разработанной реализации по сравнению с существующими программными пакетами многократной точности для GPU.

Еще

Вычисления высокой точности, параллельные алгоритмы, система остаточных классов

Короткий адрес: https://sciup.org/143172952

IDR: 143172952   |   DOI: 10.25209/2079-3316-2020-11-3-33-59

Список литературы Матрично-векторное умножение многократной точности на графическом процессоре

  • M. Courbariaux, Y. Bengio, J. David. Training deep neural networks with low precision multiplications, 2014.
  • D. H. Bailey, J. M. Borwein. “High-precision arithmetic in mathematical physics”, Mathematics, 3:2 (2015), pp. 337-367. DOI: 10.3390/math3020337
  • J. Daněk, J. Pospíšil. “Numerical aspects of integration in semi-closed option pricing formulas for stochastic volatility jump diffusion models”, International Journal of Computer Mathematics, 97:6 (2020), pp. 1268-1292. DOI: 10.1080/00207160.2019.1614174
  • Y. Feng, J. Chen, W. Wu. “The PSLQ algorithm for empirical data”, Math. Comp., 88:317 (2019), pp. 1479-1501. DOI: 10.1090/mcom/3356
  • S. Leweke, E. von Lieres. “Fast arbitrary order moments and arbitrary precision solution of the general rate model of column liquid chromatography with linear isotherm”, Comput. Chem. Eng., 84 (2016), pp. 350-362. DOI: 10.1016/j.compchemeng.2015.09.009
  • M. Kyung, E. Sacks, V. Milenkovic. “Robust polyhedral Minkowski sums with GPU implementation”, Comput. Aided Des., 67-68 (2015), pp. 48-57.
  • DOI: 10.1016/j.cad.2015.04.012
  • B. Pan, Y. Wang, S. Tian. “A high-precision single shooting method for solving hypersensitive optimal control problems”, Mathematical Problems in Engineering, 2018 (2018), 7908378, 11 pp.
  • DOI: 10.1155/2018/7908378
  • Y. Xuan, D. Li, W. Han. “Efficient optimization approach for fast GPU computation of Zernike moments”, Journal of Parallel and Distributed Computing, 111 (2018), pp. 104-114.
  • DOI: 10.1016/j.jpdc.2017.07.008
  • C. L. Lawson, R. J. Hanson, D. R. Kincaid, F. T. Krogh. “Basic linear algebra subprograms for Fortran usage”, ACM Trans. Math. Softw., 5:3 (1979), pp. 308-323.
  • DOI: 10.1145/355841.355847
  • R. Nath, S. Tomov, T. Tim Dong, J. Dongarra. “Optimizing symmetric dense matrix-vector multiplication on GPUs”, ACM, New York, NY, USA, 2011, pp. 1-10.
  • DOI: 10.1145/2063384.2063392
  • K. Isupov, V. Knyazkov, A. Kuvaev. “Design and implementation of multiple-precision BLAS Level 1 functions for graphics processing units”, Journal of Parallel and Distributed Computing, 140 (2020), pp. 25-36.
  • DOI: 10.1016/j.jpdc.2020.02.006
  • A. Omondi, B. Premkumar. Residue number systems: theory and implementation, Imperial College Press, London, UK, 2007.
  • K. Bigou, A. Tisserand. “Single base modular multiplication for efficient hardware RNS implementations of ECC”, eds. T. Güneysu, H. Handschuh, Springer Berlin Heidelberg, Berlin, Heidelberg, 2015, pp. 123-140.
  • A. Abdelfattah, D. Keyes, H. Ltaief. “KBLAS: an optimized library for dense matrix-vector multiplication on GPU accelerators”, ACM Trans. Math. Softw., 42:3 (2016), 18.
  • DOI: 10.1145/2818311
  • G. He, J. Gao, J. Wang. “Efficient dense matrix-vector multiplication on GPU”, Concurrency and Computation: Practice and Experience, 30:19 (2018), e4705.
  • DOI: 10.1002/cpe.4705
  • T. Inoue, H. Tokura, K. Nakano, Y. Ito. “Efficient triangular matrix vector multiplication on the GPU”, Lecture Notes in Computer Science, vol. 12043, eds. R. Wyrzykowski, E. Deelman, J. Dongarra, K. Karczewski, Springer International Publishing, Cham, 2020, pp. 493-504.
  • DOI: 10.1007/978-3-030-43229-4_42
  • Quadruple precision BLAS routines for GPU: QPBLAS-GPU ver.1.0. User's manual, 2013, 58 pp. (accessed 19 May 2019).
  • R. Iakymchuk, S. Collange, D. Defour, S. Graillat. “ExBLAS: reproducible and accurate BLAS library”, Numerical Reproducibility at Exascale (NRE2015) workshop held as part of the Supercomputing Conference (SC15) (November 20, 2015, Austin, TX, USA) URL https://hal.archives-ouvertes.fr/hal-01202396/file/exblas.pdf.
  • D. Mukunoki, T. Ogita. “Performance and energy consumption of accurate and mixed-precision linear algebra kernels on GPUs”, Journal of Computational and Applied Mathematics, 372 (2020), 112701.
  • DOI: 10.1016/j.cam.2019.112701
  • Y. Hida, X. S. Li, D. H. Bailey. “Algorithms for quad-double precision floating point arithmetic”, ARITH-15 (11-13 June 2001, Vail, CO, USA), pp. 155-162.
  • DOI: 10.1109/ARITH.2001.930115
  • D. E. Knuth. The art of computer programming, 3rd ed., Addison-Wesley Longman Publishing Co., Inc., USA, 1997, 978-0201896848.
  • ISBN: 9780201896848
  • J. R. Shewchuk. “Adaptive precision floating-point arithmetic and fast robust geometric predicates”, Discrete Computational Geometry, 18:3 (1997), pp. 305-363.
  • DOI: 10.1007/PL00009321
  • T. Ogita, S. M. Rump, S. Oishi. “Accurate sum and dot product”, SIAM J. Sci. Comput., 26:6 (2005), pp. 1955-1988.
  • DOI: 10.1137/030601818
  • M. Lu, B. He, Q. Luo. “Supporting extended precision on graphics processors”, DaMoN'10: Proceedings of the Sixth International Workshop on Data Management on New Hardware (2010, Indianapolis, Indiana, USA), pp. 19-26.
  • DOI: 10.1145/1869389.1869392
  • M. Joldes, J. Muller, V. Popescu. “Implementation and performance evaluation of an extended precision floating-point arithmetic library for high-accuracy semidefinite programming”, 2017 IEEE 24th Symposium on Computer Arithmetic (ARITH) (24-26 July 2017, London, UK), pp. 27-34.
  • DOI: 10.1109/ARITH.2017.18
  • T. Nakayama, D. Takahashi. “Implementation of multiple-precision floating-point arithmetic library for GPU computing”, The 23rd IASTED International Conference on Parallel and Distributed Computing and Systems PDCS 2011 (December 14-16 2011, Dallas, USA), pp. 343-349.
  • DOI: 10.2316/P.2011.757-041
  • K. Isupov. “Using floating-point intervals for non-modular computations in residue number system”, IEEE Access, 8 (2020), pp. 58603-58619.
  • DOI: 10.1109/ACCESS.2020.2982365
  • N. J. Higham. Accuracy and stability of numerical algorithms, 2nd, SIAM, Philadelphia, PA, USA, 2002, 978-0-89871-521-7, xxvii+663 pp.
  • ISBN: 9780898715217
  • J. Muller, N. Brunie, F. de Dinechin, C. Jeannerod, M. Joldes, V. Lefèvre, G. Melquiond, N. Revol, S. Torres. Handbook of floating-Point arithmetic, 2, Birkhäuser, Basel, 2018, 978-3-319-76525-9.
  • ISBN: 9783319765259
Еще
Статья научная