Windows Version of TGFF 3.1 (binary only)

Original design: David Rhodes and Robert Dick.

Subsequent development: Keith Vallerio.

**T**ask **G**raphs **F**or
**F**ree (TGFF) was designed to provide a flexible and
standard way of generating pseudo-random task-graphs for use in
scheduling and allocation research. This includes the areas of
embedded systems, hardware/software co-design, operating systems (both
real-time and general-purpose), parallel or distributed hardware or
software studies, flow-shop scheduling, as well as any other area
which requires problem instances consisting of partially-ordered or
directed acyclic graphs (DAGs) of tasks, *i.e.*, task-graphs.

While TGFF strives to be general-purpose, it generates graphs and associated resource parameters in accordance with the user's parameterized graph and database specifications and thereby allows the generation of graphs tailored to particular domains.

The task-graphs (DAGs) generated by TGFF can be readily restricted to out-trees via user parameters. For example, a random out-tree can be generated by limiting the in-degree parameter to 1. Series-parallel graphs, graphs that consist of multiple chains of sequentially linked nodes, can be generated using the new algorithm. The resulting graphs may be viewed as a postscript file or using VCG. (An example comparing eps and vcg versions of TGFF output can be found here.)

Either periodic or aperiodic cases can be generated. For periodic
cases, the user specifies a set of integer * period-multipliers
* which determine the relative periods of the multiple task-graphs
in each case. For example, least-common multiple (LCM) solution
approaches can be hampered by choosing relatively prime numbers. A
period laxity factor is used to determine the relative laxity of the
task-graph's period with respect to the deadlines of its tasks.

Deadlines for each childless task within all task-graphs are
determined based on the task's level and a * deadline laxity
factor*. Challenging cases can be generated by making the
laxity small while relatively easier instances can be created by
making it large. For task-sets produced with TGFF's default
settings, there is no guarantee of feasibility for the schedules
produced. For another deadline setting approach, see the packed schedules feature. (Please note
that packed schedules may not be used with some of the new features.
Notably, the VCG output and series-parallel task graph options are
not available for packed schedules.)

Processor, communication, and task attributes can be declared and related in a correlated manner along with an inter-task communication data-size attribute.

The program and its internal pseudo-random number generator are written in C++ and are portable to architectures with 32 bit floating point numbers which have 24 bit mantissas. This allows researchers to generate identical task graphs, given identical parameters and input seeds, Enabling direct comparison of their schedulers/allocators. The program provides the primary output in a text file and also generates an encapsulated PostScript file depicting the graphs. An example of the PostScript output is shown at the top of this page.

Download the source code | Download paper (Old algorithm only) | Download documentation (pdf) |

Extension suggestions | Packed schedules | Version notes | Romanian translation of website by Aleksandra Seremina. |

Page maintained by Robert Dick.