Enhanced applicability of loop transformations

M. Palkovic

Research output: ThesisPhd Thesis 2 (Research NOT TU/e / Graduation TU/e)Academic

Abstract

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.
LanguageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Department of Electrical Engineering
Supervisors/Advisors
  • Corporaal, Henk, Promotor
  • Catthoor, Francky V.M., Promotor, External person
Award date24 Sep 2007
Place of PublicationEindhoven
Publisher
Print ISBNs978-90-386-1584-4
DOIs
StatePublished - 2007

Fingerprint

Data storage equipment
Data transfer
Embedded systems
Explosions
Electric power utilization
Costs

Cite this

Palkovic, M. (2007). Enhanced applicability of loop transformations Eindhoven: Technische Universiteit Eindhoven DOI: 10.6100/IR629342
Palkovic, M.. / Enhanced applicability of loop transformations. Eindhoven : Technische Universiteit Eindhoven, 2007. 186 p.
@phdthesis{95b08337b7644601a18a7b0422544b4d,
title = "Enhanced applicability of loop transformations",
abstract = "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.",
author = "M. Palkovic",
year = "2007",
doi = "10.6100/IR629342",
language = "English",
isbn = "978-90-386-1584-4",
publisher = "Technische Universiteit Eindhoven",
school = "Department of Electrical Engineering",

}

Palkovic, M 2007, 'Enhanced applicability of loop transformations', Doctor of Philosophy, Department of Electrical Engineering, Eindhoven. DOI: 10.6100/IR629342

Enhanced applicability of loop transformations. / Palkovic, M.

Eindhoven : Technische Universiteit Eindhoven, 2007. 186 p.

Research output: ThesisPhd Thesis 2 (Research NOT TU/e / Graduation TU/e)Academic

TY - THES

T1 - Enhanced applicability of loop transformations

AU - Palkovic,M.

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

U2 - 10.6100/IR629342

DO - 10.6100/IR629342

M3 - Phd Thesis 2 (Research NOT TU/e / Graduation TU/e)

SN - 978-90-386-1584-4

PB - Technische Universiteit Eindhoven

CY - Eindhoven

ER -

Palkovic M. Enhanced applicability of loop transformations. Eindhoven: Technische Universiteit Eindhoven, 2007. 186 p. Available from, DOI: 10.6100/IR629342