Template Generation - A Graph Profiling Algorithm

The availability of high-level design entry tooling is crucial for the viability of any reconfigurable SoC architecture. This paper presents a template generation algorithm. The objective of template generation step is to extract functional equivalent structures, i.e. templates, from a control data flow graph. By profiling the graph, the algorithm generates all the possible templates and the corresponding matches. Using unique serial numbers and circle numbers, the algorithm can find all distinct templates with multiple outputs. A new type of graph (hydragraph) that can cope with multiple outputs is introduced. The generated templates pepresented by the hydragraph are not limited in shapes, i.e., we can find templates with multiple outputs or multiple sinks.