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

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

211

шаге вывода, а в случае метода вывода делением дизъюнктов – на

втором. Однако количество шагов является спорной оценкой скорости

выполнения методов. Следует ориентировочно оценить сложность

каждого шага.

На каждом шаге вывода резолюционными методами по графу

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

(резольвент) происходит повторный анализ потенциальной

резольвируемости дизъюнктов, то есть связи

в графе анализируются

повторно. Эта проблема лишь частично решается применением

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

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

(появляются дополнительные дизъюнкты). При больших масштабах

задачи с большим количеством дизъюнктов на эту процедуру может

уйти довольно много времени, даже если подвергать оценке лишь

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

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

(резольвенты). Кроме того, выбор конкретного множества связей для

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

определённой эвристике. Для этого может понадобиться

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

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

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

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

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

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

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

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

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

масштабных задачах с большим количеством литералов в дизъюнктах

это может быть целесообразно. Как уже упоминалось

выше, возможно

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

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

Метод деления дизъюнктов не требует какой-либо сложной

предварительной подготовки. Процесс деления дизъюнктов не многим

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

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

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

дизъюнктов. Кроме самого деления дизъюнктов на текущем шаге

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

необходимости формируется новая выводимая секвенция.

212

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

дизъюнктов не только имеет меньшее количество шагов вывода, но и

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

Прежде всего это утверждение обусловлено необходимостью анализа

(а возможно и построения заново) графа связей и учёта эвристик для

резолюционных параллельных методов.

Выводы

Приведённый пример демонстрирует особенности двух основных

методов логического вывода. При этом видно преимущество метода,

основанного на делении дизъюнктов. Вывод при использовании

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

каждого шага меньше. Однако стоит заметить, что реальные отличия

между методами можно пронаблюдать лишь на реальной масштабной

задаче. Недостатком метода DCDP-резолюции является не только

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

определённых эвристик при выборе конкретного DCDP-множества.

Комбинация трёх методов резолюционного вывода (OR, AND, DCDP)

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

уменьшить количество бесполезных порождаемых резольвент [2].

Однако в общем случае количество шагов будет большим, нежели в

методе деления дизъюнктов.

Литература

1. Страбыкин, Д.А. Логический вывод в системах обработки

знаний [Текст] / Д.А. Страбыкин; под ред. Д.В. Пузанкова;

СПбГЭТУ. СПб., 1998. – 164 с.

Вагин, В. Н. Достоверный и правдоподобный вывод в

интеллектуальных системах [Текст] / В.Н. Вагин, Е.Ю.

Головина, А.А. Загорянская, М.В. Фомина; под ред. В.Н.

Вагина, Д.А. Поспелова. – М. : Физматлит, 2004. – 704 с. –

ISBN 5-9221-0474-8.

213

ВОЗМОЖНОСТИ РАСПАРАЛЛЕЛИВАНИЯ ФУНКЦИИ

DGEMM НА SMP-СИСТЕМАХ

М.С. Кукушкин, Н.В. Фролова

СарФТИ, Саров

На сегодняшний день все большую популярность приобретают

вычислительные системы более чем с одним ядром (будь то SMP или

распределенная система). С появлением новых процессоров с двумя

(Intel Conroe, AMD Opteron), а теперь и четырьмя ядрами они

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

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

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

из самых известных - MPI и OpenMP.

MPI (Message Passing Interface) – стандарт для написания

параллельных приложений как на распределенной, так и на общей

памяти. Существует большее количество реализаций MPI (MPICH,

Intel MPI и др.) на различных платформах. OpenMP (Open Multi

Processing) – стандарт для написания параллельных приложений на

разделяемой памяти. Стандарт OpenMP должен поддерживаться

компилятором. На данный момент это ICC, GCC начиная с версии

4.2.0, PGI, Pathscale. Несмотря на поддержку разделяемой

памяти в

MPI, MPI и OpenMP имеют разные области применения. На

разделяемой памяти реализация на OpenMP логически проще и

читабельней, чем с использованием MPI. Другой вариант

распараллеливания на общей памяти – использование системных

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

кода – код на OpenMP кроссплатформенный.

ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ РЕШЕНИЯ

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

РЕСУРСОВ В ИЕРАРХИЧЕСКИХ СИСТЕМАХ

Е.А. Куликова

Нижегородский государственный университет

Введение

Задачи распределения ресурсов возникают при решении

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

систем, в планировании расходов и управлении деятельностью

214

предприятий. Примерами таких задач являются задача объемно-

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

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

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

разнородной сети. Математическая модель задач рассматриваемого

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

алгебраических неравенств. Задано множество критериев

оптимальности, определяющих эффективность функционирования

системы. Необходимо

найти все допустимые Парето-оптимальные

решения поставленной задачи. В работе [1] рассматривается общий

алгоритм решения подобных задач. В настоящей работе исследуется

параллельный подход к решению многокритериальных задач

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

Общая математическая модель

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

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

образом. Заданы булевы матрицы A и B, размерностей соответственно

m×k и n×k, действительный неотрицательный вектор

размерности m

и векторная функция

)( yF

, определенная на множестве n-мерных

векторов из

со значениями из {0, 1, …, p-1}. Функция

)( yF

отображает пространство

на множество вершин n-мерного p-

ичного куба. Требуется найти вектор

, удовлетворяющий

ограничениям

cxA

≤

с учетом минимизируемых критериев

)( xBF

Получаем n-критериальную задачу с линейными ограничениями и

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

)( yF

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

cxA

≤

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

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

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

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

неравенств, такие как метод ортогональных проекций Агмона-Моцкна.

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

ограничений задачи может быть

решен путем сведения этой системы к

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

системе. Данный подход исследован для систем неравенств, имеющих

215

эквивалентное представление в виде древовидной структуры [3], или в

виде потоковой модели [4, 5]. Для данных частных классов

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

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

Постановка многокритериальной задачи

Определим функцию критериев

)( yF

следующим образом. Для

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

друга сегментов

⊆

2,0 −= pt

, p≥1,

ni ,1=

. Тогда

iGj

txF =

∑

∈ )(

)(

, если

iGj

Sx ∈

∑

∈ )(

но 1

)(

−

∈

∉

∑

iGj

. После этих

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

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

вектор

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

∑

∈

≤

)(

iRj

mi ,1=

, с

учетом минимизируемых критериев

iGj

txF =

∑

∈ )(

)(

}1,...,1,0{

−

∈

ni ,1=

. Получаем задачу с m линейными ограничениями и n кусочно-

постоянными критериями.

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

быть применены различные схемы компромисса. Алгоритм решения

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

оптимальности рассмотрен в работе [3]. В данной работе исследуется

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

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

Пусть эффективной

вершиной n-мерного p-ичного куба называется

такая вершина

)...,,,(

zzzz =

, для которой

,1)(

=zf

и при этом

для любой вершины

),...,,,(

zzzz =

nizz

,1,

=≥

, для которой

существует по крайней мере одна компонента

zz >

.0)(

=zf

Каждой вершине n-мерного p-ичного куба

),...,,(

21 n

zzzz

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

неравенств транспортного типа

)(zS

cxA

≤

zxF

≤)(

. Для каждой

вершины

эта система всегда включает исходные ограничения задачи

cxA

≤

(эта часть неравенств остается неизменной и от выбора

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

216

значения критериев, которые не должны превышать границы,

заданные вершиной

. То есть решениями системы неравенств

)(zS

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

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

критериев не превышают значения, определяемые вершиной

, то

есть выполняются дополнительные условия

zxF

≤

)(

ni ,1=

Зададим на множестве вершин куба функцию

)( zf

принимающую значение 1, если система

)(zS

совместна, и 0 в

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

)( zf

является

монотонной: если

≤

(покомпонентно), то

≤)(

)(

Параллельный алгоритм решения многокритериальной

задачи

Алгоритм поиска всех эффективных вершин n-мерного p-ичного

куба, представленный в работе [1], состоит из двух этапов: 1) проверка

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

задачи внутри области, полученной на этапе 1 в случае, если решение

не единственно.

Рассмотрим данный алгоритм, модифицированный для

применения в многопроцессорных системах. Пусть h – количество

параллельных процессоров, а

T – это время проверки на совместность

одной вершины на процессоре. На первом этапе алгоритма

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

них произвести по

log

вычислений. В последовательном варианте

это займет

pnT

log

⋅

единиц времени. Если h

≥

n, то время работы

первого шага алгоритма сокращается в n раз и становится равным

log⋅

. Если же h < n, то необходимо последовательно загружать

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

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

обработанное задание. К сожалению, более мелкое разделение работ

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

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

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

217

этапа алгоритма в

⎥

⎦

⎤

⎢

⎣

⎡

раз. В этом случае оценка времени работы

первого этапа

log1 ⋅

⎟

⎠

⎞

⎜

⎝

⎛

⎥

⎦

⎤

⎢

⎣

⎡

⋅

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

свою работу. Если же задача не имеет единственного решения, то

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

На втором этапе необходимо произвести поиск внутри некоторого

гиперпараллелепипеда, полученного на первом этапе решения задачи.

Пусть размер самого широкого ребра этого гиперпараллелепипеда

равен k,

,10

−

≤≤ pk

а индекс, соответствующий ему в n-мерном

векторе значений критериев, равен j. Тогда на втором этапе алгоритма

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

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

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

что после того, как такой отрезок оказался полностью рассмотрен,

монотонность функции

)( zf

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

куба, которые лексикографически предшествуют или последуют уже

исследованным вершинам. Свойство монотонности

)( zf

дает

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

непосредственного трудоемкого подсчета. Отсюда вытекает

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

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

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

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

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

координацию

процесcоров. С другой стороны, можно предполагать, что это время

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

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

Предлагается следующий способ распределения работ по

процессорам. Из h имеющихся процессоров выберем один

координирующий. В этом вычислительном узле будет объединяться

информация обо всех

рассчитанных вершинах куба и тех вершинах,

значение функции

)( zf

в которых определяется исходя из

монотонности. По остальным h-1 процессорам будем распределять все

имеющиеся отрезки для поиска. После подсчета каждой вершины

218

процессор передает координатору информацию об этой вершине и

получает новые данные об уже рассчитанных вершинах. Происходит

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

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

координатором

где

. Тогда, учитывая то, что в

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

log

−

вершин куба,

получаем, что общее время работы второго этапа алгоритма на

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

меньшую, чем

.1)

(log1

log

⎟

⎠

⎞

⎜

⎝

⎛

−

+⋅≤⋅

⎟

⎠

⎞

⎜

⎝

⎛

⎥

⎦

⎤

⎢

⎣

⎡

−

kkTT

ατ

Здесь первое слагаемое отражает последовательную часть

алгоритма, не подлежащую параллелизации, а второе показывает

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

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

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

1)1)((

log

)

(log

log

+−+

−

kkh

kTk

βα

αα

раз.

Здесь

log

−

при k, n > 2. Отсюда видно, что при h > 2

< ¼ и

< ¼ параллельное исполнение алгоритма дает

преимущество перед однопроцессорным.

Таким образом, общее время работы алгоритма при прохождении

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

⎟

⎠

⎞

⎜

⎝

⎛

−

+⋅+

−

(loglog

kkpT

в случае, когда h ≥ n и

⎟

⎠

⎞

⎜

⎝

⎛

−

+⋅+

⎟

⎠

⎞

⎜

⎝

⎛

⎥

⎦

⎤

⎢

⎣

⎡

−

(loglog1

kkp

, если h < n.

Заключение

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

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

транспортного типа. Подобные задачи имеют большую размерность,

219

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

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

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

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

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

всего множества Парето-оптимальных решений, модифицированый

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

Литература

1. Прилуцкий М.Х., Куликова Е.А. Многокритериальные задачи

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

Электронный журнал «Исследовано в России», 085, стр. 891-

900, 2007 г. http://zhurnal.ape.relarn.ru/articles/2007/085.pdf.

Черников С. Н. Линейные неравенства.- М.: Наука, 1968, 488с.

Прилуцкий М. Х. Многокритериальное распределение

однородного ресурса в иерархических системах. // Автоматика

и телемеханика. Москва, 1996, с. 149-156.

Афраймович Л.Г., Прилуцкий М.Х. Многоиндексные задачи

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

Автоматика и телемеханика, 2006, №6, с.194-205.

Прилуцкий М. Х., Афраймович Л. Г. Условия совместности

многоиндексных систем транспортного типа. Электронный

журнал «Исследовано в России», 70, стр. 762-767, 2005.

http://zhurnal.ape.relarn.ru/articles/2005/070.pdf.

Воеводин В. В. Математические модели и методы в

параллельных процессах. Москва: Наука, 1986, 296 с.

ОБ ОПТИМИЗАЦИИ РАСПРЕДЕЛЕНИЯ ВЕТВЕЙ

ПАРАЛЛЕЛЬНЫХ MPI-ПРОГРАММ ПО ПРОЦЕССОРНЫМ

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

М.Г. Курносов, А.А. Пазников

Сибирский государственный университет телекоммуникаций

и информатики, Новосибирск

Введение

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

(ВС) в немалой степени зависит от того, каким образом организовано

220

их функционирование. В большинстве случаев современные

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

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

процессорными ядрами. Например, в системах Cray XT4 и IBM

BlueGene/L время передачи сообщений между парой процессорных

элементов зависит от их размещения в трехмерном торе, а в

(мульти)кластерных и вычислительных GRID-системах

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

организацию, в

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

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

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

общей памяти.

Доминирующее положение при разработке параллельных

программ для таких систем занимает стандарт MPI. Программа,

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

представлена информационным графом, вершинам которого

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

коммуникации между ними.

Обладая информацией о структуре параллельной программы,

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

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

ветвями.

В данной работе рассматривается задача назначения ветвей MPI-

программы на процессорные ядра ВС с целью минимизации времени

ее выполнения.

Постановка задачи

Считаем, что ВС функционирует в одном из основных режимов [1]

- обработки набора или обслуживания потока задач.

Пусть G = (V, E) – информационный граф параллельной

программы, поступившей в систему, где V = {1, 2, …, M} – множество

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

VVE

⊆ –

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

(коммуникации).

На множестве вершин V и ребер E могут быть заданы весовые

функции, характеризующие количество арифметических и логических

операций, выполняемых ветвями, а также объемы данных и размеры

сообщений, передаваемые между процессами.