Исследование эффективности векторизации гнезд циклов с нерегулярным числом итераций

Исследование эффективности векторизации гнезд циклов с нерегулярным числом итераций

Автор: Рыбаков Алексей Анатольевич, Шумилин Сергей Сергеевич

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

Рубрика: Математические основы программирования

Статья в выпуске: 4 (43) т.10, 2019 года.

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

Векторизация вычислений является важной низкоуровневой оптимизацией, используемой для создания высокоэффективного параллельного кода. Особенности набора инструкций AVX-512 позволяют применять векторизацию для сложного программного контекста, в частности для гнезд циклов и циклов с сильно разветвленным управлением. При использовании векторных инструкций для контекста с неизвестным профилем исполнения существует опасность низкой эффективности векторизации. Особенно ярко это проявляется при векторизации гнезд циклов с нерегулярным числом итераций внутреннего цикла.В статье рассматривается практический подход к векторизации гнезд циклов, основанный на предикатном представлении программы. В качестве примера приводится реализация сортировки Шелла, компактная реализация которой состоит из гнезда циклов, в котором количество итераций внутреннего цикла носит нерегулярный характер и зависит от номеров итераций внешних циклов. Такой контекст является крайне неудобным для векторизации.Приводится сравнение теоретической и практической эффективности векторизации сортировки Шелла, рассматриваются особенности этого программного контекста и объясняется их негативное влияние на производительность векторизованного кода. Полученные результаты могут быть использованы исследователями и разработчиками программного обеспечения для обнаружения причин низкой эффективности векторизации программного кода с похожими особенностями.

Еще

Векторизация, гнезда циклов с нерегулярным числом итераций, сортировка шелла, теоретическое ускорение

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

IDR: 143169811   |   DOI: 10.25209/2079-3316-2019-10-4-77-96

Список литературы Исследование эффективности векторизации гнезд циклов с нерегулярным числом итераций

  • Intel64 and IA-32 architectures software developer's manual, IntelCorporation, October 2019, Combined volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D and 4 URL https://software.intel.com/en-us/download/intel-64-and-ia-32-architectures-sdm-combined-volumes-1-2a-2b-2c-2d-3a-3b-3c-3d-and-4 (access date: 21.10.2019).
  • J. Jeffers, J. Reinders, A. Sodani. IntelXeon Phi processor high performance programming, 2 ed., Morgan Kaufmann Publ., 2016, , 662 pp. ISBN: 978-0-12-809194-4
  • IntelC++ compiler 16.0 user and reference guide, IntelCorporation, 2015 URL https://software.intel.com/en-us/download/intel-c-compiler-160-update-4-user-and-reference-guide (access date: 21.10.2019).
  • IntelIntrinsics guide URL https://software.intel.com/sites/landingpage/IntrinsicsGuide/ (access date: 21.10.2019).
  • W. McDoniel, M. Hohnerbach, R. Canales et al. “LAMMPS' PPPM long-range solver for the second generation Xeon Phi”, ISC 2017, Lecture Notes in Computer Science, vol. 10266, eds. J.M. Kunkel et al., Springer, Cham, 2017, , pp. 61-78. DOI: 10.1007/978-3-319-58667-0_4 ISBN: 978-3-319-58666-3
  • T. Malas, T. Kurth, J. Deslippe. “Optimization of the sparse matrix-vector products of an IDR Krylov iterative solver in EMGeo for the Intel KNL manycore processor”, ISC High Performance 2016, Lecture Notes in Computer Science, vol. 9945, eds. M. Taufer et al., Springer, Cham, 2016, , pp. 378-389.
  • DOI: 10.1007/978-3-319-46079-6_27 ISBN: 978-3-319-46078-9
  • Л. А. Бендерский, А. А. Рыбаков, С. С. Шумилин. «Векторизация перемножения малоразмерных матриц специального вида с использованием инструкций AVX-512», Современные информационные технологии и ИТ-образование, 14:3 (2018), с. 594-602.
  • DOI: 10.25559/SITITO.14.201803.594-602
  • O. Krzikalla, F. Wende, M. Hohnerbach. “Dynamic SIMD vector lane scheduling”, ISC High Performance 2016, Lecture Notes in Computer Science, vol. 9945, Springer, Cham, 2016, , pp. 354-365.
  • DOI: 10.1007/978-3-319-46079-6_25 ISBN: 978-3-319-46078-9
  • B. Cook, P. Maris, M. Shao. “High performance optimizations for nuclear physics code MFDn on KNL”, ISC High Performance 2016, Lecture Notes in Computer Science, vol. 9945, eds. M. Taufer et al., Springer, Cham, 2016, , pp. 366-377.
  • DOI: 10.1007/978-3-319-46079-6_26 ISBN: 978-3-319-46078-9
  • C. R. Ferreira, K. T. Mandli, M. Bader. “Vectorization of Riemann solvers for the single- ans multi-layer shallow water equations”, HPCS 2018 (16-20 July 2018, Orleans, France), 2018, pp. 415-422.
  • DOI: 10.1109/hpcs.2018.00073
  • B. Bramas. “A novel hybrid quicksort algorithm vectorized using AVX-512 on Intel Skylake”, International Journal of Advanced Computer Science and Applications, 8:10 (2017), pp. 337-344.
  • DOI: 10.14569/IJACSA.2017.081044
  • М. С. Гуськова, Л. Ю. Бараш, Л. Н. Щур. «Применение AVX512-векторизации для увеличения производительности генератора псевдослучайных чисел», Труды ИСП РАН, 30:1 (2018), с. 115-126.
  • DOI: 10.15514/ISPRAS-2018-30(1)-8
  • Д. Кнут. Искусство программирования, Вильямс, М., 2009, , 832 с.
  • ISBN: 978-5-8459-0082-1
  • D. L. Shell. “A high-speed sorting procedure”, Communications of the ACM, 2:7 (1959), pp. 30-32.
  • DOI: 10.1145/368370.368387
  • N. J. A. Sloane (ed.). The on-line encyclopedia of integer sequences, 2019, published electronically at https://oeis.org.
  • T. H. Hibbard. “An empirical study of minimal storage sorting”, Communications of the ACM, 6:5 (1963), pp. 206-213.
  • DOI: 10.1145/366552.366557
  • V. R. Pratt. Shellsort and Sorting Networks, Outstanding Dissertations in the Computer Sciences, Garland, New York, 1972, (Originally presented as the author's thesis, Stanford University, 1971).
  • ISBN: 978-0-8240-4406-0
  • J. Incerpi, R. Sedgewick. “Improved upper bounds on shellsort”, J. Computer and System Sciences, 31:2 (1985), pp. 210-224.
  • DOI: 10.1016/0022-0000(85)90042-X
  • В. Ю. Волконский, С. К. Окунев. «Предикатное представление как основа оптимизации программы для архитектур с явно выраженной параллельностью», Информационные технологии, 2003, №4, с. 36-45.
  • R. Hubbard. Using Intel ^AVX without Writing AVX, Intel ^Software Services Group, October 25, 2011 URL https://software.intel.com/en-us/articles/using-intel-avx-without-writing-avx (White Paper).
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp