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

VIATRA2/Benchmarks

< VIATRA2
Revision as of 18:46, 10 June 2008 by Bergmanngabor.gmail.com (Talk | contribs) (Mutual exclusion (A Varró benchmark))

Mutual exclusion (A Varró benchmark)

Benchmark description

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: Varró Gergely: Graph transformation benchmarks

Metamodeling and initial model

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 mutex.metamodel namespace. The following VTML file describes the metamodel (for the sake of simplicity, we have not asserted any multiplicity constraints):
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);
  }		
}

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.


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 main() sequence:

//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));
}

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 rename().

Manual creation: the VIATRA2 Model Editor (the aforementioned tree editor) can be used to create the model. Navigate to the entity representing the namespace mutex and select "Add Entity" from the context menu. A new entity will appear as a child of mutex, alongside metamodel. Select "Rename" from the context menu of this entity to name it "model". We now have the mutex.model namespace. Next, we use the tree editor to create two child entites; the Eclipse view titled "Properties" allows us to specify mutex.metamodel.process 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.

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);
  }

Note that the namespace mutex 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

STS machine

LTS machine

Measurement results

Petri-net model simulation benchmark

TODO

Object-relational mapping benchmark

TODO

Sierpiński triangles benchmark (AGTIVE 2007)

TODO

Back to the top