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

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

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



Информ. и её примен.:
Год:
Том:
Выпуск:
Страница:
Найти






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


Информ. и её примен., 2017, том 11, выпуск 3, страницы 113–122 (Mi ia492)  

On parallelization of asymptotically optimal dualization algorithms

[О распараллеливании асимптотически оптимальных алгоритмов дуализации]

E. V. Djukovaab, A. G. Nikiforovc, P. A. Prokofyeva

a Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
b M. V. Lomonosov Moscow State University, 1-52 Leninskiye Gory, GSP-1, Moscow 119991, Russian Federation
c Technische University of Munich, 21 Arcisstrasse, Munich 80333, Germany

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

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

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 16-01-00445_a
15-51-05059_Арм_а
Работа поддержана грантами РФФИ № 16-01-00445-a и № 15-51-05059.


DOI: https://doi.org/10.14357/19922264170313

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

Реферативные базы данных:

Тип публикации: Статья
Поступила в редакцию: 07.12.2016
Язык публикации: английский

Образец цитирования: E. V. Djukova, A. G. Nikiforov, P. A. Prokofyev, “On parallelization of asymptotically optimal dualization algorithms”, Информ. и её примен., 11:3 (2017), 113–122

Цитирование в формате AMSBIB
\RBibitem{DyuNikPro17}
\by E.~V.~Djukova, A.~G.~Nikiforov, P.~A.~Prokofyev
\paper On parallelization of asymptotically optimal dualization algorithms
\jour Информ. и её примен.
\yr 2017
\vol 11
\issue 3
\pages 113--122
\mathnet{http://mi.mathnet.ru/ia492}
\crossref{https://doi.org/10.14357/19922264170313}
\elib{http://elibrary.ru/item.asp?id=29992117}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/ia492
  • http://mi.mathnet.ru/rus/ia/v11/i3/p113

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