= КОМПЬЮТЕРНЫЕ МЕТОДЫ =
УДК 519.85
УПРАВЛЕНИЕ РЕСУРСОЕМКИМИ ВЫЧИСЛЕНИЯМИ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ. II. КОМПЛЕКС ДИСПЕТЧЕРИЗАЦИИ
© 2014 г. И. К. Купалов-Ярополк, Ю. Е. Малашенко, И. А. Назарова, А. Ф. Ронжин
Москва, Институт точной механики и вычислительной техники им. С.А. Лебедева РАН, ВЦ РАН Поступила в редакцию 03.03.14 г., после доработки 24.04.14 г.
Приводится описание модельного программного комплекса CORSAR, предназначенного для анализа правил диспетчеризации ресурсоемких разнородных задач переборного типа, допускающих распараллеливание по данным. При поиске решений исходные массивы разбиваются на отдельные содержательно значимые фрагменты, что позволяет использовать методы скользящего планирования и оптимизировать процессы распараллеливания при обработке заявок. Задания выполняются на высокопроизводительной гетерогенной специализированной вычислительной системе. Разработанная многопараметрическая модельная схема управления инвариантна к типам вычислительных ресурсов, обеспечивает их эффективное использование при эксплуатации, масштабируемость при модернизации и развитии системы.
DOI: 10.7868/S0002338814050102
Введение. В настоящее время во всем мире создается и вводится в эксплуатацию большое число инфокоммуникационных комплексов и сетей, в состав которых входят высокопроизводительные вычислительные системы (ВВС), предназначенные для решения ресурсоемких общенаучных проблем и практических задач. В связи с этим с особой остротой ощущается необходимость в разработке новых методов управления ВВС и способов диспетчеризации выполняемых ресурсоемких заданий. Комплексы диспетчеризации нового поколения призваны повысить эффективность использования ВВС, что должно расширить круг решаемых практических задач, сократить время реализации больших научных проектов, открыть новые направления использования методов математического моделирования для описания проблем окружающего мира.
Вследствие непрерывной модернизации и одновременного использования старого вполне работоспособного и нового суперсовременного оборудования любая ВВС со временем становится по сути гетерогенной. В частности, для многократного увеличения быстродействия алгоритмов отдельные вычислительные узлы дополнительно оснащаются специальными устройствами (ускорителями) [1]. В качестве элементной базы таких ускорителей могут использоваться заказные СБИС (ASIC) [2], БМК (eASIC) [3, 4], системы-на-кристалле (SoC) [5], ПЛИС [6], (FPGA)[7], графические сопроцессоры GPGPU [8]. Скорость обработки одного и того же задания на устройствах различных типов может отличаться в несколько раз. Некоторые ускорители предназначены для работы с конкретными алгоритмами, поэтому с их помощью эффективно решаются только определенные классы задач. Таким образом, сегодня сугубо практическая задача выбора управляющего программного обеспечения превратилась в сложную многокритериальную проблему планирования и повышения эффективности вычислительных систем.
В настоящей работе излагается макет программного обеспечения комплекса CORSAR (от английского Computation — Operations — Research — System — of — Algorithm — Resources). CORSAR используется для модельных расчетов при анализе управления высокопроизводительной гетерогенной специализированной вычислительной системой (СВС). СВС обрабатывает ресурсоемкие разнородные задачи, которые подробно описаны и обозначены в [9] как citu-задачи (от английского термина Computationally — Intensive — Task — (under) — Uncertainty, который можно перевести как ресурсоемкие вычислительные задания, выполняемые в условиях неопределенности). Решение последних осуществляется различными алгоритмическими процедурами переборного типа, которые последовательно просматривают
2
17
соответствующие массивы неделимых, содержательно значимых фрагментов исходных данных. Целью поиска является уникальный фрагмент с заранее указанными параметрами (характеристиками).
Решение осуществляется в оперативном режиме, в реальном времени, каждое задание должно быть завершено не позднее заранее оговоренного срока. Обработка соответствующих массивов данных требует большого, точно не известного объема вычислений. Задания-задачи поступают в вычислительную систему в произвольные моменты времени. Таким образом, при планировании и управлении вычислительными работами следует учитывать объективную неопределенность, связанную как с временем поступления и составом разнородных заданий, так и с длительностью их обработки [10, 11]. С точки зрения пользователей все решения равноправны, одинаково важны и должны быть получены — каждое в отдельности и все в совокупности — как можно быстрее.
Для описания как самих еки-заданий, так и особенностей их обработки разработана многопараметрическая (МП-модель) [12, 13]. МП-модель используется при планировании вычислительных работ и для оптимизации управления процессами распараллеливания при выполнении еки-заданий в условиях неопределенности [14]. МП-модель послужила основой макета программного обеспечения системы диспетчеризации, которая позволит:
эффективно использовать разнотипные вычислительные устройства;
добиваться максимальной производительности СВС при выполнении разнородных заявок; минимизировать производственные потери; завершать каждое задание в оговоренные сроки;
учитывать объем реальной, фактически необходимой вычислительной работы, требуемой для решения конкретной задачи;
реализовать принципиально новую дисциплину обслуживания, при которой в первую очередь решаются наименее ресурсоемкие еки-задачи.
1. Схема обработки задания. При формировании МП-модели для количественного описания процессов диспетчеризации еки-заданий в [12] было введено понятие вычислительной работы, которая выполняется переборными алгоритмами и измеряется в числе специализированных элементарных вычислительных операций (СЭВ-операций). Каждая СЭВ-операция состоит в просмотре отдельного фрагмента данных определенного вида и проверке его уникальности. При решении конкретной ейи-задачи число фрагментов данных, которые будут обработаны СВС до обнаружения уникального фрагмента, т.е. объем необходимой работы для идентификации последнего, априори неизвестен.
Предлагаемая модельная схема диспетчеризации комплекса СОЯ8ЛЯ не опирается на гипотезы о возможном: времени поступления заявок, объеме необходимой работы или наличии уникальных фрагментов в поступивших данных. При управлении используются следующие величины, точно известные на момент планирования: фактическое время поступления задания в СВС; число обработанных фрагментов данных; текущая производительность СВС.
Для целей математического описания модели управления будем говорить об абстрактной гетерогенной высокопроизводительной СВС, в которой в условиях неопределенности выполняются разнородные работы по поиску уникального фрагмента.
Предполагается, что заявки-задания поступают в СВС в произвольные моменты времени без каких-либо особых признаков, отношений предпочтения или предписанного порядка обслуживания. Вся исходная информация о задании в момент его появления в СВС помещается в базу данных заданий (БД-заданий). В процессе решения каждой задачи "устаревшие" данные в БД-заданий в режиме реального времени заменяются на актуальные, что позволяет отслеживать и контролировать объем оставшейся "невыполненной" работы.
Поиск решений ейи-задач ведется переборными алгоритмами. Массив исходных данных любого задания допускает разбиение на отдельные независимые части, которые не требуют синхронизации в процессе обработки, что является существенной особенностью ейи-задач. Разделение исходных данных на фрагменты происходит сразу на входе в СВС, что упрощает написание прикладных программ и повышает их надежность. Процесс распараллеливания и декомпозиция поиска решения полностью контролируются системой управления.
В соответствии с методологией исследования операций при управлении СВС в условиях объективной неопределенности используется принцип гарантированного результата [15]. При диспетчеризации заявок в СВС календарное время выполнения работ разбивается контрольными точками на отдельные этапы — плановые периоды или операционные окна. Для каждого задания в каждой контрольной точке в блоке планирования и анализа (ПК-план) в результате решения взаимосвязанной последовательности оптимизационных задач вычисляются максиминные оценки для ожидаемого времени завершения, возможный объем вычислительной работы и др.
Система управления СВС разбита на три уровня, поступающая заявка последовательно проходит каждый из них.
На верхнем уровне происходит предварительная обработка заявок: осуществляется анализ и происходит отбраковка, если задание составлено некорректно. Для заданий, прошедших входные фильтры, назначается директивный срок окончания (ДСО) [16, 17]. Последний зависит от вида задания, общей загрузки СВС и текущего состояния ресурсов. Задание с назначенным ДСО помещается в общую базу данных заданий (БД-заданий), в которой хранится и постоянно обновляется информация о ходе выполнения всех вычислительных работ.
При диспетчеризации СВС, где на разнотипном оборудовании выполняются разнородные СЭВ-операции, возникает проблема эффективного использования имеющихся ресурсов. При использовании ускорителей (еЛ81С, БРОЛ, ОРОРи) скорость обработки конкретного заданияна оборудовании различных типов может значительно отличаться. Для повышения результативности работы СВС для каждого из имеющихся переборных алгоритмов и соответствующих типов вычислительных ресурсов составляется таблица производительности. Данные из таблицы анализируются ПК-планом при планировании и используются для определения объемов текущих работ, а также при построении прогноза длительности решения каждой задачи. Наличие и постоянное обновление такой информации позволит системе управления эффективно использовать ресурсы СВС и оперативно подстраиваться к постоянно изменяющемуся составу потока заявок.
В контрольной точке принятия решения в ПК-план анализируются текущие данные о выполнении всех заданий, находящихся в СВС. На основании имеющейся в БД-заданий информации (д
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.