class: center, middle # Abstract Graph Semantics for CnC ### Reasoning about optimization techniques .author[ .alert[Tiago Cogumbreiro], Kath Knobe, Zoran Budimlić, Vivek Sarkar] --- # Problem statement * **Objective:** Develop & verify compiler techniques for CnC * **Scope:** Application-specific optimization techniques * **Approach:** Formalize and verify the techniques, leverage existing work * **Outcome:** Propose a compilation technique for CnC --- # Methodology (related work) We follow the approach set forth by (Knobe & Budimlić CPC'13). 1. Compile the CnC spec to an application-specific IR 2. Analyze and transform the IR to optimize the application's execution --- # Redundant dependencies (CPC'13) .center.img-60[  ] --- # No redundant dependencies (CPC'13) .center.img-80[  ] --- class: center, middle # How do we assess the correctness of a graph transformation? --- # Contributions 1. A tool that optimizes a CnC spec: identifies data/control requirements that are known to be ready when the step executes; 2. A theory of abstract graph semantics for CnC. --- class: middle, center # A tool that optimizes a CnC spec --- # Tool * Given a CnC spec, generate the dynamic graph * Given the dynamic graph, identify *all* redundant dependencies * Return reduced graph --- # Smith-Waterman Example ``` [int A]; (single_corner:i,j) -> [A:i,j]; [A:i,j-1] -> (top:i,j) -> [A:i,j]; [A:i-1,j] -> (left:i,j) -> [A:i,j]; [A:i-1,j-1], [A:i-1,j], [A:i,j-1] -> (center:i,j) -> [A:i,j]; env::(single_corner:0,0); env::(top:0,{1 .. NW+1}); env::(left:{1..NH+1},0); env::(center:{1..NH+1},{1..NW+1}); ``` DFGR: an Intermediate Graph Representation for Macro-Dataflow Program (Sbîrlea et al, 2014) --- .center.img-80[  ] --- # Algorithm 1. For each `env` fragment, evaluate the expression and generate step instances. 2. For each step instance, generate "can-produce" edges. 3. For each control/data instance, generate "can-consume" edges. 4. Identify redundant dependencies. --- class: middle, center # A theory of abstract graph semantics for CnC --- # Related work * Concurrent Collections (Zoran et al, 2010) * Formalizes the internal execution of a step * "What can a step do?" versus "How can steps interact?" --- # Ideas behind the formalization **(I)** Define a CnC graph. **(II)** Define how the graph is "executed": * the external behavior of a step instance * the conditions to produce/consume data/control instances --- # I. Define an abstract CnC graph Bi-partite directed graph $G$ that models the producer-consumer relations of *runtime instances*. * nodes $c$ for **computation**: step instances * nodes $i$ for **information**: control and data instances * can-consume edges: $(i, c)$ computation $c$ requires information $i$ to run * can-produce edges: $(c, i)$ computation $c$ can produce information $i$ --- # Example of an abstract CnC graph .center.img-80[  ] --- # II. Define how the graph is "executed" **Operational semantics:** .highlight[a set of rules that defines how set of operations transform a state.] *Operations:* external behavior of a computation: e.g., $c$ produces $i$ *State:* the set of available information $I$ for a computation $c$; monotonically increasing --- # Specification of the abstract CnC semantics Given a set of available information $I$, and $c$ produces $i$, obtain $I \cup \{ i \}$, **if**: 1. the information required for $c$ is available: $\forall i': (i', c) \in G \implies i' \in I$ 2. computation $c$ can produce $i$ : $(c, i) \in G$ 3. information $i$ has not been produced: $i \notin I$ --- # Specification of the abstract CnC semantics (Math) Given a graph $G$, let the reduction relation: $$I_1 \rightarrow^{c,i} I_2$$ For $I_1$, computation $c$ produces $i$, resulting in $I_2$, defined as: $$ \frac{ \forall i': (i', c) \in G \implies i' \in I \qquad (c, i) \in G \qquad i \notin I }{ I \rightarrow^{c, i} I \cup \{ i \} } $$ --- # Claim 1 ## If we preserve the connectivity of the graph, then the semantics are preserved. Let $\rightarrow^*$ be the reflexive, transitive closure of $\rightarrow^{c, i}$ for some $c$ and $i$. Let $G$ and $G'$ have the same reachability relation. If $I_1 \rightarrow^{c, i} I_2$ in G, then there exists an $I_3$ *s.t.* $I_1 \rightarrow^* I_3 \rightarrow^{c,i} I_2$. --- # Transitive Reduction [The Transitive Reduction of a Directed Graph](http://epubs.siam.org/doi/abs/10.1137/0201008). (Aho et al, 1972) * Creates the smallest graph that maintains the same reachability relation. * Complexity: O($n^3$) time, where $n$ is the number of nodes. --- class: middle, center # Extending the abstract semantics ## How much can we use this level of abstraction? --- # Example: Speculative execution * Step instance attributes: data-ready, control-ready * Data instance attributes: speculative-available * If data-ready, then execute + mark as speculative ready <br/> .note[Allows executing data-ready, but not control-ready!] * Asynchronous Checkpoint/Restart for CnC [Vrvilo '13] --- # Example: Allowing data-ready execution Theoretically, * Attributes can be represented as predicates over nodes .highlight[Speculative execution:] $$ \frac{ \forall i': (i', c) \in G \color{red}{\land \mathrm{DataReady}(i)} \implies i' \in I \quad (c, i) \in G \quad i \notin I }{ I \rightarrow^{c, i} I \cup \{ i \} } $$ --- # Future work * Static analysis: can we move our analysis to the static graph? * Speculative execution * Garbage collection of "dead" nodes --- # Conclusion * A tool that optimizes a CnC spec: identifies data/control requirements that are known to be ready when the step executes; * A theory of abstract graph semantics for CnC. --- class: center, middle # Abstract Graph Semantics for CnC ### Reasoning about optimization techniques .author[ .alert[Tiago Cogumbreiro], Kath Knobe, Zoran Budimlić, Vivek Sarkar]