Distributed data structures

Типичное вычисление с помощью параллельного BGL включает в себя несколько распределенных структур данных, работающих в этой области. Например, простой поиск по ширине включает в себя структуру данных распределенного графа, содержащую сам граф, распределенную очередь, которая управляет прохождением через граф, и распределенную карту свойств, которая отслеживает, какие вершины уже были посещены в рамках поиска.

Parallel BGL управляет этими распределенными структурами данных, позволяя каждой из структур данных присоединяться к самой группе процессов. Когда распределенная структура данных присоединяется к группе процессов, она получает свою собственную копию группы процессов, которая позволяет распределенной структуре данных общаться без столкновения с сообщениями от других распределенных структур данных. Когда группа процессов синхронизирована, все распределенные структуры данных, присоединенные к этой группе процессов, автоматически синхронизируются, так что все распределенные структуры данных в вычислении остаются синхронизированными.

Распределенная структура данных присоединяется к группе процессов путем создания копии группы процессов и передачи флагаattach_distributed_objectконструктору группы процессов. Пока эта копия группы процессов сохраняется, распределенная структура данных присоединяется к группе процессов. По этой причине большинство распределенных структур данных сохраняют копию группы процессов в качестве данных-членов, конструируя элемент сattach_distributed_object, например,

template<typename ProcessGroup>
struct distributed_data_structure
{
  explicit distributed_data_structure(const ProcessGroup& pg)
    : process_group(pg, boost::parallel::attach_distributed_object())
  { }
private:
  ProcessGroup process_group;
};

Asynchronous receives

Распределенные структуры данных в параллельном BGL могут "асинхронно" получать и обрабатывать сообщения до конца супершага BSP. Сообщения могут быть получены в любое время, когда процесс находится внутри операций группы процессов, и планирование приема сообщений полностью управляется группой процессов.

Распределенные структуры данных получают сообщения через "триггеры". Триггеры являются функциональными объектами, ответственными за обработку принятого сообщения. Каждый триггер регистрируется с помощью методатриггерагруппы процессов с использованием определенного тега сообщения (целое число) и типа данных, которые, как ожидается, будут содержаться в этом сообщении. Всякий раз, когда сообщение с этим тегом становится доступным, группа прогресса вызывает триггер с источником сообщения, тегом сообщения, данными, содержащимися в сообщении, и "контекст" сообщения.

Большинство триггеров не имеют значения возврата, хотя обычно триггеры отправляют сообщения обратно в исходный процесс. В некоторых случаях, когда цель триггера состоит в том, чтобы немедленно ответить значением, триггер должен быть зарегистрирован с помощью методаtrigger_with_replyи должен вернуть значение, которое будет отправлено обратно абоненту. Способtrigger_with_replyполезен только в сочетании с внедиапазонным обменом сообщениями.

Out-of-band messaging

Большинство сообщений, отправленных Parallel BGL, отправляются через обычные операции отправки, которые должны быть получены на следующем супершаге или, в некоторых случаях, получены с помощью триггера. Эти сообщения не чувствительны ко времени, поэтому они будут доставляться всякий раз, когда группа процессов обрабатывает их.

Однако некоторые сообщения требуют немедленных ответов. Например, если процесс должен определить текущее значение, связанное с вершиной, принадлежащей другому процессу, первый процесс должен отправить запрос второму процессу и заблокировать в ожидании ответа. Для таких сообщений группы процессов Parallel BGL обеспечивают механизм обмена сообщениями вне диапазона. Внеполосные сообщения передаются немедленно, с гораздо более высоким приоритетом, чем другие сообщения. Отправка внедиапазонных сообщений может быть связана с операцией приема, которая ждет, пока удаленный процесс не получит сообщение и не отправит свой ответ. Например, в следующем коде процесс отправляет сообщение, содержащее строкуимядля обработкивладельцас тегомmsg_get_descriptor_by_nameчерез внедиапазонное сообщение. Получатель этого сообщения немедленно доставит сообщение через триггер, который возвращает полученное значение -vertex_descriptor- которое будет передано обратно в процесс, который инициировал сообщение. Полное общение происходит немедленно, в рамках текущего супершага.

std::string name;
vertex_descriptor descriptor;
send_oob_with_reply(process_group, owner, msg_get_descriptor_by_name,
                    name, descriptor);

Process group constructors

ProcessGroup();

Конструирует новую группу процессов с иным пространством связи, чем любая другая группа процессов.

ProcessGroup(const ProcessGroup& pg, boost::parallel::attach_distributed_object);

Прикрепляет новую распределенную структуру данных к группе процессовpg. Полученная группа процессов может быть использована для связи в рамках новой распределенной структуры данных. Когда вновь построенная группа процессов в конечном итоге разрушается, распределенная структура данных отделяется от группы процессов.

Triggers

template<typename Type, typename Handler>
  void trigger(int tag, const Handler& handler);

Регистрирует триггер с данной группой процессов. При этом он будет следить за сообщениями с заданнымтегом. Когда такое сообщение будет доступно, оно будет принято в значение типа.Тип, и объект функцииобработчикбудут вызываться с четырьмя параметрами:

source

The rank of the source process (an int)

tag

The tag used to send the message (also an int)

data:

The data transmitted with the message. The data will have the type specified when the trigger was registered.

context:

The context in which the trigger is executed. This will be a value of type trigger_receive_context, which stages whether the trigger is being executed during synchronization, asynchronously in response to an "early" receive (often to free up communication buffers), or in response to an "out-of-band" message.

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

template<typename Type, typename Handler>
  void trigger_with_reply(int tag, const Handler& handler);

Подобнотриггерметод регистрирует триггер с заданной группой процессов. При этом он будет следить за сообщениями с заданнымтегом. Когда такое сообщение будет доступно, оно будет принято в значение типаТипиобработчикбудет вызываться, как и при обычном триггере. Однако триггер, зарегистрированный вtrigger_with_reply, должен вернуть значение, которое будет немедленно отправлено обратно в процесс, который инициировал отправку, приводящую к этому триггеру. Таким образом,trigger_with_replyследует использовать только для сообщений, требующих немедленного ответа. Эти триггеры могут быть вызваны только через неполосные отправители, которые ждут ответа, черезsend_oob_with_reply. Существует такжепростой триггерный интерфейсдля определения триггеров в обычных случаях.

trigger_receive_context trigger_context() const;

Устраняет текущий контекст группы процессов в отношении вызова триггеров. Когдаtrc_none, группа процессов в настоящее время не вызывает никаких триггеров. В противном случае это значение описывает, в каком контексте в настоящее время используется исполняющий триггер.

Helper operations

void poll();

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

ProcessGroup base() const;

Получает группу процессов "base" для этой группы процессов, которая является копией основной группы процессов, которая не ссылается на какую-либо конкретную распределенную структуру данных.

Process query

int process_id(const ProcessGroup& pg);

Получает идентификатор (или "rank") процесса вызова в группе процесса. Идентификаторы процессов представляют собой значения в диапазоне [0,num_processs (pg)), которые однозначно идентифицируют процесс. Идентификаторы процессов могут использоваться для инициирования связи с другим процессом.

int num_processes(const ProcessGroup& pg);

Возвращает количество процессов в группе процессов.

Message transmission

template<typename T>
  void send(const ProcessGroup& pg, int dest, int tag, const T& value);

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

Любой тип значения может быть передан черезотправить, если он обеспечивает соответствующую функциональность, которая должна быть сериализована с помощью Boost. Сериализация библиотеки.

template<typename T>
  void receive(const ProcessGroup& pg, int source, int tag, T& value);

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

optional<std::pair<int, int> > probe(const ProcessGroup& pg);

Определяет, доступно ли сообщение. Операция зонда проверяет любые сообщения, которые были отправлены на предыдущем супершаге, но еще не были получены. Если такое сообщение существует,зондвозвращает пару (источник, тег), описывающую сообщение. В противном случаезондвернет пустоеускорение:: необязательно.

Типичное использованиезондасостоит в том, чтобы постоянно исследовать сообщения в начале супершага, получая и обрабатывая эти сообщения, пока не останется сообщений.

Synchronization

void synchronize(const ProcessGroup& pg);

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

Out-of-band communication

template<typename T>
  void send_oob(const ProcessGroup& pg, int dest, int tag, const T& value);

Отправляет и внеполосное сообщение. Эта внедиапазонная операция отправки действует как обычная операцияотправки, за исключением того, что внедиапазонные сообщения доставляются немедленно по высокоприоритетному каналу.

template<typename T, typename U>
  void
  send_oob_with_reply(const ProcessGroup& pg, int dest, int
                      tag, const T& send_value, U& receive_value);

Отправляет внеполосное сообщение и ждет ответа. Функцияsend_oob_with_replyможет быть вызвана только тегами сообщений, которые соответствуют триггерам, зарегистрированным сtrigger_with_reply. Эта операция отправит сообщение немедленно (через высокоприоритетный, внедиапазонный канал), затем подождите, пока удаленный процесс отправит ответ. Данные из ответа хранятся вget_value.

template<typename T>
  void receive_oob(const ProcessGroup& pg, int source, int tag, T& value);

Получает внеполосное сообщение с даннымисточникомитегом. Как и в случае обычной операцииприема, вызовприема_oobявляется ошибкой, если отсутствует сообщение, соответствующее источнику и тегу. Эта процедура используется редко; в большинстве случаев используйтеsend_oob_with_replyдля немедленного отправления с ответом.

Авторское право (C) 2007 Дуглас Грегор

Авторское право (C) 2007 Маттиас Тройер