1、设计与应用计算机测量与控制 ()C o m p u t e r M e a s u r e m e n t&C o n t r o l 收稿日期:;修回日期:.基金项目:内江市科技孵化和成果转化专项资金项目().作者简介:饶广(),男,四川资中人,硕士,副教授,主要从事计算机应用方向的研究.饶云波(),男,四川泸州人,博士,副教授,主要从事图像/视频处理、三维重建、虚拟现实、人工智能方向的研究.引用格式:饶广,饶云波 F P G A中基于空间连续性的碎片度量及任务放置J计算机测量与控制,():文章编号:()D O I:/j c n k i /t p 中图分类号:T P 文献标识码:AF P G
2、 A中基于空间连续性的碎片度量及任务放置饶广,饶云波(内江职业技术学院,四川 内江 ;电子科技大学 信息与软件工程学院,成都 )摘要:针对部分可重构现场可编程门阵列允许在运行时对芯片的各个部分进行配置导致的区域碎片,提出了一种新的基于被占用(或空闲)空间的连续性的碎片度量及在线任务放置方法;首先从一维结构出发,得到一个单元序列对一个单元流S的碎片度量FS的贡献值,进而得到一维碎片度量值,它不依赖于到达任务的大小;然后将一维结构得到的碎片度量值结果推广到二维及高维结构;最后在F P G A上的在线任务放置过程中采用这种碎片度量方法,从而减少芯片碎片;在二维结构的F P G A上的仿真实验结果表明
3、,与通常采用的左下角、第一匹配和最佳匹配放置策略相比,采用提出的碎片度量及放置方法不仅在等待时间、分配时间和响应时间方面有所改善,而且提高了芯片的利用率,降低了失配率.关键词:F P G A;部分可重构;区域碎片;在线任务放置;时间;芯片利用率;失配率F r a g m e n t a t i o nM e t r i c a n dT a s kP l a c e m e n tB a s e do nS p a t i a lC o n t i n u i t y i nF P G AR AOG u a n g,R AOY u n b o(N e i j i a n gV o c a t
4、i o n a l&T e c h n i c a lC o l l e g e,N e i j i a n g ,C h i n a;S c h o o l o f I n f o r m a t i o na n dS o f t w a r eE n g i n e e r i n g,U n i v e r s i t yo fE l e c t r o n i cS c i e n c ea n dT e c h n o l o g yo fC h i n a,C h e n g d u ,C h i n a)A b s t r a c t:A i m e da t a r e a
5、f r a g m e n t r e s u l t e d i np a r t i a l l yr e c o n f i g u r a b l e f i e l d p r o g r a mm a b l eg a t ea r r a y s(F P G A),e a c hp a r to f t h ec h i pi s r e q u i r e d t ob e c o n f i g u r e da t r u n t i m e,an e wf r a g m e n tm e t r i c a n do n l i n e t a s kp l a c e
6、 m e n tm e t h o db a s e do n t h e c o n t i n u i t yo f o c c u p i e do r f r e es p a c e i sp r o p o s e d F i r s t l y,f r o mt h eo n e d i m e n s i o n a l s t r u c t u r e,t h e c o n t r i b u t i o no f o n e c e l l s e q u e n c e t o t h e f r a g m e n tm e t r i cFSo fo n e c
7、e l l s t r e a mS i s o b t a i n e d,a n d t h e n t h eo n e d i m e n s i o n a l f r a g m e n tm e t r i c i s o b t a i n e d,i t i s i n d e p e n d e n t o f t h e s i z eo f t h e i n c o m i n gt a s k s T h e n,t h eo b t a i n e dr e s u l t o f f r a g m e n tm e t r i c i nt h eo n e
8、d i m e n s i o n a l s t r u c t u r e i s e x t e n d e d t o t w o d i m e n s i o n a l a n dh i g h d i m e n s i o n a l s t r u c t u r e s F i n a l l y,t h i s f r a g m e n tm e t r i cm e t h o d i su s e d t o r e d u c e c h i p f r a g m e n t s d u r i n g t h eo n l i n e t a s kp l
9、a c e m e n t o nF P G A T h es i m u l a t i o nr e s u l t so nt h e t w o d i m e n s i o n a lF P G As h o wt h a t,c o m p a r e dw i t ht h eu s u a l t h eb o t t o ml e f t,f i r s t f i ta n db e s t f i tp l a c e m e n ts t r a t e g i e s,t h ep r o p o s e df r a g m e n tm e t r i ca n
10、 dp l a c e m e n tm e t h o dn o to n l yr e s u l t s i ni m p r o v e m e n t i nt e r m so ft h ew a i t i n gt i m e,a l l o c a t i o nt i m ea n dr e s p o n s e t i m e,b u t a l s o i n c r e a s e s t h ec h i pu t i l i z a t i o na n dr e d u c e s t h em i s sr a t i o K e y w o r d s:F
11、 P G A;P a r t i a l l yr e c o n f i g u r a b l e;a r e a f r a g m e n t;o n l i n e t a s kp l a c e m e n t;t i m e;c h i pu t i l i z a t i o n;m i s sr a t i o引言现场可编程门阵列(F P G A,f i e l d p r o g r a mm a b l eg a t ea r r a y)通常是部分可重构的,允许在运行时对芯片的各个部分进行配置,其中每部分可以执行一个独立的任务.具有这种特性的设备可以同时容纳多个应用,
12、其中每个应用可以由多个任务构成.要充分利用部分可重构结构的优势,就必须充分利用芯片资源.不合理放置到达任务会导致芯片区域的一些部分浪费,因为这些部分尽管是空闲的,但它们太小而无法容纳另一个到达的任务.通常把这些空闲的较小部分称为碎片,类似于传统存储系统中的碎片,这些碎片可能占芯片区域的很大比例.因此,区域碎片是获得良好的芯片资源利用的最大障碍之一.一方面,高区域碎片化表示芯片上占用部分的分散,因此可能导致低的芯片利用率;另一方面,低区域碎片化使得到达任务能够被放置,从而提高芯片利用率.在一个在线放置系统中,由于矩形任务的动态添加和删除,使得F P GA的空区域变得高度碎片化,因而无法有效地利用
13、F P G A区域.一个高度碎片化的芯片是指其中包含了大量的由一些被占用单元所分割形成的孔洞,即任务矩形边界以外的区域资源的碎片.如果一个任务的矩形区域没有可用的足够的相邻资源,则该任务可能被拒绝放置.图所示为这样的一个例子,其中任务T和T导致F P GA区域碎片化,因此,即使F P G A上的总的空闲区域大于任务T的区域,但任务T也不能放置在F P G A上.目前,有个主要的方向来提高芯片的区域利用.一是允许任务抢占,即停止活跃任务,保存它们或将它们移动到其他部分,并重新配置新的部分.文献 提出了一种任务压缩的启发式算法,这是一种一维保序算法.如果无法在芯片区域上分配(放置)到达任务,则该技
14、术尝试投稿网址:w w wj s j c l y k z c o m计算机测量与控制第 卷 图F P G A区域的碎片化将运行的任务压缩到特定的方向,从而能够得到更好的芯片利用率;文献 针对碎片资源干扰下云计算资源的优化调度,提出了采用基于膜计算和蝙蝠算法的方法,对云计算环境下不同的资源调度策略形成的资源碎片进行量化处理,重新定量划分,使其可重组成整块资源,最大化接收后续任务.仿真结果表明,所提出的方法有效提高了资源调度能力;二是采用碎片感知放置技术,在这种技术中,仔细地进行放置,以减少区域碎片,为将来的任务分配提供更多的空间.这种技术需要一个可靠的碎片测量来决定把新的任务放在哪里.所有空位置
15、都必须经过测试,才能选择一个能降低碎片的地方.因此,这种放置策略在选择位置时考虑到了碎片度量;文献 采用可重构区域中空矩形的较短边的方格(称为基准尺寸)作为碎片度量.他们计算基准尺寸的分布,并将这种分布的均值作为碎片度量.显然,不同的分布(碎片状态)可能有相同的均值,换句话说,分布的平均值并不能唯一地识别芯片的碎片数量;文献 针对F P GA可重构设计过程中会产生大量空闲碎片的问题,提出了一种碎片合并算法,测试结果表明,对于 个连续产生的随机任务进行碎片合并之后,所有任务一次申请资源成功率达到 ,等待一个任务结束之后资源申请成功率达到 ;文献 采用碎片等级来对碎片进行量化,在F P G A上寻
16、找覆盖空区域所需的所有空矩形.如果ai为第i个空矩形的面积,则碎片等级计算为Fai/ai.计算式中所使用的空矩形可能重叠,所以空区域可能不止一次参与碎片等级的计算,这样就会导致结果不准确.图(a)所示为使用同一区域次的碎片等级;文献 采用碎片度量将整个芯片上的空洞的分散程度量化为芯片碎片,即fiai/A,Fifi,其中ai为第i个空矩形的面积,A为芯片面积.他们在F P G A上寻找覆盖空区域所需的最大空矩形,并计算了碎片因子.这里仍存在着空域重叠的问题,而且两种不同的碎片状态可能得到相同的碎片因子,如图(b)所示.图碎片计算示例上述这些方法都给出的是绝对的碎片度量,仅考虑了可重构单元的分布.另一种发展趋势是相对碎片度量,它基于到达任务的大小考虑可重构单元的状态.作为相对碎片度量的一个例子,文献 根据任务的平均大小来进行计算.他们在一个空单元的垂直和水平附近使用空单元数量,如果这个数量大于或等于到达任务平均大小的倍,则该单元的碎片贡献为.总的碎片由可重构芯片区域内所有空单元的垂直碎片和水平碎片之和来计算;文献 基于多F P GA的动态可重配置的多任务调度和放置方法,通过任务级和子任务级
