Клеточно-автоматное моделирование физико-химических процессов на вычислителях с параллельной архитектурой тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Калгин, Константин Викторович

• Калгин, Константин Викторович
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Калгин, Константин Викторович

Введение

Глава 1. Формальное представление асинхронных вероятностных клеточно-автоматных моделей физико-химических процессов

1.1. Формальное представление клеточного автомата

1.2. Локальный оператор перехода.

1.3. Эволюция клеточного автомата.

1.4. Семейства подмножеств S для KÄß и КА

1.5. АКА модель реакции СО + О = СО2 на поверхности палладия

1.6. Сравнение поведений КАа, КА^ и КА7.

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

Клеточный автомат (КА) был предложен фон-Нейманом в середине прошлого века [1]. На основе этой модели подтверждалась мысль о том, что человек может создать устройство, обладающее присущими ему самому свойствами, в частности, возможностью воспроизводить себе подобного. Основные свойства клеточного автомата формулируются в следующем виде [2]: дискретность пространства, времени и состояний; однородность (все клетки организованы в регулярную пространственную структуру); синхронный режим изменения состояний; пространственная локальность; временная локальность.

Первое время клеточный автомат оставался объектом для игры ума. Сначала эта игра происходила на бумаге, затем она была перенесена на компьютер. Самым известным клеточным автоматом была и остается "Игра Жизнь" [3]. Интерес к этому клеточному автомату, как и вообще ко всем клеточным автоматам, постепенно перерос из игрового в научный. Когда начала бурно развиваться микроэлектроника (70-е годы) и появилась потребность в быстродействующих электронных схемах на многих элементарных автоматах, действующих параллельно, то клеточный автомат приобрёл важный практический смысл. Заложенные в его идее принципы параллельности и близкодей-ствия межклеточных взаимодействий как нельзя лучше соответствуют требованиям технологии больших интегральных схем.

Следующий всплеск интереса к клеточным автоматам был связан уже не с построением параллельных устройств, а с построением новых моделей вычислений [4, 5]. Это произошло в середине 80-х годов, когда были предложены клеточные автоматы, эволюция которых моделирует процесс диффузии [6-8], разделения фаз [2, 7], реакционно-диффузионные процессы [9-11], знаменитую реакцию Белоусова-Жаботинского [12], образование диссипативных структур [13].

На волне интереса к клеточно-автоматному моделированию стали развиваться асинхронные клеточные автоматы. Отчасти это связано с тем, что большое количество уже существующих кинетических методов Монте-Карло [14-16], в которых обычно используются регулярные решетки и локальные правила изменения характеристик частиц материала, представляются в форме клеточного автомата.

При этом, асинхронное клеточно-автоматное (АКА) моделирование реальных процессов требует больших вычислительных мощностей, поскольку для выявления каких-либо свойств моделируемых процессов необходимо оперировать большими количествами частиц (1010-Ю12) в течение длительного времени (103-105 итераций). Естественно возникает потребность использовать параллельные вычислители для ускорения вычислений, к этому также располагают основные свойства клеточного автомата - естественная мелкозернистая параллельность и локальность взаимодействий при функционировании. Однако, асинхронные клеточные автоматы не поддаются столь же легкому распараллеливанию, как и обычные, синхронные, клеточные автоматы.

Это связано с тем, что при распараллеливании необходимо соблюдать следующие свойства: корректность и эффективность распараллеливания, а также равноправие в выборе клеток. Первые два свойства типичны для большинства параллельных программ. Последнее свойство возникает из определения асинхронного режима работы клеточного автомата и заключается в следующем: вероятность выбора некоторой клетки на некотором шаге должна быть равна вероятности выбора любой другой клетки на любом другом шаге. Подробнее проблемы параллельного исполнения асинхронных клеточно-авто-матных моделей рассматриваются в Главе 2.

Существующие параллельные алгоритмы можно разделить на два класса: не нарушающие свойства равноправия в выборе клеток [16, 17] (сохраняющие асинхронизм), и нарушающие его [18, 19] (нарушающие асинхронизм). Алгоритм [17] разрабатывался и тестировался на компьютере с общей памятью в 1987 году, его эффективность на современных мультипроцессорах мала (Глава 2). В основе алгоритма [16] лежит алгоритм параллельного моделирования дискретно-событийных систем. Из результатов работы [16] следует, что эффективность параллельного исполнения авторской реализации этого алгоритма слишком мала для асинхронных клеточно-автоматных моделей физико-химических процессов. В работах [18-20] на трёх моделях показано, что применение алгоритмов, нарушающих асинхронизм, не вносит существенных изменений в моделируемый процесс. Вопрос о том, для каких моделей использование алгоритмов, нарушающих асинхронизм, допустимо, то есть не вносит изменения в моделируемый процесс, остаётся открытым.

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

Целью настоящей работы является создание методов и алгоритмов параллельного моделирования микроуровневых физико-химических процессов, описываемых асинхронными вероятностными клеточными автоматами, для современных вычислителей с различной архитектурой (мультипроцессор, мультикомпьютер и графический ускоритель).

Для достижения поставленной цели следует решить следующие задачи:

1. Разработать формализм для описания КА моделей микроуровневых физико-химических процессов.

2. Проанализировать существующие методы и алгоритмы параллельного исполнения КА моделей физико-химических процессов.

3. Разработать и реализовать новые алгоритмы исполнения К А моделей физико-химических процессов для мультипроцессоров, мультикомпью-теров и графических ускорителей.

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

5. Провести вычислительные эксперименты по определению статистического смещения моделируемого процесса для существующих и разработанных алгоритмов, нарушающих асинхронизм.

6. Разработать язык для описания К А моделей физико-химических процессов и транслятор, переводящий это описание в программы для вышеперечисленных вычислителей.

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

1. Предложен формализм для описания К А моделей физико-химических процессов, основанный на алгоритме параллельных подстановок.

2. Предложен новый метод параллельного исполнения АКА моделей, основанный на расширенных блочно-синхронных режимах работы КА и обеспечивающий меньшее статистическое смещение при моделировании.

3. Обоснована необходимость использования сохраняющих асинхронизм параллельных алгоритмов исполнения КА моделей физико-химических процессов в общем случае.

4. Разработаны и реализованы эффективные алгоритмы исполнения К А моделей физико-химических процессов на следующих вычислителях с параллельной архитектурой: мультипроцессоры, мультикомпьютеры и графические ускорители.

5. Разработан язык описания и транслятор, позволяющие автоматизировать разработку КА моделей физико-химических процессов.

Основные положения, выносимые на защиту:

1. Формализм для описания К А моделей микроуровневых физико-химических процессов.

2. Новый метод параллельного исполнения АКА моделей, основанный на расширенных блочно-синхронных режимах работы КА и обеспечивающий меньшее статистическое смещение при моделировании.

3. Параллельные алгоритмы исполнения КА моделей физико-химических процессов для вычислителей с различной параллельной архитектурой (мультипроцессоры, мультикомпьютеры и графические ускорители.).

4. Язык описания КА моделей микроуровневых физико-химических процессов и транслятор, переводящий описание К А модели на этом языке в программу на языке С++/Ргосеэ8^.

Научная и практическая ценность. Предложенные методы и алгоритмы позволяют за приемлемое время моделировать микроуровневые физико-химические процессы, протекающие на поверхностях катализаторов [14, 21], в масштабе необходимом исследователям для сравнения с реальными экспериментами. Созданные язык и транслятор позволяют автоматизировать процесс разработки подобных моделей.

Достоверность полученных результатов. Все основные положения и выводы, сформулированные в диссертации, подтверждаются строгими математическими выводами и доказательствами, а также тестированием отдельных процедур программного комплекса на тестовых моделях, разработанных ранее другими авторами [14, 21].

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

Апробация. Результаты диссертационной работы были представлены на 7-и Российских и международных конференциях:

1. V Всеросийская конференция молодых ученых, Санкт-Петербург, 2008;

2. Международная научная студенческая конференция "Студент и научно-технический прогресс", Новосибирск, 2008;

3. Parallel computing technologies, РаСТ-2009, Novosibirsk;

4. Cellular Automata for Research and Industry, ACRI-2010, Italy, Ascoli Picheno, 2010;

5. XIX International Conference on Chemical Reactors "CHEMREACTOR-19", Austria, Vienna, 2010;

6. VIII International Conference Mechanisms of Catalytic Reactions, Novosibirsk, 2011;

7. Parallel computing technologies, PaCT-2011, Kazan, 2011;

8. Конференция молодых ученых по вычислительной математике и информатике, ИВМиМГ СО РАН, 2011.

Результаты докладывались на семинарах:

1. "Математическое и архитектурное обеспечение параллельных вычислений" под руководством д.т.н. В.Э. Малышкина;

2. "Архитектура, системное и прикладное программное обеспечение кластерных суперЭВМ" под руководством д.т.н. Б.М. Глинского;

3. "Методы Монте-Карло" под руководством чл.-корр. Г.А. Михайлова;

4. "Семинар ИДСТУ СО РАН по вычислительным технологиям" под руководством д.т.н. Г.А. Опарина (г. Иркутск).

Публикации. Основные результаты опубликованы в изданиях рекомендованных ВАК (3 публикации), в трудах конференций (6 публикаций), и местных изданиях (2 публикации).

Автор выражает искреннюю благодарность научному руководителю О.Л. Бандман за ценные обсуждения, постоянную поддержку и внимание к данной работе.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Калгин, Константин Викторович

Заключение

В данной работе были получены следующие результаты.

1. Предложен формализм, основанный на теории параллельных подстановок, для описания КА моделей физико-химических процессов.

2. Проанализированы существующие методы и алгоритмы параллельного исполнения КА моделей физико-химических процессов. Обоснована необходимость создания новых методов и алгоритмов.

3. Предложен новый метод параллельного исполнения АКА моделей, основанный на расширенных блочно-синхронных режимах работы КА, обеспечивающих меньшее статистическое смещение при моделировании.

4. Обоснована необходимость использования сохраняющих асинхронизм параллельных алгоритмов исполнения КА моделей физико-химических процессов в общем случае.

5. Разработаны и реализованы эффективные алгоритмы исполнения К А моделей физико-химических процессов на следующих вычислителях с параллельной архитектурой: мультипроцессоры, мультикомпьютеры и графические ускорители.

6. Разработаны язык описания К А моделей физико-химических процессов и транслятор, переводящий это описание в программы для различных вычислителей с параллельной архитектурой.

Список литературы диссертационного исследования кандидат физико-математических наук Калгин, Константин Викторович, 2012 год

1. von Neumann J. Theory of self reproducing automata. USA: University of 1.linois Press, 1966. P. 388.

2. Wolfram S. A new kind of science. USA: Wolfram Media, 2002. P. 900. ISBN: 1579550088. URL: http://www.wolframscience.com.

3. Gardner M. Wheels, Life, and Other Mathematical Amusements. USA: W.H. Freeman, 1983. P. 261.

4. Vichniac G. Simulating physics with cellular automata // Physica D: Nonlinear Phenomena. 1984. Vol. 10. P. 96-116.

5. Wolfram S. Statistical Mechanics of Cellular Automata // Reviews of Modern Physics. 1983. Vol. 55. P. 601-644.

6. Toffoli T. Computation and construction universality of reversible cellular automata // Journal of Computer and System Sciences. 1977. Vol. 15. P. 213-231.

7. Margolus N., Toffoli T. Cellular Automata Machines: A New Environment for Modeling. USA: MIT Press, 1987. P. 259.

8. Bandman O. Comparative Study of Cellular Automata Diffusion Models // Proceedings of Parallel Computing Technologies, 5th International Conference, PaCT-99 / Ed. by V. Malyshkin. Vol. 1662 of LNCS. Springer, 1999. P. 395-409.

9. Weimar J. Cellular Automata for Reaction-Diffusion Systems // Parallel Computing. 1997. Vol. 23. P. 1699-1715.

10. Бандман О. Клеточно-автоматное моделирование диффузионно-реакционных процессов // Автометрия. 2003. Т. 3. С. 1-16.

11. Madore В., Ffreedman W. Computer simulation of Belousov-Zhabotinski reaction // Scinece. 1983. Vol. 222. P. 615-616.

12. Пригожин И. От существующего к возникающему. Время и сложность в физических науках. М.: Наука, Физматгиз, 1985. С. 328.

13. Elokhin V. е. a. Application of Statistical Lattice Models to the Analysis of Oscillatory and Autowave Processes in the Reaction of Carbon Monoxide Oxidation over Platinum and Palladium Surfaces // Kinetics and Catalysis. 2003. Vol. 44. P. 692-700.

14. Neizvestny I. 3D-model of epitaxial growth on porous 111 and 100 Si surfaces // Computer Physics Communications. 2002. Vol. 147. P. 272-275.

15. Lubachevsky B. Efficient parallel simulation of asynchronous cellular arrays // Complex Systems. 1987. Vol. 1. P. 1099-1123.

16. Nedea S., Lukkien J., Hilbers P., Jansen A. Methods for Parallel Simulations of Surface Reactions // Proceedings of the 17th International Symposium on Parallel and Distributed Processing / Ed. by B. Werner. IEEE Computer Society, 2003. P. 256.

17. Ziff R., Gulari E., Barshad Y. Kinetic phase transitions in an irreversible surface-reaction model // Phys Rev Lett. 1986. Vol. 56. P. 2553-2556.

18. Achasova S., Bandman O., Markova V., Piskunov S. Parallel Substitution Algorithm: Theory and Application. Singapore: World Scientic, 1994. P. 220.

19. Metropolis N., Rosenbluth A., Rosenbluth M. et al. Equation of State Calculations by Fast Computing Machines // Chem. Phys. 1953. Vol. 31. P. 1087-1092.

20. Chopard B., Droz M. Cellular Automata Modeling Of Physical Systems. USA: Cambridge University Press, 1998. P. 341.

21. Ачасова С., Бандман. О. Корректность параллельных вычислительных процессов. Новосибирск: Наука. Сиб. Отд., 1990. С. 253.

22. Калгин К. Параллельная реализация асинхронных клеточно-автоматных алгоритмов // Научно-технический вестник СПбГУ информационных технологий, механики и оптики. 2008. Т. 54. С. 108-113.

23. Михайлов Г., Войтишек А. Численное статистическое моделирование. Методы Монте-Карло. М.: Академия, 2006. С. 368.

24. Pseudo random number generators: uniform and non-uniform distributions. URL: http://www.agner.org/random/ (дата обращения: 01.04.2012).

25. Intel Many Core Testing Lab. URL: http://software.intel.com/en-us/ articles/intel-many-core-testing-lab (дата обращения: 01.04.2012).

26. Message Passing Interface. URL: http://ru.wikipedia.org/wiki/ MessagePassingInterf асе (дата обращения: 01.04.2012).

27. NVIDIA CUDA Programming Guide. URL: http://www.nvidia.com/cudaдата обращения: 01.04.2012).

28. Processing. URL: http://processing.org (дата обращения: 01.04.2012).

29. Eli project. URL: http://eli-project.sourceforge.net (дата обращения: 01.04.2012).