Improvements of the GCLP Algorithm for HW/SW Partitioning of Task Graphs

B. Knerr, M. Holzer, and M. Rupp (Austria)


HW/SW Partitioning, Multi-Resource Scheduling, Design Automation, Optimization


HW/SW partitioning of modern heterogeneous systems, which combine signal processing as well as multimedia ap plications, is usually performed on a task or process graph representation. As this optimisation problem is known to be NP-hard, existing partitioning techniques rely on heuris tic methods to traverse the vast search space. The Global Criticality/Local Phase (GCLP) algorithm, initially intro duced by Kalavade and Lee as an integral part of the Ptolemy work suite, has been frequently referred to as fast and powerful technique to generate high quality solu tions for a combined partitioning/scheduling problem. In this work the internal mechanisms of the GCLP algorithm have been thoroughly analysed and several modifications are proposed that lead either to a significant increase of the quality of the obtained solutions without affecting the com putation time of the algorithm or to a substantially lower computation time while increasing the output of valid par titioning solutions.

Important Links:

Go Back