README.md 4.34 KB
Newer Older
Julian Oppermann's avatar
Julian Oppermann committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
# GeMS - A Generator for Modulo Scheduling Problems

GeMS is a customisable, open-source toolkit for generating random, yet constrained, modulo scheduling problems with a known optimal initiation interval. These can then be used to evaluate the behavior of different scheduling algorithms under controlled conditions [1].

GeMS was designed and implemented by Sebastian Vollbrecht as part of his B.Sc. thesis project, supervised by Julian Oppermann and Andreas Koch, at TU Darmstadt's Embedded Systems and Applications group.

## License

GeMS is licensed under the Apache License, Version 2.0. Please cite [1] if GeMS was useful to you in an academic context.

## Requirements and building

You'll need:

* a Java 1.8 compatible VM
* IBM ILOG CPLEX 12.6 or newer
* JGraphT 1.2.0 (will be pulled automatically)

This project uses Gradle 4.9. In order to make your CPLEX installation known, copy `gradle.properties.sample` to `gradle.properties` and adjust the path and architecture tag (e.g. `x86-64_osx` or `x86-64_linux`) there.

Run:

* `./gradlew classes` to compile the sources
* `./gradlew javadoc` to generate the Javadoc (-> `build/docs/javadoc/index.html`)
* `./gradlew clean` to clean the build directory
* `./gradlew test` to run the provided unit tests. Depending on your system, this may take up to 1 hour.

Use `./gradlew eclipse` to generate the files required to import the project into Eclipse. Gradle projects are supported natively by IntelliJ IDEA. 

## Usage

GeMS is intended to be a toolkit to plug together generators for modulo scheduling problems, and therefore does not provide a command-line interface. See the class `graphgen.main.Main` for annotated examples. Execute `$ ./gradlew run` to start the `Main` class (with the required classpath (JGraphT, CPLEX) java.library.path (CPLEX native library)).

The internal representation of the generated graphs is simple (~ collections of nodes and edges, see `graphgen.graph.Graph`), and thus can be easily mapped to API calls, or exported to a file format. GeMS provides (see `graphgen.util.GraphFileUtils`) an export to Graphviz DOT, and to the XML-based format used by the HatScheT scheduler library [2].

## Limitations and future work

38
See the [issues](https://git.esa.informatik.tu-darmstadt.de/gems/gems/issues). Bug reports and contributions are welcome; please contact [Julian](mailto:oppermann@esa.tu-darmstadt.de).
Julian Oppermann's avatar
Julian Oppermann committed
39 40 41

## Internals

Andreas Koch's avatar
Andreas Koch committed
42
GeMS has the unique capability to construct dependence graphs that are guaranteed to be feasible, or infeasible, at the lower bound for the II search space (i.e. the usual MinII = max(RecMII, ResMII)). Graph generation proceeds in two phases: First, a cycle in the dependence graph is constructed that defines the instance's desired MinII. Then, during the edge generation phase, GeMS has to ensure that no MinII-changing edge is added. We employ several quick checks to handle common situations, but have to invoke an actual modulo scheduler to check the (in-)feasibility of smaller subgraphs in some cases. GeMS internally uses two ILP-based modulo schedulers for this purpose: The formulation by Eichenberger and Davidson [3], and the Moovac formation [4].
Julian Oppermann's avatar
Julian Oppermann committed
43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

## References

```
[1] Julian Oppermann, Sebastian Vollbrecht, Melanie Reuter-Oppermann, Oliver Sinnen, Andreas Koch
    Work in Progress: GeMS: A Generator for Modulo Scheduling Problems.
    International Conference on Compilers, Architectures and Synthesis For Embedded Systems (CASES), 2018.
    pre-print: https://www.esa.informatik.tu-darmstadt.de/twiki/pub/Staff/AndreasKochPublications/2018_CASES_JO.pdf

[2] Patrick Sittel, Julian Oppermann, Martin Kumm, Andreas Koch, Peter Zipf
    HatScheT: A Contribution to Agile HLS.
    FPGAs for Software Programmers (FSP), 2018.
    pre-print: https://www.uni-kassel.de/eecs/fileadmin/datas/fb16/Fachgebiete/Digitaltechnik/HatScheT.pdf
    project:   http://uni-kassel.de/go/hatschet
    
[3] Alexandre E. Eichenberger, Edward S. Davidson
    Efficient Formulation for Optimal Modulo Schedulers
    SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 1997
    https://doi.org/10.1145/258916.258933

[4] Julian Oppermann, Andreas Koch, Melanie Reuter-Oppermann, Oliver Sinnen
    ILP-based Modulo Scheduling for High-level Synthesis.
    International Conference on Compilers, Architectures and Synthesis For Embedded Systems (CASES), 2016.
    https://doi.org/10.1145/2968455.2968512
```