Programming Project (for one or two persons): Overlapped Scheduling for
HighLevel Synthesis by Means of Tabu Search
Summary: As shortly explained in the book,
the overlapped scheduling of an iterative dataflow 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 tabusearch to arrive at a solution of the scheduling
problem.
Detailed Description

Study Chapter 11 of the book on highlevel synthesis.

Study the description of tabu search as presented in the book (pages
7374).

Study also the following articles:
Heemstra de Groot, S.M., S.H. Gerez and O.E. Herrmann, "RangeChartGuided
Iterative DataFlowGraph Scheduling", IEEE Transactions on Circuits and
Systems I: Fundamental Theory and Applications, Vol. 39(5), pp 351364,
(May 1992).
Amellal, S. and B. Kaminska, "Functional Synthesis of Digital
Systems with TASS", IEEE Transactions on ComputerAided Design of Integrated
Circuits and Systems, Vol. 13(5), pp 537552, (May 1994).
The most important issues in the first paper are the defintion of the
scheduling
range (time frame) and the proposed way to compute the scheudling ranges
by means of the BellmanFord algorithm (see also pages 9596 of the book).
The relevant part of the second paper explains the application of tabu
search to hignlevel synthesis.

You may assume the following:

The dataflow 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
be ignored.

The cost function is the sum of the number of adders and twice the number
of multipliers.

The dataflow graph to be scheduled is read from a text file with the following
syntax:

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>.
Using this syntax, the graph of Figure 12.13 (the secondorder filter
without the multiplication
constants) with an iteration period of 4 is described as follows:
12
15
4
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 secondorder 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
by
Sabih
Gerez.