|
|
| (14 intermediate revisions by 2 users not shown) |
| Line 1: |
Line 1: |
| − | == Mutual exclusion (A Varró benchmark) == | + | == Outdated page == |
| | + | This page contains obsolete information about the VPM based VIATRA2 and preserved for archive purposes only.<br /> |
| | + | The currently maintained wiki is available at http://wiki.eclipse.org/VIATRA |
| | | | |
| − | === Benchmark description ===
| + | __TOC__ |
| − | 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 | + | 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. |
| − | 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:
| + | == Mutual exclusion (A Varró benchmark) == |
| − | 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 ===
| + | [[VIATRA2/Mutual Exclusion Benchmark | The mutual exclusion benchmark]] |
| − | [[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.
| + | |
| − | | + | |
| − | 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;
| + | |
| − | | + | |
| − | 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.
| + | |
| − | | + | |
| − | === STS machine ===
| + | |
| − | TODO:
| + | |
| − | # Basic desription of STS
| + | |
| − | # Simple constructs: choose -> iterate if-then-else -> iterate choose -> forall
| + | |
| − | # debug version?
| + | |
| − | # gtrule version
| + | |
| − | | + | |
| − | <source lang="java">
| + | |
| − | namespace mutex;
| + | |
| − | import mutex.metamodel;
| + | |
| − |
| + | |
| − | machine sts
| + | |
| − | {
| + | |
| − | rule main(in Size) = let FireCount = 0, StartTime = systime() in seq {
| + | |
| − | // mutex benchmark, STS
| + | |
| − | // see http://www.cs.bme.hu/~gervarro/publication/TUB-TR-05-EE17.pdf
| + | |
| − |
| + | |
| − | // 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 seq{
| + | |
| − | call mutex.lib.newRule(P1, P2, N, P, N1, N2);
| + | |
| − | update FireCount = FireCount +1;
| + | |
| − | //println("newRule: p1="+ name(P1) + " - p="+ name(P) + " - p2="+ name(P2));
| + | |
| − | //println("also: n1="+ name(N1));
| + | |
| − | }
| + | |
| − | } else fail;
| + | |
| − | //println("step 1 done");
| + | |
| − | | + | |
| − | // step2: mount a single resource
| + | |
| − | choose P with find mutex.lib.mountRule_lhs(P) do
| + | |
| − | let R = undef, T = undef in seq {
| + | |
| − | call mutex.lib.mountRule(P, R, T);
| + | |
| − | update FireCount = FireCount +1;
| + | |
| − | //println("mountRule: p="+ name(P) + " r=" + name(R));
| + | |
| − | }
| + | |
| − | //println("step 2 done");
| + | |
| − |
| + | |
| − |
| + | |
| − | // step3
| + | |
| − | forall P, R with find mutex.lib.requestRule_lhs(P, R) do
| + | |
| − | let Req = undef in seq {
| + | |
| − | call mutex.lib.requestRule(P, R, Req);
| + | |
| − | update FireCount = FireCount +1;
| + | |
| − | //println("requestRule: p="+ name(P) + " - r="+ name(R) );
| + | |
| − | }
| + | |
| − | //println("step 3 done");
| + | |
| − |
| + | |
| − | // step4
| + | |
| − | iterate seq{
| + | |
| − | choose P, R, T, Req with find mutex.lib.takeRule_lhs(P, R, T, Req) do
| + | |
| − | let HB = undef in seq {
| + | |
| − | call mutex.lib.takeRule(P, R, T, Req, HB);
| + | |
| − | update FireCount = FireCount +1;
| + | |
| − | //println("takeRule: p="+ name(P) + " - r="+ name(R));
| + | |
| − | }
| + | |
| − | choose P, R, HB with find mutex.lib.releaseRule_lhs(P, R, HB) do
| + | |
| − | let Rel = undef in seq {
| + | |
| − | call mutex.lib.releaseRule(P, R, HB, Rel);
| + | |
| − | update FireCount = FireCount +1;
| + | |
| − | //println("releaseRule: p="+ name(P) + " - r="+ name(R));
| + | |
| − | }
| + | |
| − | choose P1, P2, R, Rel with find mutex.lib.giveRule_lhs(P1, P2, R, Rel) do
| + | |
| − | let T = undef in seq {
| + | |
| − | call mutex.lib.giveRule(P2, R, Rel, T);
| + | |
| − | update FireCount = FireCount +1;
| + | |
| − | //println("giveRule: p1="+ name(P1) + " - r="+ name(R) + " - p2="+ name(P2));
| + | |
| − | }
| + | |
| − | };
| + | |
| − | //println("step 4 done");
| + | |
| − | print("DONE: " + FireCount + " rules fired in " + (systime() - StartTime) + "ms; ");
| + | |
| − |
| + | |
| − | //cleaning
| + | |
| − | call mutex.lib.cleanModel();
| + | |
| − | }
| + | |
| − |
| + | |
| − | }
| + | |
| − | </source>
| + | |
| − | | + | |
| − | TODO
| + | |
| − | <source lang="java">
| + | |
| − | choose P1, P2 with apply newRule(P1, P2) do
| + | |
| − | println("newRule: p1="+ name(P1) + " - p2="+ name(P2));
| + | |
| − | </source>
| + | |
| − | | + | |
| − | === Measurement results ===
| + | |
| | | | |
| | == Petri-net model simulation benchmark == | | == Petri-net model simulation benchmark == |
| | | | |
| − | TODO
| + | [[VIATRA2/Petri-net Simulation Benchmark| The Petri-net simulation bechmark]] |
| − | | + | |
| − | == Object-relational mapping benchmark ==
| + | |
| | | | |
| − | TODO
| + | == Object-relational mapping benchmark (field: model synchronisation) == |
| | + | [[VIATRA2/ORM benchmark | Object-relational mapping benchmark]] |
| | | | |
| | == Sierpiński triangles benchmark (AGTIVE 2007) == | | == Sierpiński triangles benchmark (AGTIVE 2007) == |
| | | | |
| − | TODO
| + | [[VIATRA2/Benchmarks/Sierpinsky triangles Benchmark| The Sierpiński triangles benchmark simulation benchmark]] |
This page contains obsolete information about the VPM based VIATRA2 and preserved for archive purposes only.
The currently maintained wiki is available at http://wiki.eclipse.org/VIATRA
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.
