ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2015, № 5, с. 73-89
КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^^^ МЕТОДЫ
УДК 519.85
НОРМАТИВНЫЙ ДИНАМИЧЕСКИЙ АНАЛИЗ ПРЕДЕЛЬНЫХ РЕЖИМОВ ФУНКЦИОНИРОВАНИЯ ГЕТЕРОГЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ
© 2015 г. Ю. Е. Малашенко, И. А. Назарова
Москва, ВЦ РАН e-mail: irina-nazar@yandex.ru Поступила в редакцию 30.03.15 г., после доработки 14.04.15 г.
Предлагается метод динамического многопараметрического анализа производительности вычислительной системы, предназначенной для решения разнородных ресурсоемких задач. Вводятся понятия монопольных режимов функционирования и нормативных показателей работоспособности системы. Рассматривается множество вычислительных работ разных видов, выполнимых совместно за один операционный цикл. Для определения максимально возможных объемов работ используется многокритериальная оптимизационная модель эффективного распределения имеющихся разнотипных ресурсов. Полученные парето-опти-мальные векторы-решения являются неулучшаемыми верхними оценками функциональных возможностей системы. В контрольные моменты текущие предельные значения характеристик сравниваются с нормативными. Строится диаграмма относительных отклонений, которая позволяет прослеживать динамику изменений показателей производительности. Обработка и сравнение данных за длительный промежуток времени дают возможность получать многокомпонентные гарантированные оценки работоспособности системы в случаях отказа ее элементов.
DOI: 10.7868/S000233881505008X
Введение. Современные гетерогенные вычислительные системы (ВС) предназначены для решения самых разных инженерно-технических задач и широко используются в центрах коллективного пользования. Характерными чертами таких систем являются высокая производительность, мощная оперативная память, широкое множество задействованных аппаратных решений, системных и алгоритмических приложений и др. Вычислительные комплексы требуют специализированных способов управления и планирования при обработке заданий, а также эффективного использования вычислительных средств. При изучении указанных систем чаще всего рассматриваются проблемы, связанные с распределением ограниченных ресурсов или совместным планированием вычислений. Например, в работах [1—3] указанные проблемы исследуются с помощью теории расписаний, в [4—7] — с помощью жадных алгоритмов и репликации элементов хранения данных, в [8] — с помощью теории графов, в [9—12] — методами адаптивного управления, в [13—15] формулируются как оптимизационные.
В настоящей статье процесс функционирования гетерогенной ВС изучается с точки зрения ее производительности. Как правило, последняя в литературе определяется через количество той или иной вычислительной работы, выполняемой системой в единицу времени или в течение некоторого временного интервала. В зависимости от целей под вычислительной работой понимают различные действия, например: выполнение машинной команды, обработку пикселей или полигонов пикселей в графических системах, запросы к базам данных, выполнение прикладной программы и др. Для измерения производительности ВС предлагаются десятки различных характеристик [16—19], которые прежде всего зависят от взгляда авторов на вычислительный процесс или модели описания функционирования ВС.
Рассмотрим ВС, обрабатывающую интенсивный поток разнородных ресурсоемких citu-зада-ний переборного типа (от английского термина computationally intensive task (under) uncertainty, который можно перевести как ресурсоемкие вычислительные задания, выполняемые в условиях неопределенности). Для повышения быстродействия ВС оснащена специализированными устройствами, позволяющими значительно увеличить скорость исполнения отдельных процедур по сравнению со стандартом. Для таких устройств в качестве ресурсной единицы (единичного
вычислительного модуля) рассматривается отдельно каждая микросхема (например, ASIC, eASIC, FPGA, система-на-кристалле SoC, графический ускоритель GPGPU [20]) как наименьший возможный объект, допускающий независимое управление. Различные типы устройств выполняют одно и то же задание с разной производительностью, некоторые из них могут предназначаться для работы только с определенными типами алгоритмов и подходят для решения ограниченного класса задач. Для эффективного использования ресурсов ВС и удовлетворения принципа равнозначности заданий при диспетчеризации citu-заданий применяются оптимизационные модели и подходы [13—15], формирующие определенную программно-аппаратную среду.
В настоящей работе рассматривается вопрос о функциональных характеристиках ВС, а именно о том, какие виды работ и в каких объемах можно завершить за выделенный промежуток времени на заданном наборе оборудования и с использованием имеющихся средств оптимизации.
С течением времени число и производительность вычислительных модулей гетерогенной ВС меняется, кроме того, новые реализации программного обеспечения и подсистем управления могут кардинально изменить как объем, так и весь спектр выполнимых работ. В связи с этим возникает проблема анализа динамики функциональных возможностей ВС в условиях постоянного изменения показателей работоспособности элементов вследствие поломок и отказов.
В данной статье в рамках формализма многопараметрической модели (МП-модели) [13—15] предлагается метод анализа динамики изменения производительности ВС, основанный на получении гарантированных оценок объемов выполнимых работ при эффективном распределении ресурсов. Предполагается, что входной поток заданий является интенсивным и мощности ВС позволяют завершать только часть поступающих задач [21].
В качестве характеристики функциональных возможностей ВС предлагается рассматривать вектор одновременно выполнимых вычислительных работ. Значения компонент вектора соответствуют объемам различных работ, которые можно завершить совместно за один операционный цикл. Каждому допустимому распределению имеющихся ресурсов ставится в соответствие вектор из множества выполнимых работ, а точки, лежащие на границе последнего, определяют предельные функциональные возможности ВС. Для исследования границы множества и соответствующих векторов работ рассматриваются монопольные режимы функционирования, в каждом из которых система обрабатывает только один выделенный вид заданий.
Предельные функциональные возможности ВС определяются исходя из решения следующей задачи многокритериальной оптимизации: максимизировать вектор выполнимых работ на множестве допустимых распределений вычислительных ресурсов. Подмножество оптимальных по Парето векторов выполнимых работ (неувеличиваемых ни по одной компоненте без уменьшения значения по какой-либо другой) описывает предельные функциональные возможности ВС.
В качестве оценки предельных функциональных характеристик системы предлагается выбирать парето-оптимальное решение сформулированной задачи с функционалом, зависящим от показателей монопольных режимов. Для исправной ВС, работающей с максимально возможной производительностью, вводится понятие исходного нормативного состояния. Нормативными предельными характеристиками считается парето-оптимальное решение задачи для исходного нормативного состояния системы, которое определяется с помощью весовых коэффициентов, полученных для монопольных режимов работы ВС. Для динамической оценки состояния ВС в начале каждого операционного цикла с учетом фактического состояния ресурсов вычисляются текущие предельные функциональные характеристики системы. Полученные текущие показатели сравниваются с исходными, производится свертка векторов-критериев, строятся и анализируются двумерные диаграммы отклонений от нормативных показателей.
1. Постановка задачи. Рассмотрим гетерогенную высокопроизводительную вычислительную систему, предназначенную для решения ресурсоемких citu-задач. Выполнение соответствующего вычислительного задания сводится к поиску уникального фрагмента в большом массиве исходных данных. Исходная задача считается решенной, как только в предъявленном наборе данных удается выявить уникальный фрагмент, характеристики, свойства или параметры которого задаются заранее. В противном случае необходимо убедиться, что искомый элемент в массиве отсутствует, и тем самым завершить задание [22].
Заявки на решение citu-задач различных видов поступают в систему в произвольные моменты времени без каких-либо особых признаков, отношений предпочтения или предписанного порядка обслуживания. Для получения решения каждой citu-задачи достаточно найти хотя бы один уникальный фрагмент. Все задания выполняются в режиме реального времени, их содержательные решения одинаково важны и должны быть получены все в совокупности и каждое в отдель-
ности как можно быстрее [23, 24]. Входящий в систему поток является интенсивным, мощности ВС в общем случае недостаточно, чтобы выполнить все поступающие задания.
Далее при математическом описании и для целей анализа будет рассматриваться абстрактная гетерогенная ВС, состоящая из центрального управляющего устройства и набора независимых исполняющих единичных вычислительных модулей (ЕВ-модулей) различных конструктивных типов, выполняющих работу по поиску уникальных фрагментов. Произведенная работа измеряется числом специализированных элементарных вычислительных операций (СЭВ-операций). СЭВ-операция состоит в просмотре отдельного фрагмента данных и проверке его уникальности соответствующим переборным алгоритмом. Каждый ЕВ-модуль может выполнять по крайней мере два вида работ. При выполнении конкретного еки-задания число фрагментов данных, которые пройдут обработку, априори неизвестно, т.е. объем работы, необходимой для обнаружения уникального фрагмента, определить заранее невозможно.
Для диспетчеризации ВС, выполняющей еки-задания, предложен и реализован программно-алгоритмический комплекс СОЯ8ЛЯ [25, 26], в котором используется ряд правил, позволяющих, в частности, управлять обработкой заданий с директивными сроками окончания и/или эффективно распределять разнотипные вычислительные ресурсы. В основу блока управления и планирования СОЯ8ЛЯ положена МП-модель, в которой означенные выше правила формализованы
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.