一种应用图论方法管理可重构资源的策略

One Management Strategy of Reconfigurable Resource Using Graph Theory

可重构硬件资源的管理是可重构操作系统的一个首要任务。提出了一种基于图论技术的管理空闲资源的UPFS算法。其核心思想是将FPGA的空闲区域映射成无向图,在无向图中运用邻接矩阵和方向矢量交角等概念,求解最大回路和通路,最终找到满足条件的最大空闲矩形集。仿真实验表明,UPFS算法与已有算法相比,能有效减少系统资源浪费,降低系统硬件布局时间,是可行的管理策略。

The management of reconfigurable resource is an important task for operating system of reconfigurable system.This paper presented UPFS algorithm for FPGA based on graph theory.The main idea of UPFS is the free space of FPGA mapped to undigraph,and then calculated the biggest loop and chain using adjacency matrix and direction vector inclination in undigraph concept,at last we found a set of the biggest rectangular satisfied the conditions.The simulation results show that,compared with existent algorithms,UPFS is feasible management strategy,which can reduce the waste of system resource and decrease the time of hardware distribution.