Programming Project (for one or two persons): Overlapped Scheduling for
High-Level Synthesis by Means of Tabu Search
Summary: As shortly explained in the book,
the overlapped scheduling of an iterative data-flow graph implies that
computations in a next iteration may start before finishing computations
in the current iteration. In this project the mobility of operations should
be exploited using tabu-search to arrive at a solution of the scheduling
Study Chapter 11 of the book on high-level synthesis.
Study the description of tabu search as presented in the book (pages
Study also the following articles:
Heemstra de Groot, S.M., S.H. Gerez and O.E. Herrmann, "Range-Chart-Guided
Iterative Data-Flow-Graph Scheduling", IEEE Transactions on Circuits and
Systems I: Fundamental Theory and Applications, Vol. 39(5), pp 351-364,
Amellal, S. and B. Kaminska, "Functional Synthesis of Digital
Systems with TASS", IEEE Transactions on Computer-Aided Design of Integrated
Circuits and Systems, Vol. 13(5), pp 537-552, (May 1994).
The most important issues in the first paper are the defintion of the
range (time frame) and the proposed way to compute the scheudling ranges
by means of the Bellman-Ford algorithm (see also pages 95-96 of the book).
The relevant part of the second paper explains the application of tabu
search to hign-level synthesis.
You may assume the following:
The data-flow graph consists of 5 node types only: the input, the output,
the addition, the multiplication and the delay node.
There are two functional units: the adder and the multiplier. An addition
is done in one clock cycle, a multiplication in two (no pipelining).
Multiplication constants (as e.g. shown in Figure 12.13 of the book) can
The cost function is the sum of the number of adders and twice the number
The data-flow graph to be scheduled is read from a text file with the following
Using this syntax, the graph of Figure 12.13 (the second-order filter
without the multiplication
constants) with an iteration period of 4 is described as follows:
The first line gives the number of nodes N.
The second line gives the number of edges M.
The third line contains the iteration period T0.
The next N lines declare the nodes, where each line has the form:
<node number> <node type> <comment>.
The node type is "i" for an input, "o" for an output, "+" for an addition,
"*" for a multiplication, and "d" for a delay element. All text after the
node type until the end of the line is a comment.
The next M lines declare the edges, where each line has the form:
<source node number> <destination node number> <comment>.
1 i i1
2 + c1
3 + c2
4 + c8
5 + c7
6 * c3
7 * c4
8 * c6
9 * c5
10 d d1
11 d d2
12 o o1
1 2 from i1 to c1
6 2 from c3 to c1
2 3 from c1 to c2
7 3 from c4 to c2
3 4 from c2 to c8
5 4 from c7 to c8
8 5 from c6 to c7
9 5 from c5 to c7
11 6 from d2 to c3
10 7 from d1 to c4
10 8 from d1 to c6
11 9 from d2 to c5
3 10 from c2 to d1
10 11 from d1 to d2
4 12 from c8 to o1
The program should solve the scheduling and assignment problem and print
for each adder and multiplier that it uses: the operations scheduled on the
functional unit and the time when the execution of each operation starts.
The program's results for the second-order filter (the example mentioned
above) and at
least one more graph taken from the paper by Heemstra de Groot et al.
should be presented in the report.
Last update on:
Sat Jul 10 23:00:21 CEST 2004