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

(MPI_Init, MPI_Comm_Rank, MPI_Comm_Size, MPI_Comm_Finalize),

которые встречаются в любой параллельной программе, простые функции пересылки данных (MPI_Send и MPI_Recv), и функции групповых коммуникаций (MPI_Reduce, MPI_Scatter и другие).

Эмулятор реализован в виде Win32 приложения, которое после ввода пользователем параметров самостоятельно компилирует и запускает соответствующее число ветвей параллельного приложения.

Информационные материалы

Этот раздел портала предполагает создание сайта поддержки параллельных вычислений. Здесь планируется размещать информацию по всем проблемам данного направления: от теории численных методов и их распараллеливания до практики отладки распределенных программ. В Интернете уже сейчас есть много информации по данной тематике.

В нашем портале будут размещаться копии русских документов, переводы иностранных и собственные материалы. Одним из первых будет электронный учебно-методический комплекс «Многопроцессорный вычислительные системы и параллельное программирование» («МВС и ПП»), созданный на кафедре ЮНЕСКО по НИТ К.Е. Афанасьевым, С.В. Стуколовым, А.В. Демидовым и В.В. Малышенко[3]. Данный комплекс официально зарегистрирован в Реестре баз данных Российского агентства по патентам и товарным знакам (Роспатент, свидетельство № 2003620094).

Те компоненты портала, которые существуют к настоящему моменту, пока что реализованы только на уровне прототипов и не могут быть открыты для публичного использования. Для начала активного использования компонентов портала, необходимо:

•завершить реализацию системы удаленного доступа с базовым набором функций;

•усовершенствовать статистику, выдаваемую эмулятором о ветвях параллельного приложения, перевести ее в графический вид;

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

•разработать и реализовать информационный сайт портала.

По завершению первой очереди работ, вычислительный портал будет готов к использованию в процессе подготовки специалистов по параллельным вычислениям на МФ КемГУ

11

После того, как будут реализованы поддержка защищенных протоколов передачи данных по глобальным сетям; поддержка вызова клиентом процедур и функций, хранимых на сервере; и поддержка серий экспериментов (запуск одной расчетной программы с различными исходными данными в автоматическом режиме) – система будет открыта для доступа пользователям, сторонним по отношению к КемГУ.

Построенные модели вполне допускают подобное расширение функциональности, и этот процесс пройдет в основном путем добавления нового программного кода с минимальным исправлением уже написанного.

Литература

1.Афанасьев К.Е., Гудов А.М. Информационные технологии в численных расчетах. Кемерово, 2001. 203 с.

2.Демидов А.В., Сидельников К.В. Эмуляция параллельной обработки данных на персональном компьютере // XLI Международная научная студенческая конференция «Студент и научно-технический прогресс». Сб. трудов. Новосибирск, 2003. С. 110-111.

3.Многопроцессорные вычислительные системы и параллельное программирование / Афанасьев К.Е., Стуколов С.В., Демидов А.В., Малышенко В.В. Кемерово, 2003. 181 с.

ИСПОЛЬЗОВАНИЕ OPENMP ПРИ РАСЧЕТЕ ВЛИЯНИЯ ДЕНЕЖНОЙ ПОЛИТИКИ ЦЕНТРАЛЬНОГО БАНКА НА ПРОИЗВОДСТВО

М.Н. Банникова, Д.А. Сивков

Удмуртский госуниверситет, г.Ижевск

Описание модели

Одним из основных факторов оказывающих воздействие на экономику является денежная политика Центрального банка по отношению к коммерческим банкам. Влияние денежной политики Центрального банка на производство можно представить в виде следующей схемы (см. [1])

12

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

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

Для поиска решения задачи (1) применяется метод золотого сечения. Вычисление определённых интегралов осуществляется по правилу Рунге для составной квадратурной формулы Симпсона. Для вычисления многомерных интегралов составляется рекурсивная процедура.

Поиск решения задачи (2)–(3) осуществляется с помощью метода штрафных функций и метода простого поиска.

В процессе решения поставленных задач требуется многократное вычисление значений максимизируемых функций. На эти вычисления приходятся значительные временные затраты. Поэтому возникла необходимость в распараллеливании последовательной программы.

Как отмечалось выше, для вычисления многомерных интегралов составляется рекурсивная процедура. Но в связи с возникшими проблемами при распараллеливании было решено найти другой подход к вычислению многомерных интегралов. Выбор остановился на статистических методах, которые удобны для распараллеливания.

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

Параллельная программа была написана на языке C-OpenMP и транслировалась компилятором Intel C compiler 7.1.

Для сравнения времени работы последовательной и параллельной программ были проведены тестовые расчеты на кластере PARC Удмуртского госуниверситета c использованием предоставленного для тестирования компанией Intel компьютера SPSH4 (4 процессора Intel XeonMP 2GHz 2Mb).

Сравнительный анализ

15

В случае, когда n = 1, т.е. подынтегральная функция является одномерным интегралом, параллельная программа будет эффективна, если число потоков больше 8. Красной линией показано время работы последовательной программы с рекурсивным вычислением интегралов.

16

Похожая ситуация возникает, когда n = 2. В этом случае число потоков должно быть не меньше 4.

Иная картина возникает в случае n = 3. Здесь, даже когда параллельная программа выполняется последовательно (число потоков равно 1), время её выполнения меньше, чем время выполнения последовательной программы. Это может объясняться иным методом вычисления интегралов. Однако и в этом случае для одного потока временные затраты всё равно остаются существенными. Поэтому, увеличивая число потоков можно добиться значительного уменьшения времени выполнения параллельной программы.

Литература

1.Автухович Э.В., Петров А.А., Поспелов И.Г., Шананин А.А. Исследование с помощью математической модели влияния на производство денежной политики центрального банка http://isir.ras.ru/ win/ db/show.

2.Автухович Э.В., Шананин А.А. Модель отрасли производства в условиях дефицита оборотных средств // Математическое моделирование , 2000. Т.12, №7. С.102-126.

3.Introduction to OpenMP http://www.llnl.gov/.

17

АССОЦИАТИВНАЯ ВЕРСИЯ АЛГОРИТМА ПОИСКА В ГЛУБИНУ*

Т.В. Борец

ИВМиМГ, г. Новосибирск borets@ssd.sscc.ru

систематического обхода графа. Он используется для решения многих задач исследования операций, искусственного интеллекта и других разделов информатики. Последовательный алгоритм хорошо известен и описан в книгах по теории графов и информатики [1–3]. Этот алгоритм выполняется за время O(n+m), где n – число вершин графа, а m – число его ребер. Параллельная реализация этого алгоритма на MIMD – архитектуре приведена в [4, 5].

Вданной работе представляется алгоритм, выполняющий поиск в глубину на абстрактной модели ассоциативного параллельного процессора с вертикальной обработкой данных (STAR-машина). Эта модель относится к классу SIMD-архитектур и была представлена в

[6].

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

Модель STAR-машины

STAR-машина состоит из

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

•матричной памяти;

•устройства ассоциативной обработки, состоящего из p одноразрядных процессорных элементов (p = 2i).

Для этой архитектуры в работе [6] был разработан язык высокого

уровня STAR, поддерживающий язык PASCAL. Чтобы моделировать обработку информации в матричной памяти в языке STAR имеются переменные типов данных slice, word и table. Переменная типа slice (далее слайс) моделирует доступ к таблице по столбцам, а переменная

* Работа выполнена при поддержке Российского фонда фундаментальных исследований (грант № 03-01-00399)

18

типа word – доступ по строкам. С каждой переменной типа table ассоциируется бинарная таблица из n строк и k столбцов, где n ≤ p. Также в язык были добавлены операции над этими типами данных. Мы приведем только те операции, которые необходимы для изложения алгоритма.

Пусть X и Y – слайсы, i – целочисленная переменная. Тогда SET(Y) записывает в слайс Y все единицы; CLR(Y) записывает в слайс Y все нули; Y(i) выделяет i-ю компоненту в слайсе Y (1 ≤ i ≤ p); FND(Y) выдает порядковый номер i позиции первой (или старшей) единицы в слайсе Y, где i ≥ 0; STEP(Y) выдает такой же результат, как и операция FND(Y) и затем обнуляет старшую единицу. Общепринятым способом вводятся предикаты ZERO(Y) и SOME(Y), а также следующие побитовые логические операции: X and Y, X or Y, not X, X xor Y.

Для переменных типа word выполняются те же операции, что и для переменных типа slice. Для переменных типа table определены следующие операции: COL(i,T) и ROW(i,T), которые выделяют из таблицы Т i-й столбец и i-ю строку, соответственно.

Следуя Фостеру [7], мы допускаем, что каждая элементарная операция STAR-машины выполняется за единицу времени. Поэтому сложность алгоритма определяется числом элементарных операций, которые выполняются в наихудшем случае.

Для реализации алгоритма нам потребуется следующая базовая процедура из [8], которая выполняется на STAR-машине за время пропорциональное числу битовых столбцов таблицы T.

Процедура MATCH(T: table; X: slice; v: word; var Z: slice)

определяет позиции тех строк таблицы Т, которые совпадают со словом w. Процедура возвращает слайс Z, в котором Z(i)=‘1’ тогда и только тогда, когда ROW(i, T)=w и X(i)=‘1’.

Необходимые определения

Напомним некоторые определения из теории графов. Ориентированным графом (орграфом) G называется пара

множеств (V, E), где V={1,…, n} – конечное множество вершин, Е – множество дуг (E VΧV).

Пусть e=(u, v) E – дуга графа, тогда вершину v будем называть головой дуги e, а вершину u – хвостом.

19

Подграфом для графа G называется такой граф H=(W, U), у которого W V и для любых x,y W, если (x, y) E, то (x, y) U.

Поиск в глубину – метод систематического прохождения (посещения) вершин графа. Он использует следующую стратегию: идти «вглубь», пока это возможно (есть исходящие дуги в непройденные вершины), и искать другой путь, когда таких дуг нет. Так делается, пока не обнаружены все вершины, достижимые из исходной. В порядке обхода каждой вершине приписывается М-номер

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

Вматричной памяти STAR-машины орграф задается парой таблиц left и right, так что каждой дуге (u, v) E соответствует пара <u, v>. Также используется таблица code, в i-ой строке которой записан двоичный код вершины i. Подграф и дерево поиска в глубину задаются слайсами, в которых соответствующие дуги помечаются ‘1’.

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

Структура данных

Алгоритм представлен в виде процедуры, записанной на языке STAR. Процедура использует следующие входные параметры:

•таблицы left и right задают множество дуг орграфа;

•таблица code хранит двоичные коды вершин орграфа;

•слово root хранит двоичный код вершины, с которой начинается

поиск.

Алгоритм строит дерево поиска в глубину, нумерует вершины в порядке их обхода и возвращает подграф, состоящий из вершин, недостижимых из root:

•таблица NV хранит М-нумерацию вершин графа;

•слайс T задает дерево поиска в глубину ( в Т ‘1’ отмечены позиции тех и только тех дуг, которые принадлежат дереву);

•слайс Х, в котором помечены позиции дуг, ведущих в непронумерованные вершины (после завершения работы

процедуры задает подграф, содержащий только те вершины, которые недостижимы из root).

Также нам понадобятся следующие вспомогательные переменные:

•таблица LIFO, моделирующая стек (после нумерации очередной вершины в таблицу добавляется слайс, в котором ‘1’ отмечены позиции дуг, ведущих из этой вершины в непронумерованные);

20