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

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

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

Журнал: Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi

Статья в выпуске: 1 т.9, 2020 года.

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

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

Еще

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

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

IDR: 147233215   |   DOI: 10.14529/cmse200105

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

  • 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 с.
  • 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). URL: https://software.intel.com/en-us/ mkl (дата обращения: 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., Gr¨o{\\ss}linger 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. URL: http://llvm.cs.uiuc.edu (дата обращения: 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 tensor-tensor 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
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp