# Improving Symbolic System-Level Synthesis by Solver Coordination and Domain-Specific Heuristics
## 4 System Model
### Application Model
Similar to computational tasks, each packet \(p\in\mathbf{P}^{m}\) of a message \(m\in\mathbf{T}_{i}^{m}\) that is routed on a tree of resources \(\mathbf{R}_{\text{route}}^{p}\subseteq\mathbf{R}_{ii}\cup\mathbf{R}_{rtr}\) of the NoC is assigned a start time \(s_{p}^{*}\) in a time-triggered schedule on each resource \(r\in\mathbf{R}_{\text{route}}^{p}\). Concerning the topology of applications graphs \(g_{i}^{A}\), as mentioned earlier, the paper at hand investigates a particular class of graphs, namely two terminal series-parallel (TTSP) application graphs [8]. Note that the graph depicted in Figure 4 is a TTSP application graph, as well as the yellow shaded sub-graphs. The TTSP application graphs capture the currently considerable sequential nature of control applications from the automotive domain as well as allow us to model the results of parallelizing these applications. The class of TTSP application graphs is defined recursively as follows:  
**Definition 1**. : _Two terminal series-parallel (TTSP) application graph (adapted from [8]):_  
1. _An application graph_ \(g_{i}^{A}\) _with two computational tasks_ \(t,\tilde{t}\in\mathbf{T}_{i}^{t}\) _exchanging one message_ \(m\in\mathbf{T}_{i}^{m}\) _is a TTSP application graph._
2. _If the application graphs_ \(g_{j}^{A}\) _and_ \(g_{k}^{A}\) _are TTSP application graphs, so is the resulting application graph of the following two operations:_ 1. _Two terminal parallel composition: Replace the source computational task_ \(t_{\text{src}}\in\mathbf{T}_{j}^{t}\) _of TTSP graph_ \(g_{j}^{A}\) _with the source computational task_ \(t_{\text{src}}\in\mathbf{T}_{k}^{t}\) _of TTSP graph_ \(g_{k}^{A}\) _and replace the sink computational task_ \(t_{\text{snk}}\in\mathbf{T}_{j}^{t}\) _of_ \(g_{j}^{A}\) _with the sink computational task_ \(t_{\text{snk}}\in\mathbf{T}_{k}^{t}\) _of_ \(g_{k}^{A}\)_._ 2. _Two terminal series composition: Replace the sink computational task_ \(t_{\text{snk}}\in\mathbf{T}_{j}^{t}\) _of TTSP graph_ \(g_{j}^{A}\) _with the source computational task_ \(\tilde{t}_{\text{src}}\in\mathbf{T}_{k}^{t}\) _of TTSP graph_ \(g_{k}^{A}\)_._  
The source computational task \(t_{\text{src}}\) of a TTSP application graph \(g_{i}^{A}\) is the computational task which is not connected to a message via an incoming edge, i.e., \(t_{\text{src}}\in\mathbf{T}_{i}^{t},\forall m\in\mathbf{T}_{i}^{m}:\tilde{ \exists}(m,t_{\text{src}})\in\mathbf{E}_{i}^{A}\). Similar, the sink computational task \(t_{\text{snk}}\) of a TTSP application graph \(g_{i}^{A}\) is the computational task with no outgoing edge to a message, i.e., \(t_{\text{snk}}\in\mathbf{T}_{i}^{t},\forall m\in\mathbf{T}_{i}^{m}:\tilde{ \exists}(t_{\text{src}},m)\in\mathbf{E}_{i}^{A}\). As an example, in Figure 4, the source computational task is \(t_{\text{g}}\) as well as the tasks \(t_{1},t_{19}\) and \(t_{4}\), if we look at the yellow shaded graphs individually. The sink computational task is \(t_{12}\), were again \(t_{3},t_{24}\) and \(t_{7}\) are the sink computational tasks of the yellow shaded graphs. In Section 8.1 we describe how we generated the application graphs in our test instances and detail how we realized the merging of TTSP graphs.