TY - GEN
T1 - Optimizing Timing and Code Size Using Maximum Direct Loop Fusion
AU - Liu, Meilin
AU - Xue, Chun
AU - Qiu, Meikang
AU - Sha, Edwin H.-M.
N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].
PY - 2006
Y1 - 2006
N2 - In this paper, we develop the technique that combines loop distribution with maximum direct loop fusion (LD_MDF), which performs maximum loop distribution, followed by maximum direct loop fusion to optimize timing and code size simultaneously. We illustrate using examples that dependence cycle is not always a restriction for loop distribution for multi-level loops. We map the maximum direct loop fusion problem to the graph partitioning problem. A polynomial graph partitioning algorithm is developed to compute the fusion partitions. We prove that our maximum direct loop fusion algorithm produces the fewest number of resultant loop nests without violating dependence constraints. We also show that the resultant code size of the fused loops by the technique of loop distribution with maximum direct loop fusion is always smaller than the code size of the original loops.
AB - In this paper, we develop the technique that combines loop distribution with maximum direct loop fusion (LD_MDF), which performs maximum loop distribution, followed by maximum direct loop fusion to optimize timing and code size simultaneously. We illustrate using examples that dependence cycle is not always a restriction for loop distribution for multi-level loops. We map the maximum direct loop fusion problem to the graph partitioning problem. A polynomial graph partitioning algorithm is developed to compute the fusion partitions. We prove that our maximum direct loop fusion algorithm produces the fewest number of resultant loop nests without violating dependence constraints. We also show that the resultant code size of the fused loops by the technique of loop distribution with maximum direct loop fusion is always smaller than the code size of the original loops.
KW - Code Size
KW - Embedded DSP
KW - Loop Distribution
KW - Loop Fusion
UR - https://www.scopus.com/pages/publications/85086419778
UR - https://www.scopus.com/pages/publications/85086419778#tab=impact
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9781604236446
T3 - 19th International Conference on Parallel and Distributed Computing Systems 2006, PDCS 2006
SP - 38
EP - 43
BT - 19th International Conference on Parallel and Distributed Computing Systems 2006, PDCS 2006
PB - International Society for Computers and Their Applications (ISCA)
T2 - 19th International Conference on Parallel and Distributed Computing Systems, PDCS 2006
Y2 - 20 September 2006 through 22 September 2006
ER -