Extracted Features
[!NOTE] Motivation "Weak" features, such as FLOP and bytes of memory moved, are not enough to reliably predict the runtime of operators. For instance, ReLU and Conv2D might be implemented with the same number of FLOPs, but the first will have a significantly shorter runtime.
SDFG Philosophy
From https://spcldace.readthedocs.io/en/v0.16/sdfg/ir.html:
The central tenet of our approach is that understanding and optimizing data movement is the key to portable, high-performance code. In a data-centric programming paradigm, three governing principles guide execution:
- Data containers must be separate from computations.
- Data movement must be explicit, both from data containers to computations and to other data containers.
- Control flow dependencies must be minimized, and only define execution order if no implicit dataflow is given.
The feature encoding scheme described below exploits this explicit symbolic representation: loop bounds, memory access patterns, and control flow conditions are all expressed as symbolic affine expressions over a set of program parameters, which the extractor converts into fixed-size numerical vectors suitable for GNN consumption.
Encoding Fundamentals
Before describing individual node and edge features, we introduce three foundational concepts that underpin the entire encoding.
Tracked Symbols
In an SDFG, a symbol is a scalar integer-typed container. Symbols appear in loop bounds, conditions, and memory access expressions. They can be external (compile-time-unknown problem size parameters like N, M) or internal (transient loop induction variables like i, j):
foo(int N) { // N is an external symbol
int i = 0; // i is an internal symbol
for (i = 0; i < N; i++) {
A[i] = B[i - 1] // both i and N appear in memory access subsets
}
}
Crucially, the same symbol can appear in both control flow (as a loop bound) and data flow (as an array index), which allows the GNN to learn this connection.
Before extracting any per-node features, the extractor performs a global analysis pass over the entire SDFG to identify the \(K = 10\) most frequently referenced symbols. These are called tracked symbols.
The selection procedure is:
- Count the frequency of every symbol across all SDFG elements (loop bounds, conditions, memlet subsets).
- Sort by descending frequency, then lexicographically to break ties.
- Keep the top \(K = 10\).
[!NOTE] Global, not per-node The tracked symbol list is determined once per SDFG and remains fixed for all subsequent per-node and per-edge encodings. Different SDFGs may have different tracked symbol orderings.
Tracked symbols receive dedicated coefficient dimensions in every affine encoding (assignments, conditions, subsets). Any symbolic expression is projected onto this fixed basis of \(K\) symbols. If an expression references only symbols outside the top-\(K\), it can only be indicated via an untracked flag.
Affine Expression Encoding
The atomic building block of the entire feature representation is a \((K+2)\)-dimensional vector encoding an affine expression over the \(K\) tracked symbols:
| Dimension | Content | Fallback | Example for 2*N + 3*M - 5 |
|---|---|---|---|
| \(0 \ldots K{-}1\) | Coefficient \(c_i\) for each tracked symbol \(s_i\) | -1 if not an integer |
[2, 3, 0, 0, 0, 0, 0, 0, 0, 0] |
| \(K = 10\) | Constant offset \(c_{\text{const}}\) | -1 if not an integer |
-5 |
| \(K{+}1 = 11\) | Validity flag | context-dependent | 0 |
With \(K = 10\), each affine expression is a 12-dimensional vector. This \((K{+}2)\)-vector appears throughout assignments, conditions, and subset encodings.
Note that a genuine integer coefficient of -1 (e.g., the coefficient of i in N - i) is indistinguishable from the non-integer sentinel at the feature level. In practice this is acceptable because non-integer coefficients are extremely rare in the SDFGs produced from neural network models.
[!NOTE] Validity flag semantics The validity flag at dimension \(K{+}1\) differs by context:
- Assignments and subsets:
0= valid affine,+1= expression is not polynomial or not affine over the tracked symbols.- Conditions: This position doubles as the relational operator encoding (
1===,2=<=,3=<), with-1indicating an invalid or non-representable literal.
Normalization
All feature values (coefficients, constants, flags) are normalized using log-1p compression before being stored:
This prevents large symbolic coefficients (e.g., array sizes in the millions) from dominating the feature space while preserving sign information.
Node Features
Each node in the feature graph has a fixed-size vector of 1109 dimensions. Different node types populate different non-overlapping segments of this vector; unused segments remain zero.
Feature Overview
The table below shows the dimensions of the building-block encodings and how they compose into the more complex for-entry and map-entry features.
| Symbol | Meaning | Formula | Value | Notes |
|---|---|---|---|---|
| \(s_{max}\) | max tracked symbols | 10 | 10 | Top-\(K\) symbols selected globally |
| \(\vee_{max}\) | max CNF ands | 5 | 5 | |
| \(\wedge_{max}\) | max CNF ors | 5 | 5 | |
| \(a_{max}\) | max assignments | \(s_{max}\) | 10 | One block per tracked symbol |
| \(d_{max}\) | max dimensions | 10 | 10 | For subset/memlet encoding |
| \(f_a\) | assignment num features | \(1 + (s_{max} + 2)\times a_{max}\) | 121 | \(a_{max}\) blocks of \((K{+}2)\)-vectors + 1 untracked flag |
| \(f_c\) | condition num features | \(1+(s_{max} + 2)\times (\vee_{max} \times \wedge_{max})\) | 301 | CNF tensor \(5 \times 5 \times 12\) + 1 overflow flag |
| \(f_{fe}\) | for-entry num features | \(1 + 2 \times f_{a} + f_{c}\) | 544 | 1 marker + init(\(f_a\)) + condition(\(f_c\)) + update(\(f_a\)) |
| \(f_{me}\) | map-entry num features | \(1 + 2 \times f_{a} + f_{c}\) | 544 | Identical structure to for-entry |
| \(f_{an}\) | access node features | 3 | 3 | Container ID + type + primitive type |
| \(f_{ln}\) | metadata/library node features | 2 + 8 | 10 | Marker + side-effect flag + 8-dim hash |
Feature Indices
The feature vector is partitioned by node type. Each node type occupies a contiguous range; within that range, a value of 1 in the first position serves as a type marker (one-hot indicator).
| Index | Node Type | Description |
|---|---|---|
| \(0\) | Block entry | Value of 1 indicates the entry point of a basic block of dataflow operations. |
| \(1\) | Block exit | Value of 1 indicates the exit point of a basic block. |
| \(2\) | Sequence entry | Value of 1 indicates the entry to a sequence of control flow nodes. |
| \(3\) | Sequence exit | Value of 1 indicates the exit from a sequence of control flow nodes. |
| \(4\) | Transition | Value of 1 indicates a state transition node (connects sequential control flow regions; assignments may be encoded on the corresponding edge). |
| \(5\) | For entry marker | Value of 1 indicates the entry to a for loop. |
| \(6 - 548\) | For entry body | See For/Map entry decomposition below. |
| \(549 = 5 + f_{fe}\) | For exit | Value of 1 indicates the exit from a for loop. |
| \(550\) | Map entry marker | Value of 1 indicates the entry to a parallel map. |
| \(551 - 1093\) | Map entry body | Identical structure to the for-entry body. Maps are parallel for-loops without loop-carried dependencies. |
| \(1094 = 550 + f_{me}\) | Map exit | Value of 1 indicates the exit from a parallel map. |
| \(1095\) | Access node container ID | Encodes a memory access (read or write) to a data container. This index stores a unique container ID. |
| \(1096 - 1097\) | Access node type | The container type (i.e. Scalar, Array, Pointer, Structure, Function) and its primitive data type (e.g. int64). |
| \(1098 = 1095 + f_{an}\) | Tasklet node | Encodes a simple computation as a hashed operation code (e.g. add, sub, mul, etc.). |
| \(1099\) | Library node marker | Value of 1 indicates a metadata node representing a call to an external operator, e.g. sin() from a math library. |
| \(1100\) | Side effect flag | A -1 if the metadata node has a side effect, 1 if it does not. |
| \(1101 - 1108\) | Hashed operator ID | As there is an open-ended / unknown set of such operators, hashing is used to give each operator a unique numerical fingerprint. |
For/Map Entry Decomposition (544 dimensions)
The for-entry and map-entry nodes carry the richest feature encoding. Their 544 dimensions decompose into a type marker, an initialization assignment, a loop condition, and an update assignment.
For Entry (absolute indices 5–548):
| Absolute Index | Size | Content |
|---|---|---|
| \(5\) | 1 | Type marker (always 1) |
| \(6 - 126\) | 121 | Init assignment (\(f_a\)): 10 symbol blocks of 12 + 1 untracked flag |
| \(127 - 427\) | 301 | Condition (\(f_c\)): 25 literal blocks of 12 + 1 overflow flag |
| \(428 - 548\) | 121 | Update assignment (\(f_a\)): 10 symbol blocks of 12 + 1 untracked flag |
Map Entry (absolute indices 550–1093) — identical layout shifted by +545:
| Absolute Index | Size | Content |
|---|---|---|
| \(550\) | 1 | Type marker |
| \(551 - 671\) | 121 | Init assignment |
| \(672 - 972\) | 301 | Condition |
| \(973 - 1093\) | 121 | Update assignment |
Assignment encoding (\(f_a = 121\) dimensions):
An assignment block encodes \(\{symbol := expression\}\) pairs (e.g., i := 0 for init, i := i + 1 for update). The encoding is a flat vector of 121 values: 10 contiguous blocks of 12 features followed by a single trailing flag.
Each of the 10 blocks corresponds to a tracked symbol as an assignment target (the LHS). Block \(k\) answers: "is tracked symbol \(s_k\) being assigned a value here?" If yes, the 12 features encode the RHS — what \(s_k\) is being set to — as a \((K{+}2)\)-vector expressing the right-hand side in terms of all tracked symbols. If \(s_k\) is not assigned, the block is all zeros.
- Block \(i\) (12 values):
- Dims 0–9: integer coefficient per tracked symbol, or
-1if coefficient is non-integer - Dim 10: integer constant term, or
-1if non-integer - Dim 11 (validity flag):
0= valid affine;+1= RHS is not a polynomial (e.g., involves division) or not affine (e.g.,i * j, degree > 1). For typical assignments likei := 0ori := i + 1, this stays0.
- Dims 0–9: integer coefficient per tracked symbol, or
- Index 120 (untracked flag):
-1if there exists an assignment to a symbol not in the tracked set,0otherwise.
For a for-loop for (i = ...; ...; i = ...), the init and update each produce a single assignment {indvar := expression}. If the induction variable is tracked symbol \(s_k\), block \(k\) is populated. If the induction variable is not among the top-10 tracked symbols, all 120 coefficient values remain zero and the only signal the GNN receives is the untracked flag at index 120 being set to -1. In larger SDFGs with many symbols, this is a common case.
Condition encoding (\(f_c = 301\) dimensions):
The loop condition (e.g., i < N) is converted to Conjunctive Normal Form (CNF) and encoded as a flattened \(5 \times 5 \times 12\) tensor plus one overflow flag:
- 5 AND-clauses, each containing up to 5 OR-literals.
- Each literal (12 values): The extractor computes \(P = \text{LHS} - \text{RHS}\) and stores its affine coefficients over the tracked symbols:
- Dims 0–9: integer coefficient per tracked symbol, or
-1if non-integer - Dim 10: integer constant term, or
-1if non-integer - Dim 11: serves as both relational operator and validity flag:
- Dims 0–9: integer coefficient per tracked symbol, or
| Value | Meaning |
|---|---|
0 |
inactive (padding — no literal in this slot) |
1 |
equality (==) |
2 |
less-than-or-equal (<=) |
3 |
strictly-less-than (<) |
-1 |
invalid: non-relational, not polynomial, or not affine |
- Index 300 (trailing flag):
+1if the CNF has more than 5 AND-clauses or any clause has more than 5 OR-literals (overflow).
Reference: C++ header constants
constexpr size_t MAX_SYMBOLS = 10;
constexpr size_t MAX_CNF_ANDS = 5;
constexpr size_t MAX_CNF_ORS = 5;
constexpr size_t MAX_ASSIGNMENTS = MAX_SYMBOLS;
constexpr size_t MAX_DIMS = 10;
constexpr size_t CONDITION_NUM_FEATURES =
(MAX_SYMBOLS + 2) * (MAX_CNF_ANDS * MAX_CNF_ORS) + 1;
constexpr size_t ASSIGNMENT_NUM_FEATURES =
(MAX_SYMBOLS + 2) * MAX_ASSIGNMENTS + 1;
constexpr size_t FOR_ENTRY_NUM_FEATURES =
1 + 2 * ASSIGNMENT_NUM_FEATURES + CONDITION_NUM_FEATURES;
enum NodeDim {
BLOCK_ENTRY = 0,
BLOCK_EXIT = BLOCK_ENTRY + BLOCK_ENTRY_NUM_FEATURES,
SEQUENCE_ENTRY = BLOCK_EXIT + BLOCK_EXIT_NUM_FEATURES,
SEQUENCE_EXIT = SEQUENCE_ENTRY + SEQUENCE_ENTRY_NUM_FEATURES,
TRANSITION = SEQUENCE_EXIT + SEQUENCE_EXIT_NUM_FEATURES,
FOR_ENTRY = TRANSITION + TRANSITION_NUM_FEATURES,
FOR_EXIT = FOR_ENTRY + FOR_ENTRY_NUM_FEATURES,
MAP_ENTRY = FOR_EXIT + FOR_EXIT_NUM_FEATURES,
MAP_EXIT = MAP_ENTRY + MAP_ENTRY_NUM_FEATURES,
ACCESS_NODE = MAP_EXIT + MAP_EXIT_NUM_FEATURES,
TASKLET_NODE = ACCESS_NODE + ACCESS_NODE_NUM_FEATURES,
LIBRARY_NODE = TASKLET_NODE + TASKLET_NODE_NUM_FEATURES,
};
Edge Features
Each edge in the feature graph has a fixed-size vector of 676 dimensions. Edge features describe the relationship between the two nodes they connect. They are crucial for representing both control flow (the order of operations) and data flow (the movement of data). Every forward edge type has a corresponding backward edge to enable bidirectional message passing in the GNN.
Feature Overview
Similar to nodes, edge features are composed of several components. The most complex are the dataflow edge (encoding memory access patterns) and the condition edge (encoding boolean expressions on control flow transitions).
| Symbol | Meaning | Formula | Value |
|---|---|---|---|
| \(f_{tr}\) | transition forward num features | \(1 + f_a\) | 122 |
| \(f_{cd}\) | condition forward num features | \(1 + f_c\) | 302 |
| \(f_{df}\) | dataflow forward num features | \(3 + 2 \times ((s_{max} + 2) \times d_{max} + 1)\) | 245 |
Feature Indices
The edge feature vector is partitioned based on the EdgeDim enum.
| Index | Edge Type | Description |
|---|---|---|
| \(0\) | Control Flow Forward | A value of 1 indicates a simple, unconditional forward control flow edge. |
| \(1\) | Control Flow Backward | The corresponding backward edge. Enables bidirectional message passing in the GNN. |
| \(2\) | CF Transition Forward marker | A value of 1 indicates a transition edge carrying variable assignments. |
| \(3 - 123\) | CF Transition Forward body | Assignment encoding (\(f_a = 121\) features) using the same representation as node assignments. Encodes state changes on the transition (e.g. i=i+1). |
| \(124\) | CF Transition Backward | The corresponding backward edge for a transition. |
| \(125\) | CF Condition Forward marker | A value of 1 indicates a conditional control flow edge (e.g., an if-else branch guard). |
| \(126 - 426\) | CF Condition Forward body | Condition encoding (\(f_c = 301\) features) using the same CNF representation as node conditions. Encodes the boolean expression guarding this control flow path. |
| \(427\) | CF Condition Backward | The corresponding backward edge for a conditional edge. |
| \(428\) | CF Loop Forward | A value of 1 indicates a loop-back control flow edge (the back-edge of a for/while loop). |
| \(429\) | CF Loop Backward | The corresponding backward edge for a loop-back edge. |
| \(430 - 674\) | Dataflow Edge Forward | Encodes a data dependency. See Dataflow edge decomposition below. |
| \(675\) | Dataflow Edge Backward | The corresponding backward edge for a dataflow dependency. |
Dataflow Edge Decomposition (245 dimensions)
A dataflow edge (memlet) connects an access node to a tasklet or another access node. It encodes what data moves and which subset of a container is accessed at the source and destination.
| Sub-range (within 430-674) | Size | Content |
|---|---|---|
| \(430\) | 1 | Position of the input in the destination's connector list |
| \(431\) | 1 | Source connector type (1=void, 2=ref, 3=deref) |
| \(432\) | 1 | Destination connector type |
| \(433 - 553\) | 121 | Source memory access subset (begin_subset) |
| \(554 - 674\) | 121 | Destination memory access subset (end_subset) |
Subset Encoding (121 dimensions per subset)
A subset describes a multi-dimensional memory access pattern (e.g., A[i, 0:N, j+1]). Each dimension of the access is encoded as a \((K{+}2)\)-vector, giving a \(d_{max} \times (K{+}2)\) matrix plus one overflow flag:
- Row \(d\) (12 values): The affine encoding of the access expression for dimension \(d\):
- Dims 0–9: integer coefficient per tracked symbol, or
-1if non-integer - Dim 10: integer constant term, or
-1if non-integer - Dim 11:
0= valid affine;+1= expression is not polynomial or not affine
- Dims 0–9: integer coefficient per tracked symbol, or
- Index 120 (trailing flag):
+1if the subset has more than \(d_{max} = 10\) dimensions (dimension overflow — access pattern is truncated).
Note: both assignment and subset blocks are 121 features with a trailing flag at index 120, but the semantics differ: assignments use -1 for "untracked symbol assigned", while subsets use +1 for "too many dimensions."
This gives \(10 \times 12 + 1 = 121\) features per subset, and the full dataflow forward edge uses \(3 + 2 \times 121 = 245\) features.
Worked Example: Encoding a For-Loop Node
Consider a for-loop from an SDFG where the global tracked symbols (sorted by frequency) are [N, M, i, j, k, ...]. The loop is:
for (i = 0; i < N; i = i + 1)
Here, i is tracked symbol index 2 and N is tracked symbol index 0.
Step 1 — Initialization assignment (i := 0):
The init assignment block has 121 features (absolute indices 6–126 for For). Since i is tracked symbol 2, block 2 encodes the RHS 0:
Block 2: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
^coeff(N)=0 ^coeff(i)=0 ^const=0 ^valid(0=affine)
All other blocks are zero (no other symbols are assigned). Index 120 (untracked flag) = 0.
Step 2 — Condition (i < N):
The condition is a single CNF clause with one literal (absolute indices 127–427 for For). The extractor computes \(P = i - N\) and encodes P < 0:
AND-clause 0, OR-literal 0 (indices 0-11 within the condition block):
[−1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 3]
^coeff(N)=-1 ^coeff(i)=1 ^const=0 ^operator=3 (strict <)
All other clause/literal slots are zero (inactive, operator = 0). Index 300 (overflow flag) = 0.
Step 3 — Update assignment (i := i + 1):
Block 2 of the update assignment block (absolute indices 428–548 for For) encodes the RHS i + 1:
Block 2: [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0]
^coeff(i)=1 ^const=1 ^valid(0=affine)
Step 4 — Normalization:
All non-zero values pass through \(y = \text{sign}(x) \cdot \log(1 + |x|)\). For example, the coefficient 1 becomes \(\log(2) \approx 0.693\), and -1 becomes \(-\log(2) \approx -0.693\).
Questions for the next version
- Why is SDFG specially good for runtime prediction, or for performance estimation in general (also against other Dataflow formats)?
- Eventually look at the papers from Lukas
- SDFG vs other dataflow formats
Relevant Sources
- https://spcldace.readthedocs.io/en/v0.16/sdfg/ir.html
- https://arxiv.org/pdf/2303.08142
- https://arxiv.org/pdf/2412.20179