Передача сообщений Произвольные графы объектов?

Question

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

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

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

Редактировать: Если нет простого способа передать сложное состояние, то как обычно используется передача сообщений? Мне кажется, что все, что связано с копированием данных по сети, требует грубого параллелизма, но грубый параллелизм обычно требует прохождения сложного состояния, так что большая работа может быть выполнена за один рабочий блок.

Answer 1

Я занимаюсь программированием MPI, но я не знаю ни одного типичного способа передачи сложного состояния (как вы его описываете) между процессами. Вот как я думал о вашей проблеме, она, вероятно, соответствует вашему собственному мышлению ...

Я предполагаю, что ваши графы сложных объектов представлены в памяти блоками данных и указателями на другие блоки данных - обычная разновидность реализации графа. Как лучше всего переместить один из этих COG (чтобы обозначить аббревиатуру) из адресного пространства одного процесса в адресное пространство другого? Поскольку указатель является адресом памяти, указатель в одном адресном пространстве бесполезен в другом адресном пространстве, поэтому вам придется перевести его в некоторую нейтральную форму для транспорта (я думаю?).

Следовательно, чтобы отправить COG, его необходимо преобразовать в какую-либо форму, из которой принимающий процесс может построить в своем собственном адресном пространстве локальную версию графа с указателями, указывающими на адреса локальной памяти. Вы когда-нибудь записывали эти файлы в файл? Если это так, у вас уже есть форма, в которой он может быть транспортирован. Я не хочу предлагать это, но вы могли бы даже использовать файлы для связи между процессами - и это может быть проще в обработке, чем комбинация D и MPI. Ваш выбор!

Если у вас нет формы файла для COG, можете ли вы легко представить их в виде матриц или списков смежности? Другими словами, разработать свое собственное представительство для транспорта?

Я буду очень удивлен (но с удовольствием узнаю), сможете ли вы передать COG между процессами, не преобразовывая его из основанного на указателе, в более статичную структуру, такую ​​как массивы или записи.

Редактировать, в ответ на редактирование ОП. MPI предоставляет простые способы передачи сложного состояния при условии, что сложное состояние представлено в виде значений, а не указателей. Вы можете передавать сложное состояние как во встроенном, так и в настраиваемом типе данных MPI; как показывает один из других ответов, они гибки и способны. Если наша программа не сохраняет сложное состояние в форме, которую могут обрабатывать пользовательские типы данных MPI, вам придется написать функции для упаковки / распаковки в удобное для сообщений представление. Если вы можете сделать это, то ваши сообщения будут выглядеть (для большинства целей) как вызовы функций.

Что касается проблем, связанных со сложным состоянием и зернистостью параллелизма, я не уверен, что полностью следую за вами. Мы (включаем себя в это широкое обобщение, если хотите или нет) обычно прибегаем к программированию MPI, потому что мы не можем получить достаточную производительность от одного процессора, мы знаем, что заплатим штраф в отношении вычислений, задержанных ожиданием что касается коммуникации, мы прилагаем все усилия, чтобы минимизировать это наказание, но, в конце концов, мы принимаем наказание в качестве стоимости распараллеливания. Конечно, некоторые задания слишком малы или слишком коротки, чтобы извлечь выгоду из распараллеливания, но многое из того, что мы (параллельные вычисления) делаем, слишком велико и слишком долго, чтобы избежать распараллеливания

Answer 2

Я не уверен, что правильно понял вопрос, поэтому прости меня, если мой ответ выключен. Из того, что я понимаю, вы хотите отправлять не-POD типы данных с использованием MPI.

Библиотека, которая может сделать это: Boost.MPI . Он использует библиотеку сериализации для отправки даже очень сложных структур данных. Однако есть одна загвоздка: вам придется предоставить код для сериализации данных самостоятельно, если вы используете сложные структуры, о которых Boost.Serialize еще не знает.

Я считаю, что передача сообщений обычно используется для передачи типов данных POD.

Мне не разрешено публиковать больше ссылок, поэтому я хотел бы добавить следующее:

Объяснение POD: www.fnal.gov/docs/working-groups/fpcltf/Pkg/ISOcxx/doc/POD.html

Библиотека сериализации: www.boost.org/libs/serialization/doc

Answer 3

Вы можете делать изумительные вещи с помощью пользовательских типов данных MPI. В настоящее время я работаю над проектом, в котором несколько процессов MPI отслеживают частицы в части виртуального пространства, и когда частицы переходят из одной территории процесса в другую, их данные (позиция / скорость / размер / и т. Д.) Должны быть отправлено по сети.

Способ, которым я достиг этого, следующий:

1) Все процессы имеют общий тип данных MPI Struct для отдельной частицы, которая содержит все соответствующие атрибуты и их смещение в памяти по сравнению с базовым адресом объекта частицы.

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

3) На принимающей стороне все немного сложнее. Процесс получения сначала вставляет «пустые» частицы в свою собственную структуру данных: «пустой» означает, что все атрибуты, которые будут получены от другого процесса, инициализируются к некоторому значению по умолчанию. Адреса памяти недавно вставленных частиц записываются, и по этим адресам создается тип данных, подобный типу отправителя. Прием сообщения отправителя как одного объекта этого типа автоматически распакует все данные во все нужные места, опять же, безопасным для типа способом.

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

Если приведенное выше описание не понятно, я могу опубликовать код C ++, который его реализует.

Answer 4

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

Я не знаю вашей проблемы, но, возможно, можете взглянуть на ARMCI, если вы управляете памятью вручную.