Hardware/Software Partitioning of Streaming Applications for Multi-Processor System-on-Chip
Keywords:
Branch-and-bound, hardware/software partitioning, multi-processor, system-on-chip, streaming applicationAbstract
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.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.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:Authors hold and retain copyright, and grant the journal right of first publication, with the work after publication simultaneously licensed under a Creative Commons Attribution 4.0 License CC BY that permits any use, reproduction and distribution of the work and article without further permission provided that the original work is properly cited.
Authors are permitted and encouraged to post their work online in institutional repositories, website and other social media before and after publication, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
