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

Fragmentation Metric and Task Placement Based on Spatial Continuityin FPGA

摘要:

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

Abstract:

For area fragment resulted in partially reconfigurable field-programmable gate arrays that allow parts of the chip to be configured at run-time,a new method for fragment metric and online task placement based on the continuity of occupied (or free) space is proposed in this paper.Firstly,from the one-dimensional structure,the contribution of a cell sequence to the fragment metric F_S of a cell stream S is obtained,and then the one-dimensional fragment metric is obtained,which is independent of the size of the incoming tasks.Then,the result of fragment metric obtained through one-dimensional structure is extended to two-dimensional and high-dimensional structures.Finally,this fragment metric method is used during online placement of tasks on FPGAs to reduce chip fragments.The simulation results on two-dimensional FPGA show that,compared with the usual Bottom Left,First Fit and Best Fit placement strategies,the proposed fragment metric and placement method not only results in improvement in terms of waiting time,allocation time and response time,but also increases the chip utilization and reduces miss ratio.