А.И.Илюшин, М.А.Оленин, С.А.Васильев - Решение проблемы параллельных вычислений на основе понятий «пространство-время» (А.И.Илюшин, М.А.Оленин, С.А.Васильев - Решение проблемы параллельных вычислений на основе понятий «пространство-время».pdf)

1РЕШЕНИЕ ПРОБЛЕМЫ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙНА ОСНОВЕ ПОНЯТИЙ «ПРОСТРАНСТВО-ВРЕМЯ»А.И.Илюшин, М.А.Оленин, С.А.ВасильевКафедра вычислительной механики, механико-математический факультет МГУИнститут прикладной математики ИПМ РАНАннотацияРассматривается построение распределенных систем путем композиции программных объектов.Предлагается задавать топологию связей между объектами, описывая «окрестность» каждогообъекта в виде списка «формальных соседей». Синхронизацию эволюции объекта и его «соседей»предлагается описывать с помощью «локального времени» объекта и его окрестности.

Приводятсярезультаты программирования и счета реальных задач на суперкомпьютере, показывающиевозможность сведения трудоемкости создания распределенных программных систем ктрудоемкости локального программирования.Ключевые слова и выражения:Композиция программных объектов, топология связей объектов, формальные и фактические соседи,синхронизация эволюции объектов, локальное время объекта и его окрестности.1. ВведениеОбщепризнанно, что в настоящее время программирование многопроцессорных(многоядерных) вычислительных систем является задачей, которая требует от программистаи высокой квалификации, и больших трудозатрат. В частности, можно привести цитату изинтервью ветерана в области вычислительной техники Джона Хэннеси, президентаСтэндфордского университета [1] :“… когда мы начинаем говорить о параллелизме и легкости использования действительнопараллельных компьютеров, мы говорим о проблеме, которая труднее любой проблемы, скоторой встречалась наука о компьютерах <…> Я бы запаниковал, если бы я работал впромышленности.”Попытаемся разобраться, в чем же конкретно заключается проблема.

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

Проблема частичного упорядочения действий, выполняемых этими программами, исинхронизации их взаимодействия.Именно для решения этих проблем в «ручном» режиме в настоящее время требуются инезаурядные умственные способности, и большие трудозатраты [2]. Оказывается, чтопараллельный случай можно свести к последовательному в смысле требований к2программисту и процессу программирования путем ввода принципиально новыхпрограммных механизмов, основанных на понятиях «пространство-время».Дело в том, что любая система состоит из некоторого множества частей с некоторымконкретным набором связей между ними. Это означает, что практически все прикладныепрограммисты будут программировать примерно одинаковые действия для управлениясвязями между частями программной системы.

Аналогичная ситуация с арифметическимивыражениями существовала, например, до появления Фортрана. Каждый программистпрограммировал в Ассемблере арифметические выражения. Вынесение «за скобки» всистемную часть повторяемых всеми действий – это естественный выход из такого родаситуаций.Такое вынесение может быть сделано только на основе формальной фиксации некоторогопонятия, описывающего алгоритмизируемый класс действий.

Для множеств, в которыхопределены связи между элементами (в другой формулировке для каждого элементаопределена окрестность в виде подмножества элементов, связанных с данным), такимпонятием является понятие топологического пространства.Упорядочение действий, выполняющихся в различных параллельно эволюционирующихчастях системы, с точки зрения авторов, адекватно описывается понятием времени.Именно эти два понятия и были положены в основу при разработке комплекса программныхсредств, целью которого является сведение трудоемкости программирования параллельныхсистем к трудоемкости последовательного программирования.Практической основой для представляемой разработки являлось решение реальных задачмеханики на современных суперкомпьютерах.

В частности было просчитано нескольковычислительных моделей из области газовой динамики. Однако авторы считают, что впредлагаемых средствах программирования формализованы понятия, общие для любыхприкладных систем.2. Основные идеи решения2.1. Декомпозиция/композиция программной системыНачнем с общей схемы создания распределенной программной системы, как онапредставляется авторам. При проектировании любой программной системы естественноначать с определения ее характеристик как единого целого.

Если проектируется именнораспределенная система, то далее необходимо провести декомпозицию системы, выделитьчасти, которые предположительно будут выполняться на отдельных процессорах. Например,в случае создания вычислительных моделей для физических областей такая декомпозицияобычно выполняется на уровне дискретной модели [3]. Затем следует этаппрограммирования выделенных частей.Предполагается, что на этапе декомпозиции для каждой части был определен ее интерфейс сдругими частями в виде набора функций, выполняемых данной частью, и наборов функций,которые выполняются другими частями и используются данной. После этого3программирование каждой части может быть выполнено независимо от других частейсистемы.И, наконец, нужно сделать композицию, сборку целевой системы из частей в единое целое.Основная цель представляемой авторами работы – разработка системных программныхсредств, позволяющих с малыми трудозатратами запрограммировать сборку независимосозданных программных подсистем в единую распределенную систему.2.2.

Объектно-ориентированный подходВ данной работе за основу берется обычная объектно-ориентированную модельпрограммирования, которая дополняется некоторыми новыми чертами. Программнаясистема строится из множества взаимодействующих друг с другом объектов в рамкахнекоторой объектно-ориентированной среды программирования. Используется схема, прикоторой в один объект может одновременно войти несколько процессов и один процессможет пройти через много объектов, возможно расположенных на разных процессорах.Предполагается, что разбиение системы на объекты выполняется либо на этапепроектирования при создании сложных неоднородных систем, либо может быть сделаноавтоматически.

В качестве систем, поддающихся автоматической декомпозиции, можно,например, привести вычислительные модели задач газовой динамики для областей,сравнительно простых с точки зрения геометрии и протекающих в них процессов.Для каждого объекта, как обычно, определен интерфейс — набор функций для вызовов.Взаимодействие объектов может производиться только вызовами одним объектом операцийиз интерфейса в другом объекте.Во время счета множество входящих в модель объектов отображается на множествопроцессоров.

Типичный случаем будет считать выделения одного процессора (возможновиртуального) для одного объекта.2.3. Формальные/фактические соседиДля того чтобы множество объектов объединить в систему, необходимо задать связи междуними. Используем для этого понятие «соседства». Объект Б считается соседом объекта А,если в процессе эволюции объекта А требуется взаимодействие с объектом Б.

Стоитзаметить, что понятие соседства может быть как односторонним, так и двухсторонним(объектам требуется взаимодействие друг с другом).Множество всех соседей конкретного объекта определяет «внешний мир» этого объекта, скоторым может происходить его взаимодействие.Напомним, что для каждого объекта определен некий интерфейс и взаимодействиепроисходит только с помощью вызовов функций из этого интерфейса. Поэтому, припрограммировании конкретного класса программисту для описания взаимодействия сдругими объектами в модели достаточно иметь список «формальных соседей» с ихинтерфейсами. «Фактические» соседи, классы которых реализуют интерфейсы из описанийформальных соседей, появятся только во время счета.4Таким образом, при программировании каждого объекта прикладной программист можетисходить только из локальных соображений о «внешнем мире» этого объекта,представленном в виде списка формальных соседей.2.4.

Топологические пространства объектов и организация связеймежду объектамиРаспределенная система строится из частей, которые взаимодействуют друг с другом. Впрограммной реализации связи между частями задаются ссылками. В традиционномпрограммировании необходимо вручную определить все ссылки для каждой из частейсистемы. Если частей десятки тысяч со сложной топологией связей - это очень трудоемкаязадача. Для объектно-ориентированного случая — это программирование прикладнымпрограммистом присваивания локальным переменным объекта ссылок на соседние объекты.Кроме трудоемкости «ручного» формирования ссылок возникает системная проблемакоррекции ссылок в случае перемещения объектов из одного вычислительного узла в другой.Это бывает необходимо для балансировки нагрузки многопроцессорной вычислительнойсистемы (МВС) путем «подкачки/выталкивания» неактивных или низкоприоритетныхобъектов (виртуальная память объектов - аналог подкачки страниц для традиционнойвиртуальной памяти).

При «ручном» управлении ссылками решение этой задачи становитсяслишком сложным. В нашем случае использование списка формальных соседей и вынесениезадачи формирования ссылок на фактических соседей из ведома прикладного программистав системную часть позволяет достаточно просто решить эту проблему.Для простого и наглядного задания связей между объектами введем понятие —«пространство объектов».

С точки зрения математика «пространство объектов» — этообычное топологическое пространство. Автоматизация состоит в предоставлениипользователю простого интерфейса для работы с топологией связей, а задачи создания иподдержания актуальности ссылок реализуются механизмами внутри предлагаемой намисистемы.В нашем случае топология определяется с использованием метрического пространства ифункции близости.