Как отправить и получить двоичное дерево, используя MPI?

Question

Я хочу отправить двоичное дерево из одного ядра в другое, используя некоторую функцию, такую ​​как MPI_Send ().Или есть какой-нибудь быстрый алгоритм для создания этой функции?

Используемая мной структура данных:

typedef struct BiNode{
    struct BiNode *lchi,*rchi;
    struct BiNode *parent;
    char *name;
}BiNode;

Это двоичное дерево имеет более 2000 листов.

Answer 1

Подробнее о сериализация .Дерево 2000 узлов на современных машинах и в сетях представляет собой довольно маленький фрагмент данных.Если средняя длина имени составляет дюжину байтов, вам необходимо передать несколько десятков килобайт (сегодня это не так уж и сложно).Типичная пропускная способность сети центра обработки данных составляет 100 Мбайт / с, а межпроцессное взаимодействие (с использованием, например, некоторых pipe (7) или unix (7) сокетов между ядрами одного и того же процессора) обычно как минимум в десять раз быстрее.См. Также http://norvig.com/21-days.html

Или есть ли какой-нибудь быстрый алгоритм для создания этой функции?

Вам, вероятно, нужен какой-то глубина-первый обход (и, вероятно, нет ничего быстрее).

Вы можете написать дерево в некотором текстовом формате - или в некотором текстовом протоколе - например, (в некоторых настраиваемых вариантах используется) JSON (или XML, YAML или S-выражения ).Затем воспользуйтесь преимуществами существующих библиотек JSON, таких как Jansson .Они способны кодировать и декодировать ваши данные (в некотором формате JSON) в динамически размещаемом строковом буфере.

Если производительность критична, рассмотрите возможность использования некоторого двоичного формата, такого как XDR или АСН-1 * * тысяча тридцать пять.Или просто сожмите кодировку JSON (или другую текстовую), используя некоторую существующую библиотеку сжатия (возможно, zlib ).

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

Answer 2

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

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

Так что у вас есть несколько вариантов, я думаю.

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

   • Это может не иметь смысла в контексте вашегоприложение, но это делает "дерево" очень легко для передачи.На этом этапе вы можете либо просто отправить большой массив байтов, либо создать типы данных MPI для описания каждой ячейки в массиве и отправить массив из 2000 таких элементов.

2. Повторно создайте дерево в другом процессе из исходных данных (будь то файл или что-то еще).

   • Вероятно, это не тот ответ, который вы искали, и он не поможет, если выВы сгенерировали эти данные из всего, что нетривиально в середине вашего приложения.

3. Используйте общую память POSIX.

   • Поскольку вы говорите "core »в описании вашего вопроса я предполагаю, что вы хотите передавать данные между процессами ОС на одной физической машине.Если это так, вы можете использовать разделяемую память, и вам вообще не нужно передавать сообщения.Просто откройте область общей памяти, присоедините к ней другой процесс и «пуф» всех данных будет доступен на другом конце.Пока вы разделяете всю память, на которую указывают эти указатели, я думаю, у вас все будет хорошо.