г. Новосибирск, 15-17 октября 2012 г.

Перепелкин В.А.   Ткачева А.А.  

Особенности параллельной реализации синхронных и блочно-синхронных клеточных автоматов в технологии фрагментированного программирования

Докладчик: Перепелкин В.А.

Одним из немаловажных применением высокопроизводительных вычислительных кластеров является численное моделирование химических и физических процессов с помощью клеточно-автоматных моделей (КА). [1] В работе рассматриваются особенности параллельной реализации КА с использованием технологии фрагментированного программирования. [2] При этом рассматриваются только КА, функционирующие в синхронном и блочно-синхронном режимах. В качестве примера был выбран КА, моделирующий реакцию окисления монооксида углерода на поверхности палладия. [1]
Такие блочно-синхронные КА представляются относительно простой задачей для параллельной реализации. Как правило, используется метод распараллеливания domain decomposition, когда матрица ячеек КА разрезается на блоки по процессорам с дублированием и пересылкой значений теневых граней. Тем не менее, для обеспечения более высокой производительности мультикомпьютера существует ряд приёмов, таких как асинхронные вычисления, конвейерное исполнение по итерациям, фрагментация поля на блоки, умещающиеся в кэш-памяти, совмещение буферов итераций со сдвигом и прочие. Реализация этих приёмов увеличивает и сложность разработки программы, и на практике применяется далеко не всегда.
Технология фрагментированного программирования (ТФП) [2], разрабатываемая в ИВМиМГ СО РАН, ориентирована на реализацию численных моделей для мультикомпьютеров. При этом акцент ставится на то, чтобы технологически поддержать программирование сложных свойств программы, подобных тем, что описаны выше. В ТФП описание программы представляется в трёхслойном виде. Первый слой содержит описание структур данных и процедур без побочных эффектов, используемых в программе. Для их описания используется традиционный язык программирования, например C++. Второй слой содержит ациклический двудольный орграф операций единственного срабатывания и переменных единственного присваивания, называемых фрагментами вычислений (ФВ) и фрагментами данных (ФД) соответственно. Каждый ФВ реализуется вызовом процедуры из первого слоя, которая применяется к конкретным ФД, а ФД реализуется блоком данных в памяти. На втором слое, таким образом, описывается структура вычислений, безотносительно их интерпретации. Для описания второго слоя используется язык фрагментированного программирования LuNA. Третий слой описывает отображение ФВ и ФД на ресурсы мультикомпьютера во времени – процессоры и память. Для описания третьего слоя также используется язык LuNA. Три слоя вместе образуют фрагментированную программу (ФП), которая является исполняемым представлением для исполнительной run-time системы.
Первые два слоя определяют «содержательную» часть программы – то, какие выходные значения будут выработаны из входных. Третий же слой определяет производительность мультикомпьютера на этой задаче. С помощью задания третьего слоя возможно реализовывать оптимизирующие приёмы исполнения, описанные выше. При таком подходе, во-первых, нет опасности внести в программу ошибку, т.к. третий слой не влияет на «содержание» вычислений; во-вторых, описать требуемое поведение программы проще, чем программировать его вручную (например, средствами MPI), т.к. происходит на высоком уровне в виде описания отображений.
В работе представлены две параллельные реализации для мультикомпьютера упомянутого блочно-синхронного клеточного автомата: с использованием MPI и в системе фрагментированного программирования LuNA. Представлено сравнение этих реализаций с точки зрения удобства разработки прикладной программы и эффективности полученной реализации.
1. Елохин В.И., Матвеев А.В., Городецкий В.В., Автоколебания и химические волны в реакции окисления СО на Pt и Pd: кинетические модели Монте-Карло. // Кинетика и Катализ - 2009, том 50, № 1, стр. 46-53.
2. Victor Malyshkin, Vladislav Perepelkin. Optimization methods of parallel execution of numerical programs in the LuNA fragmented programming system // The Journal of Supercomputing, Special issue on Enabling Technologies for Programming Extreme Scale Systems, Volume 61, Number 1 (2012), pp. 235-248, DOI: 10.1007/s11227-011-0649-6

Тезисы доклада:abstracts_138091_ru.pdf


К списку докладов

Комментарии

Имя:
Код подтверждения:

2.
xcunULlPMObdM11.11.2012 06:44
9ridxs , [url=http://mnrrukdxczew.com/]mnrrukdxczew[/url], [link=http://chjmvoszeupx.com/]chjmvoszeupx[/link], http://hngoozhmabow.com/
1.
wSSIQdAiJjN09.11.2012 14:24
Me dull. You smart. That's just what I nedeed.