Minimal Unroll Factor for Code Generation of Software Pipelining.
Saved in:
| Title: | Minimal Unroll Factor for Code Generation of Software Pipelining. |
|---|---|
| Authors: | Bachir, Mounira1, Touati, Sid-Ahmed-Ali1 Sid.Touati@inria.fr, Brault, Frederic1, Gregg, David1, Cohen, Albert1 |
| Source: | International Journal of Parallel Programming. Feb2013, Vol. 41 Issue 1, p1-58. 58p. 12 Diagrams, 6 Charts, 9 Graphs. |
| Subjects: | Data pipelining, Loop tiling (Computer science), Parallel processing, Embedded computer systems, Computer software, Ciphers |
| Abstract: | We address the problem of generating compact code from software pipelined loops. Although software pipelining is a powerful technique to extract fine-grain parallelism, it generates lifetime intervals spanning multiple loop iterations. These intervals require periodic register allocation (also called variable expansion), which in turn yields a code generation challenge. We are looking for the minimal unrolling factor enabling the periodic register allocation of software pipelined kernels. This challenge is generally addressed through one of: (1) hardware support in the form of rotating register files, which solve the unrolling problem but are expensive in hardware; (2) register renaming by inserting register moves, which increase the number of operations in the loop, and may damage the schedule of the software pipeline and reduce throughput; (3) post-pass loop unrolling that does not compromise throughput but often leads to impractical code growth. The latter approach relies on the proof that MAXLIVE registers (maximal number of values simultaneously alive) are sufficient for periodic register allocation (Eisenbeis et al. in PACT '95: Proceedings of the IFIP WG10.3 working conference on Parallel Architectures and Compilation Techniques, pages 264-267, Manchester, UK, ; Hendren et al. in CC '92: Proceedings of the 4th International Conference on Compiler Construction, pages 176-191, London, UK, ). However, the best existing heuristic for controlling this code growth-modulo variable expansion (Lam in SIGPLAN Not 23(7):318-328, )-may not apply the correct amount of loop unrolling to guarantee that MAXLIVE registers are enough, which may result in register spills Eisenbeis et al. in PACT '95: Proceedings of the IFIP WG10.3 working conference on Parallel Architectures and Compilation Techniques, pages 264-267, Manchester, UK, . This paper presents our research results on the open problem of minimal loop unrolling, allowing a software-only code generation that does not trade the optimality of the initiation interval ( II) for the compactness of the generated code. Our novel idea is to use the remaining free registers after periodic register allocation to relax the constraints on register reuse. The problem of minimal loop unrolling arises either before or after software pipelining, either with a single or with multiple register types (classes). We provide a formal problem definition for each scenario, and we propose and study a dedicated algorithm for each problem. Our solutions are implemented within an industrial-strength compiler for a VLIW embedded processor from STMicroelectronics, and validated on multiple benchmarks suites. [ABSTRACT FROM AUTHOR] |
| Copyright of International Journal of Parallel Programming is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 84620917 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Minimal Unroll Factor for Code Generation of Software Pipelining. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Bachir%2C+Mounira%22">Bachir, Mounira</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Touati%2C+Sid-Ahmed-Ali%22">Touati, Sid-Ahmed-Ali</searchLink><relatesTo>1</relatesTo><i> Sid.Touati@inria.fr</i><br /><searchLink fieldCode="AR" term="%22Brault%2C+Frederic%22">Brault, Frederic</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Gregg%2C+David%22">Gregg, David</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Cohen%2C+Albert%22">Cohen, Albert</searchLink><relatesTo>1</relatesTo> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22International+Journal+of+Parallel+Programming%22">International Journal of Parallel Programming</searchLink>. Feb2013, Vol. 41 Issue 1, p1-58. 58p. 12 Diagrams, 6 Charts, 9 Graphs. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Data+pipelining%22">Data pipelining</searchLink><br /><searchLink fieldCode="DE" term="%22Loop+tiling+%28Computer+science%29%22">Loop tiling (Computer science)</searchLink><br /><searchLink fieldCode="DE" term="%22Parallel+processing%22">Parallel processing</searchLink><br /><searchLink fieldCode="DE" term="%22Embedded+computer+systems%22">Embedded computer systems</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+software%22">Computer software</searchLink><br /><searchLink fieldCode="DE" term="%22Ciphers%22">Ciphers</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: We address the problem of generating compact code from software pipelined loops. Although software pipelining is a powerful technique to extract fine-grain parallelism, it generates lifetime intervals spanning multiple loop iterations. These intervals require periodic register allocation (also called variable expansion), which in turn yields a code generation challenge. We are looking for the minimal unrolling factor enabling the periodic register allocation of software pipelined kernels. This challenge is generally addressed through one of: (1) hardware support in the form of rotating register files, which solve the unrolling problem but are expensive in hardware; (2) register renaming by inserting register moves, which increase the number of operations in the loop, and may damage the schedule of the software pipeline and reduce throughput; (3) post-pass loop unrolling that does not compromise throughput but often leads to impractical code growth. The latter approach relies on the proof that MAXLIVE registers (maximal number of values simultaneously alive) are sufficient for periodic register allocation (Eisenbeis et al. in PACT '95: Proceedings of the IFIP WG10.3 working conference on Parallel Architectures and Compilation Techniques, pages 264-267, Manchester, UK, ; Hendren et al. in CC '92: Proceedings of the 4th International Conference on Compiler Construction, pages 176-191, London, UK, ). However, the best existing heuristic for controlling this code growth-modulo variable expansion (Lam in SIGPLAN Not 23(7):318-328, )-may not apply the correct amount of loop unrolling to guarantee that MAXLIVE registers are enough, which may result in register spills Eisenbeis et al. in PACT '95: Proceedings of the IFIP WG10.3 working conference on Parallel Architectures and Compilation Techniques, pages 264-267, Manchester, UK, . This paper presents our research results on the open problem of minimal loop unrolling, allowing a software-only code generation that does not trade the optimality of the initiation interval ( II) for the compactness of the generated code. Our novel idea is to use the remaining free registers after periodic register allocation to relax the constraints on register reuse. The problem of minimal loop unrolling arises either before or after software pipelining, either with a single or with multiple register types (classes). We provide a formal problem definition for each scenario, and we propose and study a dedicated algorithm for each problem. Our solutions are implemented within an industrial-strength compiler for a VLIW embedded processor from STMicroelectronics, and validated on multiple benchmarks suites. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of International Journal of Parallel Programming is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=84620917 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s10766-012-0203-z Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 58 StartPage: 1 Subjects: – SubjectFull: Data pipelining Type: general – SubjectFull: Loop tiling (Computer science) Type: general – SubjectFull: Parallel processing Type: general – SubjectFull: Embedded computer systems Type: general – SubjectFull: Computer software Type: general – SubjectFull: Ciphers Type: general Titles: – TitleFull: Minimal Unroll Factor for Code Generation of Software Pipelining. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Bachir, Mounira – PersonEntity: Name: NameFull: Touati, Sid-Ahmed-Ali – PersonEntity: Name: NameFull: Brault, Frederic – PersonEntity: Name: NameFull: Gregg, David – PersonEntity: Name: NameFull: Cohen, Albert IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 02 Text: Feb2013 Type: published Y: 2013 Identifiers: – Type: issn-print Value: 08857458 Numbering: – Type: volume Value: 41 – Type: issue Value: 1 Titles: – TitleFull: International Journal of Parallel Programming Type: main |
| ResultId | 1 |
