PARUS Project Page

Страница проекта ПАРУС / Руководство / Формат файла графа

Содержание

Формат текстового представления графа алгоритма
Спецификация графа алгоритма
Спецификация узла графа алгоритма
Спецификация рёбер графа алгоритма
Спецификация чанка

Формат текстового представления файла графа алгоритма

Инструментальная система рассчитана на двоякое представление графа алгоритма. Представление в виде класса Graph и в виде текстового файла. Приведём, формат текстового файла.
Файл графа алгоритма содержит ключевые слова, которые являются обрамляющими тегами, именами полей графа, а также их значениями. В файле графа алгоритма также могут встречаться комментарии в формате C++. В дальнейшем между '<' и '>' скобками будут содержаться понятия, а всё что содержится между '{' и '}' может быть повторено несколько раз. Символ ::= означает расшифровку понятия.
Текстовое представление графа алгоритма состоит из 2-х блоков, блока узлов и блока рёбер.

<GRAPH_BEGIN>

header "<имя файла заголовка>"
root "<имя файла с корневым узлом графа>"
tail "<имя файла с заключительным кодом>"
num_nodes <число вершин>
<nodes_block>
num_edges <число рёбер>
<edges_block>

<GRAPH_END>

header	ссылка на файл, содержащий все переменные, функции, описания типов данных, которые используются узлами графа алгоритма. Следует избегать пользоваться именами, начинающимися с MPI или px. Данные имена зарезервированы системой и MPI
root	ссылка на файл, в котором находится код, который выполнится в первую очередь на всех процессорах одновременно и одинаково. Это необходимо обычно для проведения начальной инициализации данных, которые затем будут использоваться всеми узлами на всех процессорах. Имя файла в этом поле указывать не обязательно. Можно указать только "" вместо, например "root.grf"
tail	ссылка на файл, в котором находится код, который необходимо выполнить после работы параллельной части программы обычно содержит операции по освобождению памяти и закрытию всё ещё открытых файлов
num_nodes	содержит число узлов в графе
num_edges	содержит число рёбер в графе
<nodes_block>	узлы графа алгоритма <nodes_block>::=<NODES_BEGIN> {<node>} <NODES_END>
<edges_block>	рёбра графа алгоритма <edges_block>::=<EDGES_BEGIN> {<edge>} <EDGES_END>

Cпецификация узла графа алгоритма

<node>::=
<NODE_BEGIN>

number <номер узла графа алгоритма>
type <тип узла графа алгоритма>
weight <вес узла графа алгоритма>
layer <номер уровня узла графа алгоритма>
num_input_edges <число входящих рёбер>
edges ( {<номер входящего ребра>} )
num_output_edges <число исходящих рёбер>
edges ( {<номер исходящего ребра>} )
head "<имя файла заголовка узла>"
body "<имя файла с кодом узла>"
tail "<имя файла с заключительным кодом>"

<NODE_END>

number	уникальный номер узла в пределах всего графа. Номер узла 0 зарезервирован под корневой узел, а -1 под демон, который управляет ресурсами программы и ресурсами многопроцессорной вычислительной системы. Настоятельно не рекомендуется использовать отрицательные номера, они могут быть зарезервированы для дальнейшего расширения системной части программы
type	целочисленное значение в данный момент не используется, но в будущем возможно использование для отображения графа, и ручного выполнения этапа перестройки графа алгоритма
weight	целочисленное значение, характеризующее сложность узла должно быть выражено в числе эталонных операций
layer	целочисленное значение, соответствующее уровню или ярусу графа алгоритма
num_input_edges	число рёбер входящих в данный узел
num_output_edges	число рёбер выходящих из данного узла
edges	номера рёбер входящих или выходящих из данного узла. Их число должно точно соответствовать числу входящих или выходящих рёбер
head	содержит имя файла с переменными, видимыми только в данном узле, а также с кодом, который необходимо выполнить до приёма данных от других узлов. Если данный файл не нужен, то в данном месте можно указать "", что будет означать отсутствие данного файла
body	содержит имя файла с кодом, который необходимо выполнить, получив данные от других узлов графа алгоритма
tail	содержит имя файла с кодом, который выполнится после процедуры упаковки данных для передачи их другому узлу графа алгоритма

Спецификация рёбер графа алгоритма

number <номер ребра графа алгоритма>
weight <вес ребра графа алгоритма>
type <тип ребра графа алгоритма>
num_var <число передаваемых переменных>
num_send_nodes <число посылающих узлов графа>
send_nodes ( {<номер посылающего узла>} )
num_recv_nodes <число принимающих узлов графа>
recv_nodes ( {<номер принимающего узла>} )
<send_block>
<recieve_block>

<EDGE_END>

<send_block>::=
<SEND_BEGIN>

{<chunk>}

<SEND_END>

<recieve_block>::=
<RECIEVE_BEGIN>

{<chunk>}

<RECIEVE_END>

weight	целочисленное значение, характеризующее объём передаваемых данных, выраженное в предположительном числе байт которое придётся передать другому узлу графа алгоритма через это ребро
type	задаёт тип ребра в данный момент доступно только одно значение GRAPH_NONE, которое предусматривает только передачу данных от одного процессора к единственному другому
num_var	целочисленное значение, показывающее, количество переменных, которое будет передано через данное ребро. Все переменные упаковываются в специальный массив, а потом передаются другому узлу, инициализируя одну пересылку, при этом на другом конце происходит распаковка из аналогичного массива в собственные переменные
num_send_nodes	задают число узлов, которые принимают или отправляют данные через данное ребро. В текущей реализации, в виду отсутствия реализации коллективной передачи данных, данные поля должны быть обязательно установлены в единицу
num_recv_nodes

Введём понятие — чанк (chunk). Чанк обозначает непрерывный фрагмент данных в массиве. Данный фрагмент данных будет передан через текущее ребро в другой узел графа алгоритма.
Чанки содержат информацию о передаваемых и принимаемых переменных. Один чанк — фрагмент данных связанный только с одной переменной или только с одним массивом.

name "<имя переменной>"
type <тип переменной>
left_offset "<левая граница>"
right_offset "<правая граница>"

<CHUNK_END>

name	содержит строку, являющуюся именем передаваемой переменной, но не её адресом в соответствующем языке программирования. Имена переменной или массива с принимающей стороны и с передающей стороны могут отличаться друг от друга
type	означает элементарный тип передаваемой переменной. Все указанные здесь типы должны начинаться с префикса GRAPH (Сложные типы, например struct указывать нельзя.) Это должен быть тип аналогичный GRAPH_INT, GRAPH_FLOAT
left_offset	задают смещение в элементах данного типа относительно начала, т.е. адреса переменной. Отрезок данных между left_offset и right_offset передаётся другому узлу графа алгоритма. Значения данных полей - целочисленные выражения в терминах того языка программирования, на котором предполагается последующее получение параллельной программы
right_offset