An Improved Algorithm of DFG Regularity Extraction for Reconfigurable Systems
Some code fragments of multi-media applications have a high degree of repeatability and regularity, and they can be extracted in the form of template. Template technology can be used in task compilers of reconfigurable systems. After extracting regularity and selecting proper templates to cover the original DFG, sub-graphs frequently used can be scheduled to the same processing element array by task partitioning and scheduling, which can increase system parallelism and improve the reusability of reconfigurable systems. Thus an improved regularity extraction algorithm is proposed in the paper. By using heuristic approach, the algorithm reduces the number of intermediate sub-graphs and isomorphic graphs to be judged effectively, and solves the problem of high repeated sub-graphs and untargeted graph isomorphism. Moreover, it has less structural constraints to the original DFG. Finally, regularity extraction experiments for typical applications are given to verify the rationality and efficiency of the algorithm.
reconfigurable regularity extraction graph isomorphism sub-graph extension data-flow graph
ZHANG Houjun JIANG Jianhui SHENG Weiguang
Department of Computer Science & Technology Tongji University Shanghai 201804, China School of Micro-Electronics Shanghai Jiaotong University Shanghai 200240, China
国际会议
重庆
英文
467-471
2011-08-20（万方平台首次上网日期，不代表论文的发表时间）