Hardware/Software Partitioning of Streaming Applications for Multi-Processor System-on-Chip

M. N. Marsono, J. W. Tang, Y. W. Hau

Abstract

Hardware/software (HW/SW) co-design has emerged as a crucial and integral part in the development of various embedded applications. Moreover, the increases in the number of embedded multimedia and medical applications make streaming throughput an important attribute of Multi-Processor System-on-Chip (MPSoC). As an important development step, HW/SW partitioning affects the system performance. This paper formulates the optimization of HW/SW partitioning aiming at maximizing streaming throughput with predefined area constraint, targeted for multi-processor system with hardware accelerator sharing capability. Software-oriented and hardware-oriented greedy heuristics for HW/SW partitioning are proposed, as well as a branch-and-bound algorithm with best-first search that utilizes greedy results as initial best solution. Several random graphs and two multimedia applications (JPEG encoder and MP3 decoder) are used for performance benchmarking against brute force ground truth. Results show that the proposed greedy algorithms produce fast solutions which achieve 87.7% and 84.2% near-optimal solution respectively compared to ground truth result. With the aid of greedy result as initial solution, the proposed branch-and-bound algorithm is able to produce ground truth solution up to 2.4741e+8 times faster in HW/SW partitioning time compared to exhaustive brute force method.

Keywords

Branch-and-bound; hardware/software partitioning; multi-processor; system-on-chip; streaming application

Article Metrics

Abstract view : 1016 times
PDF - 116 times

Full Text:

PDF

References

S. Wang and S. Dey, “Adaptive mobile cloud computing to enable rich mobile multimedia applications,” IEEE Transactions on Multimedia, vol. 15, no. 4, pp. 870–883, 2013.

S. Le Beux, G. Bois, G. Nicolescu, Y. Bouchebaba, M. Langevin, and P. Paulin, “Combining mapping and partitioning exploration for noc-based embedded systems,” Journal of Systems Architecture, vol. 56, no. 7, pp. 223–232, 2010.

T.-Y. Lee, Y.-H. Fan, Y.-M. Cheng, C.-C. Tsai, and R.-S. Hsiao, “Enhancement of hardware-software partition for embedded multiprocessor fpga systems,” in Third International Conference on Intelligent Information Hiding and Multimedia Signal Processing, 2007. IIHMSP 2007., vol. 1. IEEE, 2007, pp. 19–22.

B. Mei, P. Schaumont, and S. Vernalde, “A hardware-software partitioning and scheduling algorithm for dynamically reconfigurable embedded systems,” 2000.

F. Clouté, J.-N. Contensou, D. Esteve, P. Pampagnin, P. Pons, and Y. Favard, “Hardware/software co-design of an avionics communication protocol interface system: an industrial case study,” in Proceedings of the Seventh International Workshop on Hardware/Software Codesign, 1999.(CODES’99). IEEE, 1999, pp. 48–52.

P. Arató, Z. Á. Mann, and A. Orbán, “Algorithmic aspects of hardware/software partitioning,” ACM Transactions on Design Automation of Electronic Systems (TODAES), vol. 10, no. 1, pp. 136–156, 2005.

W. Jigang, T. Srikanthan, and G. Chen, “Algorithmic aspects of hardware/software partitioning: 1d search algorithms,” IEEE Transactions on Computers, vol. 59, no. 4, pp. 532–544, 2010.

G. Li, J. Feng, C. Wang, and J. Wang, “Hardware/software partitioning algorithm based on the combination of genetic algorithm and tabu search,” Engineering Review, vol. 34, no. 2, pp. 151–160, 2014.

G. Lin, W. Zhu, and M. M. Ali, “A tabu search-based memetic algorithm for hardware/software partitioning,” Mathematical Problems in Engineering, vol. 2014, 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, no. 1, pp. 118–134, 2013.

H. Ye and J.-G. Wu, “Computing models and algorithms for complex co-design systems,” Journal of University of Electronic Science and Technology of China, vol. 40, no. 3, pp. 333–345, 2011.

X. Zhao, H. Zhang, Y. Jiang, S. Song, X. Jiao, and M. Gu, “An effective heuristic-based approach for partitioning,” Journal of Applied Mathematics, vol. 2013, 2013.

J. Henkel and R. Ernst, “An approach to automated hardware/software partitioning using a flexible granularity that is driven by high-level estimation techniques,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 9, no. 2, pp. 273–289, 2001.

A. Kalavade and E. A. Lee, “The extended partitioning problem: hardware/software mapping, scheduling, and implementation-bin selection,” Design Automation for Embedded Systems, vol. 2, no. 2, pp. 125–163, 1997.

K. S. Chatha and R. Vemuri, “Hardware-software partitioning and pipelined scheduling of transformative applications,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 10, no. 3, pp. 193–208, 2002.

S. Bakshi and D. D. Gajski, “Hardware/software partitioning and pipelining,” in Proceedings of the 34th annual Design Automation Conference. ACM, 1997, pp. 713–716.

S. Bakshi and D. D. Gajski, “Partitioning and pipelining for performance-constrained hardware/software systems,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 7, no. 4, pp. 419–432, 1999.

N. N. Bı̀nh, M. Imai, A. Shiomi, and N. Hikichi, “A hardware/software partitioning algorithm for designing pipelined asips with least gate counts,” in Design Automation Conference Proceedings 1996, 33rd. IEEE, 1996, pp. 527–532.

M. B. Abdelhalim and S.-D. Habib, “An integrated high-level hardware/software partitioning methodology,” Design Automation for Embedded Systems, vol. 15, no. 1, pp. 19–50, 2011.

P. K. Nath and D. Datta, “Multi-objective hardware–software partitioning of embedded systems: A case study of jpeg encoder,” Applied Soft Computing, vol. 15, pp. 30–41, 2014.

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, pp. 1–22, 2013.

A. Bhattacharya, A. Konar, S. Das, C. Grosan, and A. Abraham, “Hardware software partitioning problem in embedded system design using particle swarm optimization algorithm,” in International Conference on Complex, Intelligent and Software Intensive Systems, 2008. CISIS 2008. IEEE, 2008, pp. 171–176.

J. Jeon and K. Choi, “Loop pipelining in hardware-software partitioning,” in Design Automation Conference 1998. Proceedings of the ASP-DAC’98. Asia and South Pacific. IEEE, 1998, pp. 361–366.

J. Wu, Q. Sun, and T. Srikanthan, “Algorithmic aspects for multiple-choice hardware/software partitioning,” Computers & Operations Research, vol. 39, no. 12, pp. 3281–3292, 2012.

D. A. Patterson and J. L. Hennessy, Computer organization and design: the hardware/software interface. Newnes, 2013.

R. P. Dick, D. L. Rhodes, and W. Wolf, “Tgff: task graphs for free,” in Proceedings of the 6th international workshop on Hardware/software codesign. IEEE Computer Society, 1998, pp. 97–101.

Refbacks

  • There are currently no refbacks.