摘要
异构片上系统(System-on-Chip,SoC)在同一芯片上集成了多种类型的处理器,在处理能力、尺寸、重量、功耗等各方面有较大优势,因此在很多领域得到了应用。具有动态部分可重构特性的SoC(Dynamic Partial Reconfigurability SoC,DPR-SoC)是异构SoC的一种重要类型,这种系统兼具了软件的灵活性和硬件的高效性。此类系统的设计通常涉及到软硬件协同问题,其中如何进行应用的软硬件划分是保证系统实时性的关键技术。DPR-SoC中的软硬件划分问题可归类为组合优化问题,问题目标是获得调度长度最短的调度方案,包括任务映射、排序和定时。混合整数线性规划(Mixed Integer Linear Programming,MILP)是求解组合优化问题的一种有效方法;然而,将具体问题建模为MILP模型是求解问题的关键一环,不同建模方式对问题求解时间有重要影响。已有针对DPR-SoC软硬件划分问题的MILP模型存在大量变量和约束方程,对问题求解时间产生了不利影响;此外,其假设条件过多,使得求解结果与实际应用不符。针对这些问题,提出了一种新颖的MILP模型,其极大地降低了模型复杂度,提高了求解结果与实际应用的符合度。将应用建模成DAG图,并使用整数线性规划求解工具对问题进行求解。大量求解结果表明,新的模型能够有效地降低模型复杂度,缩短求解时间;并且随着问题规模的增大,所提模型在求解时间上的优势表现得更加显著。
Heterogeneous System-on-Chip(SoC)integrates multiple types of processors on the same chip.It has great advantages in many aspects such as processing capacity,size,weight and power consumption,which makes it be widely used in many fields.The SoC with dynamic partial reconfigurability is an important type of heterogeneous SoC,which combines software flexibility with hardware efficiency.The design of such systems usually involves hardware and software coordination problems,and how to divide the software and hardware of the application is the key technology to ensure the real-time performance of the system.The hardware and software partitioning technology in this kind of system is a key technology for ensuring real-time system performance.The problem of hardware and software partitioning in DPR-SoC can be classified as a combinatorial optimization problem.The goal of this problem is to obtain the optimal solution with the shortest schedule length,including task mapping,sorting,and timing.Mixed integer linear programming(MILP)is an effective method for solving combinatorial optimization problems.However,building a proper model for a specific problem is the key part of solving the problem,which has great impacts on solving time.The existing MILP models for the HW/SW partitioning of DPR-SoC have a lot of variables and constraint equations.The redundant variables and constraint equations have negative impacts on solving time.Besides,the solution of the available method does not match with actual applications,for it makes too many assumptions.Basing on these exiting problems proposes a novel model which focuses on reducing the model complexity and improving its suitability to the application.Model the application as a DAG graph and solve the problem by an integer linear programming solver.Plenty of results show that the proposed model can reduce the model complexity and shorten the solving time.Further,as the scale of the problem grows,the solve time shortened more significantly.
作者
朱丽花
王玲
唐麒
魏急波
ZHU Li-hua;WANG Ling;TANG Qi;WEI Ji-bo(College of Electrical and Information Engineering,Hunan University,Changsha 410082,China;College of Electronic Science,National University of Defense Technology,Changsha 410073,China)
出处
《计算机科学》
CSCD
北大核心
2020年第4期18-24,共7页
Computer Science
基金
国家自然科学基金(61601482)。
