А.И.Илюшин, М.А.Оленин, С.А.Васильев - Решение проблемы параллельных вычислений на основе понятий «пространство-время» (1185570), страница 3
Текст из файла (страница 3)
Приведем для примера часть из программы, вкоторой задается двухмерная целочисленная решетка с помощью стандартного классаost.Topology.Mesh, который задает топологию целочисленных решеток.# Определение глобальной топологииobjInit.topology = ost.Topology.Mesh(dimension = 2)Если глобальная топология не определена, то в системе OST используется стандартнаятопология, в которой окрестность каждого объекта пуста.
Тогда все связи должны бытьзаданы локальными топологиями.Объект локальной топологии определяется при создании объекта, например, в программеинициализации прикладной системы как параметр topology создаваемого объекта.Приведем пример задания окрестности с помощью стандартного класса9ost.Topology.Neighborhood, в котором окрестность точки описывается ввиде константного множества координат соседних точек# Определение локальной топологииobject.topology = ost.Topology.Neighborhood([[x1,y1],...,[xN,yN]])В данном примере определяется окрестность объекта object, которая состоит из точек[x1,y1],...,[xN,yN].Для иллюстрации использования локальных и глобальных топологий, приведем примерпрограммы создания модели.# Определение глобальной топологииobjInit.topology = ost.Topology.Mesh(dimension = 2)# Создание объектаobject1 = objectInit.createObject( <...> )# помещение объекта в точку с координатами [0,0]objInit.set(object1, [0,0])object2 = objectInit.createObject( <...> )objInit.set(object2, [0,1])object3 = objectInit.createObject( <...> )objInit.set(object3, [1,1])object4 = objectInit.createObject( <...> )# Определение локальной топологииobject4.topology = ost.Topology.Neighborhood([[0,0]])objInit.set(object4, [2,2])В этом примере с помощью глобальной топологии задается связь между парами объектов скоординатами [0,0], [0,1] и [0,1], [1,1].
С помощью локальной топологии для объекта скоординатами [2,2] задается односторонняя связь с объектом [0,0].Использование других классов топологий, в том числе и пользовательских, аналогичноприведенному примеру.3.1.3. Формальные и фактические соседи.В данном разделе рассмотрим механизм взаимодействия объектов прикладной системы сосвоими окрестностями.
При создании модели с помощью системы OST пользовательописывает некоторый набор типов объектов. Тип определяется прикладным классом, исходятолько из локальных соображений, относящихся только к объектам описываемого типа.Конкретно локальность здесь означает, что программист вполне традиционным образомописывает внутреннее функционирование объекта данного типа, а «окружение»определяется в виде списка «формальных соседей».Понятие «список формальных соседей» можно рассматривать как существенное обобщениепонятия списка формальных параметров для подпрограммы. Элементы этого списка - этообъекты-заглушки с заданными интерфейсами, у которых можно вызывать операции так, какэто происходит в обычном объектно-ориентированном программировании.10Во время счета вместо объектов-заглушек в этот список системой OST подставляютсяссылки на фактических соседей, т.е.
на объекты, которые попали в окрестность данногоэкземпляра объекта.Для иллюстрации приведем пример вызова функции fun у соседнего объекта под номером iв списке соседей:# Вызов функции fun у соседа №iself.neighbors[i].link.fun(<...>)Для улучшения читаемости текста программы можно использовать синонимы длянаправлений соседства в конкретной топологии. Например, в случае двухмернойцелочисленной решетки возможные соседи задаются однозначно: слева, справа, сверху иснизу. Приведем аналогичный пример вызова функции у соседнего объекта слева# Вызов функции fun у соседа слеваself.left.fun(<...>)Для иллюстрации использований топологий приведем примеры классов объектовприкладных систем.# Пример класса объекта, иллюстрирующий работу со списком соседей.class applied_object(ost.Object.Abstract):# В данном примере опущена техническая часть класса,# которая не относится к использованию соседей# Функция, которая входит в интерфейс.# Выводит на экран пришедшее сообщениеdef fun(self, message):print "Call function with", data# Функция проводящая вычисленияdef run(self):# Цикл по итерациям алгоритмаwhile <...>:# перебираем всех соседейfor neighbor in self.topology.neighbors:# вызываем у каждого соседа функцию funneighbor.fun(<message>)# Класс объекта с работой через синонимы соседейclass applied_object(ost.Object.Abstract):# В данном примере опущена техническая часть класса,# которая не относится к использованию соседей# Функция, которая входит в интерфейс.# Выводит на экран пришедшее сообщениеdef fun(self, message):print "Call function with", data# Функция проводящая вычисления11def run(self):# Цикл по итерациям алгоритмаwhile <...>:self.left.fun(<message>)Для классов топологий, определенных пользователем, в системе OST предусмотренымеханизмы задания своих синонимов.3.1.4.
Примеры стандартных топологий.В данном разделе мы рассмотрим стандартные классы топологий, которые входят в системуOST.Класс целочисленной решетки ost.Topology.Mesh.Эта топология отличается простотой задания окрестности в пространстве любойразмерности. Окрестность точки задается с помощью очень простого свойства — этомножество точек, у которых ровно одна координата отличается на 1 от соответствующейкоординаты рассматриваемой точки. При использовании данного класса в конструкторезадается параметр размерности пространства.
Для малых размерностей (1,2 и 3)предусмотрены синонимы «направлений соседства».Пример использования:# Задание топологии<...>.topology = ost.Topology.Mesh(dimension = <размерность>)####Доступныеdimensiondimensiondimensionсинонимы соседей в зависимости от размерности= 1 — left, right= 2 — left, right, up, down= 3 — left, right, up, down, front, behindКласс кольца ost.Topology.Ring.Данная топология представляет собой граф в виде кольца, состоящий из N точек,пронумерованных от 1 до N.
Окрестность точки состоит из соседей справа и слева.Топологию кольца удобно применять в задачах, требующих циклическую передачу данныхмежду частями прикладной системы. Например, такая топология используется припараллельном умножении матриц, в котором полосы столбцов передаются через кольцопроцессоров, в которых хранятся полосы строк.
При использовании данного класса вконструкторе задается количество точек кольца.Пример использования# Задание топологии<...>.topology = ost.Topology.Ring(N = <количество точек кольца>)# Доступные синонимы соседей left, right12Класс неструктурированной решетки ost.Topology.Graph.С помощью данной топологии задается произвольный граф. Окрестность вершины задаетсямножеством вершин, с которыми соединена ребром данная. При использовании на практикепользователь может использовать различные интерфейсы конструктора.Задание топологии с помощью таблицы, описывающей для каждой вершины ее окрестностьedges = { P1: [P1_neighbor_1,…,P1_neighbor_N1],…Pm: [Pm_neighbor_1,…,PM_neighbor_Nm]}В данном примере P1,…,Pm — вершины графа, а список[Pi_neighbor_1,…,Pi_neighbor_Ni]задает набор вершин, входящих в окрестность i-ой точки.# Задание топологии с помощью таблицы связности<...>.topology = ost.Topology.Graph(edges = edges)Задание топологии возможно так же с помощью сторонних генераторов графов, например, спомощью широко используемой системы Metis:# Задание топологии с помощью Metis<...>.topology = ost.Topology.Graph(metis_datafile = datafile.dat)Класс фиксированной окрестности ost.Topology.Neighborhood.С помощью данного класса топологии для любой точки пространства описываетсяфиксированная окрестность, состоящая из константного множества точек.
В системе OSTКласс фиксированной окрестности применятся в случае, когда требуется специализироватьлокальную топологию конкретного объекта.В конструкторе задается список наборов координат точек, входящих в окрестность.# Определение локальной топологииobject.topology = ost.Topology.Neighborhood([P1,…,Pk])# Здесь Pi = [Pi_x1,…,Pi_xN] — набор координат i-го соседа3.2. Разметка временем действий в прикладной системеПредполагается, что каждый объект в рассматриваемой распределенной системеэволюционирует во время счета, проходя через последовательность состояний. Прикладномупрограммисту предлагается помечать каждое состояние конкретным значением «локальноговремени объекта», которое хранится в специальной переменной.Локальное время объекта может соответствовать физическому времени для моделируемогопроцесса внутри объекта или это может быть искусственное время, которое вводится лишьдля упорядочения выполняемых действий.
Например, это может быть порядковый номеритерации в алгоритме, заданном в объекте.Синхронизация вычислений между объектами осуществляется системой OST на основеединственного правила – взаимодействие разрешается, если локальные времена объектовравны.13В процессе эволюции объекты выполняют запросы на продвижение своих локальныхвремен.
Система OST обрабатывает эти запросы и в случае необходимости приостанавливаетвычисления для соблюдения правила синхронизации.Это правило в системе OST состоит в том, что для продвижения локального времениконкретного объекта до определенного значения необходимо наличие запросов в системуOST на продвижение локальных времен до этого же значения от всех соседейрассматриваемого объекта.
Такое правило, во-первых, гарантирует исключение ситуаций свызовом операции в объекте, у которого локального время больше времени вызывающегообъекта. Во-вторых, обеспечивается достаточная свобода для проведения параллельногосчета для несмежных объектов, так как допускается расхождение локальных времен междупарой несмежных объектов на сумму приращений времен для всех промежуточныхобъектов, располагающихся на пути по связям между рассматриваемыми несмежнымиобъектами.3.2.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
