All: Given a Data Dependency Graph(DDG) the unrolling degree proposed by Monica Lam et.al calculates the unrolling degree as follows.
Unrolling degree = Length of Longest Live range/ Number of cycles in the kernel ( Initiation Interval). The unrolling degree based on the Above leads to more register Spills and Fetch inside the Loops. Given the Data Dependency Graph(DDG) and the unrolling degree calculated as above we build the reuse graph. Lot has been presented On the Reuse graph. Each node nodes labelled the DDG nodes that writes into registers and the arc(u,v) represents that the destination Share same registers if there is no dependency between the between the iterations of DDG nodes. As there is no dependency as represented by the Reuse graph the life time will not overlap and assign the same registers. Each arc will Have the weight that describes the allocated registers and the Unrolling as proposed by Monica Lam given above The reuse graph will be Partitioned based on the heuristics and the Sum of weights of each arc in each partitioned is calculated. Then based on sum of weights of Each partitioned reuse graphs the least common factor of all the weights will be the new Unrolling degree. This new unrolling degree will lead to better register allocation and reduction of register pressure and because the destination registers is Shared between different iterations because of no dependency as described by the Data dependency distance given in DDG, the allocated registers will lead to less spill and Fetch. The calculation of getting the Unrolling degree(new) as above will lead to register allocation for loops ( that has the candidate of lots of Parallelism ) on assigning the Same destination registers between the DDG nodes having no dependency. Some of the Logic for calculation of new unrolling degree is taken from the proposed Unrolling degree based on Periodic register allocation Albert Cohen et.al. This will efficiently use before and after the register allocation based in gcc so that weights of each reuse graph that describes the allocated Registers Will be known after the register allocation and the weights that describes unrolling degree is done before register allocation and the new Unrolling degree efficiently calculated that reduces the register pressure. Suggestions? Thanks & Regards Ajit
