Skip to main content

Notice: this Wiki will be going read only early in 2024 and edits will no longer be possible. Please see: https://gitlab.eclipse.org/eclipsefdn/helpdesk/-/wikis/Wiki-shutdown-plan for the plan.

Jump to: navigation, search

Difference between revisions of "VIATRA2/Benchmarks"

(→‎Sierpiński triangles benchmark (AGTIVE 2007))
(→‎Mutual exclusion (A Varró benchmark))
Line 3: Line 3:
 
== Mutual exclusion (A Varró benchmark) ==
 
== Mutual exclusion (A Varró benchmark) ==
  
−
=== Benchmark description ===
+
[[VIATRA2/Mutual Exclusion Benchmark | The mutual exclusion benchmark]]
−
The Varró benchmark suite defines a set of transformations on which many transformation systems have been measured. One part of this benchmark suite is based on a distributed mutual exclusion algorithm. This section will introduce the implementation of the library of graph transformation rules that make up the benchmark. Furthermore, the transformation machines are also given that implement the long transformation sequence (LTS) and short transformation sequence (STS) algorithms outlined in the benchmark suite. Finally, some measurements are presented.
+
−
 
+
−
The mutual exclusion test case describes a process ring arbitrating control of resources. After growing the process ring
+
−
to the required size, the STS version creates one resource that is owned by one process; in the next phase, every
+
−
process issues a request on that resource; the resource will be passed along the ring until a full cycle is
+
−
performed. LTS starts with a complete ring and a separate resource owned by every process; the whole set
+
−
of resources is shifted along the process ring once in each cycle, involving waiting and blocked processes,
+
−
as well as a deadlock-resolving algorithm. The ring size is the characteristic parameter in both cases; for
+
−
LTS, the number of executed cycles can also be specified.
+
−
 
+
−
For a detailed test specification, see the following article:
+
−
Varró G., Schürr, A., Varró D.: Benchmarking for graph transformation. In: Proc. IEEE
+
−
Symposium on Visual Languages and Human-Centric Computing (VL/HCC 05), Dallas,
+
−
Texas, USA, IEEE Press (September 2005) 79–88
+
−
Or visit this page: [http://www.cs.bme.hu/~gervarro/benchmark/2.0/ Varró Gergely: Graph transformation benchmarks]
+
−
 
+
−
=== Metamodeling ===
+
−
[[Image:mutex_metamodel.png|frame|Metamodel of the mutual exclusion problem set]]First, we have to build the metamodel of the benchmark set. Processes and resources will be represented as Viatra entities, and their associations as relations; they will all be contained in the <tt>mutex.metamodel</tt> namespace. The following VTML file describes the metamodel (for the sake of simplicity, we have not asserted any multiplicity constraints):
+
−
<source lang="java">
+
−
entity(mutex)
+
−
{
+
−
  entity(metamodel) {
+
−
    entity(resource);
+
−
    entity(process);
+
−
    relation(next, process, process);
+
−
    relation(blocked, resource, process);
+
−
    relation(held_by, resource, process);
+
−
    relation(token, resource, process);
+
−
    relation(release, resource, process);
+
−
    relation(request, process, resource);
+
−
  }
+
−
}
+
−
</source>
+
−
 
+
−
We create a new Viatra model space for this benchmark by the new VIATRA2 VPM model space wizard (accessible at File/New/Other
+
−
). Opening the model space will display the Tree Editor, which can be used to directly manipulate the model space. The Eclipse view titled "VIATRA2 Models spaces" will also show a new line representing the opened model space; loading the metamodel into our new model space is as simple as drag&dropping the .vtml file from the Package Explorer (or Project Explorer) onto this item.
+
−
 
+
−
TODO link VTML files?
+
−
 
+
−
=== Initial model ===
+
−
[[Image:mutex_initmodel.png|frame|Initial model of the mutual exclusion problem set (particularly STS)]]Now we have our metamodel, but the initial model (see figure) still needs to be constructed. There are several ways to achieve this.
+
−
+
−
'''Programmatic construction''': the machine executing the transformation (or a separate VTCL machine) can create the initial model itself (before starting the benchmark timer). For example, the following code could be inserted at the beginning of the <code>main()</code> sequence:
+
−
<source lang="java">
+
−
//initialisation
+
−
let Model = undef, N1 = undef, N2 = undef, P1 = undef, P2 = undef in seq {
+
−
  new (entity(Model) in mutex);
+
−
  rename(Model, "model");
+
−
  new (mutex.metamodel.process(P1) in mutex.model);
+
−
  new (mutex.metamodel.process(P2) in mutex.model);
+
−
  new (mutex.metamodel.process.next(N1, P2, P1));
+
−
  new (mutex.metamodel.process.next(N2, P1, P2));
+
−
}
+
−
</source>
+
−
Note that N1, N2, P1, P2 are merely variable names and the created entities and relations receive generated names; if the need arises to name them properly, use <code>rename()</code>.
+
−
 
+
−
'''Manual creation''': the VIATRA2 Model Editor (the aforementioned tree editor) can be used to create the model. Navigate to the entity representing the namespace <code>mutex</code> and select "Add Entity" from the context menu. A new entity will appear as a child of <code>mutex</code>, alongside <code>metamodel</code>. Select "Rename" from the context menu of this entity to name it "model". We now have the <code>mutex.model</code> namespace. Next, we use the tree editor to create two child entites; the Eclipse view titled "Properties" allows us to specify <code>mutex.metamodel.process</code> as the "Type" of these entities (and possibly to rename them). By selecting "Add Relation" from the context menu of each process, we add a self-referencing relation to each of them. The new relations appear as a child node of the respective entities, as if they were contained by their source element; this is in conformance with the rule governing their fully qualified name. As a consequence, dragging and dropping each relation onto the other entity would change their source element, which is just what we need. Using the "Properties" view again, these relations can be typed ; their source and target could also have been specified here.
+
−
 
+
−
'''Import model''': the initial model can be represented in VTML and imported via drag&drop just as easily as the metamodel.
+
−
<source lang="java">
+
−
namespace mutex;
+
−
  entity(model) {
+
−
    mutex.metamodel.process(p1);
+
−
    mutex.metamodel.process(p2);
+
−
    mutex.metamodel.process.next(n1, p2, p1);
+
−
    mutex.metamodel.process.next(n2, p1, p2);
+
−
  }
+
−
</source>
+
−
Note that the namespace <code>mutex</code> has already been created; this VTML file merely references it. Also, the model elements are properly named now, conforming to the figure shown above. This method seems to be the smoothest, so we'll apply this one.
+
−
 
+
−
TODO link VTML files?
+
−
 
+
−
=== Pattern and rule library ===
+
−
 
+
−
During the development of the benchmark implementation, multiple versions of the transformation were developed (STS versus LTS; gtrules versus patterns and rules; debug versus "release" version). However, they all share the common set of graph transformation rules defined in the benchmark description. To avoid the needless replication of the transformation rules, all patterns and rules have been isolated into single VTCL machine (<code>mutex.lib</code>). This machine contains no <code>main()</code> rule, it is therefore not executable; it merely serves as a shared library. The different executable transformation machines all reference patterns and rules defined in this library.
+
−
 
+
−
[[Image:releaseRule.png|frame|The graphical representation of the "releaseRule" transformation rule]]
+
−
The benchmark consists of a great number of transformation rules. Here we only present the implementation of a single representative, namely <code>releaseRule</code>.
+
−
 
+
−
Writing a VTCL code that embodies this transformation rule consists of two steps: first, create a graph pattern according to the LHS (left-hand-side) of the transformation rule; second, implement the action sequence that is to be executed on finding that pattern (i.e. transforming LHS into RHS). Before we can construct the LHS pattern, there is an obstacle to overcome: it contains a negative application condition (NAC). Occurrences shall be rejected if the process still has an unfulfilled request for a resource. So the NAC can be formulated as a pattern that matches those processes that ''do'' have an outgoing edge of type "request" to a resource; the availability of this pattern will block our LHS pattern. In VTCL, this is coded as a pattern on processes, see below:
+
−
<source lang="java">
+
−
pattern req(P) = {
+
−
  process(P);
+
−
  resource(Rn);
+
−
  process.request(Reqn, P, Rn);
+
−
}
+
−
</source>
+
−
 
+
−
Now we can incorporate this NAC into the LHS pattern. The LHS is a pattern consisting of a process (that does not match the NAC), a resource, and a held-by relation between them, as shown below:
+
−
<source lang="java">
+
−
pattern releaseRule_lhs(P, R, HB) =
+
−
{
+
−
  process(P);
+
−
  resource(R);
+
−
  resource.held_by(HB, R, P);
+
−
  neg pattern req(P) = {
+
−
    process(P);
+
−
    resource(Rn);
+
−
    process.request(Reqn, P, Rn);
+
−
  }
+
−
}
+
−
</source>
+
−
Finally, we write the simple rule sequence that manipulates the model:
+
−
<source lang="java">
+
−
rule releaseRule(in P, in R, in HB, out Rel) = seq
+
−
{
+
−
  delete(HB);
+
−
  new(resource.release(Rel, R, P));
+
−
}
+
−
</source>
+
−
 
+
−
There is an option that resembles the graph rule formalism more closely: the <code>gtrule</code> construct. Although the version above will be used for its greater flexibility, we still present an alternate way to express the same thing in VTCL:
+
−
<source lang="java">
+
−
gtrule releaseRule_gtrule(out P, out R) =
+
−
{
+
−
  precondition find releaseRule_lhs(P, R, HB);
+
−
  postcondition pattern rhs(P, R, HB) =
+
−
  {
+
−
    process(P);
+
−
    resource(R);
+
−
    resource.release(Rel, R, P);
+
−
  }
+
−
}
+
−
</source>Here the right-hand side is also presented in a graph pattern format. The variable HB is not present in the RHS, even though it's listed as one of its symbolic parameters; this is the way to express deletion. Variables that are not symbolic parameters of the postcondition will not be deleted. Note that we simply reused the pattern <code>releaseRule_lhs</code> for the precondition; alternatively, it could have been defined locally just as the RHS. Or alternatively, we could reuse the RHS as an action sequence as well (which could be even simpler if it weren't for the output parameter Rel):
+
−
<source lang="java">
+
−
gtrule releaseRule_gtrule(out P, out R) =
+
−
{
+
−
  precondition find releaseRule_lhs(P, R, HB);
+
−
  action {
+
−
    let Rel = undef in call releaseRule(P, R, HB, Rel);
+
−
  }
+
−
}
+
−
</source>
+
−
 
+
−
After writing the VTCL code for the other transformation rules, our mutex library will look like this:
+
−
<source lang="java">
+
−
namespace mutex;
+
−
import mutex.metamodel;
+
−
 
+
−
//@incremental
+
−
machine lib
+
−
{
+
−
// [...]
+
−
  pattern releaseRule_lhs(P, R, HB) =
+
−
  {
+
−
    process(P);
+
−
    resource(R);
+
−
    resource.held_by(HB, R, P);
+
−
    neg pattern req(P) = {
+
−
      process(P);
+
−
      resource(Rn);
+
−
      process.request(Reqn, P, Rn);
+
−
    }
+
−
  }
+
−
  rule releaseRule(in P, in R, in HB, out Rel) = seq
+
−
  {
+
−
    delete(HB);
+
−
    new(resource.release(Rel, R, P));
+
−
  }
+
−
// [...]
+
−
}
+
−
</source>
+
−
By drag&dropping this .vtcl file onto the opened model space (in the VIATRA2 Modes spaces view), we can parse this library into the VIATRA2 framework. Another option is pressing Ctrl+P, if the file is open in a VTCL editor. Both options require that the model space already contains the metamodel.
+
−
By uncommenting the annotation above the machine, the incremental pattern matcher will be used instead of the default one.
+
−
 
+
−
=== STS machine ===
+
−
The short transformation sequence of parameter ''Size'' consists of the following steps:
+
−
# <tt>newRule</tt> is applied ''Size''-2 times to enlarge a ring
+
−
# <tt>mountRule</tt> is applied once to create a single resource attached to one of the processes
+
−
# <tt>requestRule</tt> is applied on each LHS occurrence so that all processes file a request on the resource
+
−
# an as-long-as-possible cycle consisting of single applications of <tt>takeRule</tt>, <tt>releaseRule</tt> and <tt>giveRule</tt> so that each process acquires the resource for a short time and then hands it over to the next one
+
−
 
+
−
First, let's see how to apply a rule ''once''. The following construct selects one occurrence or a LHS pattern:
+
−
<source lang="java">
+
−
choose P1, P2, N with find mutex.lib.newRule_lhs(P1, P2, N) do [...something]
+
−
</source>The omitted part can use the bound pattern variables arbitrarily. Now we'll use them to execute the model manipulation rule. Ideally, this would look like the following:
+
−
<source lang="java">
+
−
choose P1, P2, N with find mutex.lib.newRule_lhs(P1, P2, N) do
+
−
    call mutex.lib.newRule(P1, P2, N);
+
−
</source>However, our implementation of <tt>newRule</tt>, much like <tt>releaseRule</tt> above, also has some output variables to return the value of the newly created elements (that can be printed for debugging purposes, etc.). Therefore these output variables need to be declared in the caller scope too:
+
−
<source lang="java">
+
−
choose P1, P2, N with find mutex.lib.newRule_lhs(P1, P2, N) do
+
−
  let P = undef, N1 = undef, N2 = undef in
+
−
    call mutex.lib.newRule(P1, P2, N, P, N1, N2);
+
−
</source>
+
−
 
+
−
The <tt>iterate</tt> construct of VTCL executes an action repeatedly until it fails. To create a simple cycle that applies <tt>newRule</tt> ''Size''-2 times, we write an iterated action that fails if the desired number of iterations have been reached, and otherwise applies the rule as above. Step 1 is implemented this way:
+
−
<source lang="java">
+
−
// step1: new processes
+
−
let StepCount = 0 in iterate
+
−
  if(StepCount < Size-2) seq
+
−
  {
+
−
    update StepCount = StepCount+1;
+
−
+
−
    choose P1, P2, N with find mutex.lib.newRule_lhs(P1, P2, N) do
+
−
      let P = undef, N1 = undef, N2 = undef in
+
−
        call mutex.lib.newRule(P1, P2, N, P, N1, N2);
+
−
  } else fail;
+
−
//println("step 1 done");
+
−
</source>The body of the <tt>let/in</tt> construct can be replaced with a sequence block that, besides calling the rule itself, updates counters or other tracking data and/or prints useful debug information about the execution of the rule and the newly created elements, etc.
+
−
 
+
−
Step 2 is a simple rule application, it does not deserve special mention. Before discussing Step 3, let's see Step 4:
+
−
<source lang="java">
+
−
// step4
+
−
iterate seq{
+
−
  choose P, R, T, Req with find mutex.lib.takeRule_lhs(P, R, T, Req) do
+
−
    let HB = undef in call mutex.lib.takeRule(P, R, T, Req, HB);
+
−
  choose P, R, HB with find mutex.lib.releaseRule_lhs(P, R, HB) do
+
−
    let Rel = undef in call mutex.lib.releaseRule(P, R, HB, Rel);
+
−
  choose P1, P2, R, Rel with find mutex.lib.giveRule_lhs(P1, P2, R, Rel) do
+
−
    let T = undef in call mutex.lib.giveRule(P2, R, Rel, T);
+
−
};
+
−
//println("step 4 done");
+
−
</source>It uses the same <tt>iterate</tt> construct, meaning that it tries to execute this three-rule cycle as long as possible, stopping on first failure (which occurs when all rules have already been fulfilled). 
+
−
 
+
−
Step 3 could use the <tt>iterate</tt> construct too, but it uses the <tt>forall</tt> construct instead, meaning that all occurences of the LHS are determined in one step, and then the rule is executed on each one of them. In some cases, this may lead to different behaviour; now it was chosen solely for performance considerations, as it only needs a single pattern matching query.
+
−
<source lang="java">
+
−
// step3
+
−
forall P, R with find mutex.lib.requestRule_lhs(P, R) do
+
−
  let Req = undef in call mutex.lib.requestRule(P, R, Req);
+
−
//println("step 3 done");
+
−
</source>
+
−
 
+
−
=== Measurement results ===
+
−
The measurements have been carried out on a standard desktop computer with a 2 GHz Intel Core2
+
−
processor, 2 gigabytes of system RAM available, the Windows Vista operating system, running version
+
−
1.6.0 05 of the 32-bit Sun Java SE Runtime (for VIATRA2) and version 3.0 of the .NET Framework
+
−
(for GrGEN.NET). In general, several test runs were executed, ranging from five to ten runs on different
+
−
test cases. The transformation sequences were coded so that little or no output was generated; in the case
+
−
of VIATRA2, the GUI was not disabled. Execution times were measured with millisecond precision as
+
−
allowed by the operating system calls.
+
−
 
+
−
In order to compare the pattern matcher algorithms using an already available benchmark, the performance of the VIATRA 2 local search based (VIATRA/LS) and incremental (VIATRA/RETE) pattern matchers have been evaluated along with GrGEN.NET (considered to be one of the fastest graph transformation systems) with the short transformation sequence version of the distributed mutual exclusion algorithm test set, which is not a primary application field for incremental pattern matching.
+
−
 
+
−
[[Image:result_STS.png|Performance of various approaches on STS mutex benchmark]]
+
−
 
+
−
The results show that the incremental approach is more efficient than the default pattern matcher implementation (local search), since the current unoptimized local search algorithm cannot operate in linear time. Nevertheless, VIATRA2 is still outperformed by the highly optimized GrGen.NET.
+
  
 
== Petri-net model simulation benchmark ==
 
== Petri-net model simulation benchmark ==

Revision as of 06:47, 9 July 2008

The following benchmark cases demonstrate the performance of the VIATRA2 framework. Additionally, the first one has been elaborated in great detail to aid the learning and understanding of VIATRA2.

Mutual exclusion (A Varró benchmark)

The mutual exclusion benchmark

Petri-net model simulation benchmark

The Petri-net simulation bechmark

Object-relational mapping benchmark (field: model synchronisation)

Benchmark description

The Object-to-Relational schema mapping (ORM) benchmark, as presented here, is an extension of the original benchmark proposed in Sec.4 of: 

Varró G., Schürr, A., Varró D.: Benchmarking for graph transformation. In: Proc. IEEE
Symposium on Visual Languages and Human-Centric Computing (VL/HCC 05), Dallas,
Texas, USA, IEEE Press (September 2005) 79–88

The original transformation processed UML class diagrams to produce corresponding relational database schemata, according to the known mapping rules. Since a straightforward application of the incremental pattern matching approach is the synchronization between source and target models, we extended the benchmark by two additional sequences: (i) after the initial mappings are created, the source models are modified, and, in an additional pass, (ii) the system has to synchronize the changes to the target model (i.e. find the changes in the source and alter the target accordingly). A local search-based algorithm has to search for the changes first, while an incremental pattern matcher can track changes in the source model so that the model parts affected are instantly available for the synchronization sequence.

Execution phases:

  1. The generation phase creates the model graph.
  2. The build phase maps creates the initial mapping of the UML model into the relational schema domain, with reference models connecting mapped model objects.
  3. The modification phase modifies the UML models programmatically to emulate user editing actions.
  4. Finally, the synchronization phase locates the affected model elements and makes changes in the schema model accordingly.

Metamodel

UML and DB metamodel (classname attribute omitted).
Reference metamodel.

The UML and DB metamodels follow the original benchmark proposition (with minor changes in naming). Our reference metamodel is somewhat more refined, but still relies on simple edges instead of the more versatile approach of reference entities. 

entity(UML)
{
	entity(model);
	entity(metamodel) {	
 
		entity(class) {
			entity(attribute);
			relation(cl2attrs, class, attribute);
				isAggregation(cl2attrs, true);
			relation(name, class, datatypes.String);
		}
		entity(assoc) {
			entity(end);
			relation(assoc2ends, assoc, end);
				isAggregation(assoc2ends, true);
			relation(end2cl, end, class);
			relation(name, assoc, datatypes.String);
		}
		entity(general) {
			relation(parent, general, class);
			relation(child, general, class);
		}	
		entity(package) {		
			relation(p2as, package, assoc);	
				isAggregation(p2as, true);
			relation(p2cls, package, class);
				isAggregation(p2cls, true);
			relation(p2gs, package, general);
				isAggregation(p2gs, true);
		}	
	}	
 
}
entity ( DB ) {
	entity(model);
	entity(metamodel) {	
		entity ( schema ) {
			relation (tables, schema, table);
				isAggregation(tables, true);	
		}
		entity ( table ) {
			relation ( t2pkey , table , pKey );
				isAggregation(t2pkey, true);
			relation ( t2cols , table , column );
				isAggregation(t2cols, true);
			relation ( t2fkeys , table , fKey );	
				isAggregation(t2fkeys, true);
			relation(name, table, datatypes.String);
		}
		entity ( column );
		entity ( fKey ) {
			relation ( cref , fKey , column );
			relation ( ukr , fKey , pKey );		
		}
		entity ( pKey ) {  
			relation ( pkey2col , pKey , column ); 
		}
	}
}
 
// reference model
relation(schemaRef, UML.metamodel.package, DB.metamodel.schema);
relation(tableRef, UML.metamodel.class, DB.metamodel.table);
relation(tableRef, UML.metamodel.assoc, DB.metamodel.table);
relation(fKeyRef, UML.metamodel.assoc.end, DB.metamodel.fKey);
relation(fKeyRef, UML.metamodel.general, DB.metamodel.fKey);
relation(colRef, UML.metamodel.class.attribute, DB.metamodel.column);


Initial model: test case generation

Generated UML class diagram for N=K=2.

In order to produce sufficiently large model graphs for the measurements, we implemented a simple generator as described in the referenced article. By this approach, a fully connected graph is created, i.e. for N UML classes, N(N − 1) directed associations are defined (with each association represented as three nodes – an association node and two endpoints). Additionally, each UML class can reference K attributes, thus, for a given N and K, N + 3N(N − 1) + NK nodes and 4N(N − 1) + NK edges are created (see the figure on the side). Although the model produced is not “realistic” in the sense that very few practical UML class diagrams are fully connected, the method is quite efficient in creating large graphs quickly.

Transformation details

The build phase follows the original Varró benchmark description. Here we give the implementation of a representative graph transformation rule.

The ClassRule
pattern classRule_lhs(P, C, S, Str) = 
{
	package(P);
	class(C);
	package.p2cls(P2C, P, C);
	schema(S);
	package.schemaRef(R1, P, S);
	datatypes.String(Str);
	class.name(N1, C, Str);
	neg pattern mapped(C, TN, REFN) = {
		class(C);
		table(TN);
		class.tableRef(REFN, C, TN);
	}	
}	
rule classRule(in C, in S, in Str, 
  out T, out TPK, out TID, out R2, out EO2, out EO3, out CF, out UF, out N2) = seq{
	new (table(T) in S);
	rename(T,name(C));
	new (class.tableRef(R2, C, T));
	rename(R2,"class_table");		
	new (schema.tables(EO2, S, T));
	rename(EO2,"_"+name(T));
	new (table.name(N2, T, Str));
	rename(N2,"table_name");
	new (pKey(TPK) in T);
	rename(TPK,"primaryKey");
	new (table.t2pkey(EO3, T, TPK));
	rename(EO3,"table_pkey");
	new (column(TID) in T);
	rename(TID,"id");
	new (table.t2cols(CF, T, TID));
	rename(CF,"_"+name(TID));
	new (pKey.pkey2col(UF, TPK, TID));
	rename(UF,"pkey_column");
}

To support incremental synchronisation between source and target models, to avoid rebuilding target models in each pass, the reference model is used to establish a mapping relationship between source and corresponding target model elements. With correspondence edges, it is possible to track changes in both the source and target models: for instance, the graph pattern featured below matches tables in the schema model which are no longer referenced by classes or associations in the UML models (orphan tables).

Renaming (value changing) may be expressed e.g. by matching for both the attribute and the mapped column, and looking for pairs where the name (attribute value) is different. The modification sequence results in the following synchronization sequence:

  1. all orphan tables belonging to the deleted classes and their associations are deleted;
  2. all orphan tables belonging to the deleted associations are deleted;
  3. column names mapped to the renamed attributes are changed;
  4. new tables are added for the newly created class and the new associations.

The following representative pattern identifies orphan DB tables that have no reason anymore to exist, and shall be deleted: 

pattern orphanTable(T) =
{
	table(T);
	neg pattern mapped(T) = 
	{
		class(C);
		table(T);
		class.tableRef(REFN, C, T);
	} or {
		assoc(A);
		table(T);
		assoc.tableRef(REFN, A, T);
	}
}

Measurement results

Model and synchronization sequence sizes for the ORM benchmark

The measurements reported here have been carried out on a standard desktop computer with a 2 GHz Intel Core2 processor with 2 gigabytes of system RAM available, running version 1.6.0-05 of the 32-bit Sun Java SE Runtime. In general, ten test runs were executed, and the results were calculated by averaging the values excluding the highest and lowest number. The transformation sequences were coded so that little or no output was generated; in the case of VIATRA 2, we refrained from disabling the GUI. Execution times were measured with millisecond precision as allowed by the operating system calls.

The ORM synchronization benchmark was executed with the VIATRA 2 tool (due to time constraints, measurements with GrGEN.NET and others are left as future work). Models up to 67800 nodes (with edges, the total model size is 157800 model elements) were generated (see the table to the right) and the execution time for the build and synchronization phases was measured.

Results for the ORM synchronization benchmark

The results are shown in the figure to the right (model size is the total number of nodes). It is gain revealed that the scaling characteristic of both phases is exponential for VIATRA/LS and linear for VIATRA/RETE. With respect to synchronization, the constant difference between the build and sync phases for VIATRA/RETE means a constant multiplier; thus, since the model elements affected by the modification sequence are a linear fraction of the whole model, it can be concluded that the execution time for the synchronization process is a linear function of the model elements affected (as expected), and independent of the size of the rest of the model. VIATRA/LS, on the other hand, exhibits an ever increasing time difference between build and sync, thus, the time taken for the synchronization process increases exponentially with the number of affected model elements (again, as expected, since in the case of local search, the system has to locate the changed elements first which is an additional graph traversal). It is important to note that for “practical” model sizes (e.g. below the 5000 node count range), VIATRA/RETE can perform a synchronization affecting a considerable portion of the model in the 10-500 msec range which makes the approach very suitable for interactive applications.

In addition to execution times, the memory consumed by the Java Virtual Machine was also recorded. The sequence for the RETE matcher (75, 100, 114, 245, 490, 750, 1000 megabytes respectively for model sizes from 85 to 67800 nodes) shows a linearly expanding RETE network as the node count grows, which is in-line with our expectations based on the nature of the RETE building algorithm (note that the above figures include the whole user interface with a complete Eclipse instance).

Sierpiński triangles benchmark (AGTIVE 2007)

The Sierpiński triangles benchmark simulation benchmark

Retrieved from "https://wiki.eclipse.org/index.php?title=VIATRA2/Benchmarks&oldid=109249"

Back to the top