# Evolutionary System Design with Answer Set Programming
## 3 Evolutionary Design Space Exploration
### System Synthesis Problem  
Given a set \(\mathbb{T}\) of tasks and set \(\mathbb{D}\) of dependencies among them, an _application_ is a directed acyclic graph \((T,D)\) consisting of tasks \(T\subseteq\mathbb{T}\) and dependencies \(D\subseteq\mathbb{D}\) among tasks. A _hardware platform_ is a tuple \(((R,L),rd,c,se,re,p,m,e,d\epsilon)\)where:  
* \((R,L)\) is a directed graph consisting of resources \(R\), i.e., either routers, computational, or memory resources, and links \(L\) between resources describing the network;
* \(rd\in\mathbb{N}\) is the (uniform) routing delay, i.e., the time it takes for a communication to traverse a link;
* \(c:R\rightarrow\mathbb{N}\) is a total function that gives the cost of a resource;
* \(se:R\rightarrow\mathbb{N}\) is a total function that gives the static energy consumption of a resource;
* \(re\in\mathbb{N}\) is the (uniform) routing energy, i.e., the energy used whenever a link is used by a communication;
* \(m:R\to 2^{\mathbb{T}}\) is a total function that gives the set of tasks that may be executed on a resource;
* \(p\in\mathbb{N}\) is the (uniform) period in which applications have to be executed, i.e., the deadline of all tasks;
* \(e:R\times\mathbb{T}\rightarrow\mathbb{N}\) is a partial function that gives the execution time of tasks;
* that is, \(e(r,t)\) is defined if \(t\in m(r)\) for resource \(r\in R\) and task \(t\in\mathbb{T}\);
* \(de:R\times\mathbb{T}\rightarrow\mathbb{N}\) is a partial function giving the dynamic energy consumption that is dependent on what specific task is executed on what resource;  
as above, \(e(r,t)\) is defined if \(t\in m(r)\) for resource \(r\in R\) and task \(t\in\mathbb{T}\). A _system synthesis problem_ is a pair \((A,P)\) consisting of a set \(A\) of applications and a hardware platform \(P\). We assume that no two applications share a task, that is, \(\bigcap_{(T,D)\in A}T=\emptyset\). For illustration, we provide a small example system synthesis problem in Figure 1.  
On the left, we give the set of applications, which, in this case, is a single dependency graph comprising four tasks \(t_{1},t_{2},t_{3}\), and \(t_{4}\). More precisely, the (singleton) set of applications is  
\[A=\{(\{t_{1},t_{2},t_{3},t_{4}\},\{(t_{1},t_{2}),(t_{1},t_{3}),(t_{2},t_{4}),(t_ {3},t_{4})\})\}\]  
On the right, we have the hardware platform with the four computational resources \(r_{1}\) to \(r_{4}\), and four routers \(r_{5}\) to \(r_{8}\). The architecture follows a grid-like network-on-chip (NoC [11]) structure. This is not necessary for our formalization but is usually assumed and present in our benchmark instances. Each computational resource \(r_{i}\) is connected to a router \(r_{i+4}\) in both directions for \(i\in\{1,2,3,4\}\). Furthermore, routers are connected via edges:  
\[\{(r_{5},r_{6}),(r_{5},r_{7}),(r_{6},r_{5}),(r_{7},r_{5}),(r_{8},r_{7}),(r_{6},r_{8}),(r_{7},r_{8})\}\]  
All uniform characteristics, such as routing delay \(rd\), routing energy \(re\), and period \(p\), are given in the upper right corner and are set to one, one, and twenty, respectively. The cost and static energy consumption of the resources are given inside the rectangles labeled with the resource names. All routers have a uniform cost and energy consumption of one, i.e., they are all the same type of hardware component. The computational resources have the following attributes:  
\[ \begin{array}{llll}c(r_{1})=3,&&se(r_{1})=5,&&c(r_{2})=1,&&se(r_{2})=3,\\ c(r_{3})=5,&&se(r_{3})=5,&&c(r_{4})=2,&&se(r_{4})=2.\end{array} \]  
The mapping function \(m\) is given by the dashed gray arrows from the task nodes to the resources that they can be executed on. The first part of the label is the execution time on the resource, and the second part is the dynamic energy consumption. In detail, we have the mapping options \(m(r_{1})=\{t_{1},t_{4}\},m(r_{2})=\{t_{2}\},m(r_{3})=\{t_{2},t_{3}\},m(r_{4}) =\{t_{1},t_{4}\}\), with execution times \(e\) and dynamic energy consumption \(de\):  
\[