Адаптер распределенной карты свойств - это карта свойств, сохраненные значения которой распределены по нескольким непересекающимся пространствам памяти на различных процессах. Значения, локальные для текущего процесса, хранятся в локальной карте свойств и могут быть немедленно доступны через, получитьипоставить. Значения, хранящиеся в удаленных процессах, также могут быть доступны черезполучитьипоставить, но поведение немного отличается:
поставьтеоперации обновления локальной призрачной ячейки и отправьте сообщение в процесс, которому принадлежит значение. Владелец может свободно обновлять свою собственную стоимость или может игнорировать поставленный запрос.
получаютоперации, возвращающие содержимое местной призрачной ячейки. Если призрачная ячейка недоступна, она создается с использованием (настраиваемого) значения по умолчанию.
Использование распределенных карт свойств требует немного больше внимания, чем использование локальных последовательных карт свойств. Хотя синтаксис и семантика схожи, распределенные карты свойств могут содержать устаревшую информацию, которая может быть гарантированно синхронизирована только путем вызова функции синхронизацииво всех процессах.
Для решения проблемы устаревших значений распределенные карты свойств поддерживают несколькомоделей согласованностии могут быть снабжены операцией сокращения.
Карты распределенных свойств предлагают множество моделей согласованности, которые влияют на то, как значения, считываемые и записанные на удаленные ключи, относятся к значению "официального" для этого ключа, хранящегося в процессе владения. Модель согласованности распределенной карты свойств может быть установлена с функцией участникаset_consistency_modelпо битуазу-OR флагов в бустере::parallel::consistency_modelПеречисление. Отдельными флагами являются:
cm_forward: Модель согласованности по умолчанию, которая распространяет значения вперед от, ставитоперации на удаленных процессорах владельцу изменяемого значения.
cm_backward: После того, как все значения были перенаправлены или смыты в собственные процессы, каждый процесс получает значения обновлений для каждой из своих ячеек-призраков. После синхронизации значения в ячейках-призраках гарантированно соответствуют значениям, хранящимся на собственном процессоре.
cm_flush: В начале синхронизации все значения, хранящиеся локально в ячейках-призраках, отправляются на собственные процессоры.
cm_reset: Исполняетсброс()работа после синхронизации, установка значений в каждой призрачной ячейке на их значение по умолчанию.
cm_clear: Исполняетясно ()операция после синхронизации, устранение всех призрачных клеток.
Существует несколько распространенных комбинаций флагов, которые приводят к интересным моделям согласованности. Некоторые из этих комбинаций:
cm_forward: Сама по себе модель форвардной согласованности позволяет алгоритмам, таким каккратчайшие путииBreadth-First Search, работать правильно.
cm_flush&cm_reset: Все значения обновлений выстраиваются в очередь локально, а затем смываются на этапе синхронизации. Как только смыв происходит, клетки-призраки восстанавливаются до своих значений по умолчанию. Эта модель согласованности используется реализациейPageRankдля локального накопления ранга для каждого узла.
Reduction operation
Операция восстановления поддерживает согласованность, определяя, как решаются множественные записи на карту свойств и что должна делать карта свойств, если запрашиваются неизвестные значения. Более конкретно, восстановительная операция применяется в двух случаях:
Когда значение необходимо для удаленного ключа, но значение не доступно сразу, операция восстановления обеспечивает подходящий по умолчанию. Например, распределенная карта свойств, сохраняющая расстояния, может иметь операцию сокращения, которая возвращает бесконечное значение по умолчанию, тогда как распределенная карта свойств для вершинных цветов может возвращать белый цвет по умолчанию.
Когда значение получено из удаленного процесса, процесс, владеющий ключом, связанным с этим значением, должен определить, какое значение - локально сохраненное значение, значение, полученное из удаленного процесса, или некоторая комбинация этих двух - будет храниться в качестве "официального" значения на карте свойств. Операция редукции преобразует локальные и удаленные значения в "официальное" значение для хранения.
Операция восстановления распределенной карты свойств может быть установлена с помощью методаset_reducedistributed_property_map. Операция уменьшения представляет собой функциональный объект с двумя сигнатурами. Первая подпись берет (удаленный) ключ и возвращает значение по умолчанию для него, в то время как вторая подпись берет ключ и два значения (сначала локальное, затем удаленное) и возвращает комбинированное значение, которое будет храниться в локальной карте свойств. Операции по уменьшению должны также содержать статическую постояннуюnon_default_resolver",, котораяуказывает, является лиснижениепо умолчаниюна самом деледействуеткакпо умолчанию.Ондолжен быть'истинным, когда по умолчанию имеет значение (например, бесконечность для расстояния) иложным, когда по умолчанию не следует использовать.
Следующая операция восстановления используется распределенным алгоритмом PageRank. Ранг по умолчанию для удаленного узла равен 0. Ранг аккумулируется локально, а затем операция редукции объединяет локальные и удаленные значения путем их добавления. В сочетании с моделью согласованности, которая сбрасывает все значения владельцу, а затем локально сбрасывает значения на каждом этапе, полученная карта свойств вычисляет частичные суммы на каждом процессоре, а затем накапливает результаты на собственном процессоре. Операция сокращения PageRank определяется следующим образом.
template<typename T>
struct rank_accumulate_reducer {
static const bool non_default_resolver = true;
// The default rank of an unknown node
template<typename K>
T operator()(const K&) const { return T(0); }
template<typename K>
T operator()(const K&, const T& x, const T& y) const { return x + y; }
};
Distributed property map adaptor
Адаптер распределенной карты свойств создает распределенную карту свойств из локальной карты свойств, группу процессов, над которой должно происходить распределение, и тип глобального дескриптора, который индексирует распределенную карту свойств.
The type of the process group over which the
property map is distributed and is also the medium for
communication.
LocalPropertyMap:
The type of the property map that will store values
for keys local to this processor. The value_type of this
property map will become the value_type of the distributed
property map. The distributed property map models the same property
map concepts as the LocalPropertyMap, with one exception: a
distributed property map cannot be an Lvalue Property Map
(because remote values are not addressable), and is therefore
limited to Read/Write Property Map.
Key:
The key_type of the distributed property map, which
must model the Global Descriptor concept. The process ID type of
the Key parameter must match the process ID type of the
ProcessGroup, and the local descriptor type of the Key must
be convertible to the key_type of the LocalPropertyMap.
GhostCellS:
A selector type that indicates how ghost cells should be stored in
the distributed property map. There are either two or three
options, depending on your compiler:
boost::parallel::gc_mapS(по умолчанию): Использует карту STLдля хранения клеток-призраков для каждого процесса.
boost::parallel::gc_vector_mapS: Использует сортированный вектор STLдля хранения клеток-призраков для каждого процесса. Этот вариант хорошо работает, когда в ячейки-призраки, вероятно, будет мало вставок; например, если единственные используемые ячейки-призраки предназначены для соседних вершин, карта свойств может быть инициализирована с ячейками для каждой соседней вершины, обеспечивая более быстрый поиск, чем картаи используя меньше места.
boost::parallel::gc_hash_mapS: Использует GCChash_mapдля хранения клеток-призраков. Эта опция может улучшить производительность по сравнению скартойдля больших размеров проблем, где набор ячеек-призраков не может быть предопределен.
Member functions
distributed_property_map();
Дефолт-конструкция распределенной карты свойств. Карта имущества находится в недействительном состоянии и может использоваться только в том случае, если она переназначена на действующую карту имущества.
Постройте карту недвижимости из группы процессов и карту местной собственности. Еслисокращениеоперация не поставляется, по умолчаниюbasic_reduceбудет использоваться.
Заменить текущую операцию восстановления новой операциейуменьшить.
void set_consistency_model(int model);
Устанавливает модель согласованности распределенной карты свойств, которая вступит в силу на следующем этапе синхронизации. См. разделМодели согласованностидля описания эффекта различных флагов моделей согласованности.
void flush();
Излучает сообщение, отправляющее содержимое всех местных клеток-призраков владельцам этих клеток.
void reset();
Заменяет значения, хранящиеся в каждой из ячеек-призраков, значением по умолчанию, генерируемым операцией восстановления.
void clear();
Удалите все клетки-призраки с карты собственности.
Получает элемент вpm, связанный с даннымключом. Если ключ относится к данным, хранящимся локально, возвращает фактическое значение, связанное с ключом. Если ключ относится к нелокальным данным, возвращается значение призрачной ячейки. Если не существует призрачной ячейки, поведение зависит от текущей операции редукции: если операция редукции была установлена и имеетnon_default_resolversettrue, то ячейка-призрак будет создана в соответствии со значением по умолчанию, предоставленным операцией редукции. В противном случае вызовполучитьпрекратится, потому что для этой удаленной ячейки не существует значения. Чтобы избежать этой проблемы, либо установите операцию восстановления, которая генерирует значения по умолчанию,запроситезначение, а затем выполните этап синхронизации, либопоместитезначение в ячейку перед его чтением.
Помещает данноезначение, связанное сключомв карту свойствpm. Если ключ относится к данным, хранящимся локально, значение немедленно обновляется. Если ключ относится к данным, хранящимся в удаленном процессе, обновляет (или создает) локальную ячейку-призрак, содержащую это значение для ключа, и отправляет новое значение в процесс владения. Обратите внимание, что процесс владения может отклонить это значение на основе операции сокращения, но это не будет обнаружено до следующего этапа синхронизации.
Эквивалентноput(pm,key,value), за исключением того, что никакое сообщение не отправляется в процесс владения при изменении значения для нелокального ключа.
void synchronize(distributed_property_map& pm);
Синхронизируйте значения, хранящиеся в распределенных картах свойств. Каждый процесс выполняетсинхронизациюодновременно, после чего призрачные клетки в каждом процессе будут отражать фактическое значение, хранящееся в процессе владения.
Запросите, чтобы элемент "ключ" был доступен после следующего этапа синхронизации. Для нелокального ключа это означает создание клетки-призрака и запрос.
Создать распределенную карту свойств по группе процессовpgи локальную карту свойствpmap. Операция по снижению по умолчанию будет создана, если она не предусмотрена.
Distributed iterator property map
Адаптер распределенной карты свойств итератора позволяет создавать распределенные карты свойств из итераторов случайного доступа с использованием того же синтаксиса, что и карты свойств нераспределенного итератора. Специализация основана налокальной карте свойств, которая содержит индексы для локальных дескрипторов и обычно возвращается для описания индексов вершин распределенного графа.
Default-конструирует распределенную карту свойств итератора. Карта собственности находится в недействительном состоянии и должна быть переназначена до ее использования.
Построение распределенной карты свойств итератора с использованием карты свойствidдля отображения глобальных дескрипторов на локальные индексы. Последовательность итератора случайного доступа[итер,+n]должна быть допустимым диапазоном, где[0,n]является диапазоном локальных индексов.
Создает распределенную карту свойств итератора с использованием данного итератораитераи локальной карты свойств индексаid.
Distributed safe iterator property map
Адаптер распределенного безопасного итератора свойств позволяет создавать распределенные карты свойств из итераторов случайного доступа с использованием того же синтаксиса, что и нераспределенные карты свойств безопасного итератора. Специализация основана налокальной карте свойств, которая содержит индексы для локальных дескрипторов и обычно возвращается для описания индексов вершин распределенного графа. Карты свойств безопасного итератора проверяют индексы доступа, чтобы убедиться, что они не выходят за рамки, прежде чем пытаться получить доступ к значению.
Default-конструирует распределенную карту свойств безопасного итератора. Карта собственности находится в недействительном состоянии и должна быть переназначена до ее использования.
safe_iterator_property_map(RandomAccessIterator iter, std::size_t n,
const index_map_type& id);
Построение распределенной карты свойств безопасного итератора с использованием карты свойствidдля отображения глобальных дескрипторов на локальные индексы. Последовательность итератора случайного доступа[итер,+n].
Создает распределенную карту свойств безопасного итератора с использованием данного итератораитераи локальной карты свойств индексаid. Индексы вidдолжны
Local property map
Адаптер карты свойств, который получает доступ к базовой карте свойств, чей тип ключа является локальной частьютипа ключадля локального подмножества ключей. Местные карты свойств обычно используются распределенными типами графов для свойств индекса вершины.
the type of the process group over which the global
keys are distributed.
GlobalKey:
The key_type of the local property map, which
must model the Global Descriptor concept. The process ID type of
the GlobalKey parameter must match the process ID type of the
ProcessGroup, and the local descriptor type of the GlobalKey
must be convertible to the key_type of the LocalMap.
LocalMap:
the type of the property map that will store values
for keys local to this processor. The value_type of this
property map will become the value_type of the local
property map. The local property map models the same property
map concepts as the LocalMap.
