Detailed Description

• Study Chapter 11 of the book on high-level synthesis.
• Study the description of tabu search as presented in the book (pages 73-74).
• 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, (May 1992).

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 scheduling 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 be ignored.
• The cost function is the sum of the number of adders and twice the number of multipliers.
• The data-flow 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 second-order 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 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 by Sabih Gerez.