dag-gen-rnd --- A randomized multiple Direct Acyclic Graph (DAG) task generator designed for scheduling and allocation research in parallel and multi-core computing.
dag-gen-rnd supports both command line (daggen-cli) and graphical user interface (daggen-gui; in development). This generator can be easily configured through a .json file and is highly extensible for other purposes.
Supported generation algorithms:
nfj: Nested fork-joinrnd: standard randomized DAG (layer-by-layer)rnd_legacy: default randomized DAG
The utilization generation is based on:
- UUnifast
- UUnifast-discard
Python >= 3.7NetworkX >= 2.4Matplotlib >= 3.1.3pygraphviz >= 1.5numpy >= 1.17tqdm >= 4.45.0pyqt5(optional for GUI)
Install dependencies using apt:
$ sudo apt install python3-dev graphviz libgraphviz-dev pkg-config xdot
Execute these commands to create a python virtual environment:
$> pip3 install env
$> python3 -m venv env
$> source env/bin/activate
$> python3 -m pip install --upgrade pip
$> python3 -m pip install --upgrade Pillow
$> pip3 install -r requirements.txt
(Optional) To use the GUI, you need to install Qt5 for python:
$ sudo apt install python3-pyqt5
Use the configuration file config.json to configure parameters.
To generate single DAG task, set multi-DAG=false, then in single_task:
multi-DAG: falseset_number: number of dags to be generatedfname_prefixandfname_int_sufix: the resulting filename isfname_prefix``fname_int_sufix. DONT USE '-' or '_' in the resulting filename since it will affect the automation flow.dummy_source_and_sink: use it always false since tasks w time 0 will crash when running SCHED_DEADLINE
When generating single DAGs:
max_period: end to end period in ns,max_cpu_load: max cpu load. cpu load is the sum of all task runtime divided by the dag periodmin_cpu_load: min cpu loadmax_bytes: max number of bytes send per message,random_non_scalable_C: boolean indicating whether the non scalable part of C is randomized, up to 10% the size of C. If false, it will be zero.
These are the extensions to represent hardware accelerated tasks, specially FPGA with dynamic partial reconfiguration support:
max_acc_tasks: max number of tasks to be randomized.;hw_idx: this refers to the numerical FRED id of each hw task, which typically starts with 100. You can find this id in thehw_tasks.csv, generated by DART. Take thishw_tasks.csvfile as an example:
mat_mult_128, 100, 100000, p0, dart_fred/bits, 131072, 131072, 131072
mat_mult_64, 101, 100000, p0, dart_fred/bits, 32768, 32768, 32768
It says that the 1st ha task has FRED id 100 and the 2nd one id 101.
hw_C: a list of int representing the WCET of the hardware accelerated tasks;sw_C: is the same as the previous one, but for the software counterpart such that the speedup for hardware acceleration is defined ashw_C/sw_C;reconf_us: a list of int representing the Worst-Case time to configure the task partition. This time depends on the bitstream size.
Here is an example where a single IP can be inserted up to twice in the DAG:
"fpga": {
"max_acc_tasks": 2,
"hw_idx": [100],
"hw_C": [5000],
"reconf_us": [1000]
}
And this is another example where again a DAG can have up two hw tasks, but in this case, there are two different tasks to be chosen. Each task with its ID, C, and reconfiguration time. Note that, in this example, both hw tasks have the same reconf time, meaning that these tasks most probaly share the same reconfigurable region, i.e., they are not run in parallel.
"fpga": {
"max_acc_tasks": 2,
"bitstream_config_us": 1000,
"hw_idx": [100,101],
"hw_C": [5000,15000],
"reconf_us": [1000,1000]
}
When hw_tasks is used instead of max_acc_tasks, then there is no randomization for chosing the number of IPs and which IPs are placed. Take the following example:
"fpga": {
"hw_tasks": 2,
"hw_idx": [100,101],
"hw_name": ["mat128","mat64"],
"sw_C": [36333000,2807000],
"hw_C": [ 4489000,1323000],
"hw_idle_power": [1.14,0.88],
"hw_busy_power": [1.19,0.9],
"reconf_us": [27696000,27696000]
}
This example says that each DAG must have two IPs where the first one is IP mat128 and the second one is IP mat64. The only randomization happens when chosing the DAG node representing the IPs.
Note that the parameters hw_name, hw_idle_power, hw_busy_power are currently not being used but they will be important when supporting custom hardware designs for dag.c.
The following parameters are used to control the DAG size. First, it randomizes the number of layers in the graph, between layer_num_min and layer_num_max. Then, for each layer, it randomizes the number of nodes of the layer according to parallelism. The parameter connect_prob controls the edge density. It should be a value lower than 1.0.
There is a simple feasibility generated run for the generated DAG such that this DAG is more likely, but not guaranteed,to be have a feasible task placement. This check is important, otherwise dag-rand-gen would generate lot's of unfeasible DAGs and we would need to manually check for each DAG if it is actually unfeasible, wasting a lot of time. With this check, the vast majority of the generated DAG is feasible. However, some DAGs, specially for bigger DAGS with more tasks then the number of cores, could be unfeasible.
The process is like this. After the DAG structure is defined, there is a step that assigns random runtime to the tasks. The sum of the tasks runtime is then normalized according to the DAG period max_period.
All times are assuming that their tasks are placed on a CPU island with capacity 1.0. Note that, when running the optimization, the platform model must include a CPU island with capacity 1.0. Otherwise, the random dag generator would require additional inputs, like the capacity of all platform island, making it more complex and less reusable.
Then, assuming that all task could be placed on this island with capacity 1.0, which is obvioulsy a simplistic assumption, it calculates the longest path in the DAG. This path must be shorted than the DAG end-to-end deadline, which is currently set equals to the DAG period max_period. If this is not the case, the DAG is discarded.
When there are islands representing hardware accelerators, as long as the capacity for their islands is greater than 1.0 and the accelerator does not have frequency scaling, it is guaranteed that if a task is assigned to an accelerator, it's runtime will be only faster than the runtime assuming the CPU island with capacity 1.0. This way, the feasibility still holds.
In the future, when the model and experimental is expanded to support frequency scaling in the hardware accelerators, it is just a matter to ensure that the task runtime assuming the accelerator at its lowest frequency is lower than the runtime assuming the CPU island with capacity 1.0.
Until now, we have not tested scenarios with multiple FPGA slots, where each slot would be considered a different slides. Thus, this daggen is only supporting single slot hw designs.
First, change the configurations in config.json. Then, depending on your perference:
$ python3 src/daggen-cli.py
Here are some simple examples of generated DAGs:
or more complicated DAGs:
- This code is not tested on Windows, but it should not have too many problems. The only potential issue is that the difference is in folder naming where Windows uses a backslash (
\), instead of a forwardslash (/). I will test it and make it compatitable in the future. - In some cases, the critical path could be larger than the period.
- Shuai Zhao, Xiaotian Dai, Iain Bate. "DAG Scheduling and Analysis on Multi-core Systems by Modelling Parallelism and Dependency". Transactions on Parallel and Distributed Systems (TPDS). IEEE. 2022.
- Shuai Zhao, Xiaotian Dai, Iain Bate, Alan Burns, Wanli Chang. "DAG scheduling and analysis on multiprocessor systems: Exploitation of parallelism and dependency". In Real-Time Systems Symposium (RTSS), pp. 128-140. IEEE, 2020.
Please use the following citation if you use this code for your work:
Xiaotian Dai. (2022). dag-gen-rnd: A randomized multi-DAG task generator for scheduling and allocation research (v0.1). Zenodo. https://doi.org/10.5281/zenodo.6334205
BibTex:
@software{xiaotian_dai_2022_6334205,
author = {Xiaotian Dai},
title = {{dag-gen-rnd: A randomized multi-DAG task generator
for scheduling and allocation research}},
month = mar,
year = 2022,
publisher = {Zenodo},
version = {v0.1},
doi = {10.5281/zenodo.6334205},
url = {https://doi.org/10.5281/zenodo.6334205}
}
This software is licensed under MIT. See LICENSE for details.
