Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

An integrated high-level hardware/software partitioning methodology

  • Published:
Design Automation for Embedded Systems Aims and scope Submit manuscript

Abstract

Embedded systems are widely used in many sophisticated applications. To speed the time-to-market cycle, the hardware and software co-design has become one of the main methodologies in modern embedded systems. The most important challenge in the embedded system design is partitioning; i.e. deciding which modules of the system should be implemented in hardware and which ones in software. Finding an optimal partition is hard because of the large number and different characteristics of the modules that have to be considered.

In this article, we develop a new high-level hardware/software partitioning methodology. Two novel features characterize this methodology. Firstly, the Particle Swarm Optimization (PSO) technique is introduced to the Hardware/Software partitioning field. Secondly, the hardware is modeled using two extreme implementations that bound different hardware scheduling alternatives. Our methodology further partitions the design into hardware and software modules at the early Control-Data Flow Graph (CDFG) level of the design; thanks to improved modeling techniques using intermediate-granularity functional modules. A new restarting technique is applied to PSO to avoid quick convergence. This technique is called Re-Excited PSO. Our numerical results prove the usefulness of the proposed technique.

The target technology is Field Programmable Gate Arrays (FPGAs). We developed FPGA-based estimation techniques to evaluate the costs of implementing the design components. These costs are the area, delay, latency, and power consumption for both the hardware and software implementations. Hardware/software communication is also taken into consideration.

The aforementioned methodology is embodied in an integrated CAD tool for hardware/software co-design. This tool accepts behavioral, un-timed, algorithmic-level, VHDL, design representation, and outputs a valid hardware/software partition and schedule for the design subject to a set of area/power/delay constraints. This tool is code named CUPSHOP for (Cairo University PSo-based Hardware/sOftware Partitioning tool). Finally, a JPEG-encoder case study is used to validate and contrast our partitioning methodology against the prior-art methodologies.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abdelhalim MB, Habib SE-D (2007) Fast FPGA-based delay estimation for a novel hardware/software partitioning scheme. In: Proceedings of the 2nd international design and test workshop, Cairo, Egypt, pp 175–181

    Chapter  Google Scholar 

  2. Abdelhalim MB, Habib SE-D (2008) Fast FPGA-based area and latency estimation for a novel hardware/software partitioning scheme. In: Proceedings of the 21st Canadian conference on electrical and computer engineering, Niagara Falls, Ontario, Canada, pp 775–779

    Google Scholar 

  3. Abdelhalim MB, Habib SE-D (2008) Fast hardware upper-bound power estimation for a novel FPGA-based HW/SW partitioning scheme. In: Proceedings of the IEEE computer society annual symposium on VLSI, Montpellier, France, pp 393–398

    Chapter  Google Scholar 

  4. Abdelhalim MB, Salama AE, Habib SE-D (2006) Hardware software partitioning using particle swarm optimization technique. In: Proceedings of the 6th intl workshop on SOC for real-time applications, IWSOC’06, Cairo, Egypt, 2006, pp 189–194

    Chapter  Google Scholar 

  5. Abdelhalim MB, Salama AE, Habib SE-D (2007) Constrained and unconstrained hardware software partitioning using particle swarm optimization technique. In: Proceedings of the 2nd international embedded system symposium, Irvine, CA, USA, pp 207–220

    Google Scholar 

  6. Adhipathi P (2004) Model based approach to hardware/software partitioning of SOC designs. MSc Thesis, Virginia Polytechnic Institute and State University, USA

  7. Altera (2003). Apex 20 K device family architecture. Handbook

  8. Altera (2005) Avalon interface specification, Version 3.1

  9. Altera (2006) NIOS-II processor reference handbook

  10. Altera (2007) Cyclone device handbook

  11. Altera (2007) Quartus II Version 7.1 handbook—volume 4: SOPC builder

  12. Altera (2008) Cyclone PowerPlay early power estimator

  13. Armstrong JR, Adhipathi P, Baker JM Jr (2002) Model and synthesis directed task assignment for systems on a chip. In: 15th international conference on parallel and distributed computing systems, Cambridge, USA

    Google Scholar 

  14. Binh NN, Imai M, Shiomi A, Hikichi N (1996) A hardware/software partitioning algorithm for designing pipelined ASIPs with least gate counts. In: Proceedings of 33rd design automation conference, Las Vegas, Nevada, USA, pp 527–532

    Google Scholar 

  15. Chatha KS, Vemuri R (2001) MAGELLAN: multiway hardware-software partitioning and scheduling for latency minimization of hierarchical control-dataflow task graphs. In: Proceedings of the 9th international symposium on hardware/software codesign, Copenhagen, Denmark, pp 42–47

    Chapter  Google Scholar 

  16. Chen D, Cong J, Fan Y, Zhang Z (2007) High-level power estimation and low-power design space exploration for FPGAs. In: ASPDAC’07, Yokohama, Japan, pp 529–534

    Google Scholar 

  17. Chen W, Smith CH, Fralick S (1977) A fast computation algorithm for the DCT. IEEE Trans Commun 25:1004–1009

    Article  MATH  Google Scholar 

  18. De Holanda JA, Assumpcao J, Wolf DF, Marques E, Cardoso JM (2007) On adapting power estimation models for embedded soft-core processors. In: International symposium on industrial embedded systems, Costa da Caparica, Portugal, pp 345–348

    Chapter  Google Scholar 

  19. De Micheli G (1994) Synthesis and optimization of digital circuits. McGraw Hill, New York

    Google Scholar 

  20. De Souza DC, De Barros MA, Naviner LAB, Neto BGA (2003) On relevant quality criteria for optimized partitioning methods. In: Proceedings of 45th midwest symposium on circuits and systems, Cairo, Egypt, pp 1502–1505

    Google Scholar 

  21. Ditzel M (2004) Power-aware architecting for data-dominated applications. PhD thesis, Delft University of Technology, The Netherlands

  22. Eberhart RC, Kennedy J (1995) A new optimizer using particle swarm theory. In: Proceedings of the 6th international symposium on micro-machine and human science, Nagoya, Japan, pp 39–43

    Chapter  Google Scholar 

  23. Eberhart RC, Shi Y (2001) Particle swarm optimization: developments, applications and resources. In: Proceedings of 2001 congress on evolutionary computation, Seoul, Korea, pp 81–86

    Google Scholar 

  24. Eles P, Peng Z, Kuchcinski K, Doboli A (1997) System level HW/SW partitioning based on simulated annealing and tabu search. Des Autom Embed Syst 2(1):5–32

    Article  Google Scholar 

  25. Ernest RL (1997) Target architectures. In: Staunstrup J, Wolf W (eds) Hardware/software co-design: principles and practice. Kluwer Academic, Dordrecht, pp 113–148

    Google Scholar 

  26. Hanselman D, Littlefield B (2001) Mastering MATLAB 6. Prentice Hall, New York

    Google Scholar 

  27. Hassan R, Cohanim B, de Weck O, Venter G (2005) A comparison of particle swarm optimization and the genetic algorithm. In: 1st AIAA multidisciplinary design optimization specialist conference, Austin, Texas

    Google Scholar 

  28. Haupt RL, Haupt SE (2004) Practical genetic algorithms, 2nd edn. Wiley Interscience, New York

    MATH  Google Scholar 

  29. Henkel J, Ernst R (2001) An approach to automated hardware/software partitioning using a flexible granularity that is driven by high-level estimation techniques. IEEE Trans Very Large Scale Integr (VLSI) Syst 9(2):273–289

    Article  Google Scholar 

  30. Jeon J, Ahn Y, Choi K (2002) CDFG toolkit user’s guide. Technical Report No. SNU-EE-TR-2002-8. School of Electronic Engineering, Seoul National University, South Korea

  31. Jerraya AA, Romdhani M, Valderama C, Le Marrec AP, Hessel F, Marchioro GF, Daveau JM (1997) Languages for system-level specification and design. In: Staunstrup J, Wolf W (eds) Hardware/software co-design: principles and practice. Kluwer Academic, Dordrecht, pp 113–148

    Google Scholar 

  32. Jha NK, Dick RP (1998) MOGAC: a multiobjective genetic algorithm for hardware-software co-synthesis of distributed embedded systems. IEEE Trans Comput-Aided Des Integr Circuits Syst 17(10):920–935

    Article  Google Scholar 

  33. Jigang W, Srikanthan T, Chaen G (2010) Algorithmic aspects of hardware/software partitioning: 1D search algorithms. IEEE Trans Comput 59(4):532–544

    Article  Google Scholar 

  34. Jonsson B (2005) A JPEG encoder in SystemC. MSc thesis, Lulea University of Technology, Sweden

  35. Kalavade A, Lee EA (1994) A global criticality/local phase driven algorithm for the constrained hardware/software partitioning problem. In: Proceedings of 3rd international workshop on hardware/software codesign, Grenoble, France, pp 42–48

    Chapter  Google Scholar 

  36. Kalavade A, Lee EA (2002) The extended partitioning problem: hardware-software mapping and implementation-bin selection. In: De Micheli G, Ernest RL, Wolf W (eds) Readings in hardware/software co-design. Morgan Kaufmann, San Mateo, pp 293–312

    Chapter  Google Scholar 

  37. Kennedy J, Eberhart RC (1995) Particle swarm optimization. In: Proceedings of IEEE international conference on neural networks, Perth, Australia, pp 1942–1948

    Chapter  Google Scholar 

  38. Knudsen PV, Madsen J (1996) PACE: a dynamic programming algorithm for hardware/software partitioning. In: 4th international workshop on hardware/software co-design, Pittsburgh, Pennsylvania, USA, pp 85–92

    Chapter  Google Scholar 

  39. Lee TY, Fan YH, Cheng YM, Tsai CC, Hsiao RS (2007) Hardware-oriented partition for embedded multiprocessor FPGA systems. In: Proceedings of the second international conference on innovative computing, information and control, Kumamoto, Japan, pp 65–68

    Chapter  Google Scholar 

  40. Lee TY, Fan YH, Cheng YM, Tsai CC, Hsiao RS (2007) An efficiently hardware-software partitioning for embedded multiprocessor FPGA system. In: Proceedings of international multiconference of engineers and computer scientists, Hong Kong, pp 346–351

    Google Scholar 

  41. Lee TY, Fan YH, Cheng YM, Tsai CC, Hsiao RS (2007) Enhancement of hardware-software partition for embedded multiprocessor FPGA systems. In: Proceedings of the 3rd international conference on international information hiding and multimedia signal processing, Kaohsiung, Taiwan, pp 19–22

    Google Scholar 

  42. Li F, Lin Y, He L, Chen D, Cong J (2005) Power modeling and characteristics of field programmable gate arrays. IEEE Trans Comput-Aided Integr Circuits Syst 24(11):1712–1724

    Article  Google Scholar 

  43. Lin F, Wang H, Bian J (2005) HW/SW interface synthesis based on Avalon bus specification for NIOS-oriented SoC design. In: Proceedings of the international conference on field-programmable technology, Kent Ridge Guild House, Singapore, pp 305–306

    Google Scholar 

  44. Lin TY, Hung YT, Chang RG (2006) Efficient hardware/software partitioning approach for embedded multiprocessor systems. In: Proceedings of international symposium on VLSI design, automation and test, Hsinchu, Taiwan, pp 231–234

    Google Scholar 

  45. Lopez-Vallejo M, Lopez JC (2003) On the hardware-software partitioning problem: system modeling and partitioning techniques. ACM Trans Des Autom Electron Syst 8(3):269–297

    Article  Google Scholar 

  46. Luenberger DG (1984) Linear and non-linear programming. Addison-Wesley, Reading

    Google Scholar 

  47. Luthra M, Gupta S, Dutt N, Gupta R, Nicolau A (2003) Interface synthesis using memory mapping for an FPGA platform. In: Proceedings of the 21st international conference on computer design, San Jose, CA, USA, pp 140–145

    Chapter  Google Scholar 

  48. Madsen J, Gorde J, Knudsen PV, Petersen ME, Haxthausen A (1997) LYCOS: the lyngby co-synthesis system. Des Autom Embed Syst 2(2):195–236

    Article  Google Scholar 

  49. Mann ZA (2004) Partitioning algorithms for hardware/software co-design. PhD thesis, Budapest University of Technology and Economics, Hungary

  50. Marrec PL, Valderrama CA, Hessel F, Jerraya AA, Attia M, Cayrol O (1998) Hardware, software and mechanical cosimulation for automotive applications. In: Proceedings of 9th international workshop on rapid system prototyping, Leuven, Belgium, pp 202–206

    Chapter  Google Scholar 

  51. Mei B, Schaumont P, Vernalde S (2000) A hardware/software partitioning and scheduling algorithm for dynamically reconfigurable embedded systems. In: Proceedings of 11th ProRISC, Veldhoven, Netherlands

    Google Scholar 

  52. Nieman R (1998) Hardware/software co-design for data flow dominated embedded systems. Kluwer Academic, Dordrecht

    Google Scholar 

  53. Poli R (2008) Analysis of the publications on the applications of particle swarm optimization. J Artif Evol Appl 2008:685175

    Google Scholar 

  54. Shi Y, Eberhart RC (1998) Parameter selection in particle swarm optimization. In: Proceedings of 7th annual conference on evolutionary computation, New York, USA, pp 591–601

    Google Scholar 

  55. Shi Y, Eberhart RC (1999) Empirical study of particle swarm optimization. In: Proceedings of the 1999 congress on evolutionary computation, Washington DC, USA, pp 1945–1950

    Google Scholar 

  56. Stitt G (2008) Hardware/software partitioning with multi-version implementation exploration. In: Proceedings of great lakes symposium in VLSI, Orlando, Florida, USA, pp 143–146

    Google Scholar 

  57. Stitt G, Vahid F, McGregor G, Einloth B (2005) Hardware/software partitioning of software binaries: a case study of H.264 decoder. In: IEEE/ACM CODES+ISSS’05, New York, USA, pp 285–290

    Google Scholar 

  58. Tiwari V, Malik S, Wolfe A (1994) Power analysis of embedded software: a first step towards software power minimization. IEEE Trans Very Large Scale Integr (VLSI) Syst 2(4):437–445

    Article  Google Scholar 

  59. Tong Q, Zou X, Tong H, Gao F, Zhang Q (2008) Hardware/software partitioning in embedded system based on novel united evolutionary algorithm scheme. In: 2nd international conference on computer and electrical engineering, Phuket Island, Thailand, pp 141–144

    Chapter  Google Scholar 

  60. Vahid F (2002) Partitioning sequential programs for CAD using a three-step approach. ACM Trans Des Autom Electron Syst 7(3):413–429

    Article  Google Scholar 

  61. Xilinx Inc (2007) Virtex-II Pro and Virtex-II Pro X platform FPGAs: complete data sheet

  62. Zheng YL, Ma LH, Zhang LY, Qian JX (2003) On the convergence analysis and parameter selection in particle swarm optimization. In: Proceedings of the 2nd international conference on machine learning and cybernetics, Xi-an, China, pp 1802–1807

    Google Scholar 

  63. Zou Y, Zhuang Z, Cheng H (2004) HW-SW partitioning based on genetic algorithm. In: Proceedings of congress on evolutionary computation, Anhui, China, pp 628–633

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. College of Computing and Information Technology, Arab Academy of Science and Technology and Maritime Transport, P.O. Box 2033, Cairo, Egypt

    M. B. Abdelhalim

  2. Electronics and Communications Department, Faculty of Engineering, Cairo University, Giza, Egypt, 12613

    S. E.-D. Habib

Authors
  1. M. B. Abdelhalim
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. E.-D. Habib
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. B. Abdelhalim.

Additional information

This research is an extended version of IESS 2007 conference paper [5].

Rights and permissions

Reprints and permissions

About this article

Cite this article

Abdelhalim, M.B., Habib, S.ED. An integrated high-level hardware/software partitioning methodology. Des Autom Embed Syst 15, 19–50 (2011). https://doi.org/10.1007/s10617-010-9068-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10617-010-9068-9

Keywords

Search

Navigation