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

Авторы

  • Е.Н. Головченко

Ключевые слова:

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

Аннотация

Численное решение задач математической физики на распределенных вычислительных системах зачастую предполагает использование геометрического параллелизма. В результате возникает задача сбалансированного распределения сетки между процессорами, сводящаяся к задаче разбиения графа на домены. Целью исследования настоящей статьи является параллельная декомпозиция треугольных и тетраэдральных сеток большого размера. На основе последовательного инкрементного алгоритма декомпозиции графов, обеспечивающего формирование компактных доменов, и алгоритма рекурсивной координатной бисекции создан комплекс программ параллельной декомпозиции сеток. Работа выполнена при финансовой поддержке РФФИ (коды проектов № 05-01-00750а, № 08-07-00458а, № 09-01-12022-офи_м). Статья рекомендована к печати программным комитетом международной научной конференции «Научный сервис в сети Интернет: суперкомпьютерные центры и задачи» (http://agora.guru.ru/abrau2010)

Новые вычислительные технологии

Загрузки

Опубликован

2010-11-09

Выпуск

Том 11 (2010): Выпуск 4.

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

Е.Н. Головченко

Институт прикладной математики имени М.В. Келдыша РАН (ИПМ РАН)
Миусская пл., 4, 125047, Москва
• младший научный сотрудник

Библиографические ссылки

  1. Hendrickson B., Kolda T.G. Graph partitioning models for parallel computing // Parallel Computing. 2000. 26. 1519-1534.
  2. Karypis G., Kumar V. A Parallel algorithm for multilevel graph partitioning and sparse matrix ordering // J. of Parallel and Distributed Computing. 1998. 48. 71-95.
  3. Walshaw C., Cross M. Parallel optimization algorithms for multilevel mesh partitioning // Parallel Computing. 2000. 26. 1635-1660.
  4. Якобовский М.В. Инкрементный алгоритм декомпозиции графов // Вестник Нижегородского университета им. Н.И. Лобачевского. Серия «Математическое моделирование и оптимальное управление». Вып. 1(28). Нижний Новгород: Издательство ННГУ, 2005. 243-250.
  5. Hendrickson B., Leland R. A multilevel algorithm for partitioning graphs // Technical Report SAND93-1301. Sandia National Laboratories. Albuquerque, 1993.
  6. Кнут Д.Э. Искусство программирования. Сортировка и поиск. 3. М.: Издательский дом «Вильямс», 2001.
  7. Якобовский М.В. Параллельные алгоритмы сортировки больших объемов данных // Фундаментальные физико-математические проблемы и моделирование технико-технологических систем. Вып. 7. М.: Янус-К, 2004. 235-249.