Программные системы: теория и приложения
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Правила для авторов
Загрузить рукопись

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Программные системы: теория и приложения:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Программные системы: теория и приложения, 2019, том 10, выпуск 4, страницы 77–96
DOI: https://doi.org/10.25209/2079-3316-2019-10-4-77-96
(Mi ps356)
 

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

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

А. А. Рыбаков, С. С. Шумилин

Межведомственный суперкомпьютерный центр РАН
Список литературы:
Аннотация: Векторизация вычислений является важной низкоуровневой оптимизацией, используемой для создания высокоэффективного параллельного кода. Особенности набора инструкций AVX-512 позволяют применять векторизацию для сложного программного контекста, в частности для гнезд циклов и циклов с сильно разветвленным управлением. При использовании векторных инструкций для контекста с неизвестным профилем исполнения существует опасность низкой эффективности векторизации. Особенно ярко это проявляется при векторизации гнезд циклов с нерегулярным числом итераций внутреннего цикла.
В статье рассматривается практический подход к векторизации гнезд циклов, основанный на предикатном представлении программы. В качестве примера приводится реализация сортировки Шелла, компактная реализация которой состоит из гнезда циклов, в котором количество итераций внутреннего цикла носит нерегулярный характер и зависит от номеров итераций внешних циклов. Такой контекст является крайне неудобным для векторизации.
Приводится сравнение теоретической и практической эффективности векторизации сортировки Шелла, рассматриваются особенности этого программного контекста и объясняется их негативное влияние на производительность векторизованного кода. Полученные результаты могут быть использованы исследователями и разработчиками программного обеспечения для обнаружения причин низкой эффективности векторизации программного кода с похожими особенностями.
Ключевые слова и фразы: векторизация, AVX-512, гнезда циклов с нерегулярным числом итераций, сортировка Шелла, теоретическое ускорение.
Финансовая поддержка Номер гранта
Российская академия наук - Федеральное агентство научных организаций АААА-А19-119011590098-8
Работа выполнена в МСЦ РАН в рамках государственного задания по теме 0065-2019-0016 (reg. no. АААА-А19-119011590098-8).
Поступила в редакцию: 28.02.2019
Подписана в печать : 30.11.2019
Тип публикации: Статья
УДК: 519.681.5:004.272.25
ББК: З973.1
MSC: Primary 68W10; Secondary 65P99, 68M07
Образец цитирования: А. А. Рыбаков, С. С. Шумилин, “Исследование эффективности векторизации гнезд циклов с нерегулярным числом итераций”, Программные системы: теория и приложения, 10:4 (2019), 77–96
Цитирование в формате AMSBIB
\RBibitem{RybShu19}
\by А.~А.~Рыбаков, С.~С.~Шумилин
\paper Исследование эффективности векторизации гнезд циклов с нерегулярным числом итераций
\jour Программные системы: теория и приложения
\yr 2019
\vol 10
\issue 4
\pages 77--96
\mathnet{http://mi.mathnet.ru/ps356}
\crossref{https://doi.org/10.25209/2079-3316-2019-10-4-77-96}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/ps356
  • https://www.mathnet.ru/rus/ps/v10/i4/p77
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Программные системы: теория и приложения
    Статистика просмотров:
    Страница аннотации:140
    PDF полного текста:119
    Список литературы:20
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024