PACE: a dynamic programming algorithm for hardware/software partitioning
Peter Voigt Knudsen, Jan Busk Madsen · 1996
. This paper presents the PACE partitioning algorithm which is used in the LYCOS co-synthesis system for partitioning control/dataflow graphs into hardwareand software parts. The algorithm is a dynamic programming algorithm which solves both the problem of minimizing system execution time with a hardware area constraint and the problem of minimizing hardware area with a system execution time constraint. The target architecture consists of a single microprocessor and a single hardware chip (ASIC, FPGA, etc.) which are connected by a communication channel. The algorithm incorporates a realistic communication model and thus attempts to minimize communication overhead. The time-complexity of the algorithm is O(n 2 \\Delta A) and the space-complexity is O(n \\Delta A) where A is the total area of the hardware chip and n the number of code fragments which may be placed in either hardware or software. 1 Introduction The hardware/software partitioning of a system specification onto a target...