# Evolutionary System Design with Answer Set Programming
## 3 Evolutionary Design Space Exploration
### Implementation Quality and Pareto Front  
We evaluate an implementation of a system synthesis problem via three objective functions: cost, energy consumption, and latency. Given an implementation \((b,r,s)\) of a system synthesis problem \((A,((R,L),rd,c,se,re,p,m,e,de))\), we define the following total functions:  
* _Cost_ \[f_{c}(b,r)=\sum_{u\in\{b(t)|t\in\mathbb{T}\}\cup\bigcup_{d\in\mathbb{D}}r(d)}c (u)\]
* _Energy consumption_ \[f_{e}(b,r)=\sum_{u\in\{b(t)|t\in\mathbb{T}\}\cup\bigcup_{d\in\mathbb{D}}r(d)}se (u)+\sum_{t\in\mathbb{T}}de(b(t),t)+\sum_{d\in\mathbb{D}}(|r(d)|)*re\]
* _Latency_ \[f_{l}(s)=\max\{s(t)+e(b(t),t)\mid t\in\mathbb{T}\}\]Strictly speaking, all cost functions also depend on the system synthesis problem; however, we refrain from making this explicit for the sake of simplicity. The function \(f_{c}\) sums up the cost of all resources that are used, either by having a task bound to it or by being used as a routing device in a communication. The cost of our example implementation in Figure 2 is 10 as we do not use \(r_{2},r_{4},r_{6}\), or \(r_{8}\). The energy consumption \(f_{e}\) considers the static energy required by using a resource, the dynamic energy stemming from the execution of a task on a resource, and the energy consumption of the links used in any communication. Note that, in contrast to the static energy of a resource, the energy consumption of a link is counted per use in a communication. The implementation in Figure 2 has an energy consumption of 43. Finally, latency \(f_{l}\) calculates the maximum of starting plus the execution time of all tasks, i.e., the time span of the entire execution of the implementation. The example implementation in Figure 2 has a latency of 10, which is the moment that \(t_{4}\) finishes and the application has been executed. The _quality_ of an implementation \((b,r,s)\) of a system synthesis problem \((A,P)\) is given by the tuple \((f_{c}(b),f_{e}(b,r),f_{l}(s))\). Accordingly, the quality of the implementation in Figure 2 is \((10,43,15)\). Rather than one optimal implementation, we are interested in a set of non-dominated implementations, the so-called _Pareto front_[12]. Let \((b,r,s)\) and \((b^{\prime},r^{\prime},s^{\prime})\) be two implementations of a system synthesis problem \((A,P)\) and \((q_{1},q_{2},q_{3})\) and \((q_{1}^{\prime},q_{2}^{\prime},q_{3}^{\prime})\) be their respective quality; then, \((b,r,s)\)_dominates_\((b^{\prime},r^{\prime},s^{\prime})\), denoted as \((b,r,s)\sim(b^{\prime},r^{\prime},s^{\prime})\), if  
1. \(q_{i}\leq q_{i}^{\prime}\) for all \(i\in\{1,2,3\}\); and
2. \(q_{i}<q_{i}^{\prime}\) for some \(i\in\{1,2,3\}\). Figure 2: Example (parent) implementation. (**a**) Binding; (**b**) routing and scheduling. Note that \(\prec\) forms a partial relation, i.e., the qualities of some implementations are incomparable. Intuitively, the quality of an implementation has to be at least as good in all aspects and strictly better in one to dominate another implementation's quality. Then, an implementation \((b,r,s)\) of a system synthesis problem \((A,P)\) belongs to the Pareto front if no other implementation \((b^{\prime},r^{\prime},s^{\prime})\) of \((A,P)\) exists, such that \((b^{\prime},r^{\prime},s^{\prime})\prec(b,r,s)\). The system synthesis problem in Figure 1 has four non-dominated implementations; two of them bind \(t_{1}\) and \(t_{4}\) to \(r_{1}\) and \(t_{2}\) and \(t_{3}\) to \(r_{3}\), and the remaining two bind \(t_{1}\) and \(t_{4}\) to \(r_{4}\) and \(t_{2}\) and \(t_{3}\) to \(r_{3}\). The two respective implementations have the same quality, namely, \((10,43,15)\) and \((9,35,16)\), respectively, as well as identical routing and binding; the sole difference is whether \(t_{2}\) or \(t_{3}\) is executed first. We can identify two optimal trade-offs here. The implementations with quality \((10,43,15)\) emphasize a shorter latency with higher cost and energy consumption, and implementations with quality \((9,35,16)\) save costs and energy with a slightly longer execution time.