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

В метрическом пространстве каждому объекту сопоставляется некотораяточка из этого пространства, а функция близости определяет наличие связи между парамиточек. Прикладному программисту предлагается либо статически до начала основного счета,либо динамически во время счета задать координаты каждого объекта в используемомметрическом пространстве.Например, в произвольном графе можно пронумеровать вершины целыми числами иполучить размещение в одномерном метрическом пространстве.

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

Для решения этой проблемы авторами предлагаетсяиспользовать механизм, использующий понятие «ВРЕМЯ».«ВРЕМЯ» практически во всех областях деятельности человека всегда использовалось ииспользуется для упорядочения действий. В частности, время в качестве средствасинхронизации используется в многочисленных системах моделирования цифровыхустройств и дискретных систем управления.В нашем случае «ВРЕМЯ» – это разметка числами последовательности действий врассматриваемом объекте (или в других терминах – разметка последовательных состоянийобъекта).

Синхронизация достигается за счет использования механизма, которыйобеспечивает взаимодействие пары соседних объектов только при равенстве их локальныхвремен.При таком подходе прикладному программисту не нужно следить за «соседними» объектамии синхронизировать вычисления в них. Достаточно просто продвигать значение переменной«ВРЕМЯ» локально в каждом объекте, а синхронизирует вычисления описываемая системаавтоматически.3. Средства программирования прикладных системРассмотрим конкретные средства программирования прикладных распределенных систем,основанные на вышеизложенных идеях.

Предполагается, что работа ведется в более илименее любой существующей среде объектно-ориентированного программирования,дополненной некоторым числом дополнительных классов и дополнительной библиотекойподдержки времени счета.В данной работе все примеры приводятся в контексте языка PYTHON и соответствующейсистемы программирования. Будем называть эту новую среду с дополнительнымисредствами для создания распределенных программ системой OST (Object — Space — Time)Во фрагментах программ, приводимых ниже в качестве примеров, используются следующиеобозначения:- шрифт «курсив» указывает на то, что данное имя является абстрактным и в конкретнойприкладной программе должно быть заменено программистом на конкретное;- шрифт «полужирный» указывает на то, что данное имя является фиксированным в средеOST и в любой прикладной программе должно быть именно таким;- шрифт «обычный» указывает на то, что данное имя является фиксированным в средеданного языка программирования.63.1.

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

В результате, оказывается удобно использовать хорошо известный набортопологических понятий.Рассмотрим конкретные механизмы работы с топологиями множеств объектов впредлагаемой нами системе.3.1.1. Определение топологии.В нашей работе под заданием топологии некоторого пространства, мы понимаем задание длякаждой точки из этого пространства окрестности в виде множества соседних точек или,проще говоря, соседей. Для объектов, из которых состоит создаваемая распределеннаясистема, понятие окрестности соответствует понятию “внешнего окружения” объекта.В системе OST топология задаются с помощью класса, в котором определена либо функцияблизости, проверяющая соседство пары точек, либо функция описания окрестности,задающая множество точек входящих в окрестность к данной.

Такое разделение позволяетпростым способом описать разные по устройству топологии. Так функция описанияокрестности хорошо подходит для описания регулярных структур, например, целочисленныхрешеток. Функция близости, наоборот, подходит для описания нерегулярных структур,например, в случае взаимодействия через поле тяготения в небесной механике.3.1.1.1. Задание окрестности объекта с помощью функции близости.Функция близости для пары точек A и B определяет принадлежность точки B окрестноститочки A.

Сама окрестность фиксированной точки A может быть построена системой OST,например, путем перебора всевозможных значений B и проверкой с помощью функцииблизости. Проиллюстрируем задание топологии на примере графа с пронумерованнымивершинами. Граф связей, не имеющий никакой регулярной структуры, можно описатьтолько с помощью таблицы, в которой для каждой вершины хранится список соседнихвершин.

Функция близости в таком случае проверяет наличие ребра между парой вершин вэтой таблице, названной в приведенном ниже примере self.edges.Для того, чтобы при задании топологии имелась возможность хранения информации,описывающей например, ребра графа, функция близости реализуется не как одиночнаяфункция, а помещена в класс описания топологии.class applied_topology(ost.Topology.Abstract):#Таблица, задающая ребра графа#Для каждой вершины p1 в self.edges[p1] хранится список#вершин p2 с которыми p1 связана ребром7self.edges = { p1: [p1_1,...,p1_k1]p2: [p2_1,...,p2_k2]...pM: [pM_1,...,p1_kM]}#Функция близости проверяет наличие вершины p2#в списке концов ребер, выходящих из p1def proximity(self, p1, p2):# Оператор in возвращает bool значение вхождения# в списке self.edges[p1] элемента p2return p2 in self.edges[p1]3.1.1.2.

Задание окрестности объекта с помощью функции описанияокрестности.Функция описания окрестности для некоторой точки возвращает в виде списка координатывсех точек, которые входят в её окрестность.Рассмотрим применение этой функции на том же примере задания графа связей.class applied_topology(ost.Topology.Abstract):#Таблица, задающая ребра графа#Для каждой вершины p1 в self.edges[p1] хранится список#вершин p2 с которыми p1 связана ребромself.edges = { p1: [p1_1,...,p1_k1]p2: [p2_1,...,p2_k2]...pM: [pM_1,...,p1_kM]}#Функция описания окрестности вершины p#Возвращает список всех вершин, с которыми соединена данная pdef neighborhood(self, p):return self.edges[p]Какую из предложенных функций использовать для задания топологии конкретнойраспределенной системы остается на усмотрение прикладного программиста.В некоторых случаях удобнее использовать функцию близости.

Для примера рассмотримдвумерную плоскость и окрестности в виде кругов.class applied_topology(ost.Topology.Abstract):# Функция вычисления расстояния между точкамиdef distance(self, p1, p2):return sqrt( (p1[0]— p2[0])**2 +(p1[1] - p2[1])**2)# Функция близости.

Расстояние между точками меньше, чем radiusdef proximity(self, p1, p2):return self.distance(p1, p2) < radiusДля других ситуаций, использование функции описания окрестности оказывается удобнее инагляднее. Например, в случае двумерной целочисленной решетки можно описатьмножество точек, входящих в окрестность, следующим образом:8class applied_topology(ost.Topology.Abstract):def neighborhood(self, p):return [[p[0] + 1, p[1]], # точка справа[p[0] - 1, p[1]], # точка слева[p[0], p[1] + 1], # точка сверху[p[0], p[1] — 1] # точка снизу]Стоит заметить, что системе OST в случае использования функции близости дляопределения окрестности конкретной точки необходимо произвести проверку на соседство спомощью этой функции для всех точек в паре с данной точкой. Для случая статическойтопологии связей этот факт не очень существенен.

Однако, в случае изменения топологиисвязей в процессе счета, с целью оптимизации времени работы прикладной системы,рекомендуется использовать функцию описания окрестности.В системе OST предусмотрено наличие «стандартных» классов топологий, включенных всистему. Эти классы реализуют с помощью вышеописанных механизмов наиболее частовстречающиеся типы топологий.

В случае «нестандартных» топологий прикладнойпрограммист может создать собственный класс топологии и использовать его в своихприкладных системах.3.1.2. Локальная и глобальная топология.В данном разделе мы рассмотрим, как при создании модели использовать имеющиеся классытопологий для задания связей между объектами в прикладной системе. В системе OST присоздании модели программист может задать класс топологии как общий для всех объектов всистеме, либо его можно задать индивидуально для объектов со специфической топологиейокрестности. Система OST при запуске на счет , а в случае динамического изменения связейи во время счета, автоматически определит и установит все необходимые связи междуобъектами.Таким образом, экземпляры классов топологий в системе OST могут использоваться двумяспособами: как глобальные (задающие топологии всех объектов) и локальные (задающиетопологию окрестности одного объекта).Объект глобальной топологии задается в программе инициализации прикладной системы какпараметр topology создаваемой модели.