ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 4, с. 28-42
КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^^^ МЕТОДЫ
УДК 519.85
УПРАВЛЕНИЕ РЕСУРСОЕМКИМИ ВЫЧИСЛЕНИЯМИ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ. I. МНОГОПАРАМЕТРИЧЕСКАЯ МОДЕЛЬ
© 2014 г. Ю. Е. Малашенко, И. А. Назарова
ВЦ РАН
Поступила в редакцию 14.01.14 г., после доработки 14.02.14 г.
Излагается комплекс моделей, алгоритмов и программ, разработанных для управления высокопроизводительной гетерогенной специализированной вычислительной системой, выполняющей разнородные задания. Представлена многопараметрическая модель, предназначенная для управления обработкой ресурсоемких разнородных вычислительных заданий, допускающих распараллеливание по данным. Модель опирается на методологию исследования операций, и для управления в условиях объективной неопределенности в ней используется принцип гарантированного результата. В процессе диспетчеризации в каждой контрольной точке вычисляются максиминные оценки неизвестных величин (время пребывания в системе, длительность обработки и др.), на основании которых формируются диспетчерские управляющие команды. Указанный подход позволит на практике реализовать принципиально новую дисциплину обслуживания, при которой в первую очередь решаются наименее ресурсоемкие задачи.
DOI: 10.7868/S0002338814040118
Введение. В настоящее время в нашей стране интенсивно развивается проектирование и создание высокопроизводительных вычислительных систем. Внедрение и использование последних преследует различные цели — от обучения студентов до решения узковедомственных задач. Многие специализированные вычислительные системы (СВС) предназначены для выполнения определенного вида работ и имеют конкретную совокупность составных частей: общее число и типы процессоров, архитектуру, программное обеспечение, базы данных и пр.
В отечественной практике существуют примеры реализаций систем управления ресурсоемкими вычислениями, например программный комплекс "Пирамида" [1, 2]. Последний имеет иерархическую древовидную архитектуру и обеспечивает высокую надежность вычислений за счет дублирования. При проектировании комплекса использовалась концепция "распределения машинного времени": каждая заявка получает некоторый статичный набор вычислительных ресурсов, динамическое перераспределение которых между заданиями в процессе обработки невозможно. Однако понятно, что подобное перераспределение способно повысить эффективность СВС.
В данной серии статей подробно описывается математическая модель управления гетерогенной высокопроизводительной вычислительной системой, выполняющей ресурсоемкие задания, которые относятся к специальному классу, определенному в [3] как citu-задания, citu-задачи (от английского термина computationally intensive task (under) uncertainty, который можно перевести как ресурсоемкие вычислительные задания, выполняемые в условиях неопределенности). Решение каждой такой задачи (выполнение задания) сводится к поиску уникального фрагмента в большом массиве исходных данных. Поиск осуществляется переборными алгоритмами. Задача считается решенной, как только в предъявленном наборе данных удается выявить уникальный фрагмент, характеристики, свойства или параметры которого задаются заранее. В противном случае необходимо убедиться, что таковой в массиве отсутствует, и тем самым завершить задание [4].
Перебор исходного массива неделимых, содержательно значимых фрагментов для каждой из citu-задач требует большого, точно не известного, объема вычислений. В общем случае можно указать только верхнюю оценку для величины вычислительных затрат, необходимых для выполнения конкретного задания; имеет ли решение соответствующая содержательная задача — неиз-
вестно. Заявки на решение citu-задач различных видов поступают в систему в произвольные моменты времени и должны быть выполнены каждая в отдельности и все в совокупности как можно быстрее.
При планировании вычислительных работ возникает неопределенность, связанная с моментами поступления заявок, с составом и длительностью их обработки, а также с потенциальной возможностью получить решение. Заявки-задачи выполняются в режиме реального времени, допускают распараллеливание по данным и являются ресурсоемкими.
В настоящей работе для описания особенностей самих citu-заданий, а также процессов управления их выполнением в условиях неопределенности используется многопараметрическая модель (далее МП-модель). Последняя является основной аналитической частью комплекса моделей и программ для управления ресурсоемкими вычислениями CORSAR [5]. При разработке МП-модели применялась методология исследования операций, что нашло свое отражение в аббревиатуре CORSAR (от английского Computation — Operation — Research — System — of — Algorithm — Resources).
Комплекс CORSAR предназначен для диспетчеризации citu-заданий, которые выполняются гетерогенной СВС. В данной серии статей описываются архитектура, организация, состав программных компонентов системы управления и МП-модель, положенная в основу блока планирования и анализа CORSAR.
1. Многопараметрическая диспетчеризация и математическая модель. При создании МП-модели и разработке схемы управления CORSAR учитывалось следующее обстоятельство — в рассматриваемом классе citu-задачи в определенном смысле персонифицированы: все они равнозначны, а пользователи, предоставляющие задачи для обработки, равноправны в рамках правил распределения вычислительных ресурсов и очередности обработки, поэтому стратегии управления СВС не должны быть дискриминирующими по отношению к той или иной группе заявок. Кроме того, применяется такое правило выполнения заданий, при котором ни один из партнеров не может улучшить временные характеристики выполнения своей заявки, не ухудшив соответствующие показатели своих коллег. Предполагается, что пользователи не являются антагонистами и стремятся к достижению некоторой общей корпоративной цели. Администратор СВС должен распределять вычислительные ресурсы так, чтобы временные характеристики выполнения отдельной заявки не были улучшены за счет ухудшения соответствующих показателей других заданий, находящихся в СВС. Для формирования правила обслуживания, отвечающего указанному требованию, в МП-модели используется показатель относительной задержки выполнения заданий, который позволяет поставить длительность пребывания конкретного задания в СВС в зависимость от работы, фактически необходимой для его завершения, хотя объем последней априори неизвестен.
В рамках МП-модели определяются гарантированные максиминные оценки [6] длительности пребывания каждого конкретного задания в СВС и необходимые параметры управления СВС. В результате формируются динамическая стратегия планирования и правило выполнения пакета заданий, при котором в первую очередь завершаются наименее ресурсоемкие citu-задания, требующие небольших объемов работы. Указанное правило выполнения текущихработ далее будет обозначаться аббревиатурой SWAP (от английского Short — Work — Ahead — Performance) [5, 7, 8].
В комплексе CORSAR для планирования и оценки времени пребывания в системе каждого конкретного citu-задания вводится понятие директивного срока окончания (ДСО) [9]. При поступлении заявки-задания в системе управления в первую очередь определяется возможное время ее завершения в наихудшем случае с учетом объективных показателей: загруженности СВС и имеющихся требований [10]. Если предварительная оценка — срок, к которому citu-задание может быть завершено, устраивает пользователя, то оно принимается для обработки и ему присваивается директивный срок окончания, совпадающий с прогнозируемым. В противном случае пользователь снимает свою заявку. Таким образом, ДСО — это установленный администратором и согласованный с пользователем момент календарного времени, до наступления которого citu-задача должна быть решена. ДСО, в частности, используется для планирования совместного выполнения всех заданий, находящихся в СВС. При моделировании предполагается, что в случае превышения ДСО произведенные вычислительные затраты записываются в производственные потери, которые администратору предписывается свести к минимуму.
При диспетчеризации СВС, где на разнотипном оборудовании выполняются разнородные citu-задания, возникает проблема эффективного использования имеющихся ресурсов. Скорость обработки отдельного задания на оборудовании различных типов может значительно отличать-
ся. Применение МП-модели позволяет оптимизировать распределение задач по имеющимся разнотипным ресурсами исходя из производительности последних, а также с учетом общей загруженности СВС.
С позиций математического моделирования проблема управления ресурсоемкими вычислениями в указанных условиях неопределенности является многокритериальной. По сути от администратора СВС требуется достижение одновременно нескольких различных целей:
эффективно использовать разнотипные вычислительные устройства и добиваться максимальной производительности СВС при выполнении разнородных заявок;
в условиях неопределенности завершать каждое задание в оговоренные с пользователями сроки; при диспетчеризации учитывать объем реальной, фактически необходимой вычислительной работы, требуемой для решения конкретной задачи, и устанавливать соответствующий порядок обработки заданий.
В МП-модели для описания процессов диспетчеризации в [5] было введено понятие вычислительной работы, необходимой для решения citu-задачи. Работа измеряется в числе специализированных элементарных вычислительных операций (СЭВ-операций). Каждая конкретная СЭВ-операция состоит в просмотре отдельного фрагмента данных и проверке его уникальности соответствующим переборным алгоритмом. При выполнении citu-задания число фрагментов данных, которые будут в действительности просмотрены до его завершения, априори неизвестно, т.е. объем необходимой работы для обнаружения уникального фрагмента определить заранее невозможно.
При диспетчеризации в комплексе CORSAR время выполнения текущих работ разбивается контрольными точками на отдельные этапы — плановые периоды или операционные окна. Объем работы, который будет выполнен
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.