# Evolutionary System Design with Answer Set Programming
## 3 Evolutionary Design Space Exploration
### Implementations of a System Synthesis Problem  
From here on, we consider a set of applications \(A\) to determine our basic sets for task and dependencies. That is, we have \(\mathbb{T}=\bigcup\limits_{(T,D)\in A}T\) and \(\mathbb{D}=\bigcup\limits_{(T,D)\in A}D\). Furthermore, consider a hardware platform with resources \(R\). A _binding_ is a total function \(\mathbb{T}\to R\) that assigns each task a resource that it is executed on. Let \(\mathcal{R}=\{(r_{i})_{i=1}^{n}\mid\{r_{1},\ldots,r_{n}\}\subseteq R,n\in \mathbb{N}\}\) be the set of subsequences of elements of \(R\). We sometimes abuse set notation and write \(r\in S\), \((r,r^{\prime})\in S\), or \(S\cup S^{\prime}\) for \(r\in R\), \((r,r^{\prime})\in L\), and \(\{S,S^{\prime}\}\subseteq\mathcal{R}\) to denote that resource \(r\) or link \((r,r^{\prime})\) are part of a sequence \(S\) or refer to the union of all resources occurring in \(S\) and \(S^{\prime}\), respectively. We define the length of such a sequence as \(|(r_{i})_{i=1}^{n}|=n-1\). A _routing_ is a total function \(\mathbb{D}\to\mathcal{R}\) that assigns each dependency a sequence of resources that stand for the route of the communication between the two tasks. A _scheduling_ is a total function \(\mathbb{T}\cup\mathbb{D}\to\mathbb{N}\) that assigns each task and dependency a starting time, i.e., when the tasks start executing and the communication between two tasks is initiated. A binding \(b\) is _valid_ if \(t\in m(b(t))\) for all \(t\in\mathbb{T}\). That is, we can only bind tasks to resources on which they may be executed. Given a valid binding \(b\), a routing \(r\) is _valid_ on a hardware platform with links \(L\) if the following conditions are satisfied:  
1. if \(r(d)=(\ldots,r_{i},r_{i+1},\ldots)\), then \((r_{i},r_{i+1})\in L\) for all \(d\in\mathbb{D},i\in\mathbb{N}\);
2. if \(b(t)=r=b(t^{\prime})\), then \(r((t,t^{\prime}))=()\) for \((t,t^{\prime})\in\mathbb{D}\);
3. if \(b(t)=r\
eq b(t^{\prime})=r^{\prime}\), then \(r((t,t^{\prime}))=(r,\ldots,r^{\prime})\) for \((t,t^{\prime})\in\mathbb{D}\). Condition 1 ensures that the routing respects the hardware architecture in that every adjacent resource in a route has to be a link in the network graph. Condition 2 enforces an empty sequence if two depending tasks are mapped to the same resource. Condition 3 requires that every route respects the binding, i.e., it starts on the resource with the sending task and ends at the resource with the receiving task, whenever tasks are bound to different resources. Given a valid binding \(b\) and a valid routing \(r\), a scheduling \(s\) is _valid_ on a hardware platform with resources \(R\) if the following conditions are satisfied:  
1. \(0\leq s(t)\leq s(t)+e(b(t),t)\leq p\) for \(t\in\mathbb{T}\);
2. \(s(t)+e(b(t),t)\leq s((t,t^{\prime}))\) for \((t,t^{\prime})\in\mathbb{D}\);
3. \(s((t,t^{\prime}))+|r((t,t^{\prime}))|*rd\leq s(t^{\prime})\) for \((t,t^{\prime})\in\mathbb{D}\)  
the same resource, Condition 4 ensures that their execution does not overlap; either the first task has to finish before the second may start, or vice versa. Note that in case both tasks depend on each other, satisfaction of this condition follows from Condition 3. Furthermore, in our formalization, every resource can only execute one task at a time. Finally, whenever two routes share a link, Condition 5 requires either communication to finish before the other may start. This is called a _circuit switching strategy_[11] because the message blocks the whole route until it is received. A triple \((b,r,s)\) is an implementation of a system synthesis problem \((A,P)\) if \(b\) is a valid binding, \(r\) is a valid routing with respect to \(b\), and \(s\) is a valid scheduling with respect to \(b\) and \(r\). The small example system synthesis problem in Figure 1 already has 17,056 implementations.