ПРОГРАММИРОВАНИЕ, 2012, No 4, с. 40-54
ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ
УДК 681.3.06
РЕШЕНИЕ ПРОБЛЕМЫ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ НА ОСНОВЕ ПОНЯТИЙ "ПРОСТРАНСТВО-ВРЕМЯ"
© 2012 г. А.И. Илюшин, М.А. Оленин, С.А. Васильев Кафедра вычислительной механики, механико-математический факультет МГУ
119991 Москва, Ленинские Горы мкр., 1 Институт прикладной математики РАН 125047 Москва, Миусская пл., 4
E-mail: ilu@a5.kiam.ru Поступила в редакцию 16.01.2012 г.
Рассматривается построение распределенных систем путем композиции программных объектов. Предлагается задавать топологию связей между объектами, описывая "окрестность" каждого объекта в виде списка "формальных соседей". Синхронизацию эволюции объекта и его "соседей" предлагается описывать с помощью "локального времени" объекта и его окрестности. Приводятся результаты программирования и счета реальных задач на суперкомпьютере, показывающие возможность сведения трудоемкости создания распределенных программных систем к трудоемкости локального программирования.
1. ВВЕДЕНИЕ
Общепризнанно, что в настоящее время программирование многопроцессорных (многоядерных) вычислительных систем является задачей, которая требует от программиста и высокой квалификации, и больших трудозатрат. В частности, можно привести цитату из интервью ветерана в области вычислительной техники Джона Хэн-неси, президента Стэндфордского университета [1]: '"... когда мы начинаем говорить о параллелизме и легкости использования действительно параллельных компьютеров, мы говорим о проблеме, которая труднее любой проблемы, с которой встречалась наука о компьютерах < ■ ■ ■ > Я бы запаниковал, если бы я работал в промышленности."
Попытаемся разобраться, в чем же конкретно заключается проблема. Представим себе программную систему, состоящую из множества взаимодействующих программ, распределенных по множеству процессоров. В этом случае в отличие от одной последовательной программы, выполняющейся на одном процессоре, возникают две основные проблемы:
• Проблема установления связей между удаленными друг от друга программами и управления этими связями.
• Проблема частичного упорядочения действий, выполняемых этими программами, и синхронизации их взаимодействия.
Именно для решения этих проблем в "ручном" режиме в настоящее время требуются и незаурядные умственные способности, и большие трудозатраты [2]. Оказывается, что параллельный случай можно свести к последовательному в смысле требований к программисту и процессу программирования путем ввода принципиально новых программных механизмов, основанных на понятиях "пространство-время".
Дело в том, что любая система состоит из некоторого множества частей с некоторым конкретным набором связей между ними. Это означает, что практически все прикладные программисты будут программировать примерно одинаковые действия для управления связями между частями программной системы. Аналогичная ситуация с арифметическими
выражениями существовала, например, до появления Фортрана. Каждый программист программировал в Ассемблере арифметические выражения. Вынесение "за скобки" в системную часть повторяемых всеми действий - это естественный выход из такого рода ситуаций.
Такое вынесение может быть сделано только на основе формальной фиксации некоторого понятия, описывающего алгоритмизируемый класс действий. Для множеств, в которых определены связи между элементами (в другой формулировке для каждого элемента определена окрестность в виде подмножества элементов, связанных с данным), таким понятием является понятие топологического пространства.
Упорядочение действий, выполняющихся в различных параллельно эволюционирующих частях системы, с точки зрения авторов, адекватно описывается понятием времени.
Именно эти два понятия и были положены в основу при разработке комплекса программных средств, целью которого является сведение трудоемкости программирования параллельных систем к трудоемкости последовательного программирования.
Практической основой для представляемой разработки являлось решение реальных задач механики на современных суперкомпьютерах. В частности было просчитано несколько вычислительных моделей из области газовой динамики. Однако авторы считают, что в предлагаемых средствах программирования формализованы понятия, общие для любых прикладных систем.
2. ОСНОВНЫЕ ИДЕИ РЕШЕНИЯ
2.1. Декомпозиция/композиция программной системы
Начнем с общей схемы создания распределенной программной системы, как она представляется авторам. При проектировании любой программной системы естественно начать с определения ее характеристик как единого целого. Если проектируется именно распределенная система, то далее необходимо провести декомпозицию системы, выделить части, которые предположительно будут выполняться на отдельных процессорах.
Например, в случае создания вычислительных моделей для физических областей такая декомпозиция обычно выполняется на уровне дискретной модели [3]. Затем следует этап программирования выделенных частей.
Предполагается, что на этапе декомпозиции для каждой части был определен ее интерфейс с другими частями в виде набора функций, выполняемых данной частью, и наборов функций, которые выполняются другими частями и используются данной. После этого программирование каждой части может быть выполнено независимо от других частей системы.
И, наконец, нужно сделать композицию, сборку целевой системы из частей в единое целое. Основная цель представляемой авторами работы - разработка системных программных средств, позволяющих с малыми трудозатратами запрограммировать сборку независимо созданных программных подсистем в единую распределенную систему.
2.2. Объектно-ориентированный подход
В данной работе за основу берется обычная объектно-ориентированную модель программирования, которая дополняется некоторыми новыми чертами. Программная система строится из множества взаимодействующих друг с другом объектов в рамках некоторой объектно-ориентированной среды программирования. Используется схема, при которой в один объект может одновременно войти несколько процессов и один процесс может пройти через много объектов, возможно расположенных на разных процессорах.
Предполагается, что разбиение системы на объекты выполняется либо на этапе проектирования при создании сложных неоднородных систем, либо может быть сделано автоматически. В качестве систем, поддающихся автоматической декомпозиции, можно, например, привести вычислительные модели задач газовой динамики для областей, сравнительно простых с точки зрения геометрии и протекающих в них процессов.
Для каждого объекта, как обычно, определен интерфейс - набор функций для вызовов. Взаимодействие объектов может производиться
только вызовами одним объектом операций из интерфейса в другом объекте.
Во время счета множество входящих в модель объектов отображается на множество процессоров. Типичный случаем будет считать выделения одного процессора (возможно виртуального) для одного объекта.
2.3. Формальные/фактические соседи
Для того чтобы множество объектов объединить в систему, необходимо задать связи между ними. Используем для этого понятие "соседства". Объект Б считается соседом объекта А, если в процессе эволюции объекта А требуется взаимодействие с объектом Б. Стоит заметить, что понятие соседства может быть как односторонним, так и двухсторонним (объектам требуется взаимодействие друг с другом).
Множество всех соседей конкретного объекта определяет "внешний мир" этого объекта, с которым может происходить его взаимодействие.
Напомним, что для каждого объекта определен некий интерфейс и взаимодействие происходит только с помощью вызовов функций из этого интерфейса. Поэтому, при программировании конкретного класса программисту для описания взаимодействия с другими объектами в модели достаточно иметь список "формальных соседей" с их интерфейсами. "Фактические" соседи, классы которых реализуют интерфейсы из описаний формальных соседей, появятся только во время счета.
Таким образом, при программировании каждого объекта прикладной программист может исходить только из локальных соображений о "внешнем мире" этого объекта, представленном в виде списка формальных соседей.
2.4. Топологические пространства объектов и организация связей между объектами
Распределенная система строится из частей, которые взаимодействуют друг с другом. В программной реализации связи между частями задаются ссылками. В традиционном программировании необходимо вручную определить все ссылки для каждой из частей
системы. Если частей десятки тысяч со сложной топологией связей - это очень трудоемкая задача. Для объектно-ориентированного случая - это программирование прикладным программистом присваивания локальным переменным объекта ссылок на соседние объекты.
Кроме трудоемкости "ручного" формирования ссылок возникает системная проблема коррекции ссылок в случае перемещения объектов из одного вычислительного узла в другой. Это бывает необходимо для балансировки нагрузки многопроцессорной вычислительной системы (МВС) путем "подкачки/выталкивания" неактивных или низкоприоритетных объектов (виртуальная память объектов - аналог подкачки страниц для традиционной виртуальной памяти). При "ручном" управлении ссылками решение этой задачи становится слишком сложным. В нашем случае использование списка формальных соседей и вынесение задачи формирования ссылок на фактических соседей из ведома прикладного программиста в системную часть позволяет достаточно просто решить эту проблему.
Для простого и наглядного задания связей между объектами введем понятие -"пространство объектов". С точки зрения математика "пространство объектов" -это обычное топологическое пространство. Автоматизация состоит в предоставлении пользователю простого интерфейса для работы с топологией связей, а задачи создания и поддержания актуальности ссылок реализуются механизмами внутри предлагаемой нами системы.
В нашем случае топология определяется с использованием метрического пространства и функции близости. В метрическом пространстве каждому объекту сопоставляется некоторая точка из этого пространства, а ф
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.