ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2012, № 4, с. 52-61
КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^^^ МЕТОДЫ
УДК 519.85
МОДЕЛЬ УПРАВЛЕНИЯ РАЗНОРОДНЫМИ ВЫЧИСЛИТЕЛЬНЫМИ ЗАДАНИЯМИ НА ОСНОВЕ ГАРАНТИРОВАННЫХ ОЦЕНОК ВРЕМЕНИ ВЫПОЛНЕНИЯ
© 2012 г. Ю. Е. Малашенко, И. А. Назарова
Москва, ВЦ РАН Поступила в редакцию 23.01.12 г., после доработки 12.03.12 г.
Рассмотрена динамическая модель управления обработкой ресурсоемких заданий с неизвестным временем выполнения, допускающих произвольное распараллеливание по данным, в гетерогенной вычислительной системе. На основе полученных гарантированных оценок формируется диспетчерское правило, в соответствии с которым в первую очередь обслуживаются задачи с наименьшим собственным временем решения.
Введение. В современной практике применения высокопроизводительных вычислительных систем большую группу составляют потоковые задачи обработки информации [1]. В качестве примеров таких задач можно привести: поиск внеземных цивилизаций на основе обработки радиосигналов, принимаемых из космоса; выявление артефактов на снимках пустынь в Африке, Азии, Южной Америке; определение автора, источника и языка оригинала по неизвестному отрывку текста с помощью электронных переводчиков во всех библиотеках мира; обслуживание поискового запроса, требующего просмотра большого количества данных в Интернете.
При формальном подходе к перечисленным практическим проблемам вычислительное задание для каждой из них состоит в следующем: из имеющегося набора данных требуется выделить фрагмент с определенными уникальными свойствами. Для достижения поставленной цели массив начальных данных сначала можно разбить на неделимые, содержательно значимые фрагменты, а затем для каждого из них применить некоторую специальную алгоритмическую процедуру. Когда в процессе просмотра массива данных удается выявить уникальный фрагмент, говорят, что задача обработки информации решена и выполнение задания прекращается. Если же в ходе вычислительного процесса приходится просматривать весь массив предъявленных данных и попытки найти уникальный фрагмент терпят неудачу, то задание считается выполненным, а поставленная задача — нерешенной, так как цель не достигнута.
Далее будем предполагать, что процесс выделения уникального фрагмента проходит следующие основные этапы:
создание и/или рекуррентное описание большого массива отдельных фрагментов данных; формулировка правила, по которому некоторый фрагмент объявляется уникальным; выбор случайным образом фрагмента из массива и проверка его уникальности. Каждой из перечисленных выше исходных задач обработки информации свойственны следующие общие черты:
просмотр данных требует большого объема вычислений, т.е. является ресурсоемким; возможна одновременная обработка различных фрагментов исходных данных, т.е. распараллеливание процесса вычислений;
о существовании решения соответствующей содержательной задачи становится известно только по окончании выполнения вычислительного задания, т.е. возникает неопределенность, связанная с потенциальной возможностью найти уникальный фрагмент;
и как следствие — для каждого конкретного задания можно указать только верхнюю оценку величины затрат вычислительных ресурсов, необходимых для его выполнения, т.е. возникает неопределенность, связанная с длительностью обработки каждого задания и/или с объемом требуемых затрат.
Специальный класс задач, обладающих обозначенными выше свойствами, будем далее для краткости называть citu-задания, citu-работы, citu-задачи (от английского термина computationally intensive task (under) uncertainty, который можно перевести как ресурсоемкие вычислительные задания, выполняемые в условиях неопределенности).
Каждая еки-задача может иметь свои особенности, поэтому при реализации алгоритмических процедур поиска уникального фрагмента следует учитывать следующее:
возможно разбиение массива данных на отдельные, даже пересекающиеся подмножества (например, при анализе снимков земной поверхности решение исходной задачи может быть получено в результате обработки подмассива данных);
для завершения задачи часто не требуется обработки всех наборов данных — достаточно найти один уникальный фрагмент (например, для поиска первоисточника по отрывку текста), или наоборот — необходимо найти все уникальные фрагменты (например, для поискового запроса в Интернете) и т.п.
СИи-работы выполняются в рамках Грид мощными университетскими центрами или группами добровольцев. Состав ресурсов внутри таких систем, как Грид, может варьироваться от переносных компьютеров отдельных пользователей, интересующихся соответствующими проблемами, до мощных кластеров, содержащих большое число процессоров со специальными ускорителями. Обращение к системам Грид предполагает совместное использование вычислительных ресурсов, включая программное обеспечение, базы данных, а также вычислительные модули, группами конкурирующих, сотрудничающих или взаимосвязанных потребителей.
В современной практике для решения определенных классов еки-задач используются гетерогенные специализированные вычислительные системы (СВС). В случаях, когда гетерогенная СВС способна обрабатывать несколько разнородных ейи-задач одновременно, при планировании вычислительных работ возникает неопределенность, связанная как с моментами поступления и составом набора заданий, так и с длительностью их обработки. Тогда возникает классическая научно-техническая проблема, которая заключается в отыскании способов эффективного распределения разнотипных ресурсов между различными потребителями [2]. Ряд аспектов указанной проблемы анализируется в [3], где содержится не претендующий на полноту обзор литературы по данному вопросу. В нашей стране имеются примеры успешных реализаций программных комплексов [4, 5] и массово-параллельных систем [6], обязательным элементом которых является пакетирование фрагментов данных, что сокращает процедуры обмена, повышает надежность и упрощает управление в условиях гетерогенности аппаратно-программной среды
[7-11].
В настоящей работе, продолжающей исследования, начатые в [12-14] с помощью имитационного моделирования и теории вероятностей, предлагается модель управления распределением вычислительных ресурсов, базирующаяся на методах оптимизации [15] и принципе гарантированного результата [16].
1. Описание модели. Рассмотрим динамическую модель (М-модель) управления работой гетерогенной вычислительной системы, в которой в условиях неопределенности решаются ейи-за-дачи - ресурсоемкие разнородные вычислительные работы, допускающие распараллеливание по данным. Для целей модельного описания предполагается, что еки-задания выполняются на СВС, которая состоит из центрального управляющего устройства (ЦУП-устройства) и набора независимых исполняющих единичных вычислительных модулей (ЕВ-модулей). Ски-задачи поступают в СВС в произвольные моменты времени, без каких-либо особых признаков, отношений предпочтения или предписанного порядка обслуживания. Считается, что для решения каждой ейи-задачи достаточно найти хотя бы один уникальный фрагмент.
Схематично процесс обработки ейи-задач в СВС можно описать следующим образом. Все имеющиеся на данный момент ейи-задачи анализируются и подготавливаются к исполнению на входе в СВС. Вся информация о еки-заданиях, вновь поступивших или находящихся в обработке, заносится и далее хранится в так называемой базе данных заданий (БД-заданий). Информация из последней в реальном времени обрабатывается программным комплексом анализа и планирования, где формируется пакет текущих работ, который состоит из подмассивов (поднабо-ров) неделимых фрагментов данных для всех имеющихся еки-заданий.
В основу комплекса планирования и анализа (ПК-план) положено несколько взаимосвязанных математических моделей, с помощью которых осуществляется оптимизация процесса обработки еки-заданий, находящихся в СВС. В каждый контрольный момент времени вновь сформированный пакет текущих работ (ТР-пакет) поступает в промежуточный буфер данных текущих работ (БДТ-работ) и начинает выполняться на всех работоспособных ЕВ-модулях. Одновременно с обработкой происходит формирование нового ТР-пакета, который поступает в БДТ-работ в следующий контрольный момент времени. Работа комплекса завершается, когда БД-заданий оказывается пустой, т.е. когда решены все поступившие в СВС ейи-задачи.
В [17] алгоритмическая процедура решения еки-задач из рассматриваемого далее специального класса определяется как случайный перебор с неизвестным исходом. Для формализации описания процедуры выполнения отдельного еки-задания используем известную теоретическую конструкцию — случайную выборку шаров из урны без возвращения. В рамках М-модели каждому еки-заданию отвечает урна с шарами двух цветов, а процесс его выполнения рассматривается как извлечение шаров из урны и определение их цвета. Каждому неделимому содержательному фрагменту исходных данных ставится в соответствие отдельный шар, а каждому уникальному фрагменту — шар определенного цвета. Пусть, например, в урне находятся черные и белые шары, при этом уникальному фрагменту отвечает черный, тогда решение задачи сводится к отысканию и извлечению из урны первого черного шара. Если он найден — выполнение задания прекращается, а задача полагается решенной.
Будем говорить, что задание завершено, но задача не имеет решения, если после извлечения из урны все шары оказались одного, не соответствующего уникальному фрагменту, цвета. Указанное событие в реальности означает, что при обработке и просмотре всех предъявленных фрагментов данных уникальный среди них не обнаружен. Формально приходится признать вычислительную работу выполненной, хотя цель не достигнута — поиск ничего не дал. К такому результату может привести сбой в работе вычислительной системы, неправильная подготовка данных для еки-задания и ряд других причин.
В рамках М-модели считается, что исходные еки-задания бывают разных видов, вернее, исходные данные могут иметь разную физическую природу и содержательный смысл. Такие ейи-задания требуют обработки отличающимися друг от друга алгоритмическими процедурами н
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.