关键词: 图论, FPGA资源管理, 最大空闲矩形, KAMER_VU算法, 算法执行时间, 有效损耗时间

Abstract:

In order to avoid the redundancy and duplication when using the plane partition algorithm to find all maximal empty rectangles,an algorithm based on virtual undigraph marked as KAMER_VU is proposed to manage the reconfigurable empty hardware resources.Based on the FPGA of two-dimension region,the algorithm uses the mapping between the undigraph and the FPGA model and indirectly finds all maximal empty rectangles by looking for effective loop and pathway in the virtual undigraph,thus simplifying the partition of free region.Some simulations are then performed to make a comparison between the proposed algorithm and the existing SL algorithm.The results indicate that KAMER_VU effectively saves time for hardware distribution and increases the success probabi-lity of hardware allocation for task.

Key words: graph theory, FPGA resource management, maximal empty rectangle, KAMER_VU algorithm, algorithm execution time, effective loss time