Universität Karlsruhe
GrGen

GrGen is a new generative programming system for graph rewriting.

Description

It features an expressive specification language and implements a modification of the theoretically well-founded SPO approach to graph rewriting.
The generated program code executes very fast and is easy to invoke through a comfortable interface. According to a benchmark introduced by Varró the performance of rewriting, especially of the potentially costly pattern matching, is at least one order of magnitude faster than of any other known system.
We achieve this by using special tailored data structures and by a dynamically optimizing approach to sub graph matching, which means that the optimization can be done at runtime depending on the actual present host graph. In this context we use the concept of search plans to represent different matching strategies. By stating a cost model we understand the generation of good search plans as an optimization problem, which we solve heuristically.

Structure of the GrGen Tool
Structure of the GrGen tool

Download

You can download a binary package of GrGen. It contains a graph engine (aka backend), the libGr interface, and the interactive graph rewrite application GrShell. Please note, that the contained graph engine is a stable version compiled without any optimization (to enable efficient debugging). Therefore the benchmark performance is expected to be an order of magnitude shower as the figures presented below.

  • Download GrGen Binary Distribution (release date 2006-10-04)
    This download package contains the SearchPlan backend for the first time. For users of previous releases it is neccessary to update the GrShell scripts to use the new dynamic libraries. Some fixes for a bug with NACs introduced with the previous release are included.

Documentation

GrGen

GrGen is a compiler which translates graph rewrite rules specified in a declarative language into a module that can be loaded by a specific libGr backend.

libGr

The libGr offers an interface for manipulating host graphs and for applying rules declared in GrGen.

GrShell

The GrShell is an example application using the libGr. It is designed to operate as a frontend for easy application of graph rewrite rules and for running benchmarks.

Graph Engines

  • MSQL Matching and bookkeeping of graphs done by the MySQL database management system.
  • PSQL Matching and bookkeeping of graphs done by the PostgresQL database management system.
  • FrameBased: An outdated In-Memory backend.
  • SearchPlan Our fastest and most advanced graph engine based on an optimization technique for subgraph matching strategies. This graph engine contained in the download package.

Benchmark

This benchmark was introduced by Gergely Varró. The benchmark itself is described in a tech report a more high-level description as well as runtimes for several graph rewrite systems are given in a paper by Gergely Varró, Andy Schürr, and Daniel Varró. Extensive benchmark results can be found on a website maintained by Gergely Varró.

Runtimes for the mutex benchmark of the GrGen SearchPlan graph engine
Runtimes for the mutex benchmark of the GrGen SearchPlan graph engine.
Detailed numbers can be found in a table.

Runtime per rule for the mutex benchmark of the GrGen SearchPlan graph engine
Runtime per rule application for the mutex benchmark of the GrGen SearchPlan graph engine, i.e. all runtimes for the whole benchmark are divided by the size of the benchmark (which is proportional to the number of rule applications in this benchmark).
Detailed numbers can be found in a table.

Runtimes for the mutex benchmark of the GrGen SearchPlan graph engine compared with major tools
Runtimes for the mutex benchmark of the GrGen SearchPlan graph engine compared with major tools. Note the logarithmic scaling of the time axis.

The benchmark was conducted using the SearchPlan graph engine on an AMD Athlon(tm) XP 3000+ running SuSE Linux 9.3 with kernel version 2.6.11.4-21.11-default.

The runtime displayed includes the whole rule applications that include: matching, rewriting, cleanup, and the overhead executing the rewrite sequences (detailed numbers can be found in a table). The graph analysis (for the computation of the costs of the possible search plan operations) remains under 2 ms for benchmark sizes upto 1000. For sizes up to 10000 it remains under 15 ms. The runtime for the heuristic determination of searchplans was always below timer resolution (1ms).


Questions, suggestions, bugs? Feel free to contact the maintainer and main author: Rubino Geiss


Login
Links