A Parametrized Loop Fusion Algorithm for Improving Parallelism and Cache Locality
- 1 June 1997
- journal article
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 40 (6) , 340-355
- https://doi.org/10.1093/comjnl/40.6.340
Abstract
This paper, we examine the fusion problem for maximizingparallelism and data locality together for loopnests in Fortran programs, given a maximum numberof registers that each loop may use. The general fusionproblem is known to be NP-hard [1]. Here we presentan optimal solution to a restricted case: when data dependencesamong loops form a tree. We use a dynamicprogramming solution, which runs in linear time withrespect to the number of loops, and quadratic time inthe number of available ...Keywords
This publication has 0 references indexed in Scilit: