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

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 004. 021
ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ АСИНХРОННЫХ КЛЕТОЧНО-АВТОМАТНЫХ АЛГОРИТМОВ
К.В. Калгин
В статье предлагается алгоритм распараллеливания асинхронного клеточного автомата, основанный на его вероятностных свойствах. Приводятся результаты тестирования на кластере МСЦ МВС-100 000. Ключевые слова: параллельный алгоритм, методы Монте-Карло, асинхронный клеточный автомат, клеточный автомат.
Введение
В настоящее время известно много клеточно-автоматных моделей природных явлений, которые, в зависимости от назначения, различаются алфавитом состояний, структурой дискретного пространства, правилами переходов и режимами функционирования [1]. Имеются два базовых режима работы клеточных автоматов (КА) — синхронный и асинхронный. В некоторых случаях также используют смешанные синхронно-асинхронные режимы [2] - блочно-синхронный и упорядоченный.
КА моделирование реальных процессов требует больших вычислительных мощностей, поскольку для выявления в них каких-либо свойств необходимо оперировать большим количеством клеток (1010−1012) в течение длительного времени (103−105 итераций). Основные свойства КА — естественная мелкозернистая параллельность и локальность взаимодействий — делают эту модель привлекательной для использования при моделировании на мультикомпьютерах. Однако асинхронные КА не поддаются столь же легкому распараллеливанию, как синхронные.
Асинхронные клеточные автоматы (АКА), рассматриваемые в данной статье, применяются в основном для моделирования кинетических процессов в наносистемах. Известны результаты их применения для изучения поверхностных химических реакций на катализаторах [3], адсорбции, сублимации и диффузии атомов при эпитаксиальном росте кристаллов [4], при исследовании процессов диссоциации водорода в пористых электродах водородного энергетического элемента, а также при проектировании режимов напыления металлов для получения твердых и антикоррозийных покрытий [2].
Известны два варианта [5] асинхронного режима — пошаговый (step-driven) и повременной (time-driven). В первом случае итерация разбивается на шаги, и на каждом шаге с равной вероятностью может быть выбрана любая клетка для изменения состояния, а во втором — время следующего изменения определяется экспоненциально распределенной случайной величиной. В статье рассматриваются АКА первого типа, они требуют существенно меньших накладных расходов на организацию вычислений, в отличие от АКА второго типа, и при этом на больших размерах клеточной области эквиваленты им. Результаты распараллеливания повременного (time-driven) АКА представлены в [6].
Асинхронный клеточный автомат
Асинхронный клеточный автомат, как и синхронный, определяется набором [Zd, A, V, ф), где Zd — конечное подмножество дискретного d -мерного пространства,
которое определяет множество местоположений клеток, A — множество возможных состояний клеток, V — шаблон соседства — набор векторов, определяющий соседство
клетки х е Zd, V (х) = |х + v | v е V} е Zd, а ф: A|V| ^ A — правило перехода в новое состояние. Под срабатыванием клетки далее понимается изменение ее состояния по правилу перехода.
Клеткой будем называть пару (х, а) е X х А, где, а е, А — состояние клетки, а х е 7й — ее координата. Множество клеток О = {(х, а)} е Xй х А, в котором нет клеток с одинаковыми координатами, будем называть клеточным массивом. Далее будем отождествлять клетку и ее координаты, поскольку в клеточном массиве между ними существует взаимно однозначное соответствие.
В работе рассматривается двумерная прямоугольная область Xй = X2 размера Nх х Ыу, а в качестве шаблона соседства — окрестность фон Неймана
V = {(-1,0), (0, -1), (1,0), (0,1), (0,0)}.
Процесс работы АКА разбивается на итерации, которые состоят из X2 = NхNy
шагов. Шагом будем называть единичное применение функции перехода к некоторой случайно выбранной клетке. Таким образом, в ходе одной итерации АКА реализуется
некоторая случайная последовательность клеток С = {с1,…, с| 2| | с{ е X2}.
Вероятностные свойства АКА
При распараллеливании клеточный массив делится между процессами на непересекающиеся домены Д, Б2, …,. Множество граничных клеток домена Бк будем обозначать Вк = {с е Бк | 3/ Ф к: V© IФ 0}. Рассмотрим поведение АКА при моделировании одним процессом, но при логическом делении клеточного массива на домены.
Пусть С = {с1,…, С| 2| | с{ е X2} - упорядоченное множество клеток, которое определяет порядок срабатывания во время одной из итераций (рис. 1). Пусть гпк = С п (Пк Вк) — упорядоченное множество внутренних срабатываний, а
Ъоипйк = С п Вк — граничных срабатываний домена Вк.
Рис. 1. Последовательность срабатываний одной итерации
Пусть Ьк = {/0к,?к,… ,/кг,…, 1Ъкоип, где /0к = 0, а — номера шагов, на которых происходят срабатывания клеток из множества Ъоипйк.
Пусть 1 кг = {сг е гпк | /кг-1 & lt- г & lt- /кг } - упорядоченное множество клеток, срабатывания которых происходят внутри домена Вк между двумя срабатываниями на его границе. Для лучшего понимания на рис. 2 графически отображены множества Ьк и 1 кг.
Рис. 2. Разбитый на подмножества порядок срабатывания
По C и по разбиению Z2 на домены однозначным образом определяется множество троек
4(0) = {(Lk, boundк, II) |1 & lt- k & lt- p^ & lt- г & lt- boundk},
но обратное неверно — далеко не всегда по У (C) порядок срабатывания восстанавливается однозначно.
Рассмотрим другой порядок C'- с таким же разбиением, У (C'-) =). Тогда порядки C и C'- могут отличаться лишь в упорядочивании клеток из, относящихся к
различным доменам, а упорядочивание клеток внутри и на границах, а также между границами доменов сохраняется. Следовательно, исполнения C и C'- на одинаковых начальных клеточных массивах приводят к одним и тем же результатам — в этом случае эти два порядка будем называть эквивалентными.
Таким образом, для исполнения очередной итерации вместо порядка C достаточно сформировать некоторое разбиение У (C). Поскольку на каждой итерации порядок
формируется по определенным правилам, то и У (C) должно формироваться в соответствии со своими вероятностными характеристиками элементов множеств Lk, размеров
множеств Ik и boundk:
P (lk — lh = t|t& gt- 0)=(1 ^ у-в
где pk = Bk |/|
Z2
A!
(1 -ak)A-t
Z 2 Bb
д| = t) = - И t!(Л -Г)!
омиальное распределение, где Л = ^ -1, а ак = Ок Bk | /
= - 1
Алгоритм формирования У^) кратко можно описать следующим образом.
(1)
(2) (3)
1. В соответствии с (1) генерируются величины l^, тем самым определяя boundk и |Lk|. Пусть х — экспоненциально распределенная случайная величина с параметром X = - log (1 — Pk), тогда P (|_хJ = t) = (1 — pk) t 1 — pk, откуда получаем
lk = lh + [randEхp (-log (1 -pk))], где randEхp (X) — генератор псевдослучайных чисел экспоненциального распреде-
ления.
а
1. Пользуясь генератором псевдослучайных чисел биномиального распределения randBin (A, а), в соответствии с (2) получаем
ikr | = randBin (A, аk).
2. Размеры множеств boundk и Ikr уже определены, а их элементы (координаты клеток)
получаются с использованием генератора псевдослучайных чисел равномерного распределения.
Стоит заметить, что разбиение Y (C), сформированное по такому алгоритму, определяет множество эквивалентных порядков, у каждого из которых общее число срабатываний во всем клеточном массиве является случайной величиной с математическим ожиданием Z.
Реализация параллельного алгоритма
1. Построение Y©. Для каждого домена Dk соответствующим процессом строится набор (bk, boundk, I^. Затем процессы, отвечающие соседним доменам Dk и Dk, обмениваются множествами Lk, boundk и Lk, boundk,.
2. Исполнение итерации. Состояния клеток в каждом домене Dk последовательно изменяются в соответствии с полученными порядками обхода boundk и Ikp. Если очередная клетка с лежит на границе, с е boundk, и ее номер из Lk есть lk, то в соответствии с множествами Lk, и boundk, полученными от соседних процессов, выполняется следующее:
для каждого соседнего домена Dk, и для каждого срабатывания клетки с'- е boundk, с
номером lk е Lk, такого, что lk & lt- lk, с'- е V ©, причем состояние клетки с'- еще не было
получено после последнего изменения, получаем состояние клетки с'- от процесса k '- - применяем функцию перехода к клетке с е boundk —
для каждого соседнего домена Dk выполняем: если существует срабатывание клетки с'- е boundk. с номером lk е Lk, такое, что lj & lt- lk и с е V (с'-), то отсылаем новое состояние граничной клетки с соответствующему процессу.
Результаты тестирования
В качестве КА модели для тестирования была выбрана модель Изинга — математическая модель намагничивания материала в статистической физике. Описание модели в терминах АКА можно найти в [6].
Тестирование проводилось при следующих условиях. Размер клеточной области Z2| = NxNy, где Nx = 215 = 32 768 и Ny = 214 = 16 384, а Z2 делится на прямоугольники,
по форме максимально приближенные к квадратам. Используемый кластер — МСЦ МВС-100 000 (восемь процессорных ядер Xeon в одном узле). Эффективность вычисляется по формуле e = T1/(p*Tp), где p — количество используемых процессоров, а Tk -время счета на k процессорах.
1 2 4 8 16 32 64 123 256 512
Процессоры а
1 2 4 8 16 32 64
Процессоры
б
Рис. 3. а — эффективность работы при использовании всех процессоров всех узлов, б — сравнение эффективности работы при использовании одного (серые столбцы) или всех (черные столбцы) процессоров каждого из вычислительных узлов
Запуск производился в двух режимах — при использовании всех процессоров всех узлов (рис. 3, а) и при использовании лишь одного процессора из каждого узла. Сравнение эффективности работы в этих режимах (рис. 3, б) показало, что эффективность второго режима приблизительно в два раза больше. Это может быть объяснено тем, что скорость случайного доступа в память при восьми работающих процессорах на порядок меньше, чем при одном процессоре.
Заключение
В статье был предложен новый алгоритм крупноблочного распараллеливания АКА, основанный на его вероятностных свойствах. Представленные результаты тестирования реализации свидетельствуют о пригодности ее применении для моделирования больших АКА моделей реальных процессов на достаточно большом количестве процессоров.
Дальнейшая работа заключается в исследовании влияния на ускорение формы шаблона соседства V, сложности функции перехода ф и способах деления клеточной области Z2.
Литература
1. Бандман О. Л. Клеточно-автоматные модели пространственной динамики // Сборник научных докладов «Системная информатика». — Новосибирск: Изд-во СО РАН, 2006. — Вып. 10.
2. Bandman O.L. Coarse-grained parallelization of cellular-automata simulation algorithms // Parallel Computing Technologies. — Heidelberg: LNCS Springer. — 2007. -Vol. 4671. — Р. 370−384.
3. Elokhin V.I. Application of Statistical Lattice Models to the Analysis of Oscillatory and Autowave Processes on the Reaction of Carbon Monoxide Oxidation over Platinum and Palladium Surfaces // Kinetics and Catalysis. — 2003. — Vol. 44. — Р. 672−700.
4. Neizvestny I.G. 3D-model of epitaxial growth on porous {111} and {100} Si surfaces // Computer Physics Communications. — 2002. — Vol. 147. — Р. 272−275.
5. Schonfisch B., de Roos A. Synchronous and asynchronous updating in cellular automata // BioSystems. — 1999. — Vol. 51. — Р. 123−143.
6. Overeinder B.J., Sloot P.M.A. Extensions to Time Warp Parallel Simulation for Spatial Decomposed Applications // Proceedings of the 5th annual conference of the Advanced School for Computing and Imaging (ASCI). — 1999.
Калгин Константин Викторович — Новосибирский государственный университет,
студент, KalginKV@gmail. com
УДК 004. 75
АРХИТЕКТУРА СЕРВИС-ОРИЕНТИРОВАННОЙ РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ И ЕЕ РЕАЛИЗАЦИЯ НА ОСНОВЕ ФРЕЙМВОРКА 0801
А. В. Гаврилов, И. И. Доровских, И.Д. Красинский
Создание распределенных вычислительных систем является актуальным для решения больших вычислительных задач. В ходе анализа существующих РВС и технологий их построения был выделен ряд недостатков. Предложена архитектура РВС, позволяющая избежать обозначенных проблем. Реализованная по ней РВС с применением фреймворка 08в1 была использована для решения конкретных задач и показала свою эффективность.
Ключевые слова: распределенная вычислительная система, фреймворк, распределение ресурсов, планирование ресурсов, жизненный цикл, сервис-ориентированная система
Введение
Распределенная вычислительная система (РВС) [1] представляет собой систему, обеспечивающую инфраструктуру для запуска и выполнения задач на множестве входящих в нее узлов, работающих, например, на персональных компьютерах, объединенных сетью. В настоящее время такие системы составляют серьезную конкуренцию кластерам в силу активного распространения и роста компьютерных сетей. Для РВС адаптируют алгоритмы решения различных задач — расчета напряжений в сложных механизмах [2], расчета микро- и нанооптических элементов, обработки большеформатных изображений, различных задач математической физики. В основном это задачи, требующие сверхбольших вычислительных и временных затрат, например трехмерный рендеринг сложных деталей.
В данной работе описано видение сервис-ориентированной (СО) архитектуры РВС, которое положено в основу разработанной авторами системы. Результаты реализации показывают не только возможность такого подхода, но и некоторые его преимущества.

ПоказатьСвернуть
Заполнить форму текущей работой