Publication

The polyhedral model makes a large set of transformations readily available for loop nest optimizations. Like traditional program optimization it is not always clear which of those transformations are profitable and under what circumstances. In traditional compilers this is dealt with the use of hand-crafted heuristics that are often platform specific and not universality “good”. In polyhedral compilation the problem of finding the appropriate transformations is formulated as an Integer Linear Program (ILP). However, not all relevant software and hardware aspects are or can be modelled in such an ILP. Consequently, transformations obtained by solving such ILPs are not necessarily optimal. In this work, we propose the use of data-driven heuristics in polyhedral optimization. To this end, we present a hybrid approach that uses an ILP solver in cooperation with a trained machine learning model that functions as a loop fusion heuristic. The ILP scheduler optimizes individual loops, our heuristic decides which ones should be fused, and then the ILP solver further optimizes the combined loops. The heuristic discovers by itself how loop fusion interacts with the ILP scheduler, the rest of the compiler, and the hardware without needing a compiler or hardware “expert” to teach it.

@mastersthesis{abc,
	abstract = {The polyhedral model makes a large set of transformations readily available for loop nest optimizations. Like traditional program optimization it is not always clear which of those transformations are profitable and under what circumstances. In traditional compilers this is dealt with the use of hand-crafted heuristics that are often platform specific and not universality {\textquotedblleft}good{\textquotedblright}. In polyhedral compilation the problem of finding the appropriate transformations is formulated as an Integer Linear Program (ILP). However, not all relevant software and hardware aspects are or can be modelled in such an ILP. Consequently, transformations obtained by solving such ILPs are not necessarily optimal.
In this work, we propose the use of data-driven heuristics in polyhedral optimization. To this end, we present a hybrid approach that uses an ILP solver in cooperation with a trained machine learning model that functions as a loop fusion heuristic. The ILP scheduler optimizes individual loops, our heuristic decides which ones should be fused, and then the ILP solver further optimizes the combined loops.
The heuristic discovers by itself how loop fusion interacts with the ILP scheduler, the rest of the compiler, and the hardware without needing a compiler or hardware {\textquotedblleft}expert{\textquotedblright} to teach it.},
	author = {Theodoros Theodoridis },
	school = {169},
	title = {Fused {\textquotedblleft}Learning{\textquotedblright} and {\textquotedblleft}Linear Programming{\textquotedblright}: a Novel Loop Fusion Approach},
	year = {2017}
}