HW/ SW Partitioning Algorithms for Multi-objective Optimization in Embedded Systems

By Adil Iguider, oussama elissati, mouhcine chami, Abdeslam En-Nouaary

Abstract


One of the most crucial steps in the design of modern Embedded Systems (ES) is the partitioning the system’s functionalities between the hardware (HW) blocks and the software (SW) blocks. The process of hardware software partitioning (HSP) is driven by several non functional requirements factors. Several works studied the influence of the execution time and the hardware area (cost) factors while dealing with the HSP problem; other works included also the power consumption factor. This article gives a study the HSP problem while considering several factors (ES metrics) and presents two approaches to solve the problem. The first approach has the objective of optimizing simultaneously a number of metrics while respecting a constraint on the global hardware area (cost metric), this approach is implemented using 0-1 Knapsack Problem (KP) algorithm; experimental results show that the algorithm is very fast and gives more reliable solutions comparing to well-known algorithms such as the Genetic Algorithm (GA) and the Simulated Annealing (SA) algorithm. The second approach aims to optimize the hardware cost while respecting given constraints on the other metrics; the proposed approach is based on Balas method.


Full Text:

PDF

References


R. Niemann and P. Marwedel, “Hardware/software partitioning using integer programming,” in Proceedings of the 1996 European conference on Design and Test, 1996, p. 473.

W. Jigang and S. Thambipillai, “A branch-and-bound algorithm for hardware/software partitioning,” in Proceedings of the Fourth IEEE International Symposium on Signal Processing and Information Technology, 2004, pp. 526–529.

P. V. Knudsen and J. Madsen, “Pace: A dynamic programming algorithm for hardware/software partitioning,” in Proceedings of the 4th International Workshop on Hardware/Software Co-Design, 1996, p. 85.

Y. Jing, J. Kuang, J. Du, and B. Hu, “Application of improved simulated annealing optimization algorithms in hardware/software partitioning of the reconfigurable system-on-chip,” Communications in Computer and Information Science, vol. 405, 2014.

C. W. Jinfu Feng, Junhua Hu and D. Qi, “Hardware/software partitioning algorithm based on genetic algorithm,” Journal of Computers, vol. 9, pp.

–1315, 2014.

J. Wu, P. Wang, S.-K. Lam, and T. Srikanthan, “Efficient heuristic and tabu search for hardware/software partitioning,” The Journal of Super computing, vol. 66, pp. 118–134, 2013.

J. W. Tang, Y. W. Hau, and M. N. Marsono, “Hardware/software partitioning of embedded system-on-chip applications,” in proceedings of the IFIP/IEEE International Conference on Very Large Scale Integration (VLSI-SoC), 2015, pp. 331–336.

L. Zhang, C. Xu, T. Zheng, and T. Li, “Hardware/software partitioning based on greedy algorithm and simulated annealing algorithm,” Journal of Computer Applications, vol. 33, no. 07, p. 1898, 2013.

Chaumont, P. A practical introduction to hardware/software codesign. New York: Springer. 2013.

Banerjee, S. &Dutt, N. Very fast simulated annealing for hw-sw partitioning.Technical Report, CECS-TR-04--17. 2004.

Madhura, P. & Marek R. &Witold P.Genetic algorithms for hardware software partitioning and optimal resource allocation. Journal of Systems Architecture, l (53), 339 – 354. 2007

Knerr, B. &Holzer, M. & Rupp, M. (2007).Novel genome coding of genetic algorithms for the system partitioning problem. International Symposium on Industrial Embedded Systems, SIES'07.134-141.

Lin, G. & Zhu, W. & Ali, M. A tabu search-based memetic algorithm for hardware/software partitioning.Mathematical Problems in Engineering .2014

Sim, J. &Mitra, T. & Wong, W. Defining neighborhood relations for fast spatial-temporal partitioning of applications on reconfigurable architectures. International Conference on International Conference on, 121-128. 2008

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

Prakasam, S. & Venkatachalam, M. &Saroja, M. &Pradheep, N. &Gowthaman P. A novel bat inspired algorithm for hardware-software codesign partitioning. International Journal of Multidisciplinary Research and Development, l (3), 88-92. 2016

Knerr, B. &Holzer, M. & Rupp, M. HW/SW partitioning using high level metrics. 2004

Wu, J. &Srikanthan, T. & Zou, G. New model and algorithm for hardware/software partitioning. Journal of Computer Science and Technology, l(23), 644-651. 2008

J. Resano, D. Mozos, E. Perez, H. Mecha, and J. Septien, “A hardware/ software partitioning and scheduling approach for embedded systems with low-power and high performance requirements,” in International Workshop on Power and Timing Modeling, Optimization and Simulation, 2003, pp. 580–589.

E. Sha, L. Wang, Q. Zhuge, J. Zhang, and J. Liu, “Power efficiency for hardware/software partitioning with time and area constraints on mpsoc,” International Journal of Parallel Programming, vol. 43, no. 3, pp. 381–402, 2015.

W. Shi, J. Wu, S.-k. Lam, and T. Srikanthan, “Algorithms for bi- objective multiple-choice hardware/software partitioning,” Computers & Electrical Engineering, vol. 50, pp. 127–142, 2016.

P. Eles, Z. Peng, K. Kuchcinski, and A. Doboli, “Hardware/software partitioning with iterative improvement heuristics,” in Proceedings of the 9th International Symposium on System Synthesis, 1996, pp. 71–.

A. Geoffrion, “Integer Programming by Implicit Enumeration and Balas’ Method”, in SIAM Review, Vol. 9, No. 2 pp. 178-190, April 1967