FPGA中基于空间连续性的碎片度量及任务放置

Fragmentation Metric and Task Placement Based on Spatial Continuity in FPGA

针对部分可重构现场可编程门阵列允许在运行时对芯片的各个部分进行配置导致的区域碎片,提出了一种新的基于被占用(或空闲)空间的连续性的碎片度量及在线任务放置方法;首先从一维结构出发,得到一个单元序列对一个单元流S的碎片度量F S的贡献值,进而得到一维碎片度量值,它不依赖于到达任务的大小;然后将一维结构得到的碎片度量值结果推广到二维及高维结构;最后在FPGA上的在线任务放置过程中采用这种碎片度量方法,从而减少芯片碎片;在二维结构的FPGA上的仿真实验结果表明,与通常采用的左下角、第一匹配和最佳匹配放置策略相比,采用提出的碎片度量及放置方法不仅在等待时间、分配时间和响应时间方面有所改善,而且提高了芯片的利用率,降低了失配率。

Aimed at area fragment resulted in partially reconfigurable field-programmable gate arrays(FPGA),each part of the chip is required to be configured at run-time,a new fragment metric and online task placement method based on the continuity of occupied or free space is proposed.Firstly,from the one-dimensional structure,the contribution of one cell sequence to the fragment metric F S of one cell stream S is obtained,and then the one-dimensional fragment metric is obtained,it is independent of the size of the incoming tasks.Then,the obtained result of fragment metric in the one-dimensional structure is extended to two-dimensional and high-dimensional structures.Finally,this fragment metric method is used to reduce chip fragments during the online task placement on FPGA.The simulation results on the two-dimensional FPGA show that,compared with the usual the bottom left,first fit and best fit placement strategies,the proposed fragment metric and placement method not only results in improvement in terms of the waiting time,allocation time and response time,but also increases the chip utilization and reduces the miss ratio.