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

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

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



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






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


Программные системы: теория и приложения, 2018, том 9, выпуск 4, страницы 493–508 (Mi ps326)  

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

К автоматическому порождению программ трафаретных вычислений с улучшенной временной локальностью

А. В. Климов

Институт проблем проектирования в микроэлектронике РАН

Аннотация: Трафаретные (stencil) алгоритмы широко используются в задачах математического моделирования на регулярных сетках, эволюции клеточных автоматов (типа игры «жизнь»), обработки изображений, анализа последовательностей и т.п. Такие алгоритмы хорошо параллелятся, но обычные подходы к распараллеливанию имеют низкую временную локальность, что ограничивает их масштабируемость. Избавление от этого недостатка возможно при использовании различных схем переупорядочения обработки точек, когда пространство разбивается на небольшие области, помещающиеся в кэш, в которых удается продвинутся сразу на несколько итераций. Однако, такие схемы трудно программируются и отлаживаются. Есть несложный метод пирамид, но он плохо масштабируется, поскольку влечет дублирование вычислений.
Наш подход состоит в использовании более сложных схем переупорядочения без дублирования, для которых код может генерироваться автоматически из относительно несложной спецификации схемы. При этом сами схемы задаются путем назначения функций распределения вычислительных узлов по пространству и времени. В этой статье излагается подход, и рассматриваются на простом примере различные варианты кода, порождаемые по различным функциям распределения.

Ключевые слова и фразы: трафаретные алгоритмы, параллельные вычисления, автоматизация распараллеливания, временная локальность, метод пирамид, потоковая модель вычислений, планирование вычислений, распределение вычислений.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 17-07-00324_а
17-07-00478_а
Работа выполнена при поддержке РФФИ (гранты №№ 17-07-00324, 17-07-00478).


DOI: https://doi.org/10.25209/2079-3316-2018-9-4-493-508

Полный текст: PDF файл (1657 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 004.4' 24
ББК: 32.973.2
MSC: Primary 97P40; Secondary 97P50, 97R40
Поступила в редакцию: 25.11.2018
19.12.2018
Подписана в печать : 30.12.2018

Образец цитирования: А. В. Климов, “К автоматическому порождению программ трафаретных вычислений с улучшенной временной локальностью”, Программные системы: теория и приложения, 9:4 (2018), 493–508

Цитирование в формате AMSBIB
\RBibitem{Kli18}
\by А.~В.~Климов
\paper К автоматическому порождению программ трафаретных вычислений с улучшенной временной локальностью
\jour Программные системы: теория и приложения
\yr 2018
\vol 9
\issue 4
\pages 493--508
\mathnet{http://mi.mathnet.ru/ps326}
\crossref{https://doi.org/10.25209/2079-3316-2018-9-4-493-508}


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

    ОТПРАВИТЬ: 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
  • Программные системы: теория и приложения
    Просмотров:
    Эта страница:22
    Полный текст:9
    Литература:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019