Язык и система фрагментированного параллельного программирования задач численного моделирования
Диссертация
Таким образом, специалистам-прикладникам приходится уделять слишком большое внимание проблемам параллельного программирования: В связи с этим, одним из перспективных направлений является создание систем параллельного программирования высокого уровня^ которые в значительной степени скрывают от пользователя технические трудности разработки параллельных программ и позволяют сосредоточиться… Читать ещё >
Содержание
- Глава 1. Средства разработки параллельных программ
- 1. 1. Классификация средств разработки параллельных программ
- 1. 2. Средства разработки асинхронных программ
- 1. 1.2.1. Проект МАРС
- 1. 2. 2. OpenTS
- 1. 2. 3. Charm-н
- 1. 2. 4. Граф Плюс
- 1. 2. 5. PLASMA
- 1. 3. Требования к системе программирования
- 1. 4. Выводы
- 2. 1. Концепция фрагментированного программирования
- 2. 1. 1. Предпосылки возникновения
- 2. 1. 2. Неформальное определение
- 2. 2. Асинхронная модель вычислений
- 2. 2. 1. Простая асинхронная модель
- 2. 2. 2. Асинхронная модель со структурными А-блоками
- 2. 2. 3. Асинхронная модель с массовыми А-блоками
- 2. 2. 4. Асинхронная модель с управлением на основе строгого частичного порядка
- 2. 3. Конструирование асинхронных программ
- 2. 3. 1. Формальное определение управляющего оператора
- 2. 3. 2. Алгоритмы генерации управляющих операторов
- 2. 4. Выводы .'
- 3. 1. Ключевые особенности
- 3. 2. Формальное определение
- 3. 2. 1. Структура программы
- 3. 2. 2. Заголовок программы
- 3. 2. 3. Объявления внешнего языка
- 3. 2. 4. Объявление фрагментов данных
- 3. 2. 5. Объявление фрагментов кода
- 3. 2. 6. Объявление данных задачи
- 3. 2. 7. Объявление фрагментов вычислений
- 3. 2. 8. Объявление управления
- 3. 3. Программирование на языке Аспект
- 3. 3. 1. Распространённые схемы управления
- 3. 3. 2. Разложение матриц
- 3. 3. 3. Вычисление п-то числа Фибоначчи
- 3. 3. 4. Анализ фрагментированного подхода
- 3. 4. Выводы
- 4. 1. Программная архитектура системы
- 4. 2. Реализация транслятора
- 4. 2. 1. Лексический анализатор
- 4. 2. 2. Синтаксический анализатор
- 4. 2. 3. Генератор внутреннего представления
- 4. 2. 4. Генератор кода
- 4. 2. 5. Ограничения реализации
- 4. 3. Реализация исполнительной подсистемы
- 4. 3. 1. Слой абстрагирования от операционной системы
- 4. 3. 2. Функциональные модули
- 4. 3. 3. Интерфейс системных вызовов
- 4. 3. 4. Ограничения реализации
- 4. 4. Порядок работы с системой
- 4. 4. 1. Трансляция Аспект-программы
- 4. 4. 2. Окончательная сборка программы
- 4. 4. 3. Отладка программы
- 4. 5. Выводы
- 5. 1. Тестовая среда и методика испытаний
- 5. 2. Тестирование на специальных тестах
- 5. 2. 1. Накладные расходы исполнительной подсистемы
- 5. 2. 2. Поддержка большого количества фрагментов
- 5. 2. 3. Накладные расходы управляющих операторов
- 5. 3. Тестирование на модельных задачах
- 5. 3. 1. Умножение матриц
- 5. 3. 2. Разложение матриц
- 5. 3. 3. Явная разностная схема
- 5. 3. 4. Использование специализированных библиотек
- 5. 4. Тестирование на прикладных задачах
- 5. 4. 1. Метод Монте-Карло
- 5. 4. 2. Метод частицы-в-ячейках
- 5. 5. Выводы
Список литературы
- Аветисян А. И., Бабкова В. В., Калугин М. Д. Разработка приложений в среде ParJava // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2008. № 54. С. 139−144.
- Алексеев Е. Р., Чеснокова О. В., Рудченко Е. A. Scilab: Решение инженерных и математических задач. М.: ALT Linux- БИНОМ. Лаборатория знаний, 2008. 269 с.
- Андрианов А. Н. Система Норма : Разработка, реализация и использоваIние для решения задач математической физики на параллельных ЭВМ: Докторская диссертация / ИПМ им. М. В. Келдыша. 2001.
- Андрианов А. Н. Применение языка Норма для решения задач на вложенных сетках // Вычислительные методы и программирование. 2002. Т. 3. С. 1−10.
- Андрианов А. Н., Ефимкин К. Н., Задыхайло И. Б. Непроцедурный язык для решения задач математической физики // Программирование. 1991. № 2. С. 80−94. !
- Анисимов В. А. Система параллельного программирования «Иня» // Математическое и архитектурное обеспечение параллельных вычислений. Новосибирск: ВЦ СО АН СССР, 1989. С. 67−73.
- Арыков С. Б. Некоторые подходы к разработке асинхронного языка программирования «Аспект» // Труды конференции молодых ученых. Новосибирск: ИВМиМГ СО РАН, 2005. С. 13−23.
- Арыков С. Б. Язык программирования Аспект // Известия Томского политехнического университета. 2008. Т. 313, № 5. С. 89−92.
- Арыков С. Б. Группировка данных в системе асинхронного параллельного программирования Аспект // Труды международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2009)». Челябинск: Изд. ЮУрГУ, 2009. С. 357−363.
- Арыков С. Б. Асинхронное программирование численных задач // Труды международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2010)». Челябинск: Изд. ЮУрГУ, 2010. С. 28−39.
- Арыков С. Б., Малышкин В. Э. Система асинхронного параллельногопрограммирования «Аспект» // Вычислительные методы и программирование. 2008. Т. 9, № 1. С. 205−209. '
- Арыков С. Б., Малышкин В. Э. Система асинхронного параллельного программирования «Аспект» // Труды Международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2008)». Челябинск: Изд. ЮУрГУ, 2008. С. 290−295. '
- Арыков С. Б., Малышкин В. Э. Алгоритмы конструирования асинхронных программ заданной степени непроцедурности методом группировки // Вестн. Новосиб. гос. ун-та. Серия: Информационные технологии.2009. Т. 7, № 1. С. 3−15.
- Ахо А., Сети Р., Ульман Д. Компиляторы: принципы, технологии и инструменты. М.: Вильяме, 2003. 768 с. ISBN: 5−8459−0189−8.
- Ачасова С. М., Бандман О. JI. Корректность параллельных вычислительных процессов. Новосибирск: Наука. Сиб. отд-ние, 1990. 253 е. ISBN: 5−02−29 334−2.f
- Басс Л., Клементе П., Кацман Р. Архитектура программного обеспечения на практике. 2-е изд. СПб.: Питер, 2005. 576 с. ISBN: 5−469−494−5.
- Бузин А. Ю. Введение в современный АПЛ. 2-е изд. М.: ВЦ РАН, 1998. 184 с. ISBN: 5−201−14 724.
- Бульонков M. A., Быстров A. В., Дудоров H. H., Котов В. E. Базовый язык параллельного программирования Барс // Программирование. 1986. № 6. С. 32−40.
- Быстров А. В., Дудоров H. Н., Котов В. Е. О базовом языке // В кн. Языки и системы программирования. Новосибирск: ВЦ СО АН СССР, 1979. С. 85−106.
- Вальковский В. А. Распараллеливание алгоритмов и программ. Структурный подход. М.: Радио и связь, 1989. 176 с. t
- Вальковский В. А., Малышкин В. Э. Синтез параллельных программ и систем на вычислительных моделях. Новосибирск: Наука, 1988. 129 с.
- Васенин В. А., Водомеров А. Н. Формальная модель системы автоматизированного распараллеливания программ // Программирование. 2007. № 4. С. 3−19.
- Вирт Н. Долой «жирные» программы // Открытые системы. 1996. № 6. С. 26−31.
- Воеводин В. В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. 296 с.
- Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608 с. ISBN: 5−94 157−160−7.
- Воробьёв H. Н. Числа Фибоначчи. Серия «Популярные лекции по математике». 4-е изд. М.: Наука, 1978. 144 с.
- Востокин С. В. Графическая объектная модель параллельных процессов и ее применение в задачах численного моделирования. Самара: Издательство Самарского научного центра РАН, 2007. 286 с. ISBN: 978−5-93 424−284−9.
- Вшивков В. А., Вшивков К. В., Дудникова Г. И. Алгоритмы решения задачи взаимодействия лазерного импульса с плазмой // Вычислительные технологии. 2001. Т. 6, № 2. С. 47−63.
- Вшивков В. А., Краева М. А., Малышкин В. Э. Параллельная реализация метода частиц//Программирование. 1997. № 2. С. 39−51.
- Гергель В. П. Теория и практика параллельных вычислений. Москва: Интернет-университет информационных технологий- Бином. Лаборатория знаний, 2007. 423 с. ISBN: 978−5-94 774−645−7.
- Григорьев Ю. Н., Вшивков В. А., Федорук М. П. Численное моделирование методами частиц-в-ячейках. Новосибирск: Издательство СО РАН, 2004. 360 с.
- Ершов А. П. Введение в теоретическое программирование (беседы о методе). Серия «Популярные лекции по математике». М.: Наука, 1977. 288 с.
- Касьянов В. Н., Бирюкова Ю. В., Евстигнеев В. А. Функциональный язык Sisal // В кн. Поддержка супервычислений и интернет-ориентированные технологии. Новосибирск: ИСИ СО РАН, 2001. С. 54−67.
- Касьянов В. Н., Поттосин И. В. Методы построения трансляторов. Новосибирск: Наука, 1986. 344 с. t
- Коварцев A. H. Автоматизация разработки и тестирования программных средств. Самара: Сам. гос. аэрокосм, ун-т., 1999. 150 с.
- Коновалов Н. А., Крюков В. А., Сазанов Ю. JI. C-DVM — язык разработки мобильных параллельных программ // Программирование. 1999. № 1. С. 20−28.
- Котов В. Е. О практической реализации асинхронных параллельных вычислений // В кн. Системное и теоретическое программирование. Новосибирск: ВЦ СО АН СССР, 1972. С. 110−125.
- Котов В. Е. Параллельное программирование с типами управления // Кибернетика. 1979. № 3. С. 1−13.
- Котов В. Е. Алгебра регулярных сетей Петри // Кибернетика. 1980. № 5. С. 10−18.
- Котов В. Е., Марчук А. Г. Некоторые итоги и перспективы развития проекта МАРС // В кн. Актуальные проблемы развития архитектуры и программного обеспечения ЭВМ и вычислительных систем. Новосибирск: ВЦ СО АН СССР, 1983. С. 13−23.
- Котов В. Е., Нариньяни А. С. Асинхронные вычислительные процессы над памятью // Кибернетика. 1966. № 3. С. 64−71.
- Краева М. А., Малышкин В. Э. Алгоритмы динамической балансировки загрузки при реализации метода частиц в ячейках на МИМД-мультиком-пьютерах // Программирование. 1999. № 1. С. 47−53.
- Кутепов В. П., Котляров Д. В., Осипов М. А. Граф-схемное потоковое параллельное программирование и его реализация на кластерных системах // Известия РАН, Теория и системы управления. 2005. № 1. С. 75−96.
- Легалов А. И. Функциональный язык для создания архитектурно-независимых параллельных программ // Вычислительные технологии. 2005. Т. 10, № 1. С. 71−89.
- Лельчук Т. И. Языковая реализация параллельной асинхронной моделивычислений // Кибернетика. 1984. № 5. С. 32−37.t
- Лельчук Т. И., Марчук А. Г. ПОЛЯР — язык параллельного асинхронного программирования // Программирование. 1983. № 4. С. 59−68.
- Лельчук Т. И., Марчук А. Г. Язык программирования Поляр: описание, использование, реализация, Под ред. В. Б. Котова. Новосибирск: ВЦ СО АН СССР, 1986. 94 с. 1
- Малышкин В. Э. ОПАЛ язык описания параллельных алгоритмов // В кн. Теоретические вопросы параллельного программирования и многопроцессорные ЭВМ. Новосибирск: ВЦ СО АН СССР, 1983. С. 91−109.
- Малышкин В. Э., Корнеев В. Д. Параллельное программирование' мультикомпьютеров. Новосибирск: Изд-во НГТУ, 2006. 296 с. ISBN: 5−7782−0702−6.
- Малышкин В. Э., Цыгулин A. A. ParaGen — генератор параллельных программ, реализующих численные модели // Автометрия. 2003. Т. 39, № 3. С. 124−135.
- Мальцев А. И. Алгоритмы и рекурсивные функции. 2-е изд. М.: Наука, 1986. 368 с.
- Марченко М. А. Комплекс программ MONC для распределенных вычисIлений методом Монте-Карло // Сиб. журн. вычисл. математики. 2004. Т. 7, № 1. С. 43−55.
- Марченко М. А., Михайлов Гг А. Весовые алгоритмы статистического моделирования диффузионных процессов // Журн. вычисл. матем. и мат. физики. 2003. Т. 43, № 4. С. 571−584.
- Мейерс С. Эффективное использование STL. Библиотека программиста. СПб.: Питер, 2002. 224 с. ISBN: 5−94 723−382−7.
- Мейерс С. Эффективное использование С++. 50 рекомендаций по улучшению ваших программ и проектов. М.: ДМК Пресс, 2006. 240 с. ISBN: 5−469−1 213−1.I
- Минц Г. Е., Тыугу Э. X. Обоснование структурного синтеза программ // Автоматический синтез программ. Таллин: Ин-т кибернетики АН ЭстССР, 1983. С. 5−40.
- Михайлов Г. А., Войтишек А. В. Численное статистическое моделирование. Методы Монте-Карло. М.: Издательский центр «Академия», 2006. 368 с. ,
- Непейвода Н. Н., Скопин И. Н. Основания программирования. Москва-Ижевск: Институт компьютерных исследований, 2003. 913 с. 1.BN: 5−93 972−299−7.i
- Пешио К. Никлаус Вирт о культуре разработки ПО // Открытые системы. 1998. № 1. С. 41−44.I
- Серебряков В. А. Лекции по конструированию компиляторов. М.: ВЦ РАН, 1994. 175 с.
- Скопин И. Н. Множественное структурирование данных // Программирование. 2006. Ш 1. С. 57−72.
- Страуструп Б. Дизайн и эволюция С++. СПб.: Питер, 2006. 448 с. ISBN: 5−469−1 217−4.
- Торгашёв В. А., Царёв И. В. Средства организации параллельных вычислений и программирования в мультипроцессорах с динамической архитектурой И Программирование. 2001. № 4. С. 53−67.
- Фаддеев Д. К., Фаддеева В. Н. Вычислительные методы линейной алгебры. 2-е изд. М.: Наука- 1963. 656 с.
- Фаулер М., Скотт К. UML. Основы. СПб.: Символ-Плюс, 2002. 192 с. ISBN: 5−93 286−032−4.
- Хантер Р. Основные концепции компиляторов. М.: Вильяме, 2002. 256 с. ISBN: 5−8459−0360−2.
- Хоар Ч. Взаимодействующие последовательные процессы. М.: Мир, 1989. 264 с. ISBN: 5−03−1 043−2.
- Accelerated Library Framework Programmer’s Guide and API Reference. URL: http://public.dhe.ibm.com/software/dw/cell/ALFProg GuideAPIv3.1 .pdf (дата обращение: 21.09.2010).
- Agha G. Actors: A Model of Concurrent Computation In Distributed Systems:
- Tech. Rep. Technical Report 844, MIT Artificial Intelligence Laboratory: 1985. i
- Anderson E., Bai Z., Bischof C. et al. LAPACK User’s Guide. 3d edition. Philadelphia: SIAM, 1999. 425 pp. ISBN: 0−89 871−447−8.
- Backus J. W., Bauer F. L., Green J. et al. Revised report on the algorithm language ALGOL 60 // Communications of the ACM. 1963. Vol. 6, no. 1. Pp. 1−17.
- Beguelin A., Dongarra J. J. Graphical development tools for network-basedconcurrent supercomputing // Proceedings of the 1991 ACM/IEEE conferience on Supercomputing (Supercomputing'1991). New York: ACM, 1991. Pp. 435−444.
- Blume W., Doallo R., Eigenmann R. et al. Parallel Programming with Polaris // Computer. 1996. Vol. 29, no. 12. Pp. 78−82.
- Buttari A., Langou Ji, Kurzak J., Dongarra J. A class of parallel tiled linear algebra algorithms for multicore architectures // Parallel Computing. 2009. Vol. 35,' no. 1. Pp. 38−53.
- Chamberlain B. L., Callahan D., Zima H. P. Parallel Programmability andIthe Chapel Language // International Journal of High Performance Computing Applications. 2007. Vol. 21, no. 3. Pp. 291−312.
- CHARM++ Programming Language Manual. URL: http://charm.cs. uiuc.edu/manuals/html/charm++/ (дата обращения: 15.07.2010).
- Choi J., Demmel J., Dhillon I. et al. ScaLAPACK: A portable linear algebra library for distributed memory computers — design issues and performance // Computer Physics Communications. 1996. Vol. 97, no. 1−2. P. 1−15.
- Cierniak M., Li W. Unifying Data and Control Transformations for Distributed Shared-Memory Machines // Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation (PLDI'1995). New York: ACM, 1995. Pp. 205−217.
- Clint W. C., Petitet A., Dongarra J. Automated Empirical Optimization of Software and the «ATLAS'Troject // Parallel Computing. 2001. Vol. 27, no. 1−2. Pp. 3−35.
- Cooperman G. TOP-C: Task-oriented parallel С for distributed and sharedimemory // Workshop on wide area networks and high performance computing. Berlin: Springer-Verlag, 1999. Pp. 109−117.i
- Feautrier P. Parametric Integer Programming // RAIRO Recherche Op’erationnelle. 1988. Vol. 22. Pp. 243−268.
- The Fortress Language Specification, Version 1.0. URL: http://labs. oracle.com/projects/plrg/Publications/fortress.1.0.pdf (дата обращения: 27.08.2010).
- Forum H. P. F. High Performance Fortran Language Specification, version 1.0: Tech. Rep. CRPC-TR92225, Rice University: 1993.
- Genetic ALgorithm Optimized for Portability and Parallelism System. URL: http://garage.cse.msu.edu/software/galopps/ (дата обращения: 17.08.2010).
- GNU General Public License. URL: http: //www.gnu. org/licenses/gpl. html (дата обращения: 18.08.2010).i
- Gustavson F. G. New Generalized Matrix Data Structures Lead to a Variety of High-Performance Algorithms // Proceedings of the IFIP TC2/WG2.5 Working Conference on the Architecture of Scientific Software. Deventer: Kluwer, B.V., 2001. Pp. 211−234. i
- Hall M. W., Anderson J. M., Amarasinghe S. P. et al. Maximizing Multiprocessor Performance with the SUIF Compiler // Computer. 1996. Vol. 29, no. 12. Pp. 84−89.
- Hoare C. A. Monitors: an operating system structuring concept // Communications of the ACM. 1974. Vol. 17, no. 10. Pp. 549−557.
- IEEE Std 1003.1, 2004 Edition. URL: http://www.opengroup. org/onlinepubs/9 695 399/basedefs/pthread.h.html (дата обращения: 30.08.2010).
- Intel® Cilk Plus. URL: http://www.cilk.com/ (дата обращения: 12.09.2010).
- Intel® Hyper-Threading Technology (Intel® HT Technology). URL: http: Iwww. intel. com/inf о/hyperthreading/ (дата обращения: 30.08.2010).
- Intel® Math Kernel Library Reference Manual. URL: http: //software.intel.com/sites/products/documentation/hpc/compilerpro/en-us/cpp/win/mkl/ref тал/index, htm (дата обращения: 17.08.2010).
- Kale L. V., Krishnan S. CHARM++: A Portable Concurrent Object Oriented System Based On С++ // SIGPLAN Notes. 1993. Vol. 28, no. 10. Pp. 91−108.
- Kasyanov V. N., Evstigneev V. A. The PROGRESS program manipulation system // Proceedings of the 2nd International Conference on Parallel Computing Technologies (PaCT'1993). Vol. 3. 1993. Pp. 651−656.
- Kraeva M. A., Malyshkin V. E. Assembly technology for parallel realization of numerical models on MIMD-multicomputers // Future generation computer systems. 2001. Vol. 17, no. 6. Pp. 755−765.
- Lamport L. The parallel execution of DO loops // Communications of the ACM. 1973. Vol. 17, no. 2. Pp. 83−93.i
- Lastovetsky A. Adaptive parallel computing on heterogeneous networks withmpC // Parallel Computing. 2002. Vol. 28, no. 10. Pp. 1369−1407.i
- Lindsley R. Kernel korner: What’s new in the 2.6 Scheduler // Linux Journal. 2004. no. 119. P. 13.
- Mascagni M., Srinivasan A. Algorithm 806: SPRNG: A Scalable Library for Pseudorandom Number Generation // ACM Transactions on Mathematical Software. 2000. Vol. 26, no. 3. Pp. 436−461.
- McCool M., Bruce A. Programming using RapidMind on the Cell BE // Proceedings of the 2006 ACM/IEEE conference on Supercomputing (SC'2006).
- New York: ACM, 2006. P. 222. I
- Moskovsky A., Roganov V., Abramov S. Parallelism granules aggregation with the T-system // Proceedings of the 9th International Conference on Parallel Computing Technologies (PaCT'2007). LNCS 4671. Berlin: Springer-Verlag, 2007. Pp. 293−302.
- Moskovsky A., Roganov V., Abramov S., Kuznetsov A. Variable Reassignment in the T++ Parallel Programming Language // Proceedings of the 9th International Conference on Parallel Computing Technologies (PaCT'2007).
- CS 4671. Berlin: Springer-Verlag, 2007. P. 579−588.i
- MPI: A Message-Passing Interface Standard. URL: http://www.mcs. anl.gov/research/projects/mpi/mpi-standard/mpi--report-l. 1/1 Impi-report .htm (дата обращения: 18.08.2010).
- Newton P., Browne J. C. The CODE 2.0 Graphical Parallel Programming Language // Proc. of the Sixth ACM International Conference on Supercomputing. New York: ACM, 1992. Pp. 167−177.
- OpenMP specifications. URL: http://openmp.org/wp/ openmp-specifications/ (дата обращения: 18.08.2010).
- Park N., Hong В., Prasanna V. K. Analysis of Memory Hierarchy Performance of Block Data Layout // Proceedings of the 2002 International Conference on Parallel Processing (ICPP'2002). Washington: IEEE Computer Society, 2002. P. 35.
- PLASjMA. URL: http://icl.cs.ntk.edu/plasma/ (дата обращения: 31.08.2010).
- POSIX Threads for Win32. URL: http://sourceware.org/ pthreads-win32/ (дата обращения: 30.08.2010).
- Reinders J. Intel Threading Building Blocks. Sebastopol: O’Reilly Media, 2007. 336 pp. ISBN: 0−596−51 480−8.
- Roy P., Haridi S. Concepts, Techniques, and Models of Computer Programming. Cambridge: MIT Press, 2004. 900 pp. ISBN: 0−262−22 069−5.
- Schloegel K., Karypis G., Kumar V. Parallel static and dynamic multi-constraint graph partitioning // Concurrency and Computation: Practice and Experience. 2002. Vol. 14,' no. 3. Pp. 219−240.
- SMP superscalar. URL: http://www.bsc.es/plantillaG.php?catid= 385 (дата обращения: 27.08.2010).
- Task Parallel Library. URL: http://msdn.microsoft.com/en-us/ library/dd460717. aspx (дата обращения: 27.08.2010).
- Voevodin V. V., Voevodin V. V. V-Ray Technology: a New Approach to the Old Problems. Optimization of the TRFD Perfect Club Benchmark to CRAY Y-MP and CRAY T3D Supercomputers // Proc. of the High Performance Computing Symposium'95. 1995. Pp. 380−385.
- Yip E. L. FORTRAN Subroutines for Out-of-Core Solutions of Large Complex Linear Systems: Tech. Rep. CR-159 142, NASA: November 1979.