# Evolutionary System Design with Answer Set Programming
## 4 Encoding the System Synthesis Problem with ASP Modulo Difference Constraints
### General Problem Encoding
Again, Condition 5 is satisfied by only considering one ordering of the communications due to symmetry, and the symmetry breaking technique is identical to the one used for resource conflicts. Now, our encoding produces valid schedules as we implemented all conditions via difference constraints. ```
1&&diff{0-T}<=0:-task(T). 2&&diff{T-0}<=V:-period(P),bind(T,R),execution(R,T,E),V=P-E.
34&&diff{T-(T,T')}<-E:-send(T,T'),bind(T,R),execution(R,T,E). 45&&diff{(T,T')-T'}<-S:-send(T,T'),hops(C,N),routing_delay(D),
6S-N*D.
78&&diff{T-T'}<-E:-conflict(T,T'),priority(T,T'),
8 task(T),task(T'),
10 execution(R,T,E). 11&&diff{T'-T}<-E:-conflict(T,T'),notpriority(T,T'),
12 task(T),task(T'),
13 execution(R,T',E). 14&&diff{C-C'}<-S:-conflict(C,C'),priority(C,C'),
15 hops(C,N),routing_delay(D),S=N*D.
16&&diff{C'-C'}<-S:-conflict(C,C'),notpriority(C,C'),
17 hops(C',N),routing_delay(D),S=N*D.
```  
**Listing 6**. Scheduling encoding. For example, the valid schedule of our parent implementation in Figure 2 is  
```
1 dl(t1,0)dl(t2,8)dl(t3,5)dl(t4,14)dl((t1,t2),5)dl((t1,t3),2)dl((t2,t4),11)dl((t3,t4),8)
```  
**Listing 7**. Locations of resources of the parent specification. In this section, we show how we can use information about the location of resources to obtain shortest path information and improve solution quality and runtime performance. More specifically, we view our architecture as a three-dimensional grid on which our resources have specific locations that can be used to easily calculate the shortest paths between them. For that purpose, we define a function \(l:R\rightarrow\mathbb{N}\times\mathbb{N}\times\mathbb{N}\) that assigns each resource their location and, given a set of resources \(R\), add facts location(\(r,l(r)\)) to our instance for each resource \(r\in R\). We use this information to firstly restrict routes to the length of the shortest path possible to improve solution quality and solving time; secondly, we use this information to enable dimension-ordered routing, which essentially removes routing from the solving process, i.e., the possible routes are known at grounding time. Listing 7 shows the coordinates of resources of our parent specification in Figure 1. Note that the computational resources have the same coordinates as the routers they are connected to. The scheme we use for our instances assumes that every computational resource has a router that it is closely and exclusively attached to, and the shortest paths are then considered between the routers. In that sense, we have a two-dimensional NoC in our example as the z-coordinate is always zero. ```
1 location(r1,(0,1,0)).location(r2,(1,1,0)). 2 location(r3,(0,0,0)).location(r4,(1,0,0)). 3 location(r5,(0,1,0)).location(r6,(1,1,0)). 4 location(r7,(0,0,0)).location(r8,(1,0,0)). ```  
**Listing 8**. Locations of resources of the parent specification. ```
1 location(r2,(1,1,0)).location(r2,(1,1,0)).location(r3,(0,0,0)).location(r4,(1,0,0)). 2 location(r5,(0,1,0)).location(r6,(1,1,0)). 3 location(r7,(0,0,0)).location(r8,(1,0,0)). 4 location(r8,(1,0,0)).location(r9,(1,1,0)). 5 location(r10,(1,1,0)).location(r11,(1,1,0)). 6 location(r12,(1,1,1,0)).location(r13,(1,1,1,0)). 73 location(r14,(1,1,1,0)).location(r15,(1,1,1,0)). 74 location(r16,(1,1,1,0)).location(r17,(1,1,1,0)).location(r18,(1,1,1,0)). 75 location(r19,(1,1,1,1,0)).location(r120,(1,1,1,0)).location(r13,(1,1,1,0)).location(r14,(1,1,1,0)).location(r15,(1,1,1,0)).location(r16,(1,1,1,0)).location(r17,(1,1,1,0))Bound Routing

Listing 8 shows how we calculate the number of hops and restrict the routes using the locations of resources. Line 1 calculates the former for two tasks that are bound to different resources. The number of hops required to route the message is exactly the Manhattan distance between the coordinates plus two. The two hops are added to account for the segment from the sending resource to its router and from the final router to the receiving resource. Line 4 covers the case when both tasks in communication are bound to the same resource, where the number of hops is then zero.