|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Построение однопроцессорного расписания с минимизацией пикового использования ресурса при помощи муравьиного алгоритмастатья
- Авторы: Абрамов А.В., Чупахин А.А.
- Сборник: Программные системы и инструменты: тематический сборник № 22
- Редактор: Писковский Виктор Олегович
- Том: 22
- Год издания: 2022
- Издательство: ООО "МАКС Пресс"
- Местоположение издательства: Москва
- Первая страница: 26
- Последняя страница: 39
- Номер статьи: 2
- Аннотация: Эффективность использования ресурсов в вычислительных системах (ВС) тесно связана с планированием заданий. Частью указанного процесса является решение задачи составления расписаний. Традиционно решение таких задач направлено на минимизацию общего времени выполнения всех заданий, но часто появляются дополнительные ограничения, связанные с вычислительными ресурсами. Причём нередко такие ресурсы оказываются недешёвыми. Таким образом, при построении ВС возникает вопрос: как определить необходимый для ВС объём ресурсов, которого точно хватит для организации вычислительного процесса и не окажется в избытке? В данной работе рассматривается проблема построения оптимального расписания с точки зрения уменьшения пикового потребления памяти ВС. ВС состоит из одного процессора, способного в каждый момент времени обрабатывать лишь одно задание. На вход алгоритму планирования подаётся ориентированный ациклический граф заданий, в котором рёбра представляют собой зависимости по данным между ними. Результат выполнения каждого задания занимает некоторый объем памяти ВС до тех пор, пока не выполнятся все непосредственные потомки данного задания. Необходимо построить расписание, минимизирующее пиковое потребление памяти. В работе приведена математическая постановка рассматриваемой задачи, показана ее NP-трудность, проведён обзор различных алгоритмов построения расписаний. Для решения поставленной задачи были выбраны муравьиный алгоритм (МА) и алгоритм имитации отжига (ИО). Приведены их реализации, а также предложены модификации для МА, в числе которых локальный поиск и подход Ant-Q, основанный на обучении с подкреплением. Проведено экспериментальное исследование свойств разработанных алгоритмов на синтетических данных и данных, предоставленных компанией ООО «Техкомпания Хуавэй».
- Добавил в систему: Чупахин Андрей Андреевич