научная статья по теме АГРЕГИРОВАНИЕ ДАННЫХ ПРИ ДИСПЕТЧЕРИЗАЦИИ РЕСУРСОЕМКИХ ВЫЧИСЛЕНИЙ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ Кибернетика

Текст научной статьи на тему «АГРЕГИРОВАНИЕ ДАННЫХ ПРИ ДИСПЕТЧЕРИЗАЦИИ РЕСУРСОЕМКИХ ВЫЧИСЛЕНИЙ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ»

ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 1, с. 104-113

КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^^^ МЕТОДЫ

УДК 519.85

АГРЕГИРОВАНИЕ ДАННЫХ ПРИ ДИСПЕТЧЕРИЗАЦИИ РЕСУРСОЕМКИХ ВЫЧИСЛЕНИЙ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

© 2014 г. Ю. Е. Малашенко, И. А. Назарова

Москва, ВЦ РАН Поступила в редакцию 25.07.13 г., после доработки 10.09.13 г.

Рассматривается процесс управления ресурсоемкими вычислениями в гетерогенной специализированной системе. Для каждой задачи вводится понятие вычислительной работы, необходимой для ее решения. Исследуются две взаимосвязанные проблемы — допустимости и быстродействия. Предложен параметрический подход к планированию, позволяющий в условиях неопределенности сбалансированно распределять ресурсы и выполнять требования пользователей.

DOI: 10.7868/S0002338814010089

Введение. Рассмотрим проблему управления гетерогенной высокопроизводительной системой, выполняющей ресурсоемкие вычислительные задания. Процедуры обработки заданий можно определить как случайный перебор с неизвестным исходом [1]. Решение задач из данного класса сводится к поиску фрагмента с наперед заданными свойствами — уникального фрагмента, в массиве исходных данных. Последний состоит из большого числа отдельных, неделимых, одинаковых по размеру, содержательно значимых фрагментов. Задача считается решенной, как только в предъявленном наборе данных удается выявить уникальный фрагмент. В противном случае необходимо убедиться, что таковой в массиве отсутствует, и тем самым завершить задание. Заявки-задания поступают в систему в произвольные моменты времени, обработка всех и каждой из них должна быть завершена в максимально сжатые сроки.

Перебор массива исходных данных для каждой из задач требует большого, точно не известного объема вычислений. В общем случае можно указать только верхнюю оценку для величины вычислительных затрат, необходимых для выполнения конкретного задания; имеет ли решение соответствующая содержательная задача — неизвестно. Таким образом, при планировании работ возникает неопределенность, связанная c моментами поступления заявок, с составом и длительностью обработки заданий, а также с потенциальной возможностью получить решение.

Описанный выше специальный класс задач в [2] определен как citu-задания, citu-задачи; от английского термина: computation — intensive — task — under — uncertainty. Следует выделить целый ряд существенных особенностей, присущих изучаемому классу: все citu-задачи выполняются в режиме реального времени, допускают распараллеливание по данным и являются ресурсоемкими; их решения одинаково важны и должны быть получены — каждое в отдельности и все в совокупности — как можно быстрее.

В данной статье для анализа проблемы управления гетерогенной специализированной высокопроизводительной системой (СВС), выполняющей citu-задания, предлагается ввести понятие вычислительной работы, которая измеряется числом специализированных элементарных вычислительных операций (СЭВ-операций). Каждая СЭВ-операция состоит в просмотре одного фрагмента данных определенного вида и проверке его уникальности. Переборный алгоритм просмотра и проверки на уникальность фрагментов исходного массива citu-задачи будем называть ^-процедурой.

Согласно предлагаемой концептуальной схеме, планирование работ осуществляется на основании результатов, полученных с помощью математических моделей. В рамках предположений, формирующих модель, считается, что citu-задания различных видов поступают в СВС в произвольные моменты времени без каких-либо особых признаков, отношений предпочтения или предписанного порядка обслуживания, а исходный массив фрагментов данных для каждого из них становится известен после предварительного анализа в СВС. При этом, с одной стороны, ре-

шения всех поступивших задач должны быть получены как можно быстрее, с другой—вычислительные ресурсы СВС ограничены, и при наличии большого числа заданий могут образовываться очереди, вызванные чрезмерной загрузкой имеющихся устройств. Возникает типичная проблема, связанная с разделением ограниченного ресурса. А именно: способна ли СВС удовлетворить имеющиеся запросы-требования на заданном временном интервале (вопрос о допустимости системы) или следует изменить зафиксированный плановый период, чтобы выполнить все необходимые работы (вопрос о быстродействии системы)? Ответы на оба вопроса взаимосвязаны. Действительно, если мощности СВС недостаточно для обработки в операционном окне выбранного объема работ, то либо следует увеличить время их выполнения, либо уменьшить последний. В настоящей статье на основе агрегированных показателей анализируется допустимость требований запланированной на заданном интервале работы и определяется минимально возможное время ее выполнения.

1. Описание модели. Далее при математическом описании будем говорить об абстрактной гетерогенной высокопроизводительной СВС, в которой в условиях неопределенности выполняются разнородные работы. Считается, что указанная СВС состоит из центрального управляющего устройства (ЦУП-устройства) и набора независимых исполняющих единичных вычислительных модулей (ЕВ-модулей) различных конструктивных типов. В ЦУП-устройстве происходит анализ поступающих заданий, определяется порядок их выполнения, а также осуществляется контроль за процессом обработки; ЕВ-модули непосредственно выполняют вычислительную работу — поиск уникального фрагмента.

Массив исходных данных любого задания допускает разбиение на отдельные независимые части, которые не требуют синхронизации в процессе обработки. Снятие требования синхронизации позволяет применить методы оптимизации [3] при планировании, организовать гибкое динамическое управление и повысить эффективность использования вычислительных ресурсов. Процесс диспетчеризации ресурсоемких вычислений разбивается контрольными точками на отдельные этапы — плановые периоды или операционные окна, а распараллеливание и распределение работ происходит с учетом текущей производительности ресурсов. Шаг по времени равен плановому периоду или операционному окну. В используемых математических моделях динамика обработки массивов исходных данных описывается системой неравенств и конечно-разностных уравнений в дискретном времени.

Общая схема работы СВС состоит в следующем. Вся исходная и текущая информация о ейи-за-даниях, как вновь поступивших, так и находящихся в обработке, помещается и далее хранится в базе данных заданий (БД-заданий). В контрольной точке принятия решения I по команде администратора в программном комплексе планирования (ПК-плане) анализируются текущие данные о ходе выполнения всех заданий, находящихся в СВС. Здесь I — начальный момент очередного планового периода. Далее администратор (специалист и/или алгоритмическая процедура) выбирает число единиц календарного времени А(1) — длительность планового периода, в ПК-плане формируется пакет текущих работ (ТР-пакет), который состоит из подмассивов (поднаборов) неделимых фрагментов данных тех заданий, которые будут обрабатываться в СВС в течение А(1). ПК-план помещает ТР-пакет в специальный буфер текущих работ (ТР-буфер) и, начиная с момента I, СВС выполняет плановую работу на всех работоспособных ЕВ-модулях.

Далее в тексте верхний индекс любой переменной будет всегда относиться к типу вычислительного модуля, а нижний (один или два) в зависимости от рассматриваемого случая отвечать номеру и виду задачи соответственно. Для того, чтобы избежать путаницы, второй нижний идентификатор, соответствующий виду задачи, помещен в скобки. При модельном описании СВС используются следующие обозначения: Е — набор (множество) ЕВ-модулей различных типов; М — общее число типов ЕВ-модулей, из которых состоит рассматриваемая СВС; ет — отдельный

ЕВ-модуль (устройство) т-го типа; Ет — множество ет ЕВ-модулей т-го типа, т = 1, М, следовательно, множество Е всех ЕВ-модулей в СВС можно записать в виде объединения

Е = Е1 и Е2 и... и ЕМ.

Для формального описания заданий будут использоваться следующие обозначения: 1„ — задание-задача с собственным номером п; К — общее число различных видов заданий, которые могут обрабатываться в данной СВС; — задание с собственным идентификационным номером п,

для которого явно указан вид к, к = 1, К. Данное обозначение введено для удобства прочтения формул, описывающих процесс обработки заданий определенного вида.

В зависимости от контекста через t обозначим либо текущий календарный момент времени, либо контрольную точку принятия решения. Таким образом, t не является переменной в традиционном смысле, это обозначение определенных моментов времени в модельном описании процесса. Для множества %(t) — заданий zn, находящихся в СВС в момент t, обозначим через Л(0 множество номеров (индексов) заданий zn из %(t); N(t) — общее число заданий zn из %(t). Таким образом |^(t)| = |Л(0| = N(t); %k(t) — множество заданий k-го вида; Nk(t) — множество номеров (индексов) заданий k-го вида; Nk(t) — общее число заданий k-го вида. Тогда

к к к

% (t) = U %k( t), Л (t) = U Xk{t), N(t) = £ Nk( t).

к = i к = i k = 1

Пусть t°„ — календарный момент поступления задания zn в СВС; Tn(t) = t — t°„ — длительность промежутка времени, в течение которого задание zn находится в СВС при условии, что на момент t оно еще не выполнено до конца, т.е. Tn(t) — время пребывания zn в СВС от поступления до текущего

момента t, если zn не завершено; t+ — момент завершения задания zn и/или его удаления из СВС; T+ = t+ — t°„ — длительность промежутка времени, в течение которого задание zn обрабатывалось и находилось в СВС, т.е. T+ — время пребывания zn в системе.

D У

В моделях предполагается, что для каждого задания zn в момент поступления tn становится известна нормативная величина Zn — общее число фрагментов данных задания zn которые необходимо будет обработать, если среди них нет уникального.

Обозначим через yn априори неизвестное число фрагментов данных, которые будут в действительности просмотрены и проверены на уникальность при решении zn или для завершения zn. Тогда Zn является верхней оценкой для объема работы (измеряемого в СЭВ-операциях), который необходимо будет пр

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком