Аналитическое моделирование матрично-векторного произведения на многоядерных процессорах

Елена Николаевна Акимова, Роман Альбертович Гареев

Аннотация


Эффективная реализация матрично-векторного произведения имеет существенную практическую значимость в областях машинного обучения, интеллектуального анализа данных, квантовой химии, математической физики, численных методов линейной алгебры, высокопроизводительных вычислений и др. В данной работе представлен алгоритм автоматизированной оптимизации матрично-векторного произведения по времени выполнения, использующийся на этапе компиляции без ручной настройки и автонастройки. Алгоритм основан на моделировании вычислений на гипотетическом многоядерном процессоре, предложенном авторами, с применением полиэдрального представления.  В отличие от подходов, основанных на ручной настройке и автонастройке, алгоритм может применяться для создания новых оптимизированных реализаций матрично-векторного произведения в условиях недоступности целевой архитектуры и ограниченности времени выполнения.  Алгоритм использован для оптимизации программного кода, реализующего решение структурной обратной задачи гравиметрии о нахождении поверхности раздела сред методом Левенберга-Марквардта. Проведено сравнение производительности полученной реализации с реализациями на основе оптимизированных библиотек линейной алгебры Intel MKL, BLIS, OpenBLAS. Результаты численных экспериментов показывают сравнимость предложенного алгоритма по эффективности с подходами, созданными с использованием ручной настройки при доступе к целевым архитектурам процессоров.


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


компилятор; линейная алгебра; матрично-векторные операции; аналитическое моделирование; обратная задача гравиметрии

Полный текст:

PDF

Литература


Yu J., Lukefahr A., Palframan D., et al. Scalpel: Customizing DNN Pruning to the Underlying Hardware Parallelism. SIGARCH Computer Architecture News. 2017. Vol. 45, no. 2. P. 548–560. DOI: 10.1145/3140659.3080215.

Yang X., Parthasarathy S., Sadayappan P. Fast Sparse Matrix-vector Multiplication on GPUs: Implications for Graph Mining. Proceedings of the VLDB Endowment. 2011. Vol. 4, no. 4. P. 231–242. DOI: 10.14778/1938545.1938548.

Kaushik D., Gropp W., Minkoff M., et al. Improving the Performance of Tensor Matrix Vector Multiplication in Cumulative Reaction Probability Based Quantum Chemistry Codes. High Performance Computing (HiPC 2008). Springer Berlin Heidelberg, Berlin, Heidelberg, 2008. P. 120–130. DOI: 10.2172/928654.

Martyshko P.S., Akimova E.N., Misilov V.E. Solving the structural inverse gravity problem by the modified gradient methods. Izvestiya, Physics of the Solid Earth. 2016. Vol. 52, no. 5. P. 704–708. DOI: 10.1134/S1069351316050098.

Hassan S.A., Mahmoud M.M., Hemeida A., et al. Effective Implementation of Matrix-Vector Multiplication on Intel’s AVX Multicore Processor. Computer Languages, Systems & Structures. 2018. Vol. 51. P. 158–175. DOI: 10.1016/j.cl.2017.06.003.

Liang J., Zhang Y. Optimization of GEMV on Intel AVX processor. International Journal of Database Theory and Application. 2016. Vol. 9. P. 47–60. DOI: 10.14257/ijdta.2016.9.2.06.

Low T.M., Igual F.D., Smith T.M. Quintana-Orti E.S., Analytical Modeling Is Enough for High-Performance BLIS. ACM Transactions on Mathematical Software. 2016. Vol. 43, no. 2. P. 12:1–12:18. DOI: 10.1145/2925987.

Frison G. Algorithms and Methods for High-Performance Model Predictive Control. Technical University of Denmark. 2016. 345 p.

Akimova E.N., Gareev R.A. Algorithm of Automatic Parallelization of Generalized Matrix Multiplication. CEUR Workshop Proceedings. 2017. Vol. 2005. P. 1–10.

Gareev R., Grosser T., Kruse M. High-Performance Generalized Tensor Operations: A Compiler-Oriented Approach. ACM Transactions on Architecture and Code Optimization. 2018. Vol. 15, no. 3. P. 34:1–34:27. DOI: 10.1145/3235029.

Intel. Intel Math Kernel Library (Intel MKL). Available at: https://software.intel.com/en-us/mkl (accessed: 27.10.2019).

Van Zee F.G., Van De Geijn R.A. BLIS: A Framework for Rapidly Instantiating BLAS Functionality. ACM Transactions on Mathematical Software. 2015. Vol. 41, no. 3. P. 14:1–14:33. DOI: 10.1145/2764454.

Xianyi Z., Qian W., Yunquan Z. Model-driven level 3 BLAS performance optimization on Loongson 3A processor. Parallel and Distributed Systems (ICPADS), 2012 IEEE 18th International Conference on Parallel and Distributed Systems, IEEE. 2012. P. 684–691. DOI: 10.1109/icpads.2012.97.

Feautrier P., Lengauer C. Polyhedron Model. Encyclopedia of Parallel Computing. Springer US, Boston, MA. 2011. P. 1581–1592. DOI: 10.1007/978-0 387-09766-4_502.

Grosser T., Groesslinger A., Lengauer C. Polly—Performing polyhedral optimizations on a low-level intermediate representation. Parallel Process. Lett. 2012. Vol. 22, no. 4. DOI: 10.1142/S0129626412500107.

Lattner C. LLVM: An Infrastructure for Multi-Stage Optimization. Master’s Thesis. 2002. Available at: http://llvm.cs.uiuc.edu (accessed: 27.10.2019).

Apra E., Klemm M., Kowalski K. Efficient Implementation of Many-Body Quantum Chemical Methods on the Intel®Xeon Phi™Coprocessor. International Conference for High Performance Computing, Networking, Storage and Analysis. 2014. P. 674–684. DOI: 10.1109/SC.2014.60

Springer P., Bientinesi P. Design of a high-performance GEMM-like tensortensor multiplication. ACM Trans. Math. Softw. 2018. Vol. 44, no. 3, Article 28. DOI: 10.1145/3157733.

Matthews D. High-performance tensor contraction without BLAS. SIAM Journal on Scientific Computing. 2016. Vol. 40. DOI: 10.1137/16M108968X.

Doerfert J., Streit K., Hack S., et al. Polly’s polyhedral scheduling in the presence of reductions. arXiv preprint. 2015. arXiv:1505.07716.

Numerov B.V. Interpretation of gravitational observations in the case of one contact surface. Dokl. Akad. Nauk SSSR. 1930. P. 569–574.

Vasin V.V., Eremin I.I. Operators and iterative processes of Fej´er type: theory and applications. Walter de Gruyter. 2009. Vol. 53. 155 p. DOI: 10.1515/9783110218190.




DOI: http://dx.doi.org/10.14529/cmse200105