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

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

331

Рис. 3. Характер изменения

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

(Тест 1)

Для повышения эффективности решения рассматриваемого класса

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

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

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

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

технологии MPI и OpenMP. Так, при вычислении ускорений на

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

используя многопоточность

⎡⎤

=− −

⎢⎥

⎣⎦

∑∑

&& &

j-1j

ttt-t t

uMR u u

На рисунке 2 (кривая «Б») приведены зависимости времени

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

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

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

вариантом очевидны.

Рассмотренные варианты распараллеливания не позволяют

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

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

количество

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

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

процессам элементы каждого типа. Однако, это приведет к

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

полный вектор

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

одновременным суммированием вкладов. На рисунке 2 (кривая «В)

332

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

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

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

решения и масштабируемость 3-го варианта алгоритма существенно

хуже, чем у варианта 2 (кривая «Б).

На рисунке 4 показано время передачи и суммирования массива из

100000 чисел двойной точности с помощью процедуры

MPI_ALLREDUCE в зависимости от числа задействованных

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

кластере (Тест 2). Очевидно, что эти операции существенно более

затратны, чем операции в задаче «Тест 1». Этим и объясняется плохая

эффективность третьего варианта алгоритма.

Рис. 4. Характер изменения времени выполнения процедуры

MPI_ALLREDUCE для различной конфигурации процессов (Тест 2)

Работа выполнена при финансовой поддержке Фонда НИОКР РТ и

Фонда содействия развитию малых форм предприятий в научно-

технической сфере.

Литература

1. Черников С.К., Садчиков Ю.В., Ашихмин А.Н. Решение

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

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

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

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

кластерных системах». Санкт-Петербург: Издательство СПГУ.

2007. С.226-234.

Черников С.К., Баскевич Т.П. Анализ динамической реакции

конструкции на вычислительных кластерах. Труды шестого

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

333

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

кластерных системах», Санкт-Петербург: Издательство СПГУ.

2007. С.217-225.

ВЫСОКОПРОИЗВОДИТЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ

СИСТЕМЫ В ИВАНОВСКОМ ГОСУДАРСТВЕННОМ

ЭНЕРГЕТИЧЕСКОМ УНИВЕРСИТЕТЕ

Л.П. Чернышева

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

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

системы (ВВС) применяются в научных и технических исследованиях,

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

высококвалифицированных специалистов в области

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

года, в Ивановском государственном энергетическом университете

(ИГЭУ) в лаборатории параллельных вычислений, в 2000 году

преобразованной в кафедру

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

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

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

параллельных вычислений.

В 1995 году ИГЭУ была приобретена многопроцессорная

вычислительная система Parsytec Power X’plorer. Она состоит из

процессоров с сокращенным набором команд PowerPC-601 и

транспьютера T805. Система включает в себя восемь процессоров.

Parsytec Power X’plorer работает под управлением операционной

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

базе ANSI C.

В 2006 году была приобретена кластерная система с

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

каждом по два двухъядерных процессора AMD Opteron 2ГГц. Общее

число процессоров – 128 процессоров. Кластерная система вошла в 7-

ую редакцию рейтингового списка Тор50. С 1 сентября 2007 года

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

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

читаются курсы "Параллельные

вычисления" и "Нейрокомпьютерные

системы и параллельные вычисления". Данные курсы являются

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

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

334

Студентам электроэнергетического факультета читаются курсы по

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

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

этого же факультета читается курс по численным методам и

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

Магистрам электромеханического читается курс по

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

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

Курсы для студентов и магистров электроэнергетического и

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

вводными курсами в

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

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

программированием и не являющихся специалистами по

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

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

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

"Информатика и вычислительная техника" по программе 552802

"Высокопроизводительные вычислительные системы". Курсы,

читаемые магистрам, направлены на формирование

высококвалифицированных специалистов

, подготовленных к

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

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

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

знаний по параллельному программированию, формирование у них

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

системах.

Структура курсов по программированию на

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

следующим принципам:

Модульность – в зависимости от подготовки и специфики

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

необходимые им темы. Каждая тема является завершенной и

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

Последовательность – курсы по параллельному

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

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

являются более сложными.

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

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

335

Адаптивность – последовательность прохождения тем и

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

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

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

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

контролем.

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

552802 "Высокопроизводительные вычислительные системы",

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

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

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

вычислений.

Студенты и магистры, изучающие данные курсы, участвуют в

работе научных студенческих конференций, проходящих каждый год в

университете. Они выступают с докладами в секции "Численные

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

АНАЛИЗ ПАРАЛЛЕЛИЗМА В МЕТОДЕ ДЕДУКТИВНОГО

ВЫВОДА ДЕЛЕНИЕМ ДИЗЪЮНКТОВ

М.М. Шихов

Вятский государственный университет, Киров

Введение

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

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

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

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

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

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

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

параллельных архитектур при их

построении. С другой стороны, если

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

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

возможности таких систем.

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

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

модифицированном исчислении предикатов первого порядка. Сам

336

метод подробно описан в монографии [2]. Модификация исчисления

описана в [3]. Далее приводятся лишь основные идеи метода.

Согласно [1] различают три вида параллелизма дедуктивного

вывода:

 параллелизм на уровне термов (parallelism at the term level);

 параллелизм на уровне заключений (parallelism at the clause

level);

 параллелизм на уровне поиска (parallelism at the search level).

Первому виду параллелизма в рассматриваемом методе

соответствует алгоритм унификации литералов – поиск наиболее

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

[2-4]). Данный алгоритм является базовым. Временные затраты

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

литералов, унифицируемыми термами (константами, переменными,

функциональными буквами), рекурсивной вложенностью термов и т.д.

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

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

оправдывают.

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

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

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

наиболее общий унификатор

в процессе унификации N литералов

делимого

X и M литералов делителя Y. Если рассматривать делимое и

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

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

литералов:

YXM

⋅

∩

⋅

YXM

⋅

−

⋅

XYM

⋅

−

⋅

337

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

Если наиболее общий унификатор не был найден, то это

соответствует тому, что

∅

, M

=X, M

=Y. Множество λ,X есть

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

соответствии с унификатором

λ.

Согласно [4] суть рекурсии сводима к следующему:

 большая задача делится на меньшие подзадачи;

 подзадачи решаются аналогично большой задаче, то есть

рекурсивно (на некотором этапе решение становится

тривиальным и не требует разбиения);

 решения подзадач объединяются (связываются) вместе так,

чтобы получить решение исходной задачи.

Процесс поиска всех возможных вариантов множеств

, M

является рекурсивным.

В исходных множествах X, Y выделяются все возможные пары

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

унификатор (НОУ). Получив таким образом варианты (…,<

CD,i

, M

RX,i

, M

RY,i

>,…); если же ни один НОУ не может быть

найден, то тривиальное решение.

Множества M

RX,i

, M

RY,i

(а также M

RX,i

CD,i

, M

RY,i

; M

RX,i

RY,i

CD,i

) используются в качестве исходных X и Y в

подзадачах рекурсивно.

Полученные решения - множество вариантов (…,<λ

, M

CD,i

RX,i

, M

RY,i

>,…) объединяются так, чтобы не было дубликатов.

Подзадачи можно решать параллельно. На этом же уровне

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

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

на один общий делитель

Y (заключение). В данном случае

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

деления дизъюнктов, но параллельного её выполнения для различных

дизъюнктов базы знаний.

338

Деление

N- 1

N-1

БЗ

Результат

Рис. 2. Параллелизм данных на уровне заключений

Третий вид параллелизма – параллелизм на уровне поиска – это

задача логического вывода, которая (упрощенно) также рекурсивна:

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

& D

&… & D

N-1

требуется доказать истинность всех

дизъюнктов. Первый путь решения - поиск контрарных пар

литералов в каждом дизъюнкте. Второй путь - выполнить

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

дизъюнкт заключения

(0≤i<N). В результате будем

получать формулу

& O

&… & O

M-1

, для которой

необходимо доказать

& O

&… & O

M-1

=ЛОЖЬ. После

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

D’

& D’

&… &

D’

N’-1

=ИСТИНА.

Решение исходной задачи сведено к рекурсивному решению

подзадач доказывающих

D’

& D’

&… & D’

N’-1

=ИСТИНА.

Полученные множества решений (НОУ) в ходе доказательства

истинности отдельного

(0≤i<N) необходимо объединить

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

объединенных множествах не принимали различных значений

(были согласованы). Если это условие невыполнимо – вывод

неуспешен.

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

параллельно. Время решения подзадач может быть различным. В

данном случае важно, что согласованное объединение решений –

ассоциативная и коммутативная операция, поэтому для

подзадач

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

решения можно объединять параллельно с решением оставшихся

подзадач. Объединение

N решений можно организовать c временными

затратами

O(log

(N)).

339

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

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

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

полученные решения с временными затратами O(log

(N)). Если хоть в

одном дизъюнкте контрарных пар нет или НОУ для таких пар не

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

Также возможно распараллеливание алгоритма преобразования

формулы

& O

&… & O

M-1

=ЛОЖЬ

в формулу

D’

& D’

&… & D’

N’-1

=ИСТИНА.

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

дизъюнктов, формирование которых можно совместить во времени.

Пусть

= L

i,0

i,1

|…|L

i,Mi-1

(0≤i<M) в составе O

& O

&… & O

M-1

– количество литералов в дизъюнкте O

. Формула O

& O

&… &

M-1

=ЛОЖЬ преобразуется в !O

& !O

&… & !O

M-1

=ИСТИНА. Затем

& !O

&… & !O

M-1

преобразуется в D’

& D’

&… & D’

N’-1

, где

(

)

'0,|...||

110

,1,1,0

NlLLLD

kMkkl

<≤=

−

. Где 0≤k

<Mi

соответствии с формулами

∏

−

, (1)

()

∑

∏

−

+==

0110

,...,,

jiM

Mkkkkkl

. (1)

При имеющихся

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

параллельное формирование дизъюнктов

на k-м узле:

()

KNklKNk /'1/'

⋅

<≤⋅

при

≤

Заключение

Были выделены основные алгоритмы, временные затраты на

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

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

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

использование систем с общей памятью. Реализация параллелизма на

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

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

слабо связанных по данным. Представляется целесообразным

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

340

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

как правило, являются многопроцессорными или многоядерными.

Параллелизм на уровне поиска (parallelism at the search level) в данном

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

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

интерфейсов MPI), а параллелизм оставшихся уровней (parallelism at

the term level, parallelism at the clause level) на уровне отдельных узлов

кластера (прикладных интерфейсов Threads, Open MP). Также интерес

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

Cluster OpenMP, как

сочетающего перечисленные возможности.

Литература

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

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

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

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

ISBN 5-9221-0474-8.

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

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

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

Шихов М.М. Использование дополнительного типа

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

предикатов. / М.М. Шихов // Всероссийская научно-

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

экология»: Сборник материалов : в 8 т. – Киров : Изд-во

ВятГУ, 2006. Том 1. ФАВТ, ФПМТ – с. 227

Люгер Дж.Ф. Искусственный интеллект: стратегии и методы

решения сложных проблем, 4-е издание [Текст] / Люгер,

Джордж, Ф. – Пер. с англ. – М. : Издательский дом 'Вильямс',

2003. – 864 с. – С.5-217.