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

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

281

Название алгоритма Среднее время работы

Бинарный метод с каскадной

схемой параллельного умножения

)2(

kO +

Бинарный метод с параллельным

умножением и возведением в

квадрат

)2(

, при условии

2≥c

Бинарный метод с параллельными

вычислениями для (

q,w)-

представления чисел

)(

, при условии

2≥c

Таблица 1. Временная сложность параллельных алгоритмов возведения в

степень по модулю (

c - количество ядер вычислительной системы)

1.23

1.22

1.17

1.03

0.77

1.42

1.33

1.13

1.53

1.92

1.86

1.15

0.00

0.20

0.40

0.60

0.80

1.00

1.20

1.40

1.60

1.80

2.00

0 1024 2048 3072 4096

Бинарный метод с каскадной

схемой параллельного

умножения

Бинарный метод с

параллельным умножением и

возведением в квадрат

Бинарный метод с

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

для (q,w)- представления

чисел

Рис. 1. График зависимости ускорений параллельных алгоритмов от длины в

битах

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

модулю

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

счисления с основанием

mbmb

ppp

modmod

)2(...)2()2(

−

+++

, (4)

где

⎥

⎤

⎢

⎡

– количество 2

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

степени.

Тогда формулу возведения в степень можно переписать

следующим образом:

mbbbmb

ppp

mod...)))(...((mod

021

222

−−

. (5)

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

282

Сначала с помощью последовательного умножения на

основание

вычисляются и сохраняются значения

mod

для всех

t 20 <≤

Затем используется следующая итерационная формула:

1,...,,mod))mod((,1

limmbrrr

iil

=⋅==

−

. (6)

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

Оценка времени работы для данного метода

)2)12(

−++Θ

Данный алгоритм имеет смысл распараллеливать на основе

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

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

малым модулям

Пусть

ppp ,...,,

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

условиям:

1),(,1, =⇒≠=∀

ppНОДjisji

;

20,1 <<=∀

psi

;

∏

∑

pmpP

)(4

. (7)

Любое число

]1,0[

−

∈

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

своими остатками от деления на

),...,(

1 s

xxx =

, где

)(mod

pxx

≡

. (8)

Теорема 1 (Китайская теорема об остатках в явном виде).

Пусть

ppp ,...,,

- попарно взаимно простые положительные целые

числа, обозначим

∏

. Обозначим

),...,(

1 s

www

представление числа

w в остатках по модулям p

, причем

w <

, m -

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

283

значение

),...,(

1 s

www =

). Пусть

- решение сравнения

)(mod1

≡

iiii

phwl mod)(≡

. Обозначим

∑∑

−=

roundmPm

)()mod()mod(

, (9)

тогда

)(mod mtw ≡

∑

≤

pmt

. Функция round осуществляет

округление до ближайшего целого числа.

Данная теорема дает возможность восстанавливать по

представлению числа

w в остатках по модулям p

его обычный вид и

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

m, причем

большая часть вычислений может быть эффективно распараллелена.

Тогда модифицированный вариант

-арного алгоритма с

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

заключаться в следующем:

Перевод числа

mb mod

в представление в остатках по

модулям

(осуществляется параллельно).

Предварительные вычисления

mod

для всех

t 20 <≤

помощью покомпонентного умножения по модулю

m на

основе теоремы 1 (большая часть вычислений осуществляется

параллельно).

Затем используется формула (6). На каждой итерации

вычисление

и умножение получившегося значения на

mod

1−

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

остаток по модулю

m. Остаток по модулю m берется только

для получившегося значения

)mod(

mbr

−

⋅

, при этом

используется теорема 1. На каждой итерации большая часть

вычислений осуществляется также параллельно.

Также заметим, что используемые значения

Pppp

,,...,,

mP mod

и h

могут либо вычисляться перед 1-м этапом 2

-арного

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

(длины в битах чисел), либо

могут браться уже «зашитые» значения для распространенных

значений

4096,2048,1024,512=k

284

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

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

перед 1-м этапом алгоритма:

)

256

16(

2((

+−+

. (10)

Полученная оценка отражает неплохую масштабируемость

алгоритма, при правильном выборе

n, S и c можно получить неплохое

ускорение.

Заключение

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

из которых наиболее подходящий – на основе (

q,w) представления

чисел. Он дает значительное ускорение, но абсолютно не

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

возможность эффективного распараллеливания на уровне реализации

длинной арифметики.

Распараллеливание

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

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

значительное ускорение и масштабируемость.

Дальнейшие направления продолжения работы:

 Распараллелить бинарный метод с CRT-представлением с

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

масштабируемость (на кластере ОГУ).

 Сократить количество умножений путем использования

метода движущегося окна в связке с параллельной CRT

арифметикой.

Литература

1. Нестеренко М.Ю., Полежаев П.Н. Подходы к

распараллеливанию алгоритмов с открытым ключом //

Математика. Информационные технологии. Образование:

Материалы региональной научно-практической конференции

в двух частях. Часть 1. – Оренбург: ГОУ ОГУ, 2006.

Нестеренко М.Ю., Полежаев П.Н. Разработка параллельного

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

для криптосистемы RSA //Материалы шестого

международного научно-практического семинара

«Высокопроизводительные вычисления на кластерных

285

системах». Том 2. /Под ред. проф. Р.Г. Стронгина. Санкт-

Петербург, 2007. – с.105-112.

Вельшенбах М. Криптография на Си и С++ в действии. – М.:

Триумф, 2004. – 464 с.

Фергюсон Н., Шнайер Б. Практическая криптография. – М.:

Вильямс, 2005. – 424 с.

ОБЗОР МЕТОДОВ ДИНАМИЧЕСКОЙ БАЛАНСИРОВКИ

НАГРУЗКИ В ГЕТЕРОГЕННЫХ КЛАСТЕРНЫХ СИСТЕМАХ

А.А. Потапов

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

Введение

Методы динамической балансировки нагрузки (БН) составляют

важную часть механизма обеспечения эффективного использования

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

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

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

центрального процессора (ЦП) [1-4], оперативной памяти (ОП) [5,6],

комбинации процессора и памяти [7-9], дисковых устройств ввода-

вывода (УВВ) [10-14] и комбинации ЦП, ОП и УВВ

[15-17]. В рамках

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

балансировки, учитывающие один или несколько (комбинацию)

критических ресурсов.

Методы БН на основе ЦП

Для обозначения методов БН на основе центрального процессора

(ЦП) в зарубежной литературе встречается обозначение “CPU-RE”

[1,3,8,9,13,14]. Обозначим загрузку процессора

i-го узла гетерогенной

кластерной системы как

load

CPU

(i), тогда ее численное значение можно

определить согласно выражению [3,14]:

)

max

()(

iCPU

Liload

⋅=

где

– количество выполняемых i-м узлом задач. Если значение

load

CPU

(i) является большим, чем заданный порог, то i-й узел системы

считается перегруженным по ЦП и метод CPU-RE передает вновь

286

поступающие запросы на

j-й узел, который имеет наименьшую

загрузку по процессору.

Методы БН на основе ЦП лучше всего подходят для систем c

централизованной балансировкой нагрузки (ЦБН), имеющих стойкую

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

узлов. Основной недостаток всех методов ЦБН заключается в их

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

вследствие использования лишь одного

активного узла БН. Попытки

преодоления ограничений методов ЦБН предпринимались

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

группы ученых под руководством Харкол-Болтера (Harchol-Balter), в

которой удалось усовершенствовать метод ЦБН путем добавления

механизма приоритетной миграции [1]. В результате чего был получен

метод распределенной балансировки однородной нагрузки (РБОН) на

основе ЦП, более эффективный, чем

исходный метод ЦБН [2].

Методы БН на основе ЦП и ОП

Группа ученых под руководством Ин Чжана (Ying Zhang)

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

нагрузки (РБОН), предложенный Харкол-Болтером, добавив в нее

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

памяти (ОП). Таким образом, был получен метод распределенной

балансировки неоднородной нагрузки (РБНН), получивший

обозначение в зарубежной литературе “CM-RE” [5,6,13,14]. Этот

метод последовательно учитывает загруженность ЦП и ОП.

Пусть объем ОП, требуемый для выполнения всех задач i-го узла

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

load

mem

(i), тогда ее

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

∑

∈

mem

jmemiload )()(

где

mem(j) – количество ОП, требуемое j-й задачей; N

– количество

задач, выполняющихся на

i-м узле. Если количество ОП i-го узла

больше или равно значению

load

mem

(i), то вместо метода CM-RE

активизируется метод CPU-RE. Если значение

load

mem

(i) превышает

объем доступной ОП, то метод CM-RE осуществляет передачу вновь

пребывающих запросов на узлы с наименьшим значением загрузки

памяти

load

mem

(i).

В работе [8] приведено экспериментальное доказательство того,

что полученный Ин Чжаном метод РБНН, построенный на основе

287

комбинации двух критических ресурсов – ЦП и ОП, является более

эффективным, чем исходный, основанный лишь на ЦП. Поэтому метод

РБНН CM-RE, учитывающий совокупность ресурсов ЦП и ОП, на

практике применяется гораздо чаще, чем методы РБОН на основе ЦП

или ОП.

Методы БН на основе дисковых УВВ

Большое количество литературы посвящено вопросу БН в

дисковых УВВ [10-13]. Один из методов БН на основе сведений об

интенсивности дисковых операций ввода-вывода был предложен в

работе [13], где для ее краткого обозначения использовано

сокращение “IO-RE”. Этот метод в отличие от рассмотренных двух

предыдущих учитывает не степени загруженности ЦП и ОП, а

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

ввода-вывода, которая измеряется на

основе анализа двух типов обращений к дисковым УВВ: явных и

неявных. Неявные обращения к подсистеме ввода-вывода вызваны

промахами при обращении к страницам ОП, вследствие

неэффективности механизма кэширования, явные – связаны с

необходимостью обмена данными с дисками по запросам задач. Пусть

уровень загрузки диска

i-го узла гетерогенной кластерной системы,

создаваемый неявными обращениями к диску

j-й задачи, обозначается

как

page(i,j), а IO(i,j) обозначает загрузку диска, создаваемую явными

обращениями

j-й задачи. Тогда уровень загрузки i-го узла можно

определить согласно выражению:

∑

∈∈

NjNj

jiIOjipageiload ),(),()(

(1)

Порог ввода-вывода

i-го узла, означающий максимально

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

не приводящий к перегрузке, обозначим как

threshold

(i). Так, i-й

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

если значение

load

(i) является большим, чем threshold

(i). Величина

порога

threshold

(i) должна соответствовать мощности подсистемы

ввода-вывода

i-го узла и может быть подсчитана как:

∑

⋅=

jload

ithreshold

)()(

(2)

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

подсистемы ввода-ввода

i-го узла, а правая часть – суммарной

288

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

заданиями гетерогенного кластера.

Производительность дискового УВВ

i-го узла (D

) может быть

рассчитана по формуле:

disk

(3)

где

disk

, S

и R

обозначают соответственно пропускную способность

диска, среднее время поиска данных и среднее время вращения диска

i-го узла, а d – средний размер данных, передаваемых по запросам

ввода-вывода.

Таким образом, порог ввода-вывода для

i-го узла threshold

(i)

можно подсчитать при помощи формулы 2, подставив вместо

load

(i).

значение выражения 1.

В общем случае метод «IO-RE» осуществляет балансировку

поступающего на

i-й узел j-го запроса за четыре этапа. Во-первых,

обновляется нагрузка

i-го узла путем добавления нагрузки,

создаваемой явными и неявными обращениями

j-й задачи к дисковой

подсистеме. Во-вторых, подсчитывается порог ввода-вывода согласно

выражению (2). В-третьих, если дисковая подсистема ввода-вывода

го узла не перегружена, то

j-я задача выполняется на i-м узле. Если i-й

узел перегружен по операциям ввода-вывода, то метод «IO-RE»

отправляет

j-ю задачу для выполнения на узел k, отвечающий двум

основным условиям:

 дисковая подсистема ввода-вывода не перегружена;

 разность нагрузок на подсистему ввода-вывода k-го и i-го

узлов больше, чем нагрузка по вводу-выводу, создаваемая

j-й

задачей.

Если балансировщик нагрузки находит подходящий

k-й узел, то

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

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

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

перегрузку. На четвертом этапе, после того как запрос поступил на

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

соответствии с нагрузкой,

создаваемой j-й задачей.

Известны также другие методы БН по УВВ. Например, Ли (Lee) и

другие в работе [11] предложили два алгоритма распределения файлов,

289

которые позволяют осуществлять БН между всеми доступными

дисками системы. Исерт (Isert) и Шван (Schwan) в работе [13]

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

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

системы. Методы балансировки однородной нагрузки по ресурсу УВВ,

предложенные в их работе, так же как и метод, рассмотренный выше,

являются достаточно эффективными

и позволяют увеличить

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

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

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

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

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

использующих ЦП и ОП [15].

Методы БН на основе комбинации ЦП, ОП и УВВ

Достаточно хорошие методы БН систем, задачи которых

интенсивно используют комбинацию ресурсов ЦП, ОП и УВВ,

предложены коллективами авторов в работах [8,14]. В их основу

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

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

коэффициентах, подсчитываемых индивидуально для каждого узла.

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

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

образом, что время

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

основным недостаткам методов можно отнести отсутствие механизма

миграции задач от одного узла к другому, а также то, что они не

предусматривают возможности для выполнения удаленных операций

ввода-вывода. Попытку преодоления недостатков метода предприняла

группа ученых под руководством Чжана (Zhang). Они

добавили

механизм приоритетной миграции задач [17]. Однако полученный в

результате их доработки метод оказался слишком ресурсоемким и

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

загрузкой ОП, даже по сравнению с исходными методами [8,14]. Более

того, величина стоимости миграции данных в работе [17] учитывает

лишь затраты на миграцию содержимого ОП, игнорируя при этом

накладные расходы

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

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

общей стоимости миграции и должны учитываться при БН.

290

Совместить положительные стороны методов, предложенных в [8,

14], и метода, полученного Чжаном (Zhang), сохранив при этом

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

руководством Ксяо Чин (Xiao Qin). В качестве основы они

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

«Input-Output/CPU/Memory» (IOCM) [14,15], что расшифровывается

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

качестве критических ресурсов совокупность дисковых УВВ, ЦП и

ОП. Метод является достаточно простым и эффективным, даже,

несмотря на то, что в IOCM отсутствует механизм приоритетной

миграции (чтобы подчеркнуть этот факт, метод обозначают еще как

«IOCM-RE»). Метод IOCM-RE позволяет учесть возможность

выполнения задачами удаленных операций ввода-вывода, благодаря

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

выполнение операций ввода-вывода к другим

узлам и принимать

результаты выполнения этих запросов. IOCM-RE построен на основе

комбинации политик IO-RE и CM-RE и действует согласно

следующему алгоритму:

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

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

(IO-RE);

 если отсутствует явная загрузка подсистемы ввода-вывода или

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

необходимых страниц в ОП, то применяется метод

балансировки на основе ОП (CM-RE);

 если узел способен справиться с растущими потребностями

задач в ОП, то активируется метод балансировки на основе

ЦП (CPU-RE).

В работе [16] метод «IOCM-RE» был доработан путем добавления

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

результате чего получил обозначение «WAL-PM». Метод «WAL-PM»

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

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

гетерогенных

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

нагрузкой.