Windows Version of TGFF 3.1 (binary only)
Original design: David Rhodes and Robert Dick.
Subsequent development: Keith Vallerio.
Task Graphs For Free (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. |
Artur Weber contacted me by email and offered to translate this webpage to Portuguese. This is the result. I do not know Artur so please exercise caution if you follow the link.
Page maintained by Robert Dick.
