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

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

151

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

времени не существует дисциплины диспетчеризации, однозначно

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

необходимости применения вытесняющей многозадачности и

карусельного (round robin) принципа диспетчеризации для реализации

вычислительной среды. Однако остаётся ряд вопросов, на которые нет

чёткого ответа. Как должна быть реализована обработка прерываний: с

относительными

или абсолютными приоритетами? Какими

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

диспетчеризации? Данный доклад рассматривает некоторые из

поставленных вопросов.

Краткий обзор дисциплин диспетчеризации

Все дисциплины диспетчеризации подразделяются на два крупных

класса – бесприоритеные и приоритетные. Бесприоритетные

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

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

отброшены. Приоритетные дисциплины диспетчеризации, в свою

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

динамическими приоритетами. Дисциплины со статическими

приоритетами предполагают, что приоритет события

, возникающего в

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

неизменным в течение всего времени работы системы. Напротив,

дисциплины с динамическими приоритетами декларируют

непрерывную корректировку приоритета события. Каждый из

подходов имеет и достоинства, и недостатки.

Быстродействующие устройства в составе аппаратуры компьютера

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

этих

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

не изменяющийся во времени.

Как показывает практика, событие, однажды определённое как

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

таковым постоянно. К таким событиям можно отнести, например,

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

прямого доступа к памяти в составе накопителя на жёстких дисках или

сетевого адаптера

. Малейшее увеличение времени реакции здесь

приводит к резкому снижению пропускной способности всей

операционной системы. К тому же на изменение приоритета задачи,

будь то программный или аппаратный способ реализации, уйдёт

152

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

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

приоритетами.

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

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

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

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

приоритетами. Разработчики современных операционных систем

нашли

выход из положения в виде системы со смешанными

приоритетами. При таком способе диспетчеризации весь интервал

приоритетов разбивается на две части. Интервал более высоких

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

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

приоритетами. В литературе значения этого интервала обозначаются

как IRQL (Interrupt Request Level). Такое название было применено при

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

Windows. Низкоприоритетный

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

реализуется как одна из дисциплин с динамическими приоритетами. В

литературе значения этого интервала именуются английским словом

Priority (собственно приоритет). Схема отношения интервалов

приоритетов иллюстрируется на рис. 1.

IRQL

0 1 2 3 … 32

APC

DISPATCH

HIGH

Приоритет простоя

Priority

0 1 2 … 32

MINIMAL DEVICE INTERRUPT

Минимальный приоритет прикладного

процесса

Максимальный приоритет прикладного

процесса

Рис. 1. Отношение аппаратных и программных приоритетов

Дисциплины диспетчеризации со статическими приоритетами

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

153

абсолютными приоритетами. И те, и другие дисциплины нашли своё

применение в современных операционных системах. В классическом

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

UNIX (в настоящее время – в Linux), для верхних половинок

обработчиков прерываний (top half) использовались относительные

приоритеты. В операционной системе Windows, напротив,

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

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

быстродействием, из чего

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

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

Современная аппаратная поддержка диспетчеризации задач

Всё изменилось при появлении в конце 1990-х годов в составе

процессоров и материнских плат компьютеров так называемого

«продвинутого» или «расширенного» контроллера прерываний – APIC

(Advanced Programmable Interrupt Controller). Его появление было

продиктовано необходимостью аппаратной поддержки

многопроцессорной и многоядерной архитектуры в составе

компьютера. С помощью APIC диспетчеризация прерываний и задач

приобрела качественно другие черты.

Контроллер APIC состоит из двух

частей (рис. 2). Одна – в составе

центрального процессора, называемая Local Apic, вторая в составе

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

IoApic. И Local Apic и IoApic могут присутствовать в системе в

нескольких экземплярах. Каждый IoApic имеет в своём составе

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

прерываний аппаратных устройств. Если объединить несколько

IoApic, то можно значительно увеличить

количество входов. В

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

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

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

подключаемых устройств.

154

Процессор

Local Apic

Процессор

Local Apic

Сигналы

Apic

IoApic IoApic

IRQ 0-23 IRQ 24-47

Рис. 2. Организация расширенного контроллера прерываний

Отличительной особенностью контроллера является то

обстоятельство, что понятие IRQL в нём введено аппаратно. Такая

организация позволяет обрабатывать прерывания значительно

быстрее. При возникновении сигнала прерывания контроллер APIC

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

повышает IRQL до уровня, заданного при установке обработчика на

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

уровень IRQL которых выше, чем текущий

. Те сигналы прерываний,

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

IRQL, выполняемого операционной системой по завершении

обработчика прерывания. При таком способе естественной

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

приоритетами.

Выводы

На основе существующих на данный момент аппаратных

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

платы архитектуры IA-32 удаётся построить диспетчер задач

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

предъявляемым требованиям. В современных операционных системах

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

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

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

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

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

Литература

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

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

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

155

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

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

3. IA-32 Intel Architecture Software Developers Manual. Volume 3:

System Programming Guide (www.intel.com).

Intel 82371FB (PIIX) AND 82371SB (PIIX3) PCI ISA IDE

XCELERATOR. April 1997 (www.intel.com).

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

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

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

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

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

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

АРХИТЕКТУРА РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ

СИСТЕМЫ И АЛГОРИТМ ДИНАМИЧЕСКОГО

ПЛАНИРОВАНИЯ ИСПОЛЬЗОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ

РЕСУРСОВ

И.Д. Ефремов, И.Д. Красинский

Самарский государственный аэрокосмический университет

им. акад. С.П. Королева

Введение

В связи с ростом числа задач, требующих сверхбольших

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

оптики, обработки изображений и др.), построение распределенных

вычислительных систем (РВС), основанных на согласованной работе

коллектива вычислителей, является актуальной задачей.

Часто РВС работает в режиме обслуживания потоков

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

распределенную программу со случайными

параметрами (числом

ветвей, набором входных параметров, временем решения и т.д.). Так

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

проблема динамического планирования распределения

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

вычислительных задач.

Реальные РВС обладают рядом особенностей: они гетерогенны,

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

параллельных ветвей, существуют простои

при передаче данных,

156

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

планирования должен учитывать

гетерогенность РВС, выбирать

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

времени.

Реализация алгоритма планирования зависит от архитектуры РВС.

Существующие технологии построения РВС (MPI, GRID и т.д.) не

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

создания программ и обслуживания.

Настоящая работа посвящена разработке и анализу архитектуры

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

использования

вычислительных ресурсов в РВС.

Архитектура РВС и требования к алгоритму динамического

планирования использования ресурсов

РВС является инфраструктурой для распределенных программ и

должна реализовывать общие для многих алгоритмов задачи: передачу

данных по сети, репликацию данных, миграцию задач, подсчет

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

поступивших задач и вычислительного ресурса узлов РВС. Кроме

этого, РВС должна планировать, распределять и балансировать

нагрузку по узлам для оптимизации времени решения

задач и

минимизации простоев узлов.

Часто параллельные алгоритмы (например, матричные алгоритмы

[3]) не могут использоваться на практике без учета архитектуры

распределенной ВС. Одним из неудобств разработки параллельных

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

они содержат алгоритмы передачи данных по сети. Предлагается

решить эту проблему, переложив функции оптимальной передачи

данных

на РВС. Распределенная программа должна лишь определить

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

параллельные алгоритмы используют стандартные топологии (кольцо,

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

уже реализованной в РВС стандартной топологией.

Для успешного развития и использования РВС должна

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

распределенных программ,

упрощая их разработку.

Такой подход позволяет сформулировать требования к

архитектуре РВС.

157

РВС должна быть модульной. Это требование позволит гибко

наращивать возможности самой РВС и расширять

ассортимент программ.

Распределенная природа РВС требует простого и

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

программ на узлах РВС.

Гетерогенность узлов РВС и каналов связи, возможность

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

ресурсов узла ВС, стохастический и заранее неизвестный

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

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

(задачами этого алгоритма являются минимизация простоев

узлов и балансировка нагрузки в зависимости от текущего

вычислительного ресурса).

Нестабильность узлов и каналов связи РВС требуют наличия

системы репликации данных и миграции задач.

Гетерогенность каналов связи требует наличия системы

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

алгоритма (возможно, с применением пиринговых

технологий).

Работа этих и других элементов инфраструктуры требует

постоянного подсчета метрик, например, оценки

вычислительной сложности задач и вычислительного ресурса

узлов.

Определив требования к архитектуре РВС, мы можем определить

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

вычислительных ресурсов. Алгоритм должен:

 учитывать гетерогенность ВС при распределении задач по

узлам;

 выбирать число параллельных ветвей (и, соответственно,

узлов);

 минимизировать возможные потери времени на передачу

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

вычислителей;

 строить оценки времени решения задачи на конкретном узле,

учитывая вычислительный ресурс узла и вычислительную

сложность задачи;

158

 учитывать неизбежные погрешности планирования на

следующих шагах работы алгоритма.

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

В работе [1] задача динамического планирования была

сформулирована следующим образом.

Имеется РВС

{

}

JJ J=…

, состоящая из

узлов, а также

конечный набор

{

}

II I= K

задач, каждая из которых

характеризуется переменным рангом

r (числом параллельных ветвей

в программе),

iir

rrr

−

≤

1, ,iL

…

и временем решения

()

iii

ttr

Каждую задачу

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

параллельных ветвей

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

{, , , }

PP P=…

– так что

∀

∈

∃

∈

0, 1iL

…−

0, 1kK=…−

, т.е. существует соответствие между задачей и ее типом.

Каждый из типов задач

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

сложностью

()

при заданном наборе входных данных

. Каждый

узел РВС

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

. Введем

эти характеристики таким образом, что время вычисления некоторой

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

, распределенной для решения на

вычислитель

()

. (1)

Общий вычислительный ресурс системы можно оценить как

−

∑

. (2)

Общую вычислительную сложность набора задач

оценим как:

()

−

∑

Время вычисления задачи:

159

(

)

ˆˆ

() max () ()

ii i i i i i

tr t t t r Ar

∈

=+ + +

, (3)

где

– время начала вычисления ветви

на узле

;

()

– время

вычислений ветви

на узле

;

– количество параллельных ветвей

решения задачи

()

– функция, характеризующая размер

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

алгоритма.

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

происходит решение одной задачи или подзадачи. Рассмотрим РВС в

некоторый момент времени. Как видно из рисунка 1 (слева), из-за

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

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

решения последней ветви на узле j

Рис. 1

Рисунок 1 – пример графика выполнения ветвей задачи без

равномерной балансировки нагрузки (а) и при равномерной

балансировке нагрузки (б). Белые и черные прямоугольники – ветви

двух разных задач.

Видно, что требуется балансировка нагрузки на узлы РВС,

учитывающая вычислительный ресурс узлов (т.е.

гетерогенность

РВС) и вычислительную сложность задач.

Как видно из рисунка 1а, равномерная балансировка

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

большее количество узлов ВС почти одновременно (с

некоторой

погрешностью

, которую можно учесть на следующем шаге

планирования). Это расширяет возможности следующего шага

160

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

распараллеливания.

Выбор

количества ветвей распараллеливания является

нетривиальной задачей. Этот выбор ограничен, с одной стороны,

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

другой – убыванием выигрыша от увеличения количества ветвей.

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

узлы РВС таким образом, чтобы на каждом шаге работы алгоритма

были заняты все свободные узлы РВС и задачи

вычислялись примерно

одновременно. Так как новые задачи могут требовать данных,

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

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

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

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

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

сортировать вычислители

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

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

выбором (большими ограничениями) к задачам с большей свободой

выбора.

Для

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

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

действия на стороне вычислителя во время решения им предыдущей

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

тут же переходит к решению следующей задачи, что

минимизирует

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

планирования и распределения задач.

Определение вычислительной сложности задач и

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

прогоном всех типов программ, поддерживаемых РВС, с различными

наборами входных параметров. Во время работы РВС можно уточнять

полученные оценки вычислительной сложности и вычислительного

ресурса.

Сформируем набор задач

{

}

II I= K

KNM

, где

–

количество типов алгоритмов,

– количество вычислителей

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

0,mM=

. В результате последовательного (сначала на всех

компьютерах тестируем тип 0 M раз, потом тип 1 M раз и т.д.)