Our dynamic programming with binning, named Codex-dp (for Co-design of Communicating Systems Using Dynamic Programming), is implemented in C and tested on a number of circuits. Experimental results are presented in a Table in [CP99]. Prakash1 and Prakash2 are taken from [PP92]; Yen is taken from [Wol95], and Bender is an example from [Ben96]. In every example, we do the process decomposition and insert appropriate communication processes in the original task graphs. Our module library consists of a number of processors and communication units (Intel Pentium II and Motorola 68030 processors, TI 302C25 DSP, Intel DMA controller, 10Mb/s Ethernet controller, etc.) We allow the sharing of these resource through TDM. A pre-processing step determines the area/delay cost of each process when it is mapped to various hardware units in the library.
We also report results on 4 more examples from various sources. The task graph for example 1 with deadline = 80.0(ms) is taken from the CPM system [Ste95]. The task graph for example 2 with deadline = 100.0(ms) contains end.begin type communication only, but has reconvergent fanout structure. The task graph for example 3 and its decomposed task graph are shown in [CP99] and has deadline = 50.0(ms). The task graph for example 4 is a large task graph taken from [Ste95] which performs the voice activity detection in a GSM phone. For this example, we used three different deadlines and report the results in row ex4-1, ex4-2, ex4-3. The corresponding deadlines were set to 170, 300, 510 (ms), respectively.
In that Table, column 2 shows the values of m and n seen by Codex-dp (cf. Complexity Analysis in [CP99]). Column 3 gives the total number of processor and communication units needed after the allocation and binding. Columns 4 and 5 give the CPU time used by Codex-dp (in seconds on a 200 MHz Pentium Pro) and the estimated area cost (in cm square.) required to implement each circuit. Column 6 gives the numbers of variables, inequalities and equations if the scheduling is formulated as a mixed integer linear program, MILP assuming that each process has four possible implementations (not presented here due to lack of space). In column 7, we show the complexity of using exhaustive search after regrouping all of the computational subprocesses back into their original coarse-grain processes and still assuming that each process has four possible implementations.
It can be seen that Codex-dp produces the optimal scheduling results in a very short time compared to the expected time for MILP or exhaustive search. For example, in ex4, the MILP solution cannot be obtained due to the large number of variables in the MILP (195 variables, 123 equations, 51 inequalities). The row entries for ex4-1, ex4-2, ex4-3 show the trade-off between area cost and total computation time. Decreasing the deadline constraint increases the area cost of the optimal solution.