×

Efficient heuristic algorithms for path-based hardware/software partitioning. (English) Zbl 1193.90223

Summary: Hardware/software (HW/SW) partitioning is one of the crucial steps of co-design systems. It determines which components of the systems are implemented in hardware and which ones are in software. In this paper the computing model is extended to cater for the path-based HW/SW partitioning with the fine granularity in which communication penalties between system components must be considered. On the new computing model an efficient heuristic algorithm is developed, in which both speedup in hardware and communication penalty are taken into account. In addition, an efficient tabu search algorithm is also customized in this paper to refine the approximate solutions produced by the heuristic algorithm. Simulation results show that the heuristic algorithm runs fast and is able to produce high-quality approximate solutions. Moreover, the tabu search algorithm can further refine them to nearly optimal solutions within an acceptable runtime. The difference between the approximate solutions and the optimal ones is bounded by 0.5%, and it hardly increases with the increase of the problem size.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
90C39 Dynamic programming
68N99 Theory of software
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R.K. Gupta, C. Coelho, G. De Micheli, Synthesis and simulation of digital systems containing interacting hardware and software components, in: Proc. the 29th ACM/IEEE Design Automation Conference, Los Alamitos, CA, USA, June 1992, pp. 225-230; R.K. Gupta, C. Coelho, G. De Micheli, Synthesis and simulation of digital systems containing interacting hardware and software components, in: Proc. the 29th ACM/IEEE Design Automation Conference, Los Alamitos, CA, USA, June 1992, pp. 225-230
[2] Gupta, R.; Micheli, G. D., Hardware-software cosynthesis for digital systems, IEEE Design and Test of Computers, 10, 3, 29-41 (1993)
[3] R. Niemann, P. Marwedel, Hardware/software partitioning using integer programming, in: Proc. the IEEE/ACM European Design Automation Conference (EDAC), Paris, France, March 1996, pp. 473-479; R. Niemann, P. Marwedel, Hardware/software partitioning using integer programming, in: Proc. the IEEE/ACM European Design Automation Conference (EDAC), Paris, France, March 1996, pp. 473-479
[4] Ernst, R.; Henkel, J.; Benner, T., Hardware-software co-synthesis for micro-controllers, IEEE Design and Test of Computer, 10, 4, 64-75 (1993)
[5] F. Vahid, D.D. Gajski, J. Gong, A binary-constraint search algorithm for minimizing hardware during hardware/software partitioning, in: Proc. IEEE/ACM European Design Automation Conference (EDAC), Paris, France, February 1994, pp. 214-219; F. Vahid, D.D. Gajski, J. Gong, A binary-constraint search algorithm for minimizing hardware during hardware/software partitioning, in: Proc. IEEE/ACM European Design Automation Conference (EDAC), Paris, France, February 1994, pp. 214-219
[6] F. Vahid, D.D. Gajski, Clustering for improved system-level functional partitioning, in: Proc. the 8th International Symposium on System Synthesis, Cannes, France, September 1995, pp. 28-33; F. Vahid, D.D. Gajski, Clustering for improved system-level functional partitioning, in: Proc. the 8th International Symposium on System Synthesis, Cannes, France, September 1995, pp. 28-33
[7] Z. Peng, K. Kuchcinski, An algorithm for partitioning of application specific system, in: Proc. of IEEE/ACM European Design Automation conference(EDAC), Paris, February 1993, pp. 316-321; Z. Peng, K. Kuchcinski, An algorithm for partitioning of application specific system, in: Proc. of IEEE/ACM European Design Automation conference(EDAC), Paris, February 1993, pp. 316-321
[8] Henkel, J.; Ernst, R., An approach to automated hardware/software partitioning using a flexible granularity that is driven by high-level estimation techniques, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 9, 2, 273-289 (2001)
[9] Madsen, J.; Grode, J.; Knudsen, P. V.; Petersen, M. E.; Haxthausen, A., LYCOS: The Lyngby co-synthesis system, Design Automation for Embedded Systems, 2, 195-235 (1997)
[10] Wu, Jigang; Srikanthan, T., Low-complex dynamic programming algorithm for hardware/software partitioning, Information Processing Letters, 98, 41-46 (2006) · Zbl 1187.68688
[11] Niemann, R.; Marwedel, P., An algorithm for hardware/software partitioning using mixed integer linear programming, Partitioning Methods for Embedded Systems. Partitioning Methods for Embedded Systems, Design Automation for Embedded Systems, 2, 2, 165-193 (1997), Special Issue
[12] Weinhardt, M., Integer programming for partitioning in software oriented codesign, Lecture Notes of Computer Science, 975, 227-234 (1995)
[13] G. Quan, X. Hu, G.W. Greenwood, Preference-driven hierarchical hardware/software partitioning, in: Proc. IEEE International Conference on Computer Design, Austin, TX, USA October 1999, pp.652-657; G. Quan, X. Hu, G.W. Greenwood, Preference-driven hierarchical hardware/software partitioning, in: Proc. IEEE International Conference on Computer Design, Austin, TX, USA October 1999, pp.652-657
[14] V. Srinivasan, S. Radhakrishnan, R. Vemuri, Hardware software partitioning with integrated hardware design space exploration, in: Proc. of DATE’98, Paris, France, February 1998, pp. 28-35; V. Srinivasan, S. Radhakrishnan, R. Vemuri, Hardware software partitioning with integrated hardware design space exploration, in: Proc. of DATE’98, Paris, France, February 1998, pp. 28-35
[15] Edwards, S. A.; Lavagno, L.; Lee, E. A., Design of embedded systems: Formal models validation, and synthesis, Proceedings of the IEEE, 85, 3, 366-390 (1997)
[16] Wu, Jigang; Srikanthan, T.; Zou, G., New model and algorithm for hardware/software partitioning, Journal of Computer Science & Technology, 23, 4, 644-651 (2008)
[17] Martello, S.; Toth, P., Knapsack Problems: Algorithms and Computer Implementations (1990), John Wiley & Sons · Zbl 0708.68002
[18] D. Pisinger, Algorithms for knapsack problems, Ph.D. Thesis, University of Copenhagen, 1995; D. Pisinger, Algorithms for knapsack problems, Ph.D. Thesis, University of Copenhagen, 1995 · Zbl 0904.90143
[19] Balas, E.; Zemel, E., An algorithm for large zero-one Knapsack problems, Operations Research, 28, 1130-1154 (1980) · Zbl 0449.90064
[20] R. Beier, B. Vocking, Probabilistic Analysis of Knapsack Core Algorithms, in: Proc. of the 15-th annual ACM-SIAM symposium on discrete algorithms, Louisiana, 2004, pp. 468-477; R. Beier, B. Vocking, Probabilistic Analysis of Knapsack Core Algorithms, in: Proc. of the 15-th annual ACM-SIAM symposium on discrete algorithms, Louisiana, 2004, pp. 468-477 · Zbl 1317.68291
[21] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0207.01701
[22] Glover, F., Future paths for integer programming and links to artificial intelligence, Computers and Operations Research, 13, 533-549 (1986) · Zbl 0615.90083
[23] Glover, F.; Laguna, M., Tabu Search (1997), Kluwer Academic Publishers · Zbl 0930.90083
[24] Rayward-Smith, V. J.; Osman, I. H.; Reeves, C. R.; Smith, G. D., Modern Heuristic Search Methods (1996), John Wiley and Sons · Zbl 0942.90004
[25] Arato, P.; Mann, Z. A.; Orban, A., Algorithmic aspects of hardware/software partitioning, ACM Transancations on Design Automation of Electronic Systems, 10, 1, 136-156 (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.