Исследование алгоритмической сложности построения Парето-множества для принятия решения при распределении ресурсов вычислительных систем

Аннотация

Современные вычислительные системы функционируют в условиях гетерогенности узлов и переменной нагрузки, что обусловливает необходимость применения многокритериальных методов при распределении вычислительных ресурсов. Одним из таких методов является предсказательный метод распределения ресурсов на основе многокритериальной модели принятия решений, ключевым этапом которого служит построение множества Парето-оптимальных решений. Вместе с тем вычислительная сложность данного этапа и возможности ее снижения ранее не исследовались. Объектом исследования являются алгоритмы построения Парето-множества в задаче предсказательного распределения ресурсов в гетерогенных вычислительных системах. Цель работы состоит в анализе вычислительной сложности базового алгоритма оптимизации и исследовании методов ее снижения применительно к задачам многокритериального распределения ресурсов. Методология: в работе формализована постановка задачи построения Парето-множества, установлена теоретическая оценка сложности базового алгоритма. Рассмотрены и проанализированы три метода снижения вычислительной сложности: предварительная фильтрация альтернатив по ключевому критерию, ранняя остановка при попарном сравнении и инкрементальное построение Парето-множества. Экспериментальная часть: для экспериментального подтверждения теоретических оценок разработана программа моделирования, с помощью которой проведены три серии экспериментов: исследование зависимости от числа узлов n, от числа критериев k и от порогового параметра θ метода фильтрации. Полученные результаты позволяют обоснованно выбирать алгоритм построения Парето-множества в зависимости от масштаба системы, числа критериев и требований к полноте решения, что способствует повышению эффективности планировщика в многокритериальных системах распределения ресурсов реального времени.