Extended Task Graph

This is an implementation of the Extended Task Graph (ETG) intermediate representation for C/C++, built as an extension for the Clava C/C++ to C/C++ Source-to-source compiler. Just like the compiler itself, it is packaged and distributed as an NPM package, which can be either used as a standalone app or as a library for other Clava-based NPM projects.

These task graphs are automatically analyzed and characterized by several metrics, and through a highly flexible granularity mechanism we can perform extensive graph operations, such as task merging, splitting and clustering, while always outputting valid and readable C/C++ source code.

Extended Task Graph of the edge detection application in this file

How to install

1. Start by installing these prerequisites. The ETG is developed and validated on Ubuntu 24.x, but it should work on all other OS supported by Clava and node.js. Make sure you have node.js 18 or higher installed, and optionally Graphviz to render/visualize the task graphs. For Ubuntu:

apt update && apt upgrade -y
sudo apt install graphviz curl -y
curl -fsSL https://deb.nodesource.com/setup_current.x | bash -
apt install -y nodejs
node -v && npm -v

2. Now, you need to create an NPM workspace for both the ETG and your own Clava-based NPM project (replace my-proj by your project's name):

PROJ_NAME=my_proj  # change this
mkdir clava-workspace
cd workspace
mkdir $PROJ_NAME
git clone https://github.com/specs-feup/extended-task-graph
git clone https://github.com/tiagolascasas/clava-js-code-transforms
cat <<EOF > package.json
{
  "name": "clava-workspace",
  "version": "1.0.0",
  "private": true,
  "workspaces": [
    "extended-task-graph",
    "clava-js-code-transformations",
    "$PROJ_NAME"
}
EOF
npm install
cd clava-js-code-transforms
npm run build
cd ../extended-task-graph
npm run build
cd ..

3. In your project folder, make sure you are including both the Clava package, as well as the ETG package. An easy way to bootstrap your Clava-based project is to use this template. Regardless, make sure you end up with a package.json whose name field matches the name of the folder and with these two dependencies:

{
    "name": "my_proj",
    "dependencies": {
        "@specs-feup/clava": "3.0.1",
        "extended-task-graph": "^1.0.0",
    }
}

4. In your own project, you can begin to use both the Clava API and the ETG for your own purposes. You can check the examples in this folder to see how to use the ETG API in your own scripts. You can run these examples examples by going to the extended-task-graph directory and running npm run, which lists the command required for each use case (e.g., npm run simple:etg generates an ETG for a provided edge detection application).

Outputs

Under normal usage (i.e., running the entire flow from code preprocessing, task graph generation and subsequent extraction of metrics) the extension outputs the following folders:

<app name>
├── ast
│   ├── original - some metrics about the original application's source code, as well as its call graph and AST
│   ├── trans - same as the above, but after applying all code preprocessing transformations
│   ├── <label> - a dump explicitly triggered by the user, using a subfolder name provided by them
│   └── <...>
├── etg 
│   ├── default - a dotfile dump of the task graph generated by the graph generation flow, prior to any user transformations
│   ├── <label> - a task graph dump explicitly triggered by the user, possibly after applying transformations, using a subfolder name provided by them
│   └── <...>
└── src
    ├── golden - source code of the original program. It differs from the input only in that all macros have been resolved
    ├── inter
    │   ├── t0-normalization - source code after applying the normalization transformation (which is always the first)
    │   ├── t1-array-flattening - source code after applying the 1st transformation of the provided recipe (e.g., array flattening by default)
    |   ├── t2-constant-folding-propagation
    |   ├── t3-struct-decomposition
    │   └── tn-<label>
    ├── subset - source code after the preprocessing transformations are applied, except for function outlining
    ├── trans - source code after applying function outlining, i.e., a valid representation for generating task graphs
    ├── trans_instr - the same as the above, but with time measuring instrumentation for each function. Useful for profiling
    ├── <label> - source code output explicitly triggered by the user, possibly after applying transformations, using a subfolder name provided by them
    └── <...>

Citing this work

If you found our work useful, please consider citing it as follows:

@inproceedings{10.1145/3652032.3657580,
     author = {Santos, Tiago and Bispo, Jo\~{a}o and Cardoso, Jo\~{a}o M. P.},
     title = {A Flexible-Granularity Task Graph Representation and Its Generation from C Applications (WIP)},
     year = {2024},
     isbn = {9798400706165},
     publisher = {Association for Computing Machinery},
     address = {New York, NY, USA},
     url = {https://doi.org/10.1145/3652032.3657580},
     doi = {10.1145/3652032.3657580},
     booktitle = {Proceedings of the 25th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems},
     pages = {178–182},
     numpages = {5},
     keywords = {FPGA, Hardware Accelerators, Hardware/Software Partitioning, Source-to-Source Compiler, Task Graph},
     location = {Copenhagen, Denmark},
     series = {LCTES 2024}
}