Передача структурированных данных

РАСПРЕДЕЛЕННЫЕ ВЫЧИСЛЕНИЯ ЛЕКЦИЯ 8 ПЕРЕДАЧА СТРУКТУРИРОВАННЫХ ДАННЫХ Структурированные данные – это данные, состоящие из множества отдельных элементов, размещённых в рамках адресного пространства процесса. С точки зрения программиста, структурированные данные представляются как содержимое разных структур. К таким структурам, в частности, относятся: одно-, двух-, трёх- и более мерные массивы, переменные типа struct (в языках C, C++, C#), динамические сегменты и проч. Данные могут размещатся в таких структурах по-разному. Представление о том, как данные размещаются в этих структурах необходимо иметь для того, чтобы правильно организовывать их посылку из памяти процесса-отправителя, а также для того, чтобы правильно организовывать их приём и размещение в процессе-получателе. Классификация видов распределения структурированных данных в рамках одного процесса Рассмотрим классификацию по трём критериям: 1) Однородность элементов; 2) Однородность подструктур (блоков); 3) Распределённость подструктур в адресном пространстве процесса. В итоге получилась вот такая классификация (см. рис. 1): Структурированные данные Нераспределённые в адресном пространстве Однородные подструктуры Неоднородные подструктуры Однородные элементы 3 Неоднородные элементы 4 1 2 Распределённые в адресном пространстве Однородные подструктуры Однородные элементы 5 Неоднородные элементы 6 Неоднородные подструктуры Однородные элементы 7 Неоднородные элементы 8 Однородные элементы Неоднородные элементы Рис. 1. Классификация структурированных данных 1 В итоге получилось восемь конечных классов (видов) структурированных данных по трём ранее заявленным критериям. Проиллюстрируем наглядно различия между этими восьми видами диаграммами с примерами на рисунке (см. рис. 2). Сосредоточенные однородные элементы (однородные подструктуры) 1 int int int int int int int int int Сосредоточенные неоднородные элементы (однородные подструктуры) 2 float int float ch float int float ch Сосредоточенные однородные элементы (неоднородные подструктуры) 3 int int int int int int int int int Сосредоточенные неоднородные элементы (неоднородные подструктуры) 4 float ch int int ch float int float ch Распределённые однородные элементы (однородные подструктуры) 5 int int int int int int int int int Распределённые неоднородные элементы (однородные подструктуры) 6 float int float float ch int float ch Распределённые однородные элементы (неоднородные подструктуры) 7 int int int int int int int int Распределённые неоднородные элементы (неоднородные подструктуры) 8 float int float int ch float float int int Рис. 2. Диаграммы примеров распределения данных по ячейкам памяти для восьми видов структурированных данных. Элементы данных в примерах распределения имеют следующие типы: байтовый (ch – размером в 1 байт), целочисленный (int – пусть будет размером в 2 байта), с плавающей точкой (float – пусть будет размером в 3 байта). Элементы данных расположены по однобайтовым ячейкам памяти и сгруппированы по блокам (подструктурам). Подструктуры же на рис. 2 выделены цветными (жёлтой, зеленой, красной) полосками поверх элементов. Постановка задачи по передаче структурированных данных Рано или поздно, но перед разработчиком параллельных программ встаёт задача организации передачи структурированных данных. Рассмотрим эту задачу на примере простой двухточечной передачи средствами MPI. В простом случае передача состоит из посылки данных процессом от2 правителем с помощью функции MPI_Send и приёма данных процессом получателем с помощью функции MPI_Recv. Как мы помним, при вызове функции MPI_Send посылаемые данные указываются тремя параметрами: адресом в памяти откуда начинаются посылаемые данные, количеством передаваемых данных в единицах типа элементов и самим типом элементов посылаемых данных. При вызове функции MPI_Recv размещение принимаемых данных также указывается тремя параметрами: адресом в памяти откуда начинать записывать принимаемые данные, количеством принимаемых данных в единицах типа элементов, типом элементов принимаемых данных. В итоге встаёт вопрос: как использовать функции MPI_Send и MPI_Recv чтобы осуществить передачу структурированных данных любого из восьми обозначенных ранее видов? Распределение элементов данных в памяти процесса Для начала разберёмся откуда возникают в памяти процесса структурированные данные того или иного вида. То есть, почему они так или иначе структурированы и распределены. На рис. 3 показано распределение в памяти элементов двух- трёх- мерного массива, описанного в программе на языке C, и два примера размещения предназначаемых для передачи данных в двухмерном массиве. Рис. 3. Распределение в памяти элементов двух- трёх- мерного массива M, описанного в программе на языке C, и два примера размещения предназначаемых для передачи данных (ячейки с данными выделены) в двухмерном массиве Многомерные статические массивы, объявляемые и используемые в программах на языках C, C++ в памяти процесса располагаются линейно. В отличие 3 от Фортрана, старшинство индексов в языках C, C++ направлено справа-налево. То есть самый правый индекс x считается самым младшим, y старше, z ещё старше. На всякий случай заметим, что в Фортране старшинство индексов наоборот направлено слева-направо. Элементы многомерных массивов расположены друг за другом в порядке возрастания младшего индекса (в нашем случае это x). После размещения всех элементов строки многомерного массива (при y=0, z=0 и пр.) следом размещаются элементы строки, соответствующей следующему значению следующего по старшинству индекса (т.е. y=1, z=0 и пр.). Таким образом подряд будут размещены все элементы массива соответствующие z=0. Следом за ними будут размещены все элементы соответствующие z=1 и так далее. Теперь рассмотрим два случая, когда для обработки данных надо от одного процесса послать другому процессу не весь массив, а только его часть. Эта ситуация часто встречается в параллельном программировании, когда обработку данных одного массива распределяют по нескольким процессам или когда в один массив на одном процессе собирают результаты работы нескольких процессов. В примере а) показано как расположены данные в памяти в случае, если необходимо передать две строчки двухмерного массива, а в примере б) показано как расположены данные в случае передачи двух столбцов. С точки зрения классического программирования расположение данных по строчкам или по столбцам особого значения не имеет. Однако это принципиально для параллельного и распределённого программирования, поскольку в примере а) показаны сосредоточенные однородные элементы с однородными подструктурами (вид структурированных данных 1), а в примере б) показаны распределённые однородные элементы с однородными подструктурами (вид структурированных данных 5). Организовать передачу данных в примере a) довольно просто, так как: имеется начальный адрес расположения данных в памяти, элементы данных расположены сосредоточенно и состоят из одинаковых элементов. Организовать передачу данных в примере б) сложнее. Данные распределены в памяти и передать их можно: или частями, что неэффективно поскольку для каждой подструктуры надо вызывать пару функций MPI_Send и MPI_Recv, на что тратиться время и системные ресурсы, или сразу одной передачей. Как организуется передача распределённых по памяти данных рассмотрим далее в своё время. Способы передачи структурированных данных с сосредоточенными элементами Сосредоточенные однородные элементы Организовать передачу структурированных данных с сосредоточенными однородными элементами 1-го (однородные подструктуры) и 3-го видов (неоднородные подструктуры) довольно просто. Известен начальный адрес, тип элементов (он один для всех) и суммарный размер всех подструктур. Передача осуществляется оной посылкой и одним приёмом (см. рис. 4) 4 Посылка: MPI_Send(addr, size, MPI_INT, . . .) MPI_Recv(addr, size, MPI_INT, . . .) Рис. 4. Передача сосредоточенных однородных элементов данных Сосредоточенные неоднородные элементы Организовать передачу структурированных данных с сосредоточенными неоднородными элементами (см. рис. 5) 2-го (однородные подструктуры) и 4-го видов (неоднородные подструктуры) немного сложнее. Здесь также известен начальный адрес, но присутствуют разные типы элементов. Тем не менее, эти данные всё же можно выразить через элементы байтового типа (char – в терминах C). Для случая однородных подструктур, можно определить размер size одной такой подструктуры в элементах типа char, а полный размер данных, это size помноженное на количество этих подструктур. В случае неоднородных подструктур определяются размеры size1, size2 и пр. каждой такой подструктуры в элементах типа char, а полный размер определяется суммой размеров всех подструктур. Рис. 5. Сосредоточенные однородные элементы в однородных и неоднородных подструктурах данных 5 На рис. 6. показан пример описания и посылки сосредоточенных структурированных данных с неоднородными элементами и однородными подструктурами. Для хранения данных объявлен массив ST с восемью структурными ячейками, содержащими элементы типа float, int, char и float. Далее определяется и сохраняется в переменную size размер, в байтах, структуры tst (с помощью функции sizeof). struct tst{ float a; int b; char c; float d; }; tst ST[8]; int size=sizeof(tst); MPI_Send(ST, 8*size, MPI_CHAR, . . .); Рис. 6. показан пример описания и посылки сосредоточенных структурированных данных с неоднородными элементами и однородными подструктурами Способы передачи структурированных данных с распределёнными элементами Типы данных в MPI-программе Кроме основных типов данных языка программирования (у нас это C, C++) в MPI-программе имеются дополнительные типы так или иначе связанные с MPI. Таким образом типы данных в MPI-программе можно разделить на 4 группы: 1. типы данных языка программирования; 2. собственные типы данных MPI; 3. переопределяемые MPI типы данных; 4. типы данных, определяемые пользователем. К первой группе можно отнести уже отмеченные основные типы языка программирования, а также условно другие типы данных, не связанные напрямую с MPI. Ко второй группе относятся собственные типы MPI. В таблице 1 приведены примеры таких типов и даётся расшифровка их значения данных. Таблица 1. Идентификатор типа данных Значение Статус принятых данных. Этот тип описывает структуру, в которую заносится статус приёма, MPI_Status количество принятых данных, номер процесса 6 MPI_Comm MPI_Group MPI_Op MPI_Request MPI_Aint MPI_Datatype от которого приняты данные и номер тэга Идентификатор области связи. Тип переменной, в которой хранится идентификатор Идентификатор группы процессов. Тип переменной, в которой хранится идентификатор Идентификатор операции приведения Идентификатор неблокирующей процедуры (квитанции) Адрес памяти в терминах MPI Идентификатор типа данных. Переменная данного типа сама по своему значению является типом данных. Она, в частности, позволяет описывать типы, формат которых может создавать (конструировать) сам пользователь Более подробно об использовании типов MPI_Aint и MPI_Datatype будет сказано далее в своё время. К третьей группе относятся переопределяемые MPI типы основных типов языка программирования. Замечание: Данное переопределение необходимо для того, чтобы можно было предопределёнными константами указывать типы элементов данных в качестве параметров функций MPI. А также, чтобы обеспечить платформонезависимость, что особенно актуально, когда процессы MPI-программы выполняются одновременно на разных платформах. В таблице 2 приведены некоторые переопределяемые типы и предопределённые константы, которые их идентифицируют в программе. Таблица 2. Переопределяемые основные типы языка Предопределённые константы программирования int – целочисленный MPI_INT float – с плавающей точкой MPI_FLOAT char – символьный (байтовый) MPI_CHAR uchar – символьный (байтовый) беззнаковый MPI_UNSIGNED_CHAR double – с плавающей точкой двойной точноMPI_DOUBLE сти long – длинный целочисленный MPI_LONG long_double – длинный с плавающей точкой MPI_LONG_DOUBLE двойной точности short – короткий (половина целочисленного) MPI_SHORT 7 К четвёртой группе относятся пользовательские типы данных. И именно они нам пригодятся для организации передачи структурированных данных с распределёнными элементами. Передача каждой подструктуры отдельным сообщением Это самый простой, но эффективный способ. На рис. 7. показан пример передачи данных из двух столбцов двухмерного массива M размером 4x4 элемента с плавающей точкой из процесса I в процесс J. Рис. 7. Пример передачи данных отдельными сообщениями из процесса I в процесс J Столбцы массива расположены в памяти четырьмя подструктурами распределённых однородных элементов. В итоге каждая из четырёх подструктур передаётся отдельно. Передача данных структур с распределёнными элементами путём создания нового типа данных Идея заключается в том, что пользователем создаётся новый тип данных, который описывает всю совокупность структуры распределённых однородных элементов как единый элемент нового типа. После этого вся совокупность данных может быть передана за один раз. На рис. 8 показан несколько обобщённая схема расположения в памяти структурированных данных с распределёнными однородными элементами и однородными подструктурами (5-й вид структурированных данных). 8 Рис. 8. Обобщённая схема расположения в памяти структурированных данных с распределёнными однородными элементами и однородными подструктурами В ячейках памяти располагаются подструктуры однородных элементов некоторого исходного(старого) типа otype (от слова old type). Все подструктуры(блоки) имеют одинаковый размер blocklen в единицах otype. Как правило (правда, не всегда) в таких структурах расстояние между подструктурами тоже одинаковое. Обозначим его stride, измеряют его также в единицах otype. При этом расстояние между подструктурами принято измерять как расстояние между начальными элементами соседних подструктур. Зная всё это можно воспользоваться функцией MPI_Type_vector чтобы описать всю эту структура как элемент данных нового типа ntype. На рис. 9. Показан синтаксис двух функций. Это функция описания элемента нового типа данных MPI_Type_vector и функции регистрации нового типа в системе MPI_Type_commit. int MPI_Type_vector (int count, int blocklen, int stride, MPI_Datatype otype, MPI_Datatype *ntype); count – количество блоков (подструктур) данных blocklen – размер блока в элементах otype stride – расстояние между блоками в элементах otype otype – тип исходных элементов ntype – новый тип данных int MPI_Type_commit (MPI_Datatype *ntype); ntype – новый тип данных регистрируемый в системе Рис. 9. Синтаксис функции описания элемента нового типа данных MPI_Type_vector и функции регистрации нового типа в системе MPI_Type_commit На рис. 10 показано описание элемента данных нового типа на примере квадрата из элементов двухмерного массива M, а также примеры посылки и приёма одного элемента данных. Следует заметить, что в примерах посылка квадрата 9 данных происходит из центра массива, приём в несколько другое место (оно обозначено красным квадратным контуром). После использования, регистрацию нового типа данных в системе можно аннулировать функцией MPI_Type_free. Рис. 10. Синтаксис функции описания элемента нового типа данных MPI_Type_vector и функции регистрации нового типа в системе MPI_Type_commit Чтобы организовать передачу структурированных данных с распределёнными неоднородными элементами и однородными подструктурами (6-й вид структурированных данных), элемент нового типа также можно описать функцией MPI_Type_vector, только в качестве старого типа данных надо выбрать char, и через этот тип выразить размер подструктур и расстояние между ними. Чтобы организовать передачу структурированных данных с распределёнными элементами и неоднородными подструктурами (7-й вид - однородными элементами и 8-й вид неоднородными элементами), элемент нового типа описывается универсальной функцией MPI_Type_struct. Данная функция универсальна и позволяет описать элемент нового типа данных на основе структурированных данных любой конфигурации. На рис. 11 показано каким образом описывается самый общий случай структурированных данных на примере 8-го вида нашей классификации. Здесь в функции указываются в качестве параметров: количество блоков(подструктур) данных count, массив blocklens размеров блоков(подструктур) (т.е. размер каждой подструктуры описывается индивидуально в элементах удобного типах или универсального char) , массив указателей(адресов) addr смещений относительно некоторой базовой точки для каждой подструктуры, массив otypes исходного(старого) 10 типа элементов в которых были выражены их размеры в blocklens, а также указатель на переменную нового типа ntype. Рис. 11. Общий случай описания нового типа структурированных данных с помощью функции MPI_Type_struct Посмотрим пример использования функции MPI_Type_struct. Пусть имеется трёхмерный массив с однородными элементами (см. рис. 12). Пусть требуется описать новый элемент данных, представляющий собой призму (половину рассечённого по диагонали трёхмерного массива). Этот случай описывает структурированные данные 7-го вида. В схеме, показывающей как располагаются элементы призмы в памяти каждый элемент представляет собой строку. На рис. 13 приведён синтаксис функции преобразования адреса MPI_Aint из терминов языка программирования в формат MPI, а также программный пример описания элемента нового типа данных с вызовами функций двухточечных пересдач. В программном примере сначала заполняется массив исходных типов элементов oldt. Потом заполняется массив bll размеров подструктур, при это первая подструктура содержит NxN элементов, а каждая последующая на N элементов меньше. Потом происходит извлечение адресов начала подструктур, преобразование этих адресов в формат MPI и сохранение их в массиве disp. В качестве базовой точки можно выбрать адрес начала первой подструктуры и относительно его надо пересчитать все адреса. Созданный новый тип данных регистрируется в системе, после чего его можно использовать при передаче. 11 Рис. 12. Призма элементов данных в трёхмерном кубическом массиве A размером NxNxN (примере N=5) Функция преобразования адреса int MPI_Address(void *location, MPI_Aint *addr) location – адрес объекта в единицах языка C addr – адрес объекта в единицах MPI_Aint -----------------------------------------------------------------Пример программы (фрагменты) int a[N][N][N]; MPI_Datatype nt; // переменная нового типа данных ... for (i=0; i=0; i--) disp[i] = disp[i] - disp[0]; // пересчёт относительно базовой точки MPI_Type_struct(N, bll, disp, oldt, &nt); MPI_Type_commit(&nt); // регистрация нового типа в системе ... if (myrank==0) MPI_Send(a, 1, nt, 1, 0, MPI_COMM_WORLD); if (myrank==1) MPI_Recv(a, 1, nt, 0, 0, MPI_COMM_WORLD, &status); MPI_Type_free(&nt); // аннулирование нового типа в системе Рис. 13. Синтаксис функции MPI_Aint и программный пример описания элемента нового типа данных с вызовами функций двухточечных передач 12 Передача данных одним сообщением путём их предварительной упаковки перед посылкой и распаковки после приёма Под конец следует кратко упомянуть ещё один приём по передаче структурированных данных. В этом случае используются функции: MPI_Pack – упаковки данных перед их посылкой в процессе отправителе и MPI_Upack – распаковка данных после их приёма в процессе получателе. Синтаксис этих функций приведён на рис. 14. Рассчитать размер буфера можно с помощью функции MPI_Pack_size. int MPI_Pack(void *pack_data, int pack_count, MPI_Datatype pack_type, void *buffer, int buffer_size, int *position, MPI_Comm comm) pack_data – адрес пакуемых данных pack_count – количество пакуемых элементов pack_type – тип каждого из пакуемых элементов OUT buffer - адрес буфера, куда запаковываются данные buffer_size – размер буфера buffer I/O position – смещение (в байтах) до первой свободной позиции в buffer comm – идентификатор области связи int MPI_Upack(void *buffer, int buffer_size, int *position, void *upack_data, int upack_count, MPI_Datatype upack_type MPI_Comm comm) OUT buffer - адрес буфера, откуда берутся данные buffer_size – размер буфера buffer I/O position – смещение (в байтах) в buffer откуда начинается распаковка upack_data – адрес для распаковки upack_count – количество распаковываемых элементов upack_type – тип каждого из распаковываемых элементов comm – идентификатор области связи Рис. 14. Синтаксис функций упаковки и распаковки данных Подробнее про упаковку и распаковку данных можно прочитать здесь: https://www.opennet.ru/docs/RUS/mpi-1/node66.html 13