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

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

181

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

ОПТИМАЛЬНОГО УПРАВЛЕНИЯ ВЫПЛАВКОЙ МЕТАЛЛА

Р.Ф. Кадыров

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

Научно-исследовательский институт математики и механики

им. Н. Г Чеботарева

Введение

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

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

конвекцией [1, 2]. Качество производимой стали существенно зависит

от теплового режима при затвердевании, при этом первостепенное

значение имеет поведение поверхностной температуры и фронта

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

является дорогостоящим и не всегда реализуемым процессом, поэтому

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

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

служит необходимость управления процессом в режиме реального

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

охлаждения в режиме реального времени, которая формулируется как

задача идентификации коэффициентов и решается методами

оптимального управления [3, 4].

Краевая задача

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

вдоль оси

z углами. В силу его симметрии краевая задача решается в

области

(0, )

VL=Ω×

, представляющей собой четверть слитка. Ее

граница

VΓ=∂

состоит из частей

, на которых

заданы различные граничные условия. Определению подлежит

температурное поле

(, ,,)Txyzt

в точках

(, ,)

yz V

∈

в моменты

времени

(0, ]

tT∈

. После дискретизации по времени с шагом

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

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

()

:( ) () , 0 ,

VHHdxKHdxgTHhdx V

ηη ηη

∈−+∇⋅∇+ =∀∈

∫∫ ∫

где

()

- функции энтальпии и температуры Кирхгоффа,

182

- подпространства пространств Соболева, обеспечивающие

выполнение нужных краевых условий;

(

)

- функция,

моделирующая вторичное охлаждение на границе

, а

(, ,,)hxyzt

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

После МКЭ-аппроксимации краевая задача численно решается при

помощи явной схемы Эйлера с циклом временных шагов [5].

Задача оптимизации

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

векторным параметром h в граничном условии. Считается, что граница

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

функция h постоянна. Таким образом, параметром управления

является вектор-функция

(, , , )

hhh h

, оптимальные значения

которой должны быть найдены на каждом временном слое.

Технологические ограничения приводят к следующему допустимому

множеству управлений:

min max

{: }

Uh h hh=∈

, где векторы

min

max

являются минимальными и максимальными

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

охлаждения.

Ставится задача: найти пару

(,)Th

такую, что,

(,)min((),)

Th fThh

∈

где

()Th

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

равенством

()

(,) ,

Th T h T dx

=−

∫

- заданная целевая температура на границе

В работе [4] предложен метод редукции многомерной задачи

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

параметры охлаждения h

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

зоны охлаждения к последней по направлению движения слитка.

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

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

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

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

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

183

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

решения. Проведен ряд вычислительных экспериментов, в ходе

которых показано:

Найденное численное решение близко к решению,

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

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

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

близко к линейному.

Литература

1. Laitinen E, Neittaanmaki P. On numerical simulation of the

continuous casting problem // J. Eng. Math. – 1987. – V. 22. – P.

335-354.

Louhenkilpi S., Laitinen E., Nieminer R. Real time simulation of

heat transfer in continuous casting // Metall. Trans. B. – 1993. – V.

24B. – P. 685-693.

Сиразетдинов Т.К. Оптимизация систем с распределенными

параметрами. М.: Наука, 1977 – 479 с.

Кадыров Р.Ф. Метод редукции в задаче оптимального

управления выплавкой металла // Вестник Казан. гос. техн. ун-

та им. А. Н. Туполева / Казань: Казан. гос. техн. ун-т, 2007. -

№1 – С. 44-46.

Кадыров Р.Ф., Лапин А.В. Применение явных разностных

схем при решении задачи о непрерывной выплавке стали // Тр.

Матем. центра им. Н.И. Лобачевского / Казань: Изд-во Казан.

матем. о-ва. 2003. - Т. 20. - С. 140–150.

АВТОМАТНАЯ МОДЕЛЬ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

Е.И. Калиниченко

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

Введение

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

систем (РВС, ПВС) показал, что при их эксплуатации часто

выявляются ошибки в алгоритмах их функционирования. Это

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

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

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

184

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

вычислений после устранения причин их появления. Но ошибки в так

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

воздушное движение, автомобили и другие), в системах,

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

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

необратимые финансовые потери. Объективной причиной

возникновения

ошибок является то, что размер РВС, ПВС очень

быстро растет. Большие системы могут в итоге содержать такое

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

большие программные проекты продемонстрировали это. Статистика

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

на её отладку. Ошибки, найденные после начала эксплуатации, могут

привести к перепроектированию

системы, что, в свою очередь, ведет к

задержкам в её маркетинге.

Важно отметить несоответствие темпов роста сложности систем и

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

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

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

алгоритмов работы систем. Это объясняется тем, что разработка

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

систем, содержащих

параллельные процессы, является очень сложной задачей. Одна из

причин сложности проектирования заключается в том, что, как

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

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

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

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

работы подобных систем является человеческий фактор (мышление

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

учесть вопросы надежности работы системы, обеспечиваемые

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

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

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

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

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

узла, но

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

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

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

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

185

значительно возрастает. При разработке алгоритмов работы

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

 разность в скорости работы отдельных узлов системы;

 взаимодействие узлов через коммуникационные каналы;

 отказы коммуникационных каналов, как временные, так и

постоянные.

Решение этой проблемы видится в создании формальных методов

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

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

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

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

коммуникационные сообщения в каналах) как формальные объекты и

обеспечивает

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

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

априорные характеристики её работы. Формальное описание

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

которое зависит от:

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

системы.

 доступности общих ресурсов.

 надежности коммуникаций, т.е. деления и воссоединения

сетевых соединений.

 надежности работы узлов, т.е. учета их отказов ("стоп",

"византийский").

 возможности последующего восстановления их

работоспособности.

Такой подход при проектировании даст следующие преимущества:

 позволит обнаружить неопределенности, несогласованности,

незавершенности в неформальном описании алгоритма работы

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

проектирование;

 обеспечит автоматический, машинно-связанный анализ

правильности формального описания по отношению к

исходным требованиям (верификация);

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

разработчика тестовых наборах (моделирование);

186

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

алгоритмов работы системы без дорогостоящего создания её

прототипа.

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

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

Модель

Большинство алгоритмов работы РВС и ПВС относятся к классу

так называемых систем, управляемых событиями, или "реактивных"

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

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

работы ПВС и РВС есть взаимодействие параллельных процессов на

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

моделью будет

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

(НКА) [1]. Почему? Во-первых, в модели НКА на уровне

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

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

построению модели РВС ПВС. Для описания работы каждого узла и

канала сообщения на уровне логических процессов используется

отдельный автомат. Затем, объединяя эти автоматы в

систему

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

системы. В-третьих, имеем возможность иерархичной детализации

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

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

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

возможно описывать алгоритмы работы РВС любой степени

сложности

и с любой степенью детализации.

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

описывается недетерминированным автоматом Мура. В каждый

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

временные отношения. Поэтому предлагаемая модель может быть

использована для описания как синхронных РВС и ПВС, так и

асинхронных. Таким образом, при описании поведения РВС и

ПВС

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

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

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

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

составе всей системы автоматов используются "абсолютные

187

временные метки" (системное время). "Относительные временные

метки" (такты времени) генерируются в каждом автомате отдельным

логическим процессом. Автомат имеет внешние входы и выходы,

через которые взаимодействует с другими автоматами. Автомат может

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

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

подавтоматов. Каждый подавтомат

представляет логический процесс в

узле или канале. Любой автомат, соответствующий узлу системы,

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

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

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

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

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

задержек в каналах связи.

Построение

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

метод "сверху вниз"). На этапе описания алгоритма работы

проектируемой системы (или же существующей, если выполняется

анализ её работы) строится структурная схема системы, позволяющая

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

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

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

этой структурной схемы.

Каждому узлу и каналу ставится в соответствие автомат,

описывающий алгоритм его работы. При этом в поведение автоматов

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

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

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

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

его

состояний на подавтоматы.

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

системы и возникающие внутри системы. Внешние события,

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

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

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

сигналами для других автоматов. Используя предложенный в [1]

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

вычисления (моделирование) на детерминированной системе –

недетерминированной.

Предложенный подход был использован для моделирования

протокола репликации (2PC - 2 Phase Commit) однородной

188

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

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

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

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

обеспечивающим её стабильное функционирование.

Заключение

Подводя итоги вышеизложенного, можно утверждать, что

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

естественно получаемая декомпозиция сложной системы;

использование формализованного подхода для описания и анализа;

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

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

Литература

1. Вашкевич Н.П., Вашкевич С.Н. Недетерминированные

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

Учебное пособие. – Пенза: Изд-во ПГТУ, Пенза 1996.

О ПАРАЛЛЕЛЬНОЙ РЕАЛИЗАЦИИ ВЛОЖЕННОГО МЕТОДА

РОЗЕНБРОКА ДЛЯ СЛАБОСВЯЗНЫХ ЖЕСТКИХ СИСТЕМ

ОДУ БОЛЬШОЙ РАЗМЕРНОСТИ

В.Е. Карпов, А.И. Лобанов

Московский физико-технический институт, Долгопрудный

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

дифференциальных уравнений (ЖС ОДУ) высокой размерности со

специальной структурой. В частности, при решении задач типа

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

высокого порядка аппроксимации матрица Якоби возникающей

системы ОДУ будет блочно-трехдиагональной. Поясним сказанное

подробнее на примере

простейшей системы уравнений, описывающих

процессы переноса с учетом химических реакций.

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

()

div( )

yv w

∂ρ

+ρ=

∂

Здесь ρ — массовая плотность смеси реагирующих веществ, v —

скорость смеси, y

— массовая доля фракции вещества в смеси.

189

Обозначение w

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

расходования i-й фракции вещества в единице объема за единицу

времени,

(

)

,... ,

ii k

wwy yT=

. С использованием уравнения

неразрывности перепишем его в характеристической форме:

∂∂

ρ+ρ =

∂∂

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

алгоритма решаются с помощью метода расщепления по физическим

процессам. Так, на одном этапе расщепления для каждой фракции

численно решается уравнение переноса, затем — система ОДУ,

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

узла введенной сетки.

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

невысокого

порядка аппроксимации по пространственным

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

балансировки загрузки процессоров при параллельной реализации.

Обмены при таком способе аппроксимации минимальны.

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

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

схем повышенного порядка аппроксимации на нерасширенном

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

точках шаблона

с весами, обеспечивающими повышение порядка [1].

Проиллюстрируем метод повышения порядка аппроксимации на

простейшем примере. Рассмотрим использование аналога сеточно-

характеристического метода [2]. Вдоль характеристики

каждое

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

уравнение

dy w

Рассмотрим пространственный узел расчетной сетки с индексом i

на двух соседних временных слоях. Для вычисления доли j-й фракции

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

в точке пересечения характеристики, проходящей через i-ю точку на

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

линейной интерполяции. В

каждом узле расчетной сетки получим

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

190

()

,,1

1,0

ji ji

iii

ji jk

iii

−

⎧

−

σ+ σ >

⎪

ρρ

⎪

⎨

⎪

−

σ+ σ ≤

⎪

ρρ

⎩

где

σ=

— число Куранта.

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

(,)

, (1)

где

11 1 1

(,, ,, ,, ),

kNkN

yyy y=Y KK K

11 1 1

(,, ,, ,, ).

kNkN

fff f=f KK K

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

имеет размерность k·N, где k — количество фракций вещества в смеси,

а N — число пространственных узлов внутри расчетной области. Для

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

переменных

n+1

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

значения переменных

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

по следующей схеме:

()

, , ,...,

nn n

jj i i i i

+−

−

=+γ =

∑

YY kkBδ Yk k

где

iii

=−τμBE J

()

, ,..., , 1,...,

ii ijjijj

−−

−

⎛⎞

=τ + β +τ μ =

⎜⎟

⎝⎠

∑∑

δ Yk k fY k J k

Здесь

E — единичная матрица, J — матрица Якоби системы, μ

, γ

— коэффициенты метода Розенброка, s — количество стадий

метода.

Из структуры системы следует, что матрица Якоби имеет частично

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

рис. 1.