Аноним

Синхронизаторы и остовы: различия между версиями

Материал из WEGA
м
Строка 6: Строка 6:




В случае синхронной организации коммуникация осуществляется в виде дискретных раундов, и сообщение, отправленное в начале раунда R, прибывает в точку назначения до его окончания. В случае асинхронной организации каждая вершина поддерживает собственный тактовый синхронизатор, причем у разных вершин они могут не совпадать. Предполагается, что каждое отправленное сообщение (в случае синхронной организации) прибывает в точку назначения в течение определенного временного интервала x после отправки, однако значение т процессорам неизвестно.
В случае ''синхронной'' организации коммуникация осуществляется в виде дискретных ''раундов'', и сообщение, отправленное в начале раунда R, прибывает в точку назначения до его окончания. В случае ''асинхронной'' организации каждая вершина поддерживает собственный тактовый синхронизатор, причем у разных вершин они могут не совпадать. Предполагается, что каждое отправленное сообщение (в случае синхронной организации) прибывает в точку назначения в течение определенного временного интервала <math>\tau \;</math> после отправки, однако значение <math>\tau \;</math> процессорам неизвестно.




В общем случае оказывается намного проще разрабатывать алгоритмы, рассчитанные на синхронную организацию (называемые синхронными алгоритмами), чем на асинхронную (соответственно, асинхронные). Авербух [ ] инициировал исследование техник моделирования, которые переводили бы синхронные алгоритмы в асинхронные. Такие техники моделирования называются синхронизаторами.
В общем случае оказывается намного проще разрабатывать алгоритмы, рассчитанные на синхронную организацию (называемые синхронными алгоритмами), чем на асинхронную (соответственно, асинхронные). Авербух [1] инициировал исследование техник моделирования, которые переводили бы синхронные алгоритмы в асинхронные. Такие техники моделирования называются ''синхронизаторами''.




При разработке первых синхронизаторов Авербух предложил определенное разбиение графа, представляющее интерес само по себе. В частности, Пелег и Шеффер [8] заметили, что это разбиение порождает подграф с определенными любопытными свойствами. Такой подграф они назвали остовом графа. Формально для целого положительного параметра k k-остовом графа G = (V, E) является подграф G0 = (V, H), H С E, такой, что для каждого ребра e = (v, u) 2 E расстояние между вершинами v и u в H, distG0(v, u), не превышает k.
При разработке первых синхронизаторов Авербух предложил определенное разбиение графа, представляющее интерес само по себе. В частности, Пелег и Шеффер [8] заметили, что это разбиение порождает подграф с определенными любопытными свойствами. Такой подграф они назвали [[Остов|остовом графа]]. Формально для целого положительного параметра k k-остовом графа G = (V, E) является подграф G' = (V, H), <math>H \subseteq E</math>, такой, что для каждого ребра <math>e = (v, u) \in E \;</math> расстояние между вершинами v и u в H, <math>dist_{G'}(v, u) \;</math>, не превышает k.


== Основные результаты ==
== Основные результаты ==
4551

правка