PARUS
PARUS Project Page / Manual / Algorithm graph format EngRussian
Contents
  1. Algorithm graph format
  2. Algorithm graph specification
  3. Specification of an individual vertex
  4. Edge specification
  5. Chunk specification

Algorithm graph format

Toolkit is aimed at dual graph representation. It is represented as a graph class and as a text file. Let us list text file format.

The file contains keywords — tags, graph fields names, and their values. It can also contain comments in C++ format. < and > will embrace notions, and { and } will contain words that can be repeated several times. ::= means definition of a notion.

Text representation consists of two parts — vertex block and edge block. 

<GRAPH_BEGIN>  
header "<header file name>"  
root "<root vertex file name>"  
tail "<tail vertex file name>"
num_nodes <number of vertices>
<nodes_block>
num_edges <number of edges>
<edges_block>
<GRAPH_END> 

header is a link to a file containing all variables, functions, and data type descriptions used by graph vertices. Names should not begin with MPI and px. Such names are reserved by the system and by MPI
root is a link to a file containing the code to be executed prior to the execution of the parallel part of the program. It is required to initialize the initial data for all processors. Filename is not required. You can set "" instead of e.g. "root.grf"
tail is a link to a file containing the code to be executed after the parallel part of the program is terminated
num_nodes is the number of vertices in a graph
num_edges is the number of edges in the graph
<nodes_block> all graph vertices

<nodes_block>::=<NODES_BEGIN>
{<node>}
<NODES_END>
<edges_block> all vertices

<edges_block>::=<EDGES_BEGIN>
{<edge>}
<EDGES_END>

Specification of an individual vertex

<node>::=
<NODE_BEGIN>
number <vertex number>
type <vertex type>
weight <vertex weight>
layer <layer number>
num_input_edges <number of edges coming into the vertex>
edges ( {<edge coming into the vertex>} )
num_output_edges <number of edges coming out of the vertex>
edges ( {<edge coming out of the vertex>} )
head "<vertex header file name>"
body "<vertex code file name>"
tail "<termination code file name>"
<NODE_END> 

number unique number of a vertex.We recommend not to use negative numbers - they can be reserved for the system part of the program
type integer; It used to map the graph to the computer monitor
weight integer; it characterizes vertex complexity in the number of sample operations
layer integer defining the layer of the vertex in the graph
num_input_edges number of edges coming into the vertex
num_output_edges is the number of edges coming out of the vertex
edges edges coming in and out of the vertex. The number of edges should be equal to num_input_edges and num_output_edges
head name of the file with variables visible only in the given vertex, and with code to be executed prior to receiving data from other vertices. If the file is not needed, the value should be ""
body name of the file with code to be executed after data from other nodes is received
tail name of the file with code to be executed after data is transferred

Edge specification

<edge>::=
<EDGE_BEGIN>
number <edge number>
weight <edge weight>
type <edge type>
num_var <number of variables passed via the edge>
num_send_nodes <number of sending vertices>
send_nodes ( {<number of the sending vertex>} )
num_recv_nodes <number of receiving vertices>
recv_nodes ( {<number of the receiving vertex>} )
<send_block>
<recieve_block>
<EDGE_END>

<send_block>::=
<SEND_BEGIN>
{<chunk>}
<SEND_END>

<recieve_block>::=
<RECIEVE_BEGIN>
{<chunk>}
<RECIEVE_END>

weight integer characterizing the amount of data transferred expressed in the number of sample messages
type edge type. Currently there is only one type - GRAPH_NONE, meaning passing data from one processor to another
num_var integer indicating the number of variables to be transferred via the edge. All variables are packed into an array and then passed to another vertex all at once; the receiving vertex performs unpacking of an array into separate variables
num_send_nodes indicate the number of vertices transferring or receiving data via the edge. In the current implementation due to the absence of multiple data transfers this field should be equal to 1
num_recv_nodes

Let us introduce the notion of chunk. Chunk is a continuous fragment of data in an array to be passed through the edge. Chunks contain information about transferred and received variables. One chunk is a fragment connected to one variable.

<chunk>::=
<CHUNK_BEGIN>
name "<variable name>"
type <variable type>
left_offset "<left address offset>"
right_offset "<right address offset>"
<CHUNK_END>

name variable name but not the address in the corresponding programming language
type variable type (complex types like struct can not be used here).The type is similar to GRAPH_INT, GRAPH_FLOAT, etc
left_offset offsets from the beginning of elements of a given type from the beginning, i.e. variable addresses. The segment between left_offset and right_offset is passed to another vertex. The values of these fields are integers in terms of programming language used to create parallel program
right_offset
Main page
Usage
Manual
External links
SourceForge resources
Project Info
Download page
Subversion repository
Project administrator
Project admin: Alexey Salnikov