Organization of distributed computer systems' functioning at processing of sets of moldable jobs.pdf Распределённые вычислительные системы (ВС) относятся к перспективнымсредствами обработки информации [1]. Основным функциональным элементомраспределённой ВС является элементарная машина (ЭМ). Структура ЭМ допуска-ет варьирование от процессорного ядра до конфигураций, включающих много-ядерные процессоры и специализированные ускорители (например, GPGPU). Ко-личество ЭМ в распределённых ВС может варьироваться в широких пределах: отдесятков до сотен тысяч.Повышение эффективности эксплуатации ресурсов распределённых ВС связа-но с использованием технологии параллельного мультипрограммирования [1, 2].Одной из актуальных проблем организации функционирования ВС в мультипро-граммных режимах является планирование решения пользовательских задач.Здесь, по аналогии с [3], под задачей понимается требование пользователя на вы-полнение параллельной программы. В общем случае проблема планирования ре-шения задач является трудноразрешимой [4]. Перспективной считается разработ-ка приближённых методов и эвристических алгоритмов управления ресурсамиВС.Повысить эффективность эксплуатации ресурсов ВС и снизить время нахож-дения задач в очереди возможно, если, в частности, каждая из них будет допус-кать решение на различных конфигурациях вычислительных ресурсов. В этомслучае задачи называют масштабируемыми, или пластичными (moldable). Иссле-дования пользовательских запросов показывают, что свойством масштабируемо-сти обладают более 80 % задач [5].Системы пакетной обработки, используемые на практике, допускают наличиев очередях масштабируемых задач и позволяют пользователям указывать количе-ство требуемых для их решения ЭМ (рангов задач) в виде диапазонов допустимыхзначений. В данной работе предполагается, что пользователем каждому допусти-мому значению ранга задачи задаётся требование на время её решения и указыва-ется предпочтение по выбору именно этих значений. Кроме этого, для каждой за-дачи определяется штраф за задержку её решения. Величина штрафа рассчитыва-ется исходя из характеристик задачи: времени поступления, класса пользователя,и т.п.В основу предложенного алгоритма положен метод [3] формирования укруп-нённых задач (пакетов). Планирование выполняется в два этапа: задачи наборараспределяются по укрупнённым задачам с целью минимизации общего времениих решения и определяется последовательность решения укрупнённых задач, ми-нимизирующая суммарный штраф за задержку решения задач набора.1. Постановка задачиИмеются распределённая ВС, состоящая из N элементарных машин, и наборI = {Ii} независимых задач, i= 1,L. Каждая задача характеризуется вектором{ k}Pi= pi и величиной штрафа ci за задержку её решения в единицу времени,ci > 0 . Элементы вектора k (k,k, k)pi = ri ti wi задачи Ii задают допустимые значенияранга ri и времени решения ti и определяют приоритет kwi выбора этих значе-ний, 0 k , k 0wi > , k= 1,qi , qi=Pi . «Удовлетворённость» пользо-вателя выбором для решения задачи значений с приоритетом kwi оценивается какk max ki k iw w. Допускается существование в векторе Pi нескольких элементов содинаковым приоритетом. Считается, что в наборе присутствуют задачи с раз-личным количеством qi допустимых значений параметров и возможно взаимо-действие ЭМ с любой другой машиной ВС; зависимости величин kri , kti , kwi , ciдруг от друга отсутствуют.Необходимо для каждой задачи Ii набора выбрать: ki - номер элемента век-тора Pi , и si - время начала решения задачи, а также выделить подсистему{ 1N}Ji = jE элементарных машин ВС, где 0

Скачать электронную версию публикации