HW/SW partitioning using discrete particle swarm

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 , R. Vemuri, Hardware/software partitioning with integrated hardware design space exploration, Proceedings of the conference on Design, automation and test in Europe, p.28-35, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 7: Robert P. Dick , David L. Rhodes , Wayne Wolf, TGFF: task graphs for free, Proceedings of the 6th international workshop on Hardware/software codesign, p.97-101, March 15-18, 1998, Seattle, Washington, United States
• 8: Karthikeyan Bhasyam , Kia Bazargan, HW/SW Codesign Incorporating Edge Delays Using Dynamic Programming, Proceedings of the Euromicro Symposium on Digital Systems Design, p.264, September 01-06, 2003
• 9: Karam S. Chatha , Ranga Vemuri, MAGELLAN: multiway hardware-software partitioning and scheduling for latency minimization of hierarchical control-dataflow task graphs, Proceedings of the ninth international symposium on Hardware/software codesign, p.42-47, April 2001, Copenhagen, Denmark [doi>10.1145/371636.371671]
• 10: Rolf Ernst, Codesign of Embedded Systems: Status and Trends, IEEE Design & Test, v.15 n.2, p.45-54, April 1998 [doi>10.1109/54.679207]
• 11: Wayne Wolf, A Decade of Hardware/Software Codesign, Computer, v.36 n.4, p.38-43, April 2003 [doi>10.1109/MC.2003.1193227]
• 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: Ralf Niemann, Hardware/Software CO-Design for Data Flow Dominated Embedded Systems, Kluwer Academic Publishers, Norwell, MA, 1998
• 14: Raymond A. Wildman , Joshua I. Kramer , Daniel S. Weile , Phillip Christie, Multi-objective optimization of interconnect geometry, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.1, p.15-23, February 2003 [doi>10.1109/TVLSI.2002.808460]
• 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 , A. Basu , R. S. Mitra, Hardware Software Partitioning Using Genetic Algorithm, Proceedings of the Tenth International Conference on VLSI Design: VLSI in Multimedia Applications, p.155, January 04-07, 1997
• 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: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 22: Karam S. Chatha , Ranga Vemuri, Hardware-Software partitioning and pipelined scheduling of transformative applications, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.10 n.3, p.193-208, June 2002 [doi>10.1109/TVLSI.2002.1043323]
• 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: Marco Sgroi , Luciano Lavagno , Alberto Sangiovanni-Vincentelli, Formal Models for Embedded System Design, IEEE Design & Test, v.17 n.2, p.14-27, April 2000 [doi>10.1109/54.844330]
• 25: Agoston E. Eiben , J. E. Smith, Introduction to Evolutionary Computing, SpringerVerlag, 2003
• 26: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

General Terms:
Algorithms, Design, Management

Keywords:
HW/SW partitioning, discrete particle swarm optimizationdiscrete particle swarm optimization