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

Embedded Systems HW/SW Partitioning Based on Lagrangian Relaxation Method

  • Conference paper
  • First Online:
Innovations in Smart Cities and Applications (SCAMS 2017)

Part of the book series: Lecture Notes in Networks and Systems ((LNNS,volume 37))

Included in the following conference series:

Abstract

Embedded systems (ES) are nowadays, in the heart of every complex electronic device. An ES is a system that combines both hardware blocks and software blocks in a single chip. The necessity to decrease the cost and the development time of the design flow of the ES and to keep the overall performance of the system require the development of new design approaches for such systems. The compound design (co-design) is a very interesting approach used to fulfill the latter requirements. The partitioning of blocks between hardware and software is one of the most important steps in this process of co-design. In this paper, we present a novel method (heuristic) based on optimal path optimization technique (lagrangian relaxation method) to deal with the partitioning problem. The solution aims to optimize the hardware area (cost) of the ES while respecting a given constraint time of execution. To validate the effectiveness of our approach, we give a comparison with the results obtained with the Genetic Algorithm (GA).

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

Access this chapter

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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Schaumont, P.: A practical introduction to hardware/software codesign (2012)

    Google Scholar 

  2. Clausen, J.: Branch and bound algorithms-principles and examples. Department of Computer Science, University of Copenhagen, pp. 1–30 (1999)

    Google Scholar 

  3. Mann, Z.A., Orban, A., Arato, P.: Finding optimal hardware/software partitions. Formal Meth. Syst. Des. 31(3), 241–263 (2007)

    Article  MATH  Google Scholar 

  4. Niemann, R., Marwedel, P.: Hardware/software partitioning using integer programming. In: Proceedings of the 1996 European Conference on Design and Test, p. 473 (1996)

    Google Scholar 

  5. Knudsen, P.V., Madsen, J.: Pace: a dynamic programming algorithm for hardware/software partitioning. In: Proceedings of the 4th International Workshop on Hardware/Software Co-design, p. 85 (1996)

    Google Scholar 

  6. Eles, P., Peng, Z., Kuchcinski, K., Doboli, A.: Hardware/software partitioning with iterative improvement heuristics. In: Proceedings of the 9th International Symposium on System Synthesis, p. 71 (1996)

    Google Scholar 

  7. Banerjee, S., Dutt, N.: Very fast simulated annealing for hw-sw partitioning. Technical report, CECS-TR-04-17 (2004)

    Google Scholar 

  8. Zhao, X., Zhang, H., Jiang, Y., Song, S., Jiao, X., Gu, M.: An effective heuristic-based approach for partitioning. J. Appl. Math. 2013, 1–8 (2013)

    Google Scholar 

  9. Saha, D., Mitra, R., Basu, A.: Hardware software partitioning using genetic algorithm. In: Proceedings of the Tenth International Conference on VLSI Design, pp. 155–160 (1997)

    Google Scholar 

  10. Purnaprajna, M., Reformat, M., Pedrycz, W.: Genetic algorithms for hardware-software partitioning and optimal resource allocation. J. Syst. Architect. 53(7), 339–354 (2007)

    Article  Google Scholar 

  11. Arato, P., Juhasz, S., Mann, Z.A., Orban, A., Papp, D.: Hardware-software partitioning in embedded system design. In: Proceedings of the 2003 IEEE International Symposium on Intelligent Signal Processing, pp. 197–202 (2003)

    Google Scholar 

  12. Chehida, K.B., Auguin, M.: Hw/sw partitioning approach for reconfigurable system design. In: Proceedings of the 2002 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, pp. 247–251 (2002)

    Google Scholar 

  13. Knerr, B., Holzer, M., Rupp, M.: Novel genome coding of genetic algorithms for the system partitioning problem. In: Proceedings of the 2007 International Symposium on Industrial Embedded Systems, pp. 134–141 (2007)

    Google Scholar 

  14. Li, S.G., Feng, F.J., Hu, H.J., Wang, C., Qi, D.: Hardware/software partitioning algorithm based on genetic algorithm. J. Comput. 9(6), 1309–1315 (2014)

    Google Scholar 

  15. Mudry, P.A., Zuerey, G., Tempesti, G.: A hybrid genetic algorithm for constrained hardware-software partitioning. In: Proceedings of the 2006 IEEE Design and Diagnostics of Electronic Circuits and systems, pp. 1–6 (2006)

    Google Scholar 

  16. Li, G., Feng, J., Wang, C., Wang, J.: Hardware/software partitioning algorithm based on the combination of genetic algorithm and tabu search. Eng. Rev. 34(2), 151–160 (2014)

    MathSciNet  Google Scholar 

  17. Lin, G., Zhu, W., Ali, M.M.: A tabu search-based memetic algorithm for hardware/software partitioning. Math. Prob. Eng. 2014, 1–15 (2014)

    Google Scholar 

  18. Bhuvaneswari, M., Jagadeeswari, M.: Hardware/software partitioning for embedded systems. In: Application of Evolutionary Algorithms for Multi-objective Optimization in VLSI and Embedded Systems, pp. 21–36 (2015)

    Google Scholar 

  19. Lin, G.: An iterative greedy algorithm for hardware/software partitioning. In: Proceedings of 2013 Ninth International Conference on Natural Computation (ICNC), pp. 777–781 (2013)

    Google Scholar 

  20. Sim, J.E., Mitra, T., Wong, W.F.: Defining neighborhood relations for fast spatial-temporal partitioning of applications on reconfigurable architectures. In: Proceedings of 2008 International Conference on ICECE Technology, pp. 121–128 (2008)

    Google Scholar 

  21. Rini, D.P., Shamsuddin, S.M., Yuhaniz, S.S.: Particle swarm optimization: technique, system and challenges. Int. J. Comput. Appl. 14(1), 19–26 (2011)

    Google Scholar 

  22. Farmahini-Farahani, A., Kamal, M., Fakhraie, S.M., Safari, S.: HW/SW partitioning using discrete particle swarm. In: Proceedings of the 17th ACM Great Lakes symposium on VLSI, pp. 359–364 (2007)

    Google Scholar 

  23. Wu, J., Srikanthan, T., Lei, T.: Efficient heuristic algorithms for path-based hardware/software partitioning. Math. Comput. Model. 51(7), 974–984 (2010)

    Article  MATH  Google Scholar 

  24. Fisher, M.L.: The lagrangian relaxation method for solving integer programming problems. Manage. Sci. 27(1), 1–18 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  25. Czibula, O.G., Gu, H., Zinder, Y.: Lagrangian relaxation versus genetic algorithm based matheuristic for a large partitioning problem. Theor. Comput. Sci. (2017)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut National des Postes et Télécomunications, Lab. STRS, Av. Allal El Fassi, Madinat Al Irfane, Rabat, Morocco

    Adil Iguider, Mouhcine Chami, Oussama Elissati & Abdeslam En-Nouaary

Authors
  1. Adil Iguider
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mouhcine Chami
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Oussama Elissati
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Abdeslam En-Nouaary
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Adil Iguider .

Editor information

Editors and Affiliations

  1. Computer Sciences Department, Faculty of Sciences and Techniques, Abdelmalek Essaadi University, Tangier, Morocco

    Mohamed Ben Ahmed

  2. Computer Sciences Department, Faculty of Sciences and Techniques, Abdelmalek Essaadi University, Tangier, Morocco

    Anouar Abdelhakim Boudhir

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer International Publishing AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Iguider, A., Chami, M., Elissati, O., En-Nouaary, A. (2018). Embedded Systems HW/SW Partitioning Based on Lagrangian Relaxation Method. In: Ben Ahmed, M., Boudhir, A. (eds) Innovations in Smart Cities and Applications. SCAMS 2017. Lecture Notes in Networks and Systems, vol 37. Springer, Cham. https://doi.org/10.1007/978-3-319-74500-8_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-74500-8_14

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-74499-5

  • Online ISBN: 978-3-319-74500-8

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation