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.