Hybrid two-stage HW/SW partitioning algorithm for dynamic partial reconfigurable FPGAs

doi:10.16511/j.cnki.qhdxxb.2016.21.004

Download: PDF(1130 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract More and more hardware platforms are providing dynamic partial reconfiguration; thus, traditional hardware/software partitioning algorithms are no longer applicable. Some studies have analyzed the dynamic partial reconfiguration as mixed-integer linear programming (MILP) models to get solutions. However, the MILP models are slow and can only handle small problems. This paper uses heuristic algorithms to determine the status of some critical tasks to reduce the scale of the MILP problem for large problems. Tests show that this method is about 200 times faster with the same solution quality as the traditional mathematical programming method.

Keywords HW/SW partitioning dynamic partial reconfiguration heuristic method mixed-integer linear programming (MILP)

ZTFLH:

TP301.6

Issue Date: 15 March 2016

	Service

	E-mail this article
	E-mail Alert
	RSS
	Articles by authors

	MA Yuchun
	ZHANG Chao
	LUK Wayne

Cite this article:

MA Yuchun,ZHANG Chao,LUK Wayne. Hybrid two-stage HW/SW partitioning algorithm for dynamic partial reconfigurable FPGAs[J]. Journal of Tsinghua University(Science and Technology), 2016, 56(3): 246-252,261.

URL:

http://jst.tsinghuajournals.com/EN/10.16511/j.cnki.qhdxxb.2016.21.004 OR http://jst.tsinghuajournals.com/EN/Y2016/V56/I3/246

[1] 张良, 徐成, 田峥, 等. 基于贪心算法和模拟退火算法的软硬件划分[J]. 计算机应用, 2013(07):1898-1902. ZHANG Liang, XU Cheng, TIAN Zheng, et al. Hardware/software partitioning based on greedy algorithm and simulated annealing algorithm[J]. Journal of Computer Applications, 2013(7):1898-1902. (in Chinese)
[2] 李正民, 郭金金, 吕莹莹. 一种嵌入式系统软硬件划分算法[J]. 计算机仿真, 2011(10):204-207. LI Zhengmin, GUO Jinjin, LV Yingying. Simulation research on HW-SW partitioning of embedded system based on ant colony algorithm[J].Computer Simulation, 2011(10):204-207. (in Chinese)
[3] 李春江. 面向动态可重构片上系统的过程级软硬件划分方法研究[D]. 长沙:湖南大学, 2010. LI Chunjiang. Research on Hardware and Software Partitioning Method on Process Level for Dynamically Reconfigurable System-on-Chip[D]. Changsha:Hunan University, 2010. (in Chinese)
[4] Niemann R, Marwedel P. Hardware/software partitioning using integer programming[C]//European Design and Test Conference. Paris, France:IEEE Press, 1996:473-479.
[5] Cordone R, Redaelli F, Redaelli M A, et al. Partitioning and scheduling of task graphs on partially dynamically reconfigurable FPGAs[J].Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 2009,28(5):662-675.
[6] 王璞, 武继刚. 高效软硬件划分算法及其提升技术[J]. 计算机科学, 2012(1):290-294. WANG Pu, WU Jigang. Efficient heursitic and tabu search for hardware/software partitioning[J].Computer Science,2012(1):290-294. (in Chinese)
[7] Banerjee S, Bozorgzadeh E, Dutt N D. Integrating physical constraints in HW-SW partitioning for architectures with partial dynamic reconfiguration[J].Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, 2006,14(11):1189-1202.
[8] LIU Peng, WU Jigang, WANG Yongji. Integrated heuristic for hardware/software co-design on reconfigurable devices[C]//Parallel and Distributed Computing, Applications and Technologies (PDCAT). Beijing, China:IEEE Press, 2012:370-375.
[9] Xilinx. Partial Reconfiguration User Guide.[EB/OL].[2015-01-15].http://www.xilinx.com/support/documentation/sw_manuals/xilinx14_7/ug702.pdf.
[10] HE Running, MA Yuchun, ZHAO Kang, et al. ISBA:An independent set-based algorithm for automated partial reconfiguration module generation[C]//International Conference on Computer-Aided Design (ICCAD). San Jose, CA, USA:IEEE Press, 2012:500-507.
[11] MA Yuchun, LIU Jinglan, ZHANG Chao, et al. HW/SW partitioning for region-based dynamic partial reconfigurable FPGAs[C]//Computer Design (ICCD), IEEE International Conference on, Seoul, Korea, IEEE Press, 2014:470-476.
[12] Hara Y, Tomiyama H, Honda S, et al. Proposal and quantitative analysis of the CHStone benchmark program suite for practical C-based high-level synthesis[J]. Journal of Information Processing, 2009(17), 242-254,
[13] UCSB. Benchmark[EB/OL].[2015-01-15]. http://express.ece.ucsb.edu/benchmark/.
[14] Lindo. Lindo Software Products[EB/OL].[2015-01-15]. http://www.lindo.com.

[1]	WU Bin, XIAO Yan, ZHANG Yunlei. Parallel incremental dynamic community detection algorithm based on Spark[J]. Journal of Tsinghua University(Science and Technology), 2017, 57(10): 1030-1037.
[2]	LIU Yang, WEI Wei. Fast Nash bargaining algorithm for resource scheduling problems with a large number of media streaming channels[J]. Journal of Tsinghua University(Science and Technology), 2017, 57(10): 1056-1062.
[3]	HAN Donghong, SONG Ming, ZHANG Hongliang, WANG Jiaxi, WANG Jiaxing, WANG Guoren. Algorithm for clustering uncertain data streams based on density[J]. Journal of Tsinghua University(Science and Technology), 2017, 57(8): 884-891.
[4]	WAN Xin, LIU Ximing, MIAO Jichen, WU Zhifang. Improved linear interpolation algorithm for multi-slice helical CT[J]. Journal of Tsinghua University(Science and Technology), 2016, 56(12): 1346-1351.
[5]	ZHAO Jingling, CHEN Shilei, CAO Mengchen, CUI Baojiang. Malware algorithm recognition based on offline instruction-flow analyse[J]. Journal of Tsinghua University(Science and Technology), 2016, 56(5): 484-492.
[6]	CHEN Donghui, CHEN Ling, WANG Junkai, WU Yong, WANG Jingchang. Approximation algorithms for aggregate queries on uncertain data[J]. Journal of Tsinghua University(Science and Technology), 2018, 58(3): 231-236.