skip to main content
10.1145/1228784.1228870acmconferencesArticle/Chapter ViewAbstractPublication PagesglsvlsiConference Proceedingsconference-collections
Article

HW/SW partitioning using discrete particle swarm

Published: 11 March 2007 Publication History

Abstract

Hardware/Software partitioning is one of the most important issues of codesign of embedded systems, since the costs and delays of the final results of a design will strongly depend on partitioning. We present an algorithm based on Particle Swarm Optimization to perform the hardware/software partitioning of a given task graph for minimum cost subject to timing constraint. By novel evolving strategy, we enhance the efficiency and result's quality of our partitioning algorithm in an acceptable run-time. Also, we compare our results with those of Genetic Algorithm on different task graphs. Experimental results show the algorithm's effectiveness in achieving the optimal solution of the HW/SW partitioning problem even in large task graphs.

References

[1]
J. Kennedy and R. Eberhart, "Particle swarm optimization," in Proc. IEEE Intl. Conf. Neural Networks, vol. 4, 1995, pp. 1942--1948.
[2]
Y. Shi and R. Eberhart, "A modified particle swarm optimizer," in Proc. IEEE World Cong. on Computational Intelligence, 1998, pp. 96--73.
[3]
J. Kennedy and R. Eberhart, "A discrete binary version of the particle swarm algorithm," in Proc. IEEE Conf. Syst., Man, and Cybernetics, Orlando, FA, 1997, pp. 4104--4109.
[4]
S. Yang, M. Wang, and L. Jiao, "A quantum particle swarm optimization," in Cong. Evolutionary Computing, vol. 1, Jun. 2004, pp. 320--324.
[5]
B. Al-kazemi and C. K. Mohan, "Multi-phase discrete particle swarm optimization," in Proc. Intl. Workshop Frontiers in Evolutionary Algorithms, 2002.
[6]
V. Srinivasan, S. Radhakrishnan, and R. Vemuri, "Hardware software partitioning with integrated hardware design space exploration," in Proc. Design Automation and Test in Europe, 1998, pp. 28--35.
[7]
R. P. Dick, D. I. Rhodes, and W. Wolf, "TGFF: task graphs for free," in Proc. Int. Workshop Hardware-Software codesign, Mar. 1998, pp. 97--101.
[8]
K. Bhasyam and K. Bazargan, "HW/SW codesign incorporating edge delays using dynamic programming," in Proc. Euromicro Symp. Digital System Design, Sept. 2003.
[9]
K. S. Chatha and R. Vemuri, "MAGELLAN: multiway hardware software partitioning and scheduling for latency minimization of hierarchical control-dataflow task graphs," in Proc. Intl. Conf. Hardware-Software Codesign and System Synthesis, 2001.
[10]
R. Ernst, "Codesign of embedded systems: status and trends," in Proc. IEEE Design & Test of Computers, 1998, pp.45--54.
[11]
W. Wolf, "A decade of hardware/software codesign," in Computer, pp. 38--43, Apr. 2003.
[12]
R. Niemann and P. Marwedel, "An algorithm for hardware/software partitioning using mixed integer linear programming," in Proc. Design Automation for Embedded Systems, special issue: Partitioning Methods for Embedded Systems, vol. 2, Mar. 1997, pp. 165--193.
[13]
R. Niemann, "Hardware/software codesign for data flow dominated embedded systems," Kluwer Academic Publishers, 1998.
[14]
R. A. Wildman, J. I. Kramer, D. S. Weile, and P. Christie, "Multi-objective optimization of interconnect geometry," in IEEE Trans. On Very Large Scale Integration Syst., pp. 15--23, Feb. 2003.
[15]
K. C. Tan, T. H. Lee, and E. F. Khor, "Evolutionary algorithms for multi-objective optimization: performance assessments and comparisons," in Proc. Cong. Evo1utionary Computation, May 2001, pp. 979--986.
[16]
D. Saha, R. S. Mitra, and A. Basu, "Hardware software partitioning using genetic algorithm," in Proc. Int. Conf. VLSI design, Jan. 1997, pp. 155--160.
[17]
J. I. Hidalgo, and J. Lanchares, "Functional partitioning for hardware/software codesign using genetic algorithm," in Proc. Euromicro Conf., 1997.
[18]
M. J. W. Savage, Z. Salcic, G. Coghill, and G. Covic, "Extended genetic algorithm for codesign optimization of DSP syst. in FPGAs," in Proc. IEEE Intl. Conf. Field-Programmable Technology, Dec. 2004, pp. 291--294.
[19]
Y. Zou, Z. Zhuang, and H. Chen, "HW/SW partitioning based on genetic algorithm," in Proc. Cong. Evolutionary Computation, vol. 1, Jun. 2004, pp. 628--633.
[20]
P. Arato, S. Juhasz, Z. A. Mann, A. A. Orban, and D. Papp, "Hardware software partitioning in embedded system design," in Proc. Intelligent Signal Processing, Sept. 2003.
[21]
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms, MIT Press, 2001.
[22]
K. S. Chatha, and R. Vemuri, "Hardware-software partitioning and pipelined scheduling of transformative applications," in IEEE Trans. Very Large Scale Integration Syst., vol. 10, pp. 193--208, Jun. 2002.
[23]
P. Arato, S. Juhasz, Z. A. Mann, A. A. Orban, and, D. Papp, "Hardware software partitioning in embedded system design," in Proc. Intelegent Signal Processing, 2003.
[24]
M. Sgroi, L. Lavagno, and A. Sangiovanni-Vincentelli, "Formal Models for Embedded System Design," in IEEE Design & Test of Computers, vol. 17, no. 2, Jun. 2000, pp.14--27.
[25]
A. E. Eiben, and J. E. Smith, Introduction to evolutionary computing, Berlin Heildberg: Springer-Verlag, 2003.
[26]
T. Mitchell, Machine learning, New York, McGraw-Hill, 1997.

Cited By

View all
  • (2021)A Comparison of Different Optimization Algorithms for HW/SW Partitioning Using a High-Performance Cluster2021 IEEE/ACS 18th International Conference on Computer Systems and Applications (AICCSA)10.1109/AICCSA53542.2021.9686929(1-8)Online publication date: Dec-2021
  • (2020)Embedded Systems Hardware Software Partitioning Approach Based on Game TheoryInnovations in Smart Cities Applications Edition 310.1007/978-3-030-37629-1_40(542-555)Online publication date: 1-Feb-2020
  • (2019)Embedded systems hardware software partitioning using minimax algorithmProceedings of the 4th International Conference on Smart City Applications10.1145/3368756.3369009(1-6)Online publication date: 2-Oct-2019
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GLSVLSI '07: Proceedings of the 17th ACM Great Lakes symposium on VLSI
March 2007
626 pages
ISBN:9781595936059
DOI:10.1145/1228784
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 March 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. HW/SW partitioning
  2. discrete particle swarm optimizationdiscrete particle swarm optimization

Qualifiers

  • Article

Conference

GLSVLSI07
Sponsor:
GLSVLSI07: Great Lakes Symposium on VLSI 2007
March 11 - 13, 2007
Stresa-Lago Maggiore, Italy

Acceptance Rates

Overall Acceptance Rate 312 of 1,156 submissions, 27%

Upcoming Conference

GLSVLSI '25
Great Lakes Symposium on VLSI 2025
June 30 - July 2, 2025
New Orleans , LA , USA

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 28 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2021)A Comparison of Different Optimization Algorithms for HW/SW Partitioning Using a High-Performance Cluster2021 IEEE/ACS 18th International Conference on Computer Systems and Applications (AICCSA)10.1109/AICCSA53542.2021.9686929(1-8)Online publication date: Dec-2021
  • (2020)Embedded Systems Hardware Software Partitioning Approach Based on Game TheoryInnovations in Smart Cities Applications Edition 310.1007/978-3-030-37629-1_40(542-555)Online publication date: 1-Feb-2020
  • (2019)Embedded systems hardware software partitioning using minimax algorithmProceedings of the 4th International Conference on Smart City Applications10.1145/3368756.3369009(1-6)Online publication date: 2-Oct-2019
  • (2018)GPHMicroprocessors & Microsystems10.1016/j.micpro.2010.09.00535:1(68-80)Online publication date: 28-Dec-2018
  • (2018)Embedded Systems HW/SW Partitioning Based on Lagrangian Relaxation MethodInnovations in Smart Cities and Applications10.1007/978-3-319-74500-8_14(149-160)Online publication date: 21-Mar-2018
  • (2015)A new hardware/software partitioning technique2015 Tenth International Conference on Computer Engineering & Systems (ICCES)10.1109/ICCES.2015.7393030(113-118)Online publication date: Dec-2015
  • (2013)Reliable pre-scheduling delay estimation for hardware/software partitioning2013 IEEE 56th International Midwest Symposium on Circuits and Systems (MWSCAS)10.1109/MWSCAS.2013.6674880(1246-1250)Online publication date: Aug-2013
  • (2009)Study on Hardware Software partitioning using Immune Algorithm and its Convergence Property2009 IEEE International Conference on Intelligent Computing and Intelligent Systems10.1109/ICICISYS.2009.5358254(4-8)Online publication date: Dec-2009
  • (2007)Modeling communication cost and hardware alternatives in PSO based HW/SW partitioning2007 Internatonal Conference on Microelectronics10.1109/ICM.2007.4497673(111-114)Online publication date: Dec-2007

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media