Define input data structures.

[joaquinffernandez]

We must define the input data structures used to generate the sb partitioner graphs.

Probably something of the form:

$[1, \cdots, N] \rightarrow \{ \text{id, exp} \}$

Where interval is an SBG interval (it could be a unique interval), the id of the variable involved and the expression which is a linear function.

The input will probably be a list or set of expressions of the from defined above.
Note We must take into account that besides the id and the exp we will have to add the cost functions.

[joaquinffernandez]

If we define the occurrence of a variable in a given expression as:

$\text{Var} : \{$
$\text{id} : \text{string}$
$\text{exp} : (a,b)$ where $a, b \in \mathbb{N}^0$ and they represent a constant and multiplication factor in the expression: $a * i + b$
$\text{def} : \{n_1,\dots,n_k\}$ where $n_i$ is the id of a set node where the variable is computed, i.e, it appears on the left hand side of the equation.
$\}$

Then, and individual node representing the calculation unit in the parallel model representation could be defined as:
$\text{Node} : \{$
$\text{id} : \text{string}$
$\text{interval} : [1,\dots,M]$
$\text{lhs} : \{ L_1, \dots, L_k \}$ where $L_i$ has type $\text{Var}$
$\text{rhs} : \{ R_1, \dots, R_g \}$ where $R_i$ has type $\text{Var}$
$\}$

And finally we could define:
$\text{Nodes} : \{ I_1, \dots, I_m\}$ with $I_j$ of type $\text{Node}$

With this given structure, the algorithm to construct the edges of the partition graph could be defined as:

• $\forall I_j \in \text{Nodes}$ do
  • $\forall R_i \in I_j.rhs$ do
    • $\text{IM}(R_i) \leftarrow$ Build the image set for the variable expression of $R_i$.
    • $\forall D_k \in R_i.defs$ do
      • Let $I_s$ $\leftarrow$ The corresponding node for $D_k$ node id in $\text{Nodes}$
      • Let $L_w$ $\leftarrow$ The left hand side variable that matches $R_i$ in the input LHS set.
      • $\text{IM}(L_w) \leftarrow$ Build the image set for the variable expression of $L_w$.
      • Compute $D \leftarrow \text{IM}(R_i) \cap \text{IM}(L_w)$
      • If $D \neq \emptyset$ it means that the node $I_s$ computes a variable (or part of a variable) $L_w$ that should be communicated to $I_j$. In this case:
        • If $check\_1\_N\_rel(I_s, L_w)$:
          • Build 1 $\rightarrow$ N edge
        • If $check\_1\_N\_rel(I_j, R_i)$:
          • Build N $\rightarrow$ 1 edge
        • Otherwise we are in a N - M relationship:
          • Build an Edge set between $(I_j, I_s)$ with cardinality $\#D$

where:
$check\_1\_N\_rel(Node, Exp):$
return $\#(Node.interval) > 1$ and $Exp[0] == 0$

This means that there is a constant expression defined in a non scalar node.

Build an 1 $\rightarrow$ N edge example, given these two nodes:

for i in 1:2 loop  // Node 1
      when 1 then
        sendPartTotal[i] := partTotal[i];
        partTotal[i] := 0;
      end when;
    end for;

for i in 1:N loop // Node 2
      when 2 then
        partTotal[1]:= partTotal[1] + 10;
    end when;		
    end for;

The first node defines $partTotal[i]$ for the interval $\{1,2\}$ and the second one defines $partTotal[1]$ in the interval $\{1, \cdots,N/2\}$ so in the algorithm above, the first $check\_1\_N\_rel(I_s, L_w)$ will return $True$ because in this case we have an intersection between
$partTotal[i]$ in range $\{1,2\}$ from the first node and $partTotal[1]$ in range $\{1,\cdots,N/2\}$ in the second node that is equal to $\{1\}$ and we have a 1 to N relation.

This means that each time $partTotal[1]$ is updated in the second node it must be communicated to first node. So in this case, the edge should be:

$1 \leftarrow \{1:N/2\} \rightarrow i$

Where the left hand side of the map is the receiver of the new value and the right hand side of the map are the senders. In the same way we can define the opposite check for N to 1 relations.

The set nodes should be constructed directly from the $\text{Node}$ structure:

• $\forall N \in \text{Nodes}$ do
• Build $V \leftarrow$ from $N.id$ and $N.interval$ where interval defines the Set vertex basically.

We should probably define an operator $IM$ to construct a linear map from a given expression and a domain interval, applies the map and returns the image through the map.

[joaquinffernandez]

From this Modelica example:

model test
Real x[10];

equation
der(x[1]) = x[2];  // This will be computing node 1 with interval [1,1]
for i in 2:N-1 loop
  der(x[i]) = x[i-1] + x[i+1]; // This will be computing node 1 with interval [2,N]
end for;
der(x[N]) = x[N-1];
end test;

We can define:

For the lhs of computing node 1
$V_1 = \{$
$\text{id} : x$
$\text{exp} = (0,1) \rightarrow$ to form the expression $0*i+1$ that corresponds to $x[1]$
$\text{defs} = \{\}$
$\}$

For the rhs of computing node 1
$V_2 = \{$
$\text{id} : x$
$\text{exp} = (0,2) \rightarrow$ to form the expression $0*i+2$ that corresponds to $x[2]$
$\text{defs} = \{n_1, n_2\}$
$\}$

For the lhs of computing node 2
$V_3 = \{$
$\text{id} : x$
$\text{exp} = (1,0) \rightarrow$ to form the expression $1*i+0$ that corresponds to $x[i]$
$\text{defs} = \{\}$
$\}$

For the rhs of computing node 2
$V_4 = \{$
$\text{id} : x$
$\text{exp} = (1,-1) \rightarrow$ to form the expression $1*i-1$ that corresponds to $x[i-1]$
$\text{defs} = \{n_1, n_2\}$
$\}$

$V_5 = \{$
$\text{id} : x$
$\text{exp} = (1,1) \rightarrow$ to form the expression $1*i+1$ that corresponds to $x[i+1]$
$\text{defs} = \{n_1, n_2\}$
$\}$

The nodes can be represented as:

$N_1 = \{$
$\text{id} : n_1$
$\text{interval} : [1,1]$
$\text{lhs} : \{V_1\}$
$\text{rhs} : \{V_2\}$
$\}$

$N_2 = \{$
$\text{id} : n_2$
$\text{interval} : [2,N]$
$\text{lhs} : \{V_3\}$
$\text{rhs} : \{V_4, V_5\}$
$\}$

[joaquinffernandez]

model test
Real x[10];
Real y[10];

equation
for i in 1:N/2 loop
  der(y[i]) = 10; 
end for;

for i in N/2+1:N loop
  der(y[i]) = 10;
end for;

  der(x[1]) = 1; 

for i in 2:N loop
  der(x[i]) = y[i]; 
end for;
end test;

[joaquinffernandez]

Simple SBG graph representation, let's assume we have the expanded following graph:

This graph can be represented in SBG by:

Where the left hand side nodes are compacted to form the set-vertex $\{1,5\}$, the right hand side nodes form the set-vertex $\{6,10\}$ and there's only one edge-set representing the 5 edges in the original graph.
The relation is represented by 2 linear functions that works in the following way:

• The edge has a domain $\{11,15\}$ which is the same for the two linear functions.
• There's a map that goes from the domain of the edge-set to the left hand side set-vertex: $\{11,15\} \rightarrow 1*x -10$, so in this case, if we apply the map for each component we get: $\{ (11,1), \dots, (15,5)\}$ and we obtain original left hand side graph vertices.
• There's a map that goes from the domain of the edge-set to the right hand side set-vertex: $\{11,15\} \rightarrow 1*x -5$, so in this case, if we apply the map for each component we get: $\{ (11,6), \dots, (15,10)\}$ and we obtain original right hand side graph vertices.

This way we can obtain a compact representation of the original graph, and given that we can perform the map operations without expanding the sets, we can keep the compact representation in all the operations.

[joaquinffernandez]

Simple example application:

model test
constant Integer N = 10;
Real x[N];

equation
der(x[1]) = 100;  // This will be computing node 1 with interval [1,1]
for i in 2:N loop
  der(x[i]) = x[i] + x[i-1]; // This will be computing node 1 with interval [2,N]
end for;
end test;

The input for this model could be:
For the lhs of computing node 1
$V_1 = \{$
$\text{id} : x$
$\text{exp} = (0,1) \rightarrow$ to form the expression $0*i+1$ that corresponds to $x[1]$
$\text{defs} = \{\}$
$\}$

For the lhs of computing node 2
$V_2 = \{$
$\text{id} : x$
$\text{exp} = (1,0) \rightarrow$ to form the expression $1\times i+0$ that corresponds to $x[i]$
$\text{defs} = \{\}$
$\}$

For the rhs of computing node 2
$V_3 = \{$
$\text{id} : x$
$\text{exp} = (1,-1) \rightarrow$ to form the expression $1\times i-1$ that corresponds to $x[i-1]$
$\text{defs} = \{n_1, n_2\}$
$\}$

$V_4 = \{$
$\text{id} : x$
$\text{exp} = (1,0) \rightarrow$ to form the expression $1\times i+1$ that corresponds to $x[i]$
$\text{defs} = \{n_1, n_2\}$
$\}$

The nodes can be represented as:

$N_1 = \{$
$\text{id} : n_1$
$\text{interval} : [1,1]$
$\text{lhs} : \{V_1\}$
$\text{rhs} : \{\}$ Constant expression so RHS is empty.
$\}$

$N_2 = \{$
$\text{id} : n_2$
$\text{interval} : [2,N]$
$\text{lhs} : \{V_2\}$
$\text{rhs} : \{V_3, V_4\}$
$\}$

$Nodes = \{N_1, N_2\}$

Algorithm application from $Nodes$ input:

• Construct 2 set vertices from the corresponding node intervals: $\{1\}$ and $\{2,\dots,N\}$.

Now we apply the algorithm defined above

Assume we have a $\text{BuildPWL}$ operator that given a $\text{Var.exp}$ and an interval as domain it returns a piecewise linear map as defined here.

• For $N_1$ we have that $N_1.rhs$ is $\emptyset$.
• Now, for $N_2$ we have: $N_2.rhs = \{V_3, V_4\}$:
  • For $V_3$:
    • Build $P_1$ from $V_3.exp = (1,-1)$ and interval $\{2,\dots,N\}$.
    • Compute the image set $A$ for $P_1$ which is equal to: $\{1,\dots, N-1\}$
    • Now iterate over $V_3.def = \{n_1, n_2\}$:
      • First, for $n_1$:
        • Get $V_1$ which is the left hand side variable defined in $n_1$.
        • Build $P_2$ from $V_1.exp = (0,1)$ and interval $\{1\}$.
        • Compute the image set $B$ for $P_2$ which is equal to: $\{1\}$
        • Compute $C = A \cap B$ which is equal to: $\{1\}$
        • Given that $C \neq \emptyset$ we can build and edge between $N_2$ and $N_1$:
          • Using the cardinality of $C$ create a new set for the set edge, let's say $\{N+1\}$
          • Create the set edge maps:
          • For the first map: $\{N+1\} \rightarrow (1\times x - (N+1) + 2)$
          • For the second map: $\{N+1\} \rightarrow (1)$
      • Now, for $n_2$:
        • Get $V_2$ which is the left hand side variable defined in $n_2$.
        • Build $P_3$ from $V_2.exp = (1,0)$ and interval $\{2,\dots,N\}$.
        • Compute the image set $B$ for $P_3$ which is equal to: $\{2,\dots,N\}$
        • Compute $C = A \cap B$ which is equal to: $\{2,\dots,N-1\}$
        • Given that $C \neq \emptyset$ we can build and edge between $N_2$ and $N_2$:
          • Using the cardinality of $C$ create a new set for the set edge, let's say $\{N+2, \dots,2\times N-1\}$
          • Create the set edge maps:
            • For the first map: $\{N+2,\dots,2\times N-1\} \rightarrow (1\times x - (N+2) + 2)$
            • For the second map: $\{N+2,\dots,2\times N-1\} \rightarrow (1\times x - (N+2) + 3)$

After this iteration the graph should look like:

Then, the same has to be done for $V_4$.

[joaquinffernandez]

Build edge-set maps
If the lhs variable of the node is constant, i.e. the factor of the expression involved is zero, then we just return that constant. Otherwise, we must compute the new linear map as:
$\text{Var.exp} - D_{offset} + V_{offset}$

Where $\text{Var.exp}$ is the lhs variable expression of the node, $D_{offset}$ is the domain offset of the edge, i.e. the minimum element of the edge set domain and $V_{offset}$ is the variable offset that is obtained as:

• Get the pre-image of the intersection set for the edge through the PWL map generated for the right hand side expression.
• Get the image of the left hand side expression from the domain set obtained in the previous step.
• Get the minimum element of the image domain set.