Performance Improvement of Force-directed Partitioning Algorithm for HW/SW Codesign

KIPS Transactions on Software and Data Engineering, Vol. 9, No. 4, pp. 491-496, Apr. 2002
10.3745/KIPSTA.2002.9.4.491, Full Text:


Most partitioning algorithms for hardware-software codesign do not consider scheduling. Therefore, partitioning should be performed again if time constraints are not satisfied in scheduling the partitioned results. Existing FDS-applied methods which consider scheduling in partitioning decide the control step of the node to schedule while selecting nodes for partitioning. In selecting nodes for partitioning, several aspects should be considered together such as added cost or time due to the partition of the node, or the degree of interference due to the scheduling of the node. At this time, the induced force, which means the degree of intereference of scheduling other nodes, is computed all over the control step of the corresponding node and other depending nodes. In this paper, a new FDS-applied partitioning algorithm is proposed, where partitioning is performed using the defined scheduling urgency and relative scheduling urgency of the nodes. Since the nodes are partitioned by the computation of relative scheduling urgencies only at the earliest control step and the latest control step among the assignable steps, the time complexity for the computation of induced force could be improved. Experimental result on the benchmarks show the improvement of execution time of the proposed algorithm compared to the existing FDS-applied methods.

Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.

Cite this article
[IEEE Style]
J. Y. Oh, M. J. Lee, J. Y. Lee and D. S. Park, "Performance Improvement of Force-directed Partitioning Algorithm for HW/SW Codesign," KIPS Journal A (2001 ~ 2012) , vol. 9, no. 4, pp. 491-496, 2002. DOI: 10.3745/KIPSTA.2002.9.4.491.

[ACM Style]
Ju Young Oh, Myoun Jae Lee, Jun Yong Lee, and Do Soon Park. 2002. Performance Improvement of Force-directed Partitioning Algorithm for HW/SW Codesign. KIPS Journal A (2001 ~ 2012) , 9, 4, (2002), 491-496. DOI: 10.3745/KIPSTA.2002.9.4.491.