Data transfers and storage of large arrays in background memories are dominating contributors to the chip area and power consumption of all modern multimedia embedded systems. Modern high-level memory optimizations contribute to the cost-ef??cient realization of these systems. In these optimizations an important step involves loop transformations across the global program scope. These transformations can be performed on a geometrical model extracted from the program. The geometrical model captures all the memory access dependencies in the program. Loop transformations in general modify the order in which the iterations and statements within a loop body are executed. This could be bene??cial for different reasons such as enabling more parallelism or improving locality of the accessed data. Due to the limitations of current geometrical models, the applicability of the transformations is limited. In this dissertation, we propose several applicability-enhancing techniques for loop transformations. First, hierarchical rewriting separates and encapsulates the details of the application into functions, reducing the complexity of the problem by hiding undesired constructs. Second, we instantiate and extend the scenario technique for loop transformations. A scenario is de??ned as a selected set of paths in the program which we choose to exploit in the same way. A careful exploitation of scenario information, similar to inlining, path predication or hyperblock creation, can signi??cantly enlarge the exploration space for optimizations. Unlike path predication or inlining, however it can work across several conditional branches, merge several condition bodies, and still control the exponential code explosion. Applying scenarios introduces several tradeoffs. The most obvious is that of code duplication vs. more optimizations (similar to tail duplication during hyperblock creation) when additional loop transformations are enabled by scenario usage. The exploration space of the scenario creation technique grows exponentially with the number of paths in the control-??ow graph of the application. In this dissertation we propose several heuristics for the scenario creation technique. These heuristics have different time requirements and accuracy limitations. Thus the designer has the possibility to choose the heuristic based on his time and accuracy constraints and the size of the problem. In addition, most current (global scope) loop optimizations target the best solution for locality. In this dissertation we show that targeting the best solution for locality is not necessarily optimal for a particular platform instance, and that trade-offs should be involved during loop transformations when the platform is unknown. This dissertation provides real-life examples of trade-offs during loop transformations and gives an overview of the joint research work in high-lever estimators for loop transformations which will make the loop transformations trade-off oriented.
|Qualification||Doctor of Philosophy|
|Award date||24 Sep 2007|
|Place of Publication||Eindhoven|
|Publication status||Published - 2007|