综合时间因素和空间因素的FPGA任务放置方法

摘要

本发明公开了一种综合时间因素和空间因素的FPGA任务放置方法。本发明首先将FPGA及在FPGA上执行的任务抽象成具有一定长度和宽度的矩形块。然后对每个新到达的任务均记录两个时间属性，即，到达FPGA的时刻（简称到达时刻）、在FPGA内执行的时间（简称执行时间）。最后，通过综合考虑任务的到达时刻、执行时间和任务与空闲块的空间匹配，设计代价函数为任务选择合适的放置位置。本发明综合考虑了任务与空闲块在空间上和时间上的重叠长度，使得任务紧凑地放置在FPGA内，从而减少了FPGA内的空闲碎片空间，提高了FPGA的空间利用率。

主权项

一种综合时间因素和空间因素的FPGA任务放置方法，其特征在于操作步骤为：首先将FPGA及在FPGA上执行的任务抽象成具有一定长度和宽度的矩形块；然后对每个新到达的任务均记录两个时间属性：到达FPGA的时刻，即到达时刻，和在FPGA内执行的时间，即执行时间；最后，通过综合考虑任务的到达时刻、执行时间和任务与空闲块的空间匹配，设计代价函数为任务选择合适的放置位置；所述的代价函数应该考虑到以下几个因素的影响：(1)空间上，新到任务与放置位置的相邻任务邻接边的重叠长度；(2)时间上，新到任务与放置位置的相邻任务执行时间的重叠度；所述的代价函数的表达式定义为：其中式中各符号的含意分别是：present_moment为当前时刻,表示新到任务放置在某个放置位置时，与其相邻的第i个任务的邻接边重叠长度，为新到任务与第i个相邻任务在时间维上重叠度，为第i个相邻任务的执行时间，为第i个相邻任务的开始时刻，为新到任务的执行时间；式中分为三种情况：情况1，新到任务的完成时刻早于相邻任务的完成时刻；情况2，新到任务的相邻边为FPGA边界，则记为相邻任务完成时刻为无穷；情况3，新到任务的完成时刻晚于相邻任务的完成时刻；式中两个常数的意义为：的设定是为了使，即保证情况1的代价函数值大于情况2的代价函数值；而的设定是为了使，即保证情况3 的代价函数值小于情况2与情况1的代价函数值。