一种针对动态部分可重构SoC软硬件划分的高效MILP模型
发布时间：2021-03-06 22:09
异构片上系统（System-on-Chip,SoC）在同一芯片上集成了多种类型的处理器,在处理能力、尺寸、重量、功耗等各方面有较大优势,因此在很多领域得到了应用。具有动态部分可重构特性的SoC（Dynamic Partial Reconfigurability SoC,DPR-SoC）是异构SoC的一种重要类型,这种系统兼具了软件的灵活性和硬件的高效性。此类系统的设计通常涉及到软硬件协同问题,其中如何进行应用的软硬件划分是保证系统实时性的关键技术。DPR-SoC中的软硬件划分问题可归类为组合优化问题,问题目标是获得调度长度最短的调度方案,包括任务映射、排序和定时。混合整数线性规划（Mixed Integer Linear Programming,MILP）是求解组合优化问题的一种有效方法;然而,将具体问题建模为MILP模型是求解问题的关键一环,不同建模方式对问题求解时间有重要影响。已有针对DPR-SoC软硬件划分问题的MILP模型存在大量变量和约束方程,对问题求解时间产生了不利影响;此外,其假设条件过多,使得求解结果与实际应用不符。针对这些问题,提出了一种新颖的MILP模型,其极大地降...
【文章来源】：计算机科学. 2020,47(04)北大核心
【文章页数】：7 页
【部分图文】：
FPGA异构系统
基于簇的软硬件划分流程如图2所示,FPGA可重构区域矩形的高可以自由设置。通常,软硬件划分的第一步是根据实际应用对资源的需求来配置可重构区域候选集,即图2中的P1,将任务按一定的算法分配到不同的簇内。分簇的方法有文献[27]提出的ISBA算法和ILP方法等。簇内任务的映射约束有:簇0内的任务只能分配到CPU上或者region0上执行;簇1内的任务只能分配到CPU上或者region1上执行。
以一个DAG为例,其任务数|V|=10,通信计算比CCR=0.1,簇数目m=2,区域的重构开销RT=2。考虑每个运算单元上的负载均衡,尽量保证每个簇内的任务数近似相等。图3给出了一个DAG模型示例的分簇结果,节点以及边的属性都在图中给出:V={n0,n1,…,n9},E={e0,e1,…,e11},PR={PR0,PR1}。图中标红的任务被划分到PR0={n0,n3,n4,n6,n7},剩下的任务被划分到PR1={n1,n2,n5,n8,n9}。图4给出了MILP-refined的求解结果,映射结果为P={n0,n1,n7},PR0={n3,n5,n8,n9},PR1={n2,n6,n4}。圆形节点代表应用的任务节点ni,其有3个属性,分别为任务的开始时间sni、执行耗时exni和结束时间endni。?r_ni∈PR0,PR1,其中r_ni为重构节点,具有重构开始时间rr_ni、重构开销RT、重构结束时间endrr_ni3个属性。
【参考文献】：
期刊论文
[1]RESSP:基于FPGA的可重构SDN交换结构[J]. 何璐蓓,厉俊男,杨翔瑞,孙志刚. 计算机科学. 2018(01)
[2]调度感知同步数据流建模[J]. 唐麒,吴尚峰,施峻武,魏急波. 国防科技大学学报. 2017(02)
[3]基于混合式两阶段的动态部分重构FPGA软硬件划分算法[J]. 马昱春,张超,Luk Wayne. 清华大学学报(自然科学版). 2016(03)
[4]FPGA上SHA-1算法的流水线结构实现[J]. 李磊,韩文报. 计算机科学. 2011(07)
[5]遗传和模拟退火融合的软硬件划分[J]. 李兰英,韩素娟,刁双君. 计算机工程与应用. 2010(28)
本文编号：3067903
【文章来源】：计算机科学. 2020,47(04)北大核心
【文章页数】：7 页
【部分图文】：
FPGA异构系统
基于簇的软硬件划分流程如图2所示,FPGA可重构区域矩形的高可以自由设置。通常,软硬件划分的第一步是根据实际应用对资源的需求来配置可重构区域候选集,即图2中的P1,将任务按一定的算法分配到不同的簇内。分簇的方法有文献[27]提出的ISBA算法和ILP方法等。簇内任务的映射约束有:簇0内的任务只能分配到CPU上或者region0上执行;簇1内的任务只能分配到CPU上或者region1上执行。
以一个DAG为例,其任务数|V|=10,通信计算比CCR=0.1,簇数目m=2,区域的重构开销RT=2。考虑每个运算单元上的负载均衡,尽量保证每个簇内的任务数近似相等。图3给出了一个DAG模型示例的分簇结果,节点以及边的属性都在图中给出:V={n0,n1,…,n9},E={e0,e1,…,e11},PR={PR0,PR1}。图中标红的任务被划分到PR0={n0,n3,n4,n6,n7},剩下的任务被划分到PR1={n1,n2,n5,n8,n9}。图4给出了MILP-refined的求解结果,映射结果为P={n0,n1,n7},PR0={n3,n5,n8,n9},PR1={n2,n6,n4}。圆形节点代表应用的任务节点ni,其有3个属性,分别为任务的开始时间sni、执行耗时exni和结束时间endni。?r_ni∈PR0,PR1,其中r_ni为重构节点,具有重构开始时间rr_ni、重构开销RT、重构结束时间endrr_ni3个属性。
【参考文献】：
期刊论文
[1]RESSP:基于FPGA的可重构SDN交换结构[J]. 何璐蓓,厉俊男,杨翔瑞,孙志刚. 计算机科学. 2018(01)
[2]调度感知同步数据流建模[J]. 唐麒,吴尚峰,施峻武,魏急波. 国防科技大学学报. 2017(02)
[3]基于混合式两阶段的动态部分重构FPGA软硬件划分算法[J]. 马昱春,张超,Luk Wayne. 清华大学学报(自然科学版). 2016(03)
[4]FPGA上SHA-1算法的流水线结构实现[J]. 李磊,韩文报. 计算机科学. 2011(07)
[5]遗传和模拟退火融合的软硬件划分[J]. 李兰英,韩素娟,刁双君. 计算机工程与应用. 2010(28)
本文编号：3067903
本文链接：https://www.wllwen.com/kejilunwen/dianzigongchenglunwen/3067903.html
