|
Математические основы программирования
Исследование эффективности векторизации гнезд циклов с нерегулярным числом итераций
А. А. Рыбаков, С. С. Шумилин Межведомственный суперкомпьютерный центр РАН
Аннотация:
Векторизация вычислений является важной низкоуровневой оптимизацией, используемой для создания высокоэффективного параллельного кода. Особенности набора инструкций AVX-512 позволяют применять векторизацию для сложного программного контекста, в частности для гнезд циклов и циклов с сильно разветвленным управлением. При использовании векторных инструкций для контекста с неизвестным профилем исполнения существует опасность низкой эффективности векторизации. Особенно ярко это проявляется при векторизации гнезд циклов с нерегулярным числом итераций внутреннего цикла.
В статье рассматривается практический подход к векторизации гнезд циклов, основанный на предикатном представлении программы. В качестве примера приводится реализация сортировки Шелла, компактная реализация которой состоит из гнезда циклов, в котором количество итераций внутреннего цикла носит нерегулярный характер и зависит от номеров итераций внешних циклов. Такой контекст является крайне неудобным для векторизации.
Приводится сравнение теоретической и практической эффективности векторизации сортировки Шелла, рассматриваются особенности этого программного контекста и объясняется их негативное влияние на производительность векторизованного кода. Полученные результаты могут быть использованы исследователями и разработчиками программного обеспечения для обнаружения причин низкой эффективности векторизации программного кода с похожими особенностями.
Ключевые слова и фразы:
векторизация, AVX-512, гнезда циклов с нерегулярным числом итераций, сортировка Шелла, теоретическое ускорение.
Поступила в редакцию: 28.02.2019 Подписана в печать : 30.11.2019
Образец цитирования:
А. А. Рыбаков, С. С. Шумилин, “Исследование эффективности векторизации гнезд циклов с нерегулярным числом итераций”, Программные системы: теория и приложения, 10:4 (2019), 77–96
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ps356 https://www.mathnet.ru/rus/ps/v10/i4/p77
|
Статистика просмотров: |
Страница аннотации: | 140 | PDF полного текста: | 119 | Список литературы: | 20 |
|