Efficient nested loop pipelining in high level synthesis using
polyhedral bubble insertion
A. Morvan, S. Derrien, und P. Quinton. Field-Programmable Technology (FPT), 2011 International
Conference on, Seite 1--10. (Dezember 2011)
Zusammenfassung
Loop pipelining is a key transformation in high-level synthesis
tools as it helps maximizing both computational throughput and
hardware utilization. Nevertheless, it somewhat looses its
efficiency when dealing with small trip-count inner loops, as
the pipeline latency overhead quickly limits its efficiency.
Even if it is possible to overcome this limitation by pipelining
the execution of a whole loop nest, the applicability of nested
loop pipelining has so far been limited to a very narrow subset
of loops, namely perfectly nested loops with constant bounds. In
this work we propose to extend the applicability of nested-loop
pipelining to imperfectly nested loops with affine dependencies
by leveraging on the so-called polyhedral model. We show how
such loop nest can be analyzed, and under certain conditions,
how one can modify the source code in order to allow nested loop
pipeline to be applied using a method called polyhedral bubble
insertion. We also discuss the implementation of our method in a
source-to-source compiler specifically targeted at High-Level
Synthesis tools.
%0 Conference Paper
%1 Morvan2011-rd
%A Morvan, A
%A Derrien, S
%A Quinton, P
%B Field-Programmable Technology (FPT), 2011 International
Conference on
%D 2011
%K Arrays Hardware Law Pipeline_processing Polyhedral_model Schedules To_Read Vectors computational_throughput hardware_utilization high-level_synthesis_tools high_level_synthesis nested_loop_pipelining pipeline_latency pipeline_processing polyhedral_bubble_insertion polyhedral_model program_compilers program_control_structures source-to-source_compiler source_code_modification
%P 1--10
%T Efficient nested loop pipelining in high level synthesis using
polyhedral bubble insertion
%X Loop pipelining is a key transformation in high-level synthesis
tools as it helps maximizing both computational throughput and
hardware utilization. Nevertheless, it somewhat looses its
efficiency when dealing with small trip-count inner loops, as
the pipeline latency overhead quickly limits its efficiency.
Even if it is possible to overcome this limitation by pipelining
the execution of a whole loop nest, the applicability of nested
loop pipelining has so far been limited to a very narrow subset
of loops, namely perfectly nested loops with constant bounds. In
this work we propose to extend the applicability of nested-loop
pipelining to imperfectly nested loops with affine dependencies
by leveraging on the so-called polyhedral model. We show how
such loop nest can be analyzed, and under certain conditions,
how one can modify the source code in order to allow nested loop
pipeline to be applied using a method called polyhedral bubble
insertion. We also discuss the implementation of our method in a
source-to-source compiler specifically targeted at High-Level
Synthesis tools.
@inproceedings{Morvan2011-rd,
abstract = {Loop pipelining is a key transformation in high-level synthesis
tools as it helps maximizing both computational throughput and
hardware utilization. Nevertheless, it somewhat looses its
efficiency when dealing with small trip-count inner loops, as
the pipeline latency overhead quickly limits its efficiency.
Even if it is possible to overcome this limitation by pipelining
the execution of a whole loop nest, the applicability of nested
loop pipelining has so far been limited to a very narrow subset
of loops, namely perfectly nested loops with constant bounds. In
this work we propose to extend the applicability of nested-loop
pipelining to imperfectly nested loops with affine dependencies
by leveraging on the so-called polyhedral model. We show how
such loop nest can be analyzed, and under certain conditions,
how one can modify the source code in order to allow nested loop
pipeline to be applied using a method called polyhedral bubble
insertion. We also discuss the implementation of our method in a
source-to-source compiler specifically targeted at High-Level
Synthesis tools.},
added-at = {2015-04-11T18:41:09.000+0200},
author = {Morvan, A and Derrien, S and Quinton, P},
biburl = {https://www.bibsonomy.org/bibtex/2e35144412f59956b34e26849e91c57f5/christophv},
booktitle = {{Field-Programmable} Technology ({FPT)}, 2011 International
Conference on},
interhash = {9bef76efc4963474fd177f771483bbd7},
intrahash = {e35144412f59956b34e26849e91c57f5},
keywords = {Arrays Hardware Law Pipeline_processing Polyhedral_model Schedules To_Read Vectors computational_throughput hardware_utilization high-level_synthesis_tools high_level_synthesis nested_loop_pipelining pipeline_latency pipeline_processing polyhedral_bubble_insertion polyhedral_model program_compilers program_control_structures source-to-source_compiler source_code_modification},
month = dec,
pages = {1--10},
timestamp = {2015-04-11T18:41:09.000+0200},
title = {Efficient nested loop pipelining in high level synthesis using
polyhedral bubble insertion},
year = 2011
}