Journal of South China University of Technology (Natural Science Edition) ›› 2010, Vol. 38 ›› Issue (11): 91-95.doi: 10.3969/j.issn.1000-565X.2010.11.017

• Computer Science & Technology • Previous Articles     Next Articles

Graph Theory-Based Algorithm to Manage FPGA Resources

Zhang Hong-lie 1.2  Zhang Guo-yin1   

  1. 1.College of Computer Science and Technology,Harbin Engineering University,Harbin 150001,Heilongjiang,China;2.College of Computer and Control Engineering,Qiqihar University,Qiqihar 161006,Heilongjiang,China
  • Received:2010-01-06 Revised:2010-06-28 Online:2010-11-25 Published:2010-11-25
  • Contact: 张国印（1962-），男，教授，博士生导师，主要从事信息安全、嵌入式系统的研究．E—mail：zhangguoyin@hrbeu．edu．cn E-mail:zhang_honglie@163．com
  • About author:张宏烈（1966-），女，教授，主要从事嵌入式系统与可重构计算的研究．
  • Supported by:

    黑龙江省自然科学基金资助项目（B2007-07）; 齐齐哈尔市工业攻关项目（GYGG—09009）

PDF

805

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

CLC Number: