ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ
И РЕАЛИСТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
Исследования в области параллельных вычислений ведутся в
институте более 40 лет. Теоретические разработки осуществляются в
Отделе математического обеспечения высокопроизводительных
вычислительных систем. Они сконцентрированы в таких основных
областях: формальные модели параллельных вычислений, параллельные
архитектуры, параллельные языки и системы программирования,
синтез параллельных программ, организация параллельных вычислений
на MIMD-архитектурах, параллельное решение задач большого
размера, клеточные и клеточно-нейронные вычисления, параллельные
вычислительные технологии, Grid-вычисления и системы
метакомпьютинга. Такое разнообразие тематик поддерживается и
поощряется с тем, чтобы обеспечить критическую массу результатов,
необходимых для создания современных технологий вычислений.
Именно технологии объединяют в единое целое разнообразные
теоретические и экспериментальные исследования.
Изучение параллельных вычислений началось в институте под
руководством А. Ершова в начале 60-х годов. В работах В. Котова и
А. Нариньяни были заложены основы теории асинхронных вычислений,
разработаны первые асинхронные языки и системы программирования.
Многие результаты тех лет воплощены сейчас в разных
технологических системах. В частности, широко известное основное
средство программирования коммуникаций в параллельных программах
для мультикомпьютеров MPI (message passing interface) было
разработано в начале 80-х в управляющей структуре «асинхронный
канал». Накопленная масса результатов в теории, алгоритмах и
программировании позволила в конце 80-х создать в Новосибирске, в
ВЦ СО АН, 8-процессорную вычислительную систему СИБИРЬ с пиковой
производительностью 100 мегафлопс, что было очень неплохо для тех
лет и той элементной базы. Для СИБИРИ был создан весь необходимый
комплекс системного параллельного программирования, включая
создание распределенной ОС и систем параллельного
программирования. Появление высокопроизводительных вычислительных
комплексов сделало актуальным решение задачи разработки
реалистических математических моделей большого размера.
Под реалистическими моделями понимаются комплексные модели, в
которых в одном объеме пространства моделируются несколько
взаимодействующих физических процессов, а число модельных
объектов сопоставимо с числом реальных. Например, в модели
эволюции протопланетного диска одновременно моделируются
гравитационные, газодинамические, каталитические процессы,
химические реакции, коагуляция. Если моделируются процессы в
некотором объеме газа, то число модельных частиц в том же объеме
должно быть сопоставимо с числом физических молекул в газе.
По силе воздействия на совершенствование методов научных
исследований реализацию больших моделей можно сравнить с
изобретением телескопа и микроскопа. Следует ожидать, что уже в
ближайшее время станет практически невозможной разработка
принципиально новых промышленных технологий без крупномасштабного
моделирования. А научный метод в дополнение к теории и натурному
эксперименту обогатится новым фундаментальным компонентом -
вычислительным экспериментом.
Реализация моделей большого размера потребовала разработки новых
методов и средств параллельного программирования. Дело в том, что
параллельные программы должны обладать рядом новых, сложно
реализуемых динамических свойств, связанных с обеспечением их
должного поведения: динамической настройкой на доступные ресурсы,
динамической балансировкой загрузки, динамическим учетом
поведения модели, динамическим обеспечением точности вычислений и
т.п. В некотором смысле, поведение параллельной программы должно
следовать поведению моделируемого объекта или явления.
Существующие системы программирования не обеспечивают
автоматически наличия этих свойств программ. Таким образом,
важнейшим фактором использования суперкомпьютеров становится
создание нового поколения методов, языков и средств параллельного
программирования.
В параллельных вычислениях выделяются два типа параллелизма:
крупно- и мелкозернистый. Крупнозернистый параллелизм исследуется
в рамках комплексного проекта создания сборочной технологии
параллельного программирования. Ее математической основой
является структурный метод синтеза параллельных программ,
разработанный нами в середине 80-х годов.
Основные проблемы разработки параллельных программ для
мультикомпьютера связаны с обеспечением недетерминизма ее
поведения. Решение может быть найдено на пути создания
мелкофрагментированных программ, чья фрагментированность
сохраняется в ходе вычислений. Численные алгоритмы на
прямоугольных сетках — пример класса алгоритмов, допускающих
такое представление и нередко (но далеко не всегда) хорошо
реализуемых на мультикомпьютерах общепринятыми способами.
Фрагментами служат вычисления внутри одной ячейки сетки.
В параллельных программах, разработанных в сборочной технологии,
поведение системы параллельно исполняющихся и взаимодействующих
процессов организуется так, что они ведут себя в мультикомпьютере
подобно жидкости в системе сообщающихся сосудов — если некоторый
процессор окажется перегруженным, то лишняя работа «переливается»
в соседние процессоры. Так достигается высокое качество
распределения ресурсов и гибкая настройка параллельной программы
на все доступные ресурсы, а, значит, и ее переносимость в классе
мультикомпьютеров. Программа может вообще ничего не знать о
структуре коммуникационной сети мультикомпьютера и будет очень
устойчива к разным сбоям оборудования.
В сборочном стиле уже реализован ряд проектов. Крупный проект,
стартовавший в 2003 году, направлен на разработку системного
программного обеспечения Grid-вычислений, которое послужит
вовлечению в решение сверхбольших задач множества удаленных
мультикомпьютеров. Одна такая задача — эволюция протопланетного
диска и формирование планетной системы — уже поставлена. В
следующем году должны проводиться эксперименты с моделью, в
которой будет порядка 200 миллиардов модельных частиц. Для
решения этой задачи было бы не лишним использование всех
имеющихся в мире мультикомпьютеров.
Идеи мелкозернистого параллелизма восходят к работам фон Неймана,
который в середине прошлого века предложил модель клеточного
автомата. Это модель некоторого биологического сообщества,
состоящего из множества «клеток», расположенных в метрическом
пространстве и взаимодействующих только с такими же клетками из
своего окружения. Все клетки выполняют свои функции параллельно,
моделируя таким образом пространственную динамику некоторого
природного явления. Уже на этом уровне появилось понимание того,
что даже при очень простых клетках их кооперативная работа может
моделировать сложные процессы. Это направление интенсивно
развивалось в Институте математики СО РАН в 1960-1970 г., и
оттуда вместе с несколькими сотрудниками пришло в наш отдел. На
основе накопленного опыта была разработана формальная теория
клеточных вычислений — Алгоритм Параллельных Подстановок (АПП),
который интенсивно используется для описания, преобразования и
проектирования клеточных алгоритмов самых разных назначений.
Другое направление в развитии идей мелкозернистого параллелизма
связано с поиском новых математических моделей нелинейной
пространственной динамики (газовая динамика, фазовые переходы,
нелинейные волны, химические реакции), поведение которых плохо
описывается системами дифференциальных уравнений.
В. Малышкин, д.т.н.
стр. 10
|
