article

System Level Hardware/Software Partitioning Based on Simulated Annealing and Tabu Search

Authors:

Krzysztof Kuchcinski,

Alexa DoboliAuthors Info & Claims

Design Automation for Embedded Systems, Volume 2, Issue 1

Pages 5 - 32

https://doi.org/10.1023/A:1008857008151

Published: 01 January 1997 Publication History

Abstract

This paper presents two heuristics for automatic hardware/software partitioning of system level specifications. Partitioning is performed at the granularity of blocks, loops, subprograms, and processes with the objective of performance optimization with a limited hardware and software cost. We define the metric values for partitioning and develop a cost function that guides partitioning towards the desired objective. We consider minimization of communication cost and improvement of the overall parallelism as essential criteria during partitioning. Two heuristics for hardware/software partitioning, formulated as a graph partitioning problem, are presented: one based on simulated annealing and the other on tabu search. Results of extensive experiments, including real-life examples, show the clear superiority of the tabu search based algorithm.

References

[1]

J. K. Adams and D. E. Thomas. Multiple-process behavioral synthesis for mixed hardware-software systems. In Proc. International Symposium on System Synthesis, pp. 10---15. 1995.

Digital Library

[2]

P. M. Athanas and H. F. Silverman. Processor reconfiguration through instruction-set metamorphosis. Computer, 11---18, March 1993.

Digital Library

[3]

E. Barros, W. Rosenstiel and X. Xiong. A method for partitioning UNITY language in hardware and software. In Proc. European Design Automation Conference EURO-DAC/VHDL, pp. 220---225. 1994.

Digital Library

[4]

Generic requirements for operations of broadband switching systems. Bellcore TANWT-001248 issue 2, October 1993.

[5]

A. Bender. Design of an optimal loosely coupled heterogeneous multiprocessor system. In Proc. European Design & Test Conference, pp. 275---281. 1996.

Digital Library

[6]

G. Boriello, P. Chou and R. Ortega. Embedded system co-design towards portability and rapid integration. In Hardware/Software Co-Design, NATO ASI 1995, G. De Micheli and M. G. Sami (eds.), Kluwer Academic Publishers, Boston, 1996.

[7]

K. Buchenrieder and J. W. Rozenblit. Codesign: An overview. In Codesign--Computer-Aided Software/ Hardware Engineering, J. Rozenblit and K. Buchenrieder (eds.), IEEE Press, 1995.

[8]

K. Buchenrieder, A. Sedlemeier and C. Veith. Industrial hardware/software co-design. In Hardware/Software Co-Design, NATO ASI 1995, G. De Micheli and M. G. Sami eds., Kluwer Academic Publishers, Boston, 1996.

[9]

R. Camposano and J. Wilberg. Embedded system design. Design Automation for Embedded Systems 1: 5---50, 1996.

Digital Library

[10]

P. H. Chou, R. B. Ortega and G. Boriello. The Chinook hardware/software co-synthesis system. In Proc. International Symposium on System Synthesis, pp. 22---27. 1995.

Digital Library

[11]

G. De Micheli. Computer-aided hardware-software codesign. IEEE Micro, 10---16, August 1994.

Digital Library

[12]

G. De Micheli. Hardware/software codesign: Application domains and design technologies. In Hardware/ Software Co-Design, NATO ASI 1995, G. De Micheli and M. G. Sami (eds.), Kluwer Academic Publishers, Boston, 1996.

[13]

M. De Prycker. Asynchronous Transfer Mode: Solution for Broadband ISDN. Ellis Horwood, New York, 1993.

Digital Library

[14]

M. Edwards and J. Forrest. A development environment for the cosynthesis of embedded software/hardware systems. In Proc. European Design Automation Conference EDAC, pp. 469---473. 1994.

[15]

P. Eles, K. Kuchcinski, Z. Peng and M. Minea. Synthesis of VHDL concurrent processes. In Proc. European Design Automation Conference EURO-DAC/VHDL, pp. 540---545. 1994.

Digital Library

[16]

P. Eles, Z. Peng and A. Doboli. VHDL system-level specification and partitioning in a hardware/software co-synthesis environment. In Proc. Third International Workshop on Hardware/Software Codesign, IEEE, pp. 49---55. 1994.

Digital Library

[17]

R. Ernst, J. Henkel and T. Benner. Hardware-software co-synthesis for microcontrollers. IEEE Design & Test of Computers, 64---75, September 1993.

Digital Library

[18]

D. D. Gajski and F. Vahid. Specification and design of embedded hardware-software systems. IEEE Design & Test of Computers, 53---67, Spring 1995.

Digital Library

[19]

F. Glover, E. Taillard and D. de Werra. A user's guide to tabu search. Annals of Operations Research 41: 3---28, 1993.

Digital Library

[20]

G. Goosens, J. van Praet, D. Lanneer, W. Geurts and F. Thoen. Programmable chips in consumer electronics and telecommunications. In Hardware/Software Co-Design,NATO ASI 1995, G. De Micheli and M. G. Sami (eds.), Kluwer Academic Publishers, Boston, 1996.

[21]

P. Grün. VHDL to C Compilation in a Hardware/Software Co-Synthesis Environment, Master Thesis, Technical University of Timisoara, 1995.

[22]

R. K. Gupta and G. De Micheli. System synthesis via hardware-software co-design. Technical Report No. CSL-TR-92-548, Comp. Syst. Lab., Stanford Univ., 1992.

Digital Library

[23]

R. K. Gupta and G. De Micheli. Hardware-software cosynthesis for digital systems. IEEE Design & Test of Computers, 29---41, September 1993.

Digital Library

[24]

R. K. Gupta. Co-synthesis of hardware and software for digital embedded systems. Kluwer Academic Publishers, Boston, 1995.

Digital Library

[25]

IEEE standard VHDL language reference manual. IEEE Std 1076---1993, IEEE Press, 1994.

[26]

B-ISDN operation and maintanace principles and functions. ITU-T Recommendation I.610, 1993.

[27]

T. Ben Ismail and A. A. Jerraya. Synthesis steps and design models for codesign. Computer, 44---52, February 1995.

Digital Library

[28]

A. Kalavade and E. A. Lee. A global criticality/local phase driven algorithm for the constrained hardware/ software partitioning problem. In Proc. Third International Workshop on Hardware/Software Codesign, pp. 42---48. 1994.

Digital Library

[29]

B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning Graphs. Bell Systems Tech. J. 49(2): 291---307, 1970.

[30]

S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi. Optimization by simulated annealing. Science 220(4598): 671---680, 1983.

[31]

L. Lavagno, A. Sangiovanni-Vincentelli and H. Hsieh. Embedded system codesign. In Hardware/software co-design, NATO ASI 1995, G. De Micheli and M. G. Sami (eds.), Kluwer Academic Publishers, Boston, 1996.

[32]

S. Narayan, F. Vahid and D. D. Gajski. Modeling with Spec Charts, Technical Report #90-20, Dept. of Inf. and Comp. Science, Univ. of California, Irvine, 1990/1992.

[33]

R. Niemann and P. Marwedel. Harware/software partitioning using integer programming. In Proc. European Design & Test Conference, pp. 473---479. 1996.

Digital Library

[34]

K. A. Olukotun, R. Helaihel, J. Levitt and R. Ramirez. A software-hardware co-synthesis approach to digital system simulation. IEEE Micro, 48---58, August 1994.

Digital Library

[35]

Z. Peng and K. Kuchcinski. An algorithm for partitioning of application specific systems. In Proc. European Design Automation Conference EDAC, pp. 316---321. 1993.

[36]

Z. Peng and K. Kuchcinski. Automated transformation of algorithms into register-transfer level implementation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 13(2): 150---166, February 1994.

Digital Library

[37]

E. Stoy and Z. Peng. A design representation for hardware/software co-synthesis. In Proc. Euromicro Conference, pp. 192---199. 1994.

[38]

F. Vahid, J. Gong and D. Gajski. A binary-constraint search algorithm for minimizing hardware during hardware/software partitioning. In Proc. European Design Automation Conference EURO-DAC/VHDL, pp. 214---219. 1994.

Digital Library

[39]

W. H. Wolf. Hardware-software co-design of embedded systems. Proceedings of the IEEE 82(7): 967---989, July 1994.

[40]

C. W. Yeh, C. K. Cheng and T. T.Y. Lin. Optimization by iterative improvement: An experimental evaluation on two-way partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 14(2): 145---153, February 1995.

Digital Library

[41]

T. Y. Yen and W. Wolf. Sensitivity-driven co-synthesis of distributed embedded systems. In Proc. International Symposium on System Synthesis, pp. 4---9. 1995.

Digital Library

Cited By

Boroujerdian BJing YTripathy DKumar ASubramanian LYen LLee VVenkatesan VJindal AShearer RReddi V(2023)FARSI: An Early-stage Design Space Exploration Framework to Tame the Domain-specific System-on-chip ComplexityACM Transactions on Embedded Computing Systems10.1145/354401622:2(1-35)Online publication date: 24-Jan-2023
https://dl.acm.org/doi/10.1145/3544016
Zhang KLiu YZhang JZhang GJin JLi YTang F(2023)TDCA: improved optimization algorithm with degree distribution and communication traffic for the deployment of software components based on AUTOSAR architectureSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-07989-127:12(7999-8012)Online publication date: 17-Mar-2023
https://dl.acm.org/doi/10.1007/s00500-023-07989-1
Zheng XLiang SXiong X(2021)A hardware/software partitioning method based on graph convolution networkDesign Automation for Embedded Systems10.1007/s10617-021-09255-925:4(325-351)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s10617-021-09255-9
Show More Cited By

Recommendations

Efficient heuristic and tabu search for hardware/software partitioning

Hardware/software (HW/SW) partitioning is a crucial step in HW/SW codesign that determines which components of the system are implemented on hardware and which ones on software. It has been proved that the HW/SW partitioning problem is NP-hard. In this ...
Benchmarking Tabu Search and Simulated Annealing for the Capacitated Vehicle Routing Problem
ICCMB '21: Proceedings of the 2021 4th International Conference on Computers in Management and Business

This paper addresses the Capacitated Vehicle Routing Problem (CVRP) consisting of a single depot and several customers that are supplied with goods by capacitated vehicles from a depot. The main objective of the vehicle routing problem is to minimize ...
Efficient heuristic algorithms for path-based hardware/software partitioning

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Design Automation for Embedded Systems

Design Automation for Embedded Systems Volume 2, Issue 1

January 1997

114 pages

ISSN:0929-5585

Issue’s Table of Contents

Copyright © Copyright © 1997 Kluwer Academic Publishers.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 January 1997

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

68
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Boroujerdian BJing YTripathy DKumar ASubramanian LYen LLee VVenkatesan VJindal AShearer RReddi V(2023)FARSI: An Early-stage Design Space Exploration Framework to Tame the Domain-specific System-on-chip ComplexityACM Transactions on Embedded Computing Systems10.1145/354401622:2(1-35)Online publication date: 24-Jan-2023
https://dl.acm.org/doi/10.1145/3544016
Zhang KLiu YZhang JZhang GJin JLi YTang F(2023)TDCA: improved optimization algorithm with degree distribution and communication traffic for the deployment of software components based on AUTOSAR architectureSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-07989-127:12(7999-8012)Online publication date: 17-Mar-2023
https://dl.acm.org/doi/10.1007/s00500-023-07989-1
Zheng XLiang SXiong X(2021)A hardware/software partitioning method based on graph convolution networkDesign Automation for Embedded Systems10.1007/s10617-021-09255-925:4(325-351)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s10617-021-09255-9
Hou NYan XHe F(2019)A survey on partitioning models, solution algorithms and algorithm parallelization for hardware/software co-designDesign Automation for Embedded Systems10.1007/s10617-019-09220-723:1-2(57-77)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10617-019-09220-7
Zhang TYue QZhao XLiu G(2019)An improved firework algorithm for hardware/software partitioningApplied Intelligence10.1007/s10489-018-1310-349:3(950-962)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s10489-018-1310-3
Zuo WPouchet LAyupov AKim TLin CShiraishi SChen D(2017)Accurate High-level Modeling and Automated Hardware/Software Co-design for Effective SoC Design Space ExplorationProceedings of the 54th Annual Design Automation Conference 201710.1145/3061639.3062195(1-6)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3061639.3062195
(2016)Assignment of unexpected tasks in embedded system design processMicroprocessors & Microsystems10.1016/j.micpro.2016.01.00144:C(17-21)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.micpro.2016.01.001
Sapienza GBrestovac GGrgurina RSeceleanu T(2016)On applying multiple criteria decision analysis in embedded systems designDesign Automation for Embedded Systems10.1007/s10617-016-9171-720:3(211-238)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1007/s10617-016-9171-7
Jemai MOuni B(2015)Hardware software partitioning of control data flow graph on system on programmable chipMicroprocessors & Microsystems10.1016/j.micpro.2015.04.00639:4(259-270)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1016/j.micpro.2015.04.006
Sha EWang LZhuge QZhang JLiu J(2015)Power Efficiency for Hardware/Software Partitioning with Time and Area Constraints on MPSoCInternational Journal of Parallel Programming10.1007/s10766-013-0283-443:3(381-402)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1007/s10766-013-0283-4
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents