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

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

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



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






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


Программные системы: теория и приложения, 2019, том 10, выпуск 4, страницы 77–96 (Mi ps356)  

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

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

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

Межведомственный суперкомпьютерный центр РАН

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

Ключевые слова и фразы: векторизация, AVX-512, гнезда циклов с нерегулярным числом итераций, сортировка Шелла, теоретическое ускорение.

Финансовая поддержка Номер гранта
Российская академия наук - Федеральное агентство научных организаций АААА-А19-119011590098-8
Работа выполнена в МСЦ РАН в рамках государственного задания по теме 0065-2019-0016 (reg. no. АААА-А19-119011590098-8).


DOI: https://doi.org/10.25209/2079-3316-2019-10-4-77-96

Полный текст: PDF файл (1663 kB)

Тип публикации: Статья
УДК: 519.681.5:004.272.25
ББК: З973.1
MSC: Primary 68W10; Secondary 65P99, 68M07
Поступила в редакцию: 28.02.2019
Подписана в печать : 30.11.2019

Образец цитирования: А. А. Рыбаков, С. С. Шумилин, “Исследование эффективности векторизации гнезд циклов с нерегулярным числом итераций”, Программные системы: теория и приложения, 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}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/ps356
  • http://mi.mathnet.ru/rus/ps/v10/i4/p77

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Программные системы: теория и приложения
    Просмотров:
    Эта страница:2
    Полный текст:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020