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

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

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



Выч. мет. программирование:
Год:
Том:
Выпуск:
Страница:
Найти






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


Выч. мет. программирование, 2014, том 15, выпуск 4, страницы 579–592 (Mi vmp274)  

Автоматический выбор наиболее эффективных реализаций алгоритмов

А. А. Сиднев, В. П. Гергель

Нижегородский государственный университет им. Н.И. Лобачевского

Аннотация: Предложен подход к прогнозированию времени распределенных высокопроизводительных вычислений, не требующий проведения экспериментов на всех целевых вычислительных системах. Выбор оптимального алгоритма производится по информации об асимптотической сложности оцениваемых алгоритмов на основе использования методов машинного обучения. Предложенный в работе подход позволяет значительно сократить как количество экспериментов, так и размерность задач, которые решаются при оценке производительности вычислительной системы. Оценка времени выполнения алгоритмов по параметрам вычислительной системы позволяет определить, насколько вычислительная система эффективна при решении определенного класса задач без проведения экспериментов на ней. Возможно быстрое уточнение прогноза по минимальному числу экспериментов с малоразмерными задачами на целевой вычислительной системе. Предложенное решение может применяться и при автоматической настройке библиотеки перед ее использованием (подобно автоматической настройке в библиотеке ATLAS (Automatically Tuned Linear Algebra Software)). Выполнен сравнительный анализ результатов предсказания времени решения ряда задач на 84 вычислительных системах. Использование случайного леса в сочетании с методом наименьших квадратов показывает, что средняя относительная ошибка оценки времени выполнения составляет 17% при обучении на данных, соответствующих задачам малой размерности, и 9% при обучении на данных из всего диапазона изменения параметров алгоритма тестовой выборки. Полученные оценки позволяют выполнять выбор наиболее эффективной реализации алгоритма более чем в 80% случаев, а потери времени от ошибочного выбора не превосходят 6%.

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

Полный текст: PDF файл (393 kB)
Тип публикации: Статья
УДК: 004.852; 004.272.43
Поступила в редакцию: 24.08.2014

Образец цитирования: А. А. Сиднев, В. П. Гергель, “Автоматический выбор наиболее эффективных реализаций алгоритмов”, Выч. мет. программирование, 15:4 (2014), 579–592

Цитирование в формате AMSBIB
\RBibitem{SidGer14}
\by А.~А.~Сиднев, В.~П.~Гергель
\paper Автоматический выбор наиболее эффективных реализаций алгоритмов
\jour Выч. мет. программирование
\yr 2014
\vol 15
\issue 4
\pages 579--592
\mathnet{http://mi.mathnet.ru/vmp274}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/vmp274
  • http://mi.mathnet.ru/rus/vmp/v15/i4/p579

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