ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2012, № 5, с. 15-22
= КОМПЬЮТЕРНЫЕ МЕТОДЫ
УДК 519.85
УПРАВЛЕНИЕ РЕСУРСОЕМКИМИ РАЗНОРОДНЫМИ ВЫЧИСЛИТЕЛЬНЫМИ ЗАДАНИЯМИ С ДИРЕКТИВНЫМИ
СРОКАМИ ОКОНЧАНИЯ
© 2012 г. Ю. Е. Малашенко, И. А. Назарова
Москва, ВЦ РАН Поступила в редакцию 12.03.12 г.
Рассмотрена динамическая модель управления обработкой ресурсоемких задач, допускающих произвольное распараллеливание по данным, в гетерогенной вычислительной системе. Длительность выполнения заданий не известна, однако сроки их решения должны быть согласованы и заданы. Для наихудшего случая получены гарантированные оценки времени завершения каждой задачи. Предложенная модель позволяет учитывать и минимизировать максимальную величину возможного превышения назначенных сроков для любого набора исходных заданий.
Введение. В настоящее время конвейерные процессоры с динамически перестраиваемой архитектурой на базе БРОЛ (ПЛИС) [1, 2] являются наиболее перспективными элементами для построения мощных вычислительных комплексов. Различными группами исследователей-пользователей и инженеров-системщиков изучаются возможности распараллеливания исполнения программ, реконфигурации архитектуры системы под решение определенных вычислительных проблем. Для управления такими системами необходимы и разрабатываются интерактивные сценарии диалога диспетчер — пользователь в декларативной, частично вербальной, частично технологической, постановке: задание — требования — возможности — сроки.
В настоящей работе предлагается модель для анализа и планирования процедуры обработки ресурсоемких вычислительных заданий, которые определены и подробно описаны в [3] как ски-задания (ски-задачи, ски-работы), выполняемые в условиях неопределенности. Каждая из ски-задач заключается в выделении фрагмента с наперед заданными свойствами из большого массива исходных данных, ее решение осуществляется с помощью перебора. В процессе просмотра возникает объективная неопределенность, связанная как с длительностью поиска, так и с потенциальной возможностью получить решение. Здесь кратко отметим, что все ски-задания:
1) выполняются в режиме реального времени [4];
2) допускают распараллеливание по данным [5];
3) является ресурсоемкими.
В современной практике для решения ски-задач используются гетерогенные специализированные вычислительные системы. В случаях, когда такая система способна обрабатывать несколько разнородных ски-задач одновременно, при планировании вычислительных работ возникает научно-техническая проблема, которая заключается в отыскании способов эффективного распределения разнотипных ресурсов между различными работами, выполняющимися в заданных временных рамках.
В данной работе рассматривается следующая проблема. Диспетчеру специализированной системы, состоящей из большого числа вычислительных модулей различных типов, взаимосвязанные пользователи (клиенты) в случайные моменты времени предоставляют для решения разнородные ски-задачи. Все задания должны быть завершены все вместе и каждое в отдельности как можно быстрее, но не позднее определенного срока. В противном случае полученное решение может потерять актуальность и не будет представлять интереса.
Массив исходных данных для каждой из ски-задач состоит из одинаковых по размеру отдельных неделимых содержательно значимых фрагментов и становится известен после появления задачи в системе. Выполнение отдельной ски-работы прекращается, когда обнаружен фрагмент, удовлетворяющий наперед заданному критерию — уникальный фрагмент, или если просмотрен весь массив, но ничего найти не удалось. Считается, что архитектура вычислительной системы позволяет просматривать наборы фрагментов каждого ски-задания в произвольном порядке, в том числе параллельно, т.е. каждая часть данных может обрабатываться независимо от других.
Диспетчер-планировщик в реальном времени должен:
1) распределять вычислительные ресурсы таким образом, чтобы при выполнении ни одно из равнозначных заданий равноправных пользователей не оказалось в худшей ситуации, чем остальные;
2) завершать каждое конкретное задание до наступления назначенного срока.
В литературе при проектировании современных систем реального времени в основном рассматриваются "жестко" заданные директивные сроки окончания, нарушение которых может иметь фатальные последствия. При анализе и управлении такими системами предлагается учитывать и ориентироваться на наихудший случай развития ситуации, в котором директивный срок окончания может быть превышен [6].
Настоящая статья посвящена изучению функционирования гетерогенного вычислительного комплекса, исполняющего разнородные работы с более мягкими временными ограничениями. В рассматриваемой модели управления предполагается, что при поступлении citu-задачи в систему с учетом объективных показателей и имеющихся требований определяется возможное время ее завершения в наихудшем случае. Если эта оценка — срок, к которому citu-задание может быть закончено, устраивает клиента, то оно принимается для обработки, и ему присваивается директивный срок окончания, совпадающий с прогнозируемым. Таким образом, директивный срок окончания (ДСО) — это установленный диспетчером и согласованный с пользователем момент календарного времени, до наступления которого citu-задача должна быть решена. Дальнейшее планирование осуществляется исходя из предположения, что события будут носить самый негативный характер, при этом ДСО используется как ограничение при формировании диспетчерских правил совместного выполнения всех заданий, находящихся в специализированной вычислительной системе.
Заметим, что понятие ДСО, введенное выше, несколько разнится от классического dead-line [7], поскольку устанавливается диспетчером, а не пользователем системы, хотя и по договоренности с последним. Однако принятое допущение больше соответствует реальной ситуации, в этом случае citu-работа, которая не может быть выполнена по объективным причинам, будет сразу отклонена, что позволит решить другие задачи в срок; и дает возможность диспетчеру более гибко подходить к формированию пакета текущих заданий.
Данная работа продолжает исследования, начатые в [3, 8—10], однако отличается от них методами изучения и конечной целью. В [8—10] с помощью имитационного моделирования и теории вероятностей анализировались временные показатели длительности обработки citu-заданий. В [3] предложены способы повышения производительности системы и уменьшения относительных задержек выполнения. В настоящей статье показано, как, опираясь на методы оптимизации [11] и принцип гарантированного результата [12], можно оценить и минимизировать максимальную величину возможного превышения установленных сроков завершения для любого набора исходных citu-заданий.
Перейдем к описанию математической модели (М-модели), которая используется при планировании и реализации диспетчерских правил по соблюдению ДСО.
1. Описание модели. Для целей модельного описания будем говорить об абстрактной гетерогенной специализированный вычислительной системе (СВС), в которой в условиях неопределенности выполняются разнородные citu-работы. Пусть указанная СВС состоит из центрального управляющего устройства (ЦУП-устройства) и набора независимых исполняющих единичных вычислительных модулей (ЕВ-модулей) различных конструктивных типов. Далее в тексте верхний индекс будет всегда относиться к типу вычислительного модуля, а нижний (один или два) в зависимости от рассматриваемого случая — отвечать номеру и виду задачи соответственно. Для того, чтобы избежать путаницы, второй нижний идентификатор, соответствующий виду задачи, помещен в скобки и по нему не производится суммирование.
Для описания СВС введем следующие обозначения: H — ЦУП-устройство, в котором происходит анализ входного потока, определяются ДСО и порядок выполнения заданий, а также осуществляется контроль за ходом их обработки; E — набор (множество) ЕВ-модулей нескольких типов. Пусть M— общее число различных типов ЕВ-модулей, из которых состоит рассматриваемая СВ-система; em —
ЕВ-модуль (устройство) m-го типа; Eп — множество ЕВ-модулей m-го типа em, m = 1, M, следовательно, множество E всех ЕВ-модулей в СВС можно записать в виде объединения
E = E 4J E 2(J...(J EM.
Под специализированной элементарной вычислительной операцией (СЭВ-операция) будем понимать просмотр отдельного неделимого содержательно значимого фрагмента данных опре-
деленного вида и проверку его уникальности. Предполагается, что каждый конкретный ЕВ-мо-дуль может выполнять СЭВ-операции по крайней мере одного вида, а производительность конкретного ЕВ-модуля при выполнении citu-заданий разных видов неодинакова и может меняться (перегрев оборудования, изменение тактовой частоты или работа с другим программным обеспечением). Кроме того, будем считать, что ЕВ-модули с течением времени могут выходить из строя. В зависимости от контекста через t обозначим либо текущий календарный момент времени, либо контрольную точку принятия решения. Здесь и далее t не является непрерывной переменной, это фиксированный момент времени.
Пусть pmk(t) — быстродействие и/или производительность ЕВ-модуля m-го типа, т.е. модуль em может выполнять в единицу времени p^it) СЭВ-операций к-го вида начиная с момента t; Rm(t) — общее число работоспособных ЕВ-модулей m-го типа на момент времени t; Pk(t) — максимальное число СЭВ-операций к-го вида, которые можно выполнить в единицу времени на СВС начиная с момента t на всех работоспособных ЕВ-модулях, тогда
M
рк(t) = X pm(t)Rm(t), k=и.
m = 1
Будем считать, что СВС может одновременно обрабатывать как одно, так и несколько заданий на всех действующих в данный момент ЕВ-модулях. Отдельное citu-задание может быть разделено на подзадания, каждое из которых в свою очередь выполняется самостоятельно или в составе некоторого набора (пакета). В рамках рассматриваемой М-модели предполагается, что citu-задания поступают в СВС в произвольные моменты времени без каких-либо особых признаков, отношений предпочтения или предписанного порядка обслуживания; и для решения каждой citu-задачи достаточно найти хотя б
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.