Стронгин Р.Г (ред.) Высокопроизводительные параллельные вычисления на кластерных системах

Подождите немного. Документ загружается.

141

эффективность. В первую очередь к ним относятся стохастическая

изменчивость параметров сетей и вычислительных узлов, их

нестационарность и неоднородность.

В докладе рассматриваются способы исследования и

моделирования параллельной производительности в Грид в рамках

архитектуры PEG. Предлагается подход к построению моделей

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

аргументов. Для ряда простых случаев (однородных архитектур

Грид)

получены аналитические приближения функции распределения

времени работы приложения, а также параллельного ускорения;

проведено сопоставление с экспериментальными данными.

Однако, в связи со сложностью аналитического описания

реальных Грид-систем, в общем случае оценки вероятностных

характеристик времени работы можно получить только численно. С

этой целью авторами разработана программная система-симулятор,

позволяющая моделировать случайное

поведение элементов Грид

(производительностей узлов и пропускной способности сети на

различных ее участках). Это позволило, в частности, исследовать

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

приложений в Грид.

Выбор способа параллельной декомпозиции задачи является,

пожалуй, наиболее эффективным инструментом управления временем

ее выполнения в Грид. В общем случае распределение времени работы

параллельного

приложения характеризуется параметрами масштаба и

сдвига. Параметр масштаба, управляющий размахом распределения,

может быть интерпретирован как объективный случайный фактор

(своего рода случайная ошибка системы). Параметр сдвига, в свою

очередь, интерпретируется как систематический фактор, управление

которым позволяет сократить время работы приложения и, как

следствие, повысить параллельную эффективность. В том случае, если

задана

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

текущую топологию Грид-среды (вычислительные мощности узлов,

пропускные способности сети), можно оптимизировать среднее время

выполнения приложения, также сокращая границы его изменчивости.

В отличие от кластерных решений, имеющих в распоряжении быстрые

сетевые каналы, которые не заняты «побочным» трафиком, в Грид-

среде время на коммуникации становится

более значительным по

отношению к времени вычислений, и менее детерминированным. Это

позволяет использовать более гибкие схемы декомпозиции,

142

оптимальным образом разделяя коммуникационные каналы между

вычислительными узлами.

С применением программного симулятора исследованы три

основных модели оптимальной декомпозиции: пропорциональная

(только по производительности узлов), барьерная и каскадная.

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

алгоритмов наиболее эффективной является каскадная декомпозиция.

Она в некоторых случаях позволяет в 1,5-2 раза сократить среднее

значение

времени выполнения приложения по сравнению с

равномерной декомпозицией.

Литература

1. Foster I., Kesselman. C. The Grid: Blueprint for a New Computing

Infrastructure. Morgan-Kaufman, 1999.

Thain D., Tannenbaum T., and Livny M. Condor and the Grid //

Berman F., (Editor), Fox G. (Editor), Hey J.G. A. (Editor) Grid

Computing: Making The Global Infrastructure a Reality. ―John

Wiley, 2003.

Stockinger H. Defining the Grid ― a snapshot of the current view

// Journal of Supercomputing. ―Springer Science+Business

Media, 2007.

Уэйлгам Т. Grid взята в заложники // Директор ИС, №1, 2006.

Sloot P. M. А. et al. Computational e-Science: Studying complex

systems in silico. ― A National Coordinated Initiative. White

Paper. ― 2007 [http://www.science.uva.nl/research/pscs/papers/

archive/Sloot2007a.pdf]

ПЛАНИРОВАНИЕ НАГРУЗКИ В ПАРАЛЛЕЛЬНЫХ

ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

Т.С. Дьячук, Р.К. Кудерметов

Запорожский национальный технический университет

Введение

Известно, что эффективность параллельных вычислений может

существенно зависеть от стратегии планирования нагрузки узлов

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

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

кластеров, которые используются для параллельных вычислений [1].

143

В данном докладе рассматривается модель планирования

выполнения произвольного потока заданий, каждое из которых

представляет собой задачу, допускающую распараллеливание на

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

загруженность процессоров узлов кластера. Поток заданий

формируется путем запросов в произвольные моменты времени на

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

максимальное число

вычислительных узлов кластера.

Модель планирования нагрузки

В данной работе рассматривается стратегия планирования

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

на кластере Beowulf [2], узлы которого представляют собой

персональные компьютеры одинаковой мощности. Узлы объединены

сетью и работают под управлением операционной системы

Red Hat Linux 7.2 [3]. Для организации параллельных вычислений

используется стандарт MPI 1, реализованный в библиотеке mpich 1.2.4.

Введем понятие степени загруженности узла, которая

соответствует сумме приоритетов работающих

на узле процессов и,

таким образом, характеризует потенциальную часть процессорного

времени, которая может быть выделена новому процессу с

определенным приоритетом.

Необходимо распределить параллельные задачи, возникающие в

произвольные моменты времени между узлами кластера таким

образом, чтобы время выполнения задач было минимальным.

Введем также следующие понятия:

 равномерная загруженность системы – состояние, при

котором все узлы имеют одинаковую степень загруженности;

 пропорциональная загруженность системы – состояние, когда

степень загруженности i-го узла в

−

раз меньше степени

загруженности N-го узла, у которого максимальная

загруженность (N – число узлов в системе);

 неравномерная загруженность системы – состояние, при

котором загружен только один узел, а остальные

простаивают.

Для решения поставленной задачи была разработана

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

144

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

функцией:

,minΨ ), Ω →

)

(

N21

β,...,β,β

(1)

где

– время выполнения задания;

– функция, характеризующая возможный параллелизм задачи

(на какое количество параллельных подзадач можно разделить

исходную задачу);

Ω

– функция, характеризующая загруженность кластерной

системы;

– степень загруженности i-го узла кластера.

Особенностью данной модели является то, что число

параллельных ветвей решаемой задачи определяется исходя из степени

загруженности узлов и, кроме того, допускается, что на одном узле

может выполняться несколько ветвей параллельной программы.

Результаты исследований

В результате практического применения разработанной модели на

Beowulf-кластере были получены коэффициенты ускорения работы

системы при равномерной, пропорциональной и неравномерной

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

пять узлов кластера. Задания были выбраны такими, которые не

требуют интенсивного обмена данными между узлами кластера,

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

только степень загруженности узлов.

Под коэффициентом ускорения подразумевается отношение

времени, потраченного на решение задачи в системе при равномерном

распределении подзадач между узлами кластера (число ветвей задачи

равно числу узлов системы) к времени затраченному на решение

задачи с помощью предложенной модели (число ветвей задачи

определялось планировщиком). Данные результатов исследования

приведены в таблице

145

Коэффициент ускорения Максимальная

степень

загруженности

(степень

загруженности

N-го узла)

Равномерная

загруженность

Пропорциональная

загруженность

Неравномерная

загруженность

0 1.00 1.00 1.00

1.60 1.68 1.90

2.00 2.29 2.70

2.29 2.82 3.52

2.50 3.33 4.20

2.67 3.64 4.80

2.80 3.92 5.60

2.93 4.27 6.40

3.05 4.50 7.20

3.14 4.78 8.01

3.23 5.10 8.80

Выводы

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

процессорного ресурса параллельной вычислительной системы.

Полученные коэффициенты ускорения показывают, что

разработанный алгоритм является эффективным для применения в

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

экономию машинного времени. В настоящее время проводятся

исследования по расширению модели планировщика.

Литература

1. Лацис А. Как построить и использовать суперкомпьютер. –

М.: Бестселлер, 2003. – 240 с.

Столлингс В. Операционные системы. 4-е изд.: Пер. с англ. –

М.: Издательский дом “Вильямс”, 2004. – 848 с.

Роббинс А. Linux: программирование в примерах. 2-е изд.:

Пер. с англ. – М.:КУДИЦ-ОБРАЗ, 2006. – 656 с.

146

ДИСПЕТЧЕР ЗАДАЧ ОПЕРАЦИОННОЙ СИСТЕМЫ

С ИСПОЛЬЗОВАНИЕМ ЕДИНОЙ ОЧЕРЕДИ ЗАЯВОК

В.Ю. Егоров

Пензенский государственный университет

Введение

В настоящее время вопросы построения диспетчера задач

операционной системы, удовлетворяющего многочисленным

предъявляемым требованиям, изучены уже достаточно глубоко.

Однако и в этой области остаётся ряд вопросов, подлежащих

рассмотрению.

Стандартная схема организации диспетчера задач, реализующего

приоритетную дисциплину обслуживания, включает в себя набор

очередей, в котором одна очередь хранит заявки на исполнение с

одним

и тем же приоритетом, как показано на рисунке 1. Заявки

поступают от нитей (threads) процессов (часто в переводной

литературе называемых потоками). Сначала обслуживаются заявки с

максимальным приоритетом (например, 32), затем рассматривается

очередь с приоритетом 31 и так далее.

Обслуживание

Очереди заявок

…

Рис. 1. Очереди задач по приоритетам

Для аппаратных приоритетов (IRQL) такая схема является

наиболее оптимальной, поскольку обеспечивает приемлемое время

реакции для всех типов аппаратных устройств. Однако для

обслуживания заявок с нулевым аппаратным приоритетом возникают

проблемы, связанные с качеством и гарантиями обслуживания.

Необходимо, чтобы заявка с любым, пусть даже самым низким,

приоритетом была обслужена в приемлемое время. В противном

случае, существует реальная вероятность сценария, при котором

147

заявки с низким приоритетом никогда не будут выбраны.

Сформулируем основные требования к дисциплине диспетчеризации

современной операционной системы:

Любая задача должна получать часть процессорного времени

для своего выполнения (требование гарантии обслуживания).

Любая задача должна получать долю процессорного времени в

соответствии со своим приоритетом и общей загруженностью

центрального процессора (первое требование качества

обслуживания).

Процессорное время должно выделяться каждой задаче с

некоторой периодичностью, позволяющей имитировать

непрерывность выполнения задачи (второе требование

качества обслуживания).

Задаче, в интерактивном режиме взаимодействующей с

пользователем, должно выделяться больше процессорного

времени, чем задаче, выполняющейся в фоновом режиме

(требование адаптивности обслуживания).

Удовлетворение данным требованиям приводит к тому, что

алгоритм выбора следующей заявки на обслуживание задачи

значительно усложняется и становится нетривиальным. В данном

докладе предлагается вариант диспетчера задач, удовлетворяющий

предъявляемым требованиям

и простой в реализации.

Организация диспетчера задач в виде односвязного списка

Основная идея предлагаемого метода заключается в отказе от

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

которой реализована только одна очередь задач. В структуру нити

необходимо добавить дополнительное поле, которое будет

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

«текущим количеством приоритета» заявки (τ), в отличие от текущего

приоритета (ε)

и базового приоритета заявки (α). Текущий приоритет

заявки ε – это целое беззнаковое число, значение которого может

отклоняться от базового приоритета заявки в меньшую или большую

сторону в зависимости от текущего состояния операционной системы.

Текущее количество приоритета заявки τ – это также целое

беззнаковое число, служащее для расчёта места заявки в очереди,

значение

которого никогда не может быть больше, чем текущий

приоритет заявки: τ≤ε (1).

148

Заявка q в любой момент времени характеризуется тремя

значениями: базовым приоритетом α, текущим приоритетом ε и

текущим количеством приоритета τ. Будем обозначать заявку в

очереди как q

α,ε,τ

. Очередь заявок, ожидающих обслуживания, будем

обозначать как Ω.

Весь алгоритм диспетчера задач при реализации данного метода

разбивается всего на две функции, подлежащие реализации: функцию

добавления заявки в очередь

(

)

τεα

put

q ,f Ω

и функциию выбора

следующей заявки из очереди с целью обслуживания

(

)

τεα

get

q ,f Ω

Функция извлечения заявки

(

)

τεα

get

q ,f Ω

очень проста. При

необходимости помещения заявки на обслуживание нужно просто

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

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

обслуживания. Функция

(

)

τεα

put

q ,f Ω

сложнее. Она рассчитывает

место заявки в очереди заявок, исходя из базового и текущего

приоритета, как самой заявки, так и заявок, уже находящихся в

очереди. Ниже приведён упрощённый словесный алгоритм функции

(

)

τεα

put

q ,f Ω

Проверить, нет ли данной заявки уже в очереди заявок. Если

есть, то алгоритм завершён.

Если текущее количество приоритета τ заявки не равно нулю,

то перейти к пункту 4. Иначе сделать значение τ заявки

равным её текущему приоритету ε и перейти к пункту 3.

Поставить заявку в конец очереди заявок. Алгоритм завершен.

Уменьшить τ заявки на единицу.

Взять первую заявку из головы списка q

Если значение τ заявки q

меньше чем значение τ добавляемой

заявки, то перейти к пункту 8. Иначе взять следующую заявку

i+1

по списку и повторить пункт 6.

Если по итогам поиска не нашлось заявок, удовлетворяющих

условию, то перейти к пункту 3.

Поставить добавляемую заявку в очередь перед найденной

заявкой q

. Алгоритм завершён.

149

В результате выполнения данного алгоритма в качестве функции

(

)

τεα

put

q ,f Ω

все заявки, поступающие на вход диспетчера задач,

будут гарантированно обслужены. При этом сохраняется отношение

приоритетов, то есть заявки с более высоким приоритетом будут

обслуживаться чаще, чем заявки с более низким приоритетом.

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

постепенное снижение значения τ до нуля. Если исходное значение ε

было

больше, то и количество квантов, полученное заявкой до того,

как её значение τ станет равным нулю, также будет больше. После

того, как значение τ всех задач достигнет нуля, цикл повторяется.

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

значения τ заявки, так и значения ε. Значение τ можно увеличивать

после окончания операции ввода

-вывода этой задачи для более

быстрого взаимодействия с аппаратными устройствами. Для

повышения адаптивности обслуживания при активизации процесса на

экране пользователя значение ε всех нитей процесса следует повысить

на 1 или 2 пункта.

Во время работы операционной системы постоянно возникает

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

процессов. Для операционных систем, работающих в архитектуре IA-

32, для

этого необходимо, как минимум, перегрузить таблицу страниц

процесса. Для центрального процессора работа по переключению

адресных пространств есть весьма трудоёмкая задача. Одним из

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

как следствие, повышения производительности системы, является

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

выполнялись нити одного и того же процесса,

затем нити следующего

процесса и так далее. Таким образом, производительность системы

повысится. Для того, чтобы добиться такого повышения

производительности, необходимо внести изменения в пункт 6

рассмотренного выше алгоритма. После внесения изменения пункт

будет выглядеть следующим образом.

Если значение τ заявки q

меньше чем значение τ добавляемой

заявки, то перейти к пункту 8. Если значение τ заявки q

равно

значению τ добавляемой заявки и обе заявки принадлежат одному

процессу, то также перейти к пункту 8. Иначе взять следующую заявку

i+1

по списку и повторить пункт 6.

150

Заключение

В докладе предлагается простой алгоритм диспетчера задач,

позволяющий осуществлять диспетчеризацию заявок на обслуживание

с использованием программных приоритетов. К особенностям

алгоритма относятся:

использование единой очереди заявок на обслуживание;

реализация приоритетной дисциплины обслуживания заявок;

простота реализации алгоритма;

возможность динамического изменения приоритета заявок.

К минусам алгоритма можно отнести наличие массовой операции

поиска места

для добавляемой заявки.

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

обслуживание может быть использован при разработке операционной

системы общего назначения.

Литература

1. Соломон Д., Руссинович М. Внутреннее устройство Microsoft

Windows 2000. Мастер-класс: Пер. с англ.– СПб.: Питер;

Издательско-торговый дом «Русская редакция», 2001. – 752 с.

Таненбаум Э. Современные операционные системы. 2-е изд. –

СПб.: Питер, 2002. – 1040 с.

Робачевский А.М. Операционная система UNIX. – СПб.: БХВ-

Санкт-Петербург, 1999. – 528 с.

Гордеев А.В., Молчанов А.Ю. Системное программное

обеспечение – СПб.: Питер 2001. – 736 с.

Бек Л. Введение в системное программирование: Пер. с англ.

– М.: Мир, 1988. – 448 с.

СОВРЕМЕННЫЕ ДИСЦИПЛИНЫ

ДИСПЕТЧЕРИЗАЦИИ ЗАДАЧ

В.Ю. Егоров

Пензенский государственный университет

Введение

При выборе метода, согласно которому следует реализовывать

диспетчер задач интерактивной операционной системы, разработчик