Networked Embedded Systems Lab
Prof. Marco Zimmerling
Introduction to Embedded Systems – WS 2022/23
Exercise 7: Architecture Synthesis I
Task 1: Scheduling
Consider the sequence graph in Figure 1.
NOP 0
1 2 6 8 10
3 7 9 11
n
NOP
Figure 1: Sequence graph
All the operations are handled by the same resource type and have the same execution time:
D∗ = D− = D< = D+ = 1.
a) Set up a system of inequations which represent the constraints to valid schedules.
b) Set up an optimization model for the optimization of the latency L. Resource constraints need not
be taken into account. (Hint: add an objective function to the system of inequations to get a linear
program).
c) What is the minimal achievable latency
• if there is only one resource unit which handles all operations?
• if there are unlimited resource units?
Indicate valid starting times for the operations in both cases and check the validity of the schedules by
means of the system of inequations determined previously.
1
Task 2: Design Space Exploration
Consider again the sequence graph and the specification of task 1. Assume that there is only one resource
type which can compute all operations (+, −, <, ∗) and has an area of 1. The cost of an implementation is
given by the total required area. The goal is to find the Pareto-points of the design space which is given by
the parameters cost and latency. The number of allocated resources is not yet fixed.
a) Compute a lower and an upper bound for the latency in order to limit the possible Pareto-points.
b) Find a lower and an upper bound for the cost in order to limit the possible Pareto-points.
c) Find all Pareto-points and represent them in a diagram.
Task 3: Marked Graphs
Consider the marked graph in Figure 2. The node labeled with + represents an addition of the two input
values.
I) At the input a a sequence of numbers is read in, with a(k) representing the k-th number. Determine
the outgoing sequence b(k) as function of the input values.
II) The initial mark with the value s is replaced by n marks s1 , ..., sn . Determine a recursive formula for
the output sequence b(k).
Input Output
Figure 2: Marked Graph 1
Task 4: List Scheduling
Given the sequence graph in Figure 3.
Suppose that two adders (r1 ) and a multiplier (r2 ) are available as resources. Addition takes one time unit and
multiplication takes two time units. The first operation starts at t = 0 and the top node (’nop’) is executed
within zero time units. The priority is assigned for each operation as maximal distance to the bottom node
(’nop’).
a) Fill out Table 1 using the list scheduling algorithm. For a timestep t, Ut,k denotes the set of operations
that are ready to be scheduled on resource rk (to be more specific, the set of operations that can be
mapped on resource rk and whose predecessors are all completed). St,k denotes the set of operations
that starts at time t on resource rk , while Tt,k is the set of operations in execution at time t on resource
rk .
b) What is the calculated latency?
c) Suppose that area costs for the adder and multiplier are 1 and 2 respectively. If it is allowed to spend
additional hardware by 2 area units, which resource should be added to shorten the latency? Two adders
or one multiplier? Explain why.
d) What is the new latency with the additional resource?
2
Figure 3: Sequence graph for Task 4
e) In case of unlimited hardware resources, what is the minimal latency?
3
t k Ut,k Tt,k St,k
r1
0
r2
r1
1
r2
r1
2
r2
r1
3
r2
r1
4
r2
r1
5
r2
r1
6
r2
r1
7
r2
r1
8
r2
r1
9
r2
r1
10
r2
r1
11
r2
r1
12
r2
r1
13
r2
Table 1: Table for Task 2
