Механизм децентрализованного распределения задач между вычислительными элементами

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Механизм децентрализованного распределения задач между вычислительными элементами

Халимон В.И., Смирнов А.В.



В настоящий момент наблюдается несоответствие темпов роста вычислительной мощности ЭВМ, с одной стороны, и распространенности вычислительных сетей и их пропускной способности, с другой.

Это дает возможность отдельным независимым исследователям использовать распределенные вычислительные системы на основе широко распространенных локальных и корпоративных сетей ЭВМ. Организация вычислений в таких сетях имеет ряд принципиальных отличий от схожих проблем для глобальных вычислительных сетей (GRID-систем). Отличия заключаются, в первую очередь, в следующих моментах:

· составление оптимального соответствия отдельных вычислительных фрагментов доступным ЭВМ (вычислительным элементам);

· повышение надежности процесса вычислений;

· управление нагрузкой на отдельные ЭВМ.

Принципы организации распределенных вычислений для таких сетей в данный момент не проработаны достаточно глубоко.

Наличие приведенных факторов делает особенно актуальной задачу разработки новых, учитывающих специфику названных сетей ЭВМ, схем организации и управления распределенными вычислениями.

Объектом исследований является среда организации распределенных вычислений в сетях ЭВМ.

Сети ЭВМ, рассматриваемые в данном случае, обладают рядом особенностей:

· корпоративные и локальные вычислительные сети состоят из сравнительно небольшого числа ЭВМ (до нескольких сотен), объединенных в локальные сети;

· локальные сети чаще всего удалены друг от друга территориально и связаны через internet-среду;

· компьютеры, входящие в такие сети, могут существенно отличаться своими аппаратными характеристиками, физической доступностью, видом и надежностью сетевого подключения и режимами использования;

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

Целью является минимизация времени решения вычислительных задач за счет улучшения механизма распределения отдельных фрагментов задачи (подзадач) внутри вычислительной сети.

Для достижения этой цели необходимо решить следующие задачи:

· изучить особенности функционирования ЭВМ и коммуникаций в целевых сетях;

· проанализировать особенности организации распределенных вычислений в таких сетях;

· разработать математическую модель процесса проведения распределенных вычислений, учитывающую особенности среды выполнения вычислений и решаемых задач;

· разработать и реализовать имитационную модель процесса проведения распределенных вычислений в виде программы;

· синтезировать алгоритм распределения задач с использованием математической модели;

· исследовать эффективность синтезированных алгоритмов с помощью программной реализации имитационной модели;

· проверить алгоритмы на практических задачах.

Алгоритм ориентирован на объемные вычислительные задачи, разбиваемые на подзадачи, минимальное время проведения расчетов по которым составляет час или более машинного времени. Для задач, которые могут быть разделены на менее ресурсоемкие подзадачи (за счет увеличения их количества), вопросы составления оптимального распределения, как правило, не встают по причине незначительности потерь времени при утрате результата решения по причине сбоя какой-либо ЭВМ, кроме, естественно, ЭВМ, хранящей результаты расчетов по всем подзадачам для решаемой в данной момент задачи.

Описание системы организации распределенных вычислений

В основе исследуемой системы лежит архитектура клиент-сервер [5]. При этой схеме в сети есть компьютер-сервер, который находится в состоянии ожидания запросов от клиентов. Получив такой запрос, сервер обрабатывает его и посылает результат клиенту.

Модель взаимодействия процессов в системе - управляющий-рабочие [5]. В этой схеме в системе есть специальная станция - управляющий, владеющий набором подзадач, - портфелем. Он распределяет подзадачи по вычислительным элементам - рабочим и собирает результат. Это вариант схемы клиент - сервер, в которой рабочие станции выступают в роли вычислительных серверов, а управляющий является клиентом.

Система, как программный комплекс, состоит из следующих компонентов:

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

· диспетчер - программа, запускаемая на любой из ЭВМ, входящей в сеть. Диспетчер соответствует одной решаемой задаче и отвечает за организацию процесса вычислений: формирует подзадачи, отправляет их на вычислительные станции, сохраняет и анализирует результаты вычислений; станции выделяются диспетчеру координатором динамически;

· агент - программа, запускаемая на вычислительных элементах. Она решает три задачи:

o собирает статистические данные о функционировании вычислительного элемента;

o осуществляет регистрацию на координаторе при подключении вычислительного элемента к сети;

o получает данные о подзадаче от диспетчера, осуществляет собственно сами вычисления, необходимые для решения подзадачи, и отсылает результат обратно диспетчеру.

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

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

Рассмотрим процесс порождения и распределения подзадач более подробно.

В каждый момент времени имеется очередь вычислительных подзадач и набор доступных вычислительных элементов.

Подзадачи разделяются на три вида, в соответствии с типом события, в результате наступления которого данная подзадача была порождена:

· стартовые (инициирование процесса вычислений);

· порожденные (завершение одной из вычислительных подзадач);

· повторные (сбой вычислительного элемента).

Стартовые подзадачи - это подзадачи, которые ставятся в очередь в момент начального старта вычислений, т.е. они соответствуют начальному разбиению задачи.

Порожденные подзадачи создаются на основе анализа уже завершенных подзадач, например, в случае недостаточной точности полученного результата или невыполнения условия окончания вычислений

Повторные подзадачи - это подзадачи, которые уже были переданы на вычислительные элементы, однако по каким-либо причинам не были завершены. Условия отказа могут быть как явные (сообщение о прекращении вычислений в результате программного сбоя), так и определятся косвенно (потеря связи с элементом на длительный промежуток времени).

В общем случае нельзя предсказать количество подзадач, одновременно поступающих в очередь в результате наступления события первого или второго вида. В идеальном случае поток повторных подзадач имеет нулевую интенсивность.

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

Отсутствие подзадач в очереди означает окончание процесса вычислений при условии, что все назначенные элементам подзадачи уже завершены.

Подзадача может быть исключена из очереди в результате одного из двух событий:

· назначение подзадачи вычислительному элементу (передача в обслуживание);

· абортивное прекращение вычислений.

Все доступные в данный момент вычислительные элементы составляют обсуживающие аппараты (ОА) или каналы обслуживания. Количество элементов может меняться в результате следующих событий:

Увеличение количества:

· к вычислительной сети подключился новый элемент (сюда входят элементы, которые были заняты пользовательскими задачами);

· вычислительный элемент закончил обработку назначенной подзадачи (либо подзадача выполнена, либо произошел отказ от ее обработки) и готов к приему новых подзадач;

Уменьшение количества:

· назначение вычислительному элементу подзадачи;

· наступление периода недоступности вычислительного элемента (отключение элемента от сети или поступление ресурсоемкой пользовательской подзадачи).

Т.е. ОА может находиться в одном из трех состояний:

· свободен;

· обслуживает заявку;

· сбой.

Общая схема системы представлена на рисунке.

вычислительный сеть глобальный

Схема системы

Необходимо составить такое назначение подзадач на вычислительные элементы, чтобы предполагаемое время вычислений было минимально.



Для решения этой задачи предлагается ввести следующие характеристики вычислительного элемента:

· вычислительная мощность;

· агрессивность;

· надежность.

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

Агрессивность - характеристика, зависящая от времени и основанная на статистических данных, собираемых на самом вычислительном элементе. Этот показатель начинает увеличиваться перед тем отрезком времени, когда ресурсы вычислительного элемента будут долгое время не использоваться владельцем (например, компьютер оставлен включенным, пока владелец находится на работе) и падает до нуля перед теми отрезками времени, когда вычислительные ресурсы заняты полностью или не доступны совсем (компьютер выключен на ночь). Причем величина агрессивности является интегральной по отношению к количеству свободных ресурсов в предстоящем отрезке времени, т.е. она будет максимальной перед долгими периодами простоя.

Благодаря тому, что агрессивность начинает увеличиваться до того, как наступит реальное освобождение ресурсов, координатор сможет реализовать более «дальновидное» распределение заданий, не имея подробных статистических данных о конкретных элементах, а располагая только суммарными оценками.

Математически агрессивность определяется следующим образом:

,

где:

a - численное значение агрессивности;

t₁ - планируемое время начала решения подзадачи;

t₂ - расчетное время окончания решения подзадачи;

L(t) - загрузка задачами пользователя в момент времени t.

t₂ вычисляется на основе данных о предполагаемой ресурсоемкости подзадачи, загрузке вычислительного элемента и его мощности:

вычислительный сеть глобальный

,

где:

P - численное значения мощности вычислительного элемента;

C - вычислительная ресурсоемкость подзадачи.

Определение t₂ осуществляется итеративно методом приращения с помощью численного интегрирования с шагом, равным интервалу фиксации статистики, пока значение интеграла не превысит ресурсоемкость подзадачи.

Оценка ресурсоемкости подзадачи осуществляется разработчиком при их формировании на основе тестовых запусков. Оценка производится в единицах вычислительной мощности на основе сравнения времени выполнения с эталонной задачей.

Если на интервале (t₁; t₂) статистическая вероятность отказа элемента выше определенного порога, то агрессивность считается равной нулю.

Надежность обратно пропорциональна количеству отказов от полученных подзадач по вине вычислительного элемента за определенный отрезок времени.

В набор статистических данных, собираемых программой-агентом на вычислительном элементе, входят:

· среднее время выполнения одной подзадачи, с учетом ее ресурсоемкости;

· коэффициент загрузки ЭВМ задачами пользователя (от 0 - отсутствие загрузки, до 1 - полностью загружен задачами пользователя);

· количество отказов на определенном интервале времени;

· периоды недоступности элемента;

Статистика собирается на таком интервале времени, который позволяет выявить периодичность изменения статистических значений (например, сутки, неделя) в зависимости от режима использования ЭВМ.

Использование статистических данных порождает дополнительные проблемы, которые необходимо решить в рамках работы:

· разработка алгоритма определения продолжительности интервала сбора статистики;

· разработка эффективных методов расчета агрессивности в случае расхождения реального режима использования ЭВМ на текущем интервале времени со спрогнозированным на основе статистических данных [6].

Алгоритм распределения подзадач

Для решения задачи распределения подзадач предполагается использовать математический аппарат теории массового обслуживания [1, 2].

Построение математической модели основывается на следующих предпосылках:

· для каждого ВЭ, занятого расчетами подзадачи, можно рассчитать вероятность его освобождения на некотором интервале времени;

· для любого ВЭ можно узнать вероятность его отказа / недоступности на любом интервале времени;

· для каждой подзадачи можно рассчитать примерное время ее решения на любом ВЭ в любом интервале времени (за счет статистических данных или методов прогнозирования загрузки);

· зная характер вычислений (итеративный, с увеличивающимся количеством подзадач и т.д.), можно предсказать вероятность появления некоторого количества подзадач определенной ресурсоемкости на следующем интервале времени;

· анализируя данные о потоке подзадач (изменение их количества и ресурсоемкости) и вероятности окончания расчетов на ВЭ, можно спрогнозировать ресурсоемкость подзадач, которые, возможно, будут порождены на следующем интервале времени.

Методики определения и анализа соответствующих статистик приведены в [3, 4, 7].

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

Таким образом, мы гарантированно минимизируем время выполнения расчетов по наиболее ресурсоемким подзадачам, уменьшая тем самым последствия от возникновения возможных сбоев. Разбиение на группы упрощает решение, позволяя оперировать понятиями ресурсоемкости группы и ее объема - для подзадач, и вероятностью окончания расчетов каким-либо вычислительным элементом определенной группы, перехода его в другую группу или вероятности сбоя - для групп вычислительных элементов. Также возможно установить зависимость между ресурсоемкостью уже решенной подзадачи и количеством и ресурсоемкостью порожденных на основе результатов ее расчета подзадач, анализируя совокупность решенных подзадач определенной группы.

В основе разбиения лежит идея оценки вероятного времени вычисления подзадачи на ВЭ определенной группы и вероятности появления более ресурсоемкой подзадачи на интервале расчета.

Анализ подзадач позволяет также классифицировать решаемую задачу по ряду признаков на следующие типы:

По характеру вычислений [5]:

· Итеративные вычисления;

· Рекурсивные вычисления;

По ресурсоемкости порождаемых подзадач при решении одной подзадачи:

· Убывающей ресурсоемкости;

· Постоянной ресурсоемкости;

· Возрастающей ресурсоемкости;

По количеству порождаемых подзадач на одну заданного типа:

· Без порождения;

· Один к одному;

· Один ко многим;

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

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

В модели учтены следующие факторы:

· непостоянство состава вычислительной сети;

· вариации вычислительной мощности отдельных элементов;

· наличие случайных отказов при проведении вычислений, а также при передаче задания и результата;

· различная ресурсоемкость передаваемых на обработку подзадач

· неточность в предварительной оценке ресурсоемкости подзадач;

· учет загрузки ВЭ пользовательскими задачами.

В качестве прикладной задачи планируется реализовать метод молекулярной динамики в применении к задачам физической химии [8, 9].



Литература

1. Саульев, В.К. Математические модели теории массового обслуживания [Текст] / В.К. Саульев. - М.: Статистика, 1979. - 96 с., ил.

2. Хинчин, А.Я. Работы по математической теории массового обслуживания [Текст] / А.Я. Хинчин. - М.: Физматгиз, 1963. - 236 с.

3. Кругликов, В.К. Вероятностный машинный эксперимент в приборостроении [Текст] / В.К. Кругликов. - Л.: Машиностроение, Ленингр. отд-ние, 1985. - 247 с., ил.

4. Подлесный, Н.И. Специальные методы идентификации, проектирования и живучесть систем управления [Текст] / Н.И. Подлесный, А.А. Рассоха, С.П. Левков. - К.: Высшая школа, 1990. - 446 с.

5. Грегори, Э. Основы многопоточного, параллельного и распределенного программирования [Текст] / Эндрюс Грегори. - Addison-Wesley, 2003.

6. Yang L. Homeostatic and Tendency-based CPU Load Predictions [Текст] / L. Yang, I. Foster, J.M. Schopf // International Parallel and Distributed Processing Symposium, 2003.

7. Smith W. Using run-time predictions to estimate queue wait times and improve scheduler performance. In Job Scheduling Strategies for Parallel Processing. [Текст] / W. Smith, V. Taylor, and I. Foster., (D.G. Feitelson and L. Rudolph eds.). - Springer Verlag, 1999.

8. Бродская, Е.Н. Метод молекулярной динамики в физической коллоидной химии [Текст]: Методическое пособие / Е.Н. Бродская, Е.М. Пиотровская - НИИ химии СПбГУ, 1999.

9. Allen M.P. Computer Simulation of Liquids [Текст] / M.P. Allen, D.J. Tildesley. - Oxford University Press, 1987. - 406 p.

10. Востокин, С.В. Применение интерпретатора сценария GraphPlus для управления распределенными вычислениями [Текст] / С.В. Востокин // Известия СНЦ РАН. - М.: СНЦ РАН, 2005. - Т. 7, №1 (13), с. 138-142.

Размещено на Allbest.ru

...