next up previous
Next: Experimental results Up: Reduced Set of RSGs Previous: Graph pruning

Graph union

Two compatible graphs $ rsg_1$ and $ rsg_2$, (COMPATIBLE $ (rsg_1, rsg_2) =
1$), can be fused in a single graph, $ rsg$, which captures the data structure information represented by the two original graphs. This union of graphs is carried out by the JOIN $ (rsg_1, rsg_2) = rsg$ function which builds the new graph, $ rsg$, from the original ones, $ rsg_1$ and $ rsg_2$. This function does not modify the pvars set, $ P$, nor the selectors set, $ S$. On the contrary, the nodes set, $ N$, and link sets, $ PL$ and $ NL$, should be updated.

In particular, some of the nodes of $ rsg_1$ and $ rsg_2$ are going to be summarized if they are compatible. Now, using the function MERGE_NODES described in Sect. 3.2 we can describe the sets $ N$, $ PL$, and $ NL$ of the new RSG, resulting from the union of $ rsg_1$ and $ rsg_2$:

$ \bullet$ The set of nodes, $ N$, for the new graph, $ rsg$, comprises three subsets: the non-compatible nodes from $ rsg_1$, the non-compatible nodes from $ rsg_2$, and the nodes resulting from the union of compatible nodes (MERGE_NODES):

$ N(rsg)$ = $ \{n_i \in N(rsg_1) \vert \nexists n_j \in N(rsg_2),$ C_NODES $ (n_i,n_j)=1)\} ~ \cup $ $ \{n_i \in N(rsg_2) \vert \nexists n_j
\in N(rsg_1),$ C_NODES $ (n_i,n_j)=1)\} ~ \cup $ $ \{n =$MERGE_NODES $ (n_i, n_j)$, $\forall n_i \in N(rsg_1), ~ \forall n_j
\in N(rsg_2) \vert (\text{\tt C\_NODES}(n_i, n_j)=1)\}$

Therefore, we can define a MAP$ (n_i)$, $ n_i \in rsg_1$, function which points out which node of the new graph $ rsg$ is now representing a certain node of the $ rsg_1$:

   MAP$ (n_i)= \left\{\begin{array}{l}
n \in N(rsg) \text{ if }
\exists n_j \in N(rsg_...
...NODES}(n_i, n_j) = n) \\
\par n_i \in N(rsg) \text{ o.c. }

The map function for $ rsg_2$ nodes is similarly defined. By using this MAP function it is easy to describe the new $ PL(rsg)$ and $ NL(rsg)$ sets.

$ \bullet$ The set of references from pvars to nodes $ PL(rsg)$ are obtained by translating the old references from $ rsg_1$ and $ rsg_2$ to the new graph using the MAP function.

$ PL(rsg) = \{<pvar, MAP(n_i)> \vert~ \forall (<pvar, n_i> \in
PL(rsg_1)\} ~\cup$
$ \{<pvar, MAP(n_j)> \vert~ \forall (<pvar, n_j> \in

$ \bullet$ Similarly, we obtain the set of links between nodes:

$ NL(rsg) = \{<MAP(n_i), sel_j, MAP(n_k)> \vert~ \forall <n_i, sel_j, n_k> \in
NL(rsg_1) \}~ \cup $
$ \{<MAP(n_i), sel_j, MAP(n_k)> \vert~ \forall <n_i,
sel_j, n_k> \in NL(rsg_2) \}$

This way, in the new graph, $ rsg$, we keep all the references and links existing in the original graphs, $ rsg_1$ and $ rsg_2$, just changing the source and destination nodes for the corresponding ones of the new graph using the MAP function.

Thus, the new $ rsg$ resulting from the union of two compatible graphs has been completely defined. We emphasize here that due to this RSG union we can save a great amount of memory space, but at the same time we enable the representation of several memory configurations (which are not completely equal) with the same RSG.

next up previous
Next: Experimental results Up: Reduced Set of RSGs Previous: Graph pruning
Rafael Asenjo Plaza 2002-02-19