On the Effectiveness of Register Moves to Minimise Post-Pass Unrolling in Software Pipelined Loops

Mounira Bachir; Albert Cohen; Sid-Ahmed-Ali TOUATI

hal-00716183, version 1

On the Effectiveness of Register Moves to Minimise Post-Pass Unrolling in Software Pipelined Loops

Mounira Bachir^a^, 1, Albert Cohen ², Sid-Ahmed-Ali TOUATI ³

HPCS 2012 : International Conference on High Performance Computing & Simulation (2012)

a – INRIA
1: Laboratoire d'Informatique de Paris 6 (LIP6)
http://www.lip6.fr/
CNRS : UMR7606 – Université Pierre et Marie Curie (UPMC) - Paris VI 4 Place JUSSIEU 75252 PARIS CEDEX 05 France
2: PARKAS (INRIA Paris-Rocquencourt)
http://www.di.ens.fr/ParkasTeam.html
INRIA – Ecole normale supérieure de Paris - ENS Paris – CNRS : UMR 8548 Département d'informatique École normale supérieure 45 rue d'Ulm F-75230 Paris Cedex 05 France
3: Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S)
http://www.i3s.unice.fr/
Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271 2000, route des Lucioles - Les Algorithmes - bât. Euclide B 06900 Sophia Antipolis France

Bibliographic reference

Attached file list to this document:

PDF

Touati_hpcs_2012.pdf

(200.6 KB)

hal-00716183, version 1
http://hal.inria.fr/hal-00716183
oai:hal.inria.fr:hal-00716183
From: Sid Touati <>
Submitted on: Tuesday, 10 July 2012 10:13:41
Updated on: Thursday, 12 July 2012 16:18:03

See short view

Associated documents

PDF :

Export

Bibtex EndNote TEI RefWorks

%% hal-00716183, version 1
%% http://hal.inria.fr/hal-00716183
@inproceedings{bachir:hal-00716183,
    hal_id = {hal-00716183},
    url = {http://hal.inria.fr/hal-00716183},
    title = {{On the Effectiveness of Register Moves to Minimise Post-Pass Unrolling in Software Pipelined Loops}},
    author = {Bachir, Mounira and Cohen, Albert and TOUATI, Sid-Ahmed-Ali},
    abstract = {{Software pipelining is a powerful technique to expose fine-grain parallelism, but it results in variables staying alive across more than one kernel iteration. It requires periodic register allocation and is challenging for code generation: the lack of a reliable solution currently restricts the applicability of software pipelining. The classical software solution that does not alter the computation throughput consists in unrolling the loop a posteriori [12], [11]. However, the resulting unrolling degree is often unacceptable and may reach absurd levels. Alternatively, loop unrolling can be avoided thanks to software register renaming. This is achieved through the insertion of move operations, but this may increase the initiation interval (II) which nullifies the benefits of software pipelining. This article aims at tightly controling the post-pass loop unrolling necessary to generate code. We study the potential of live range splitting to reduce kernel loop unrolling, introducing additional move instructions without inscreasing the II. We provide a complete formalisation of the problem, an algorithm, and extensive experiments. Our algorithm yields low unrolling degrees in most cases -- with no increase of the II.}},
    language = {English},
    affiliation = {Laboratoire d'Informatique de Paris 6 - LIP6 , PARKAS - INRIA Paris-Rocquencourt , Laboratoire d'Informatique, Signaux, et Syst{\`e}mes de Sophia-Antipolis - I3S},
    booktitle = {{HPCS 2012 : International Conference on High Performance Computing \& Simulation}},
    address = {Madrid, Spain},
    organization = {Pr Waleed Smari},
    editor = {IEEE, ACM },
    audience = {international },
    year = {2012},
    month = Jul,
    pdf = {http://hal.inria.fr/hal-00716183/PDF/Touati\_hpcs\_2012.pdf},
}

%F hal-00716183, version 1
%0 Conference Proceedings
%U http://hal.inria.fr/hal-00716183
%2 INFO:INFO_ES;INFO:INFO_OH
%T On the Effectiveness of Register Moves to Minimise Post-Pass Unrolling in Software Pipelined Loops
%A Bachir, Mounira
%A Cohen, Albert
%A TOUATI, Sid-Ahmed-Ali
%+ Laboratoire d'Informatique de Paris 6 - LIP6 , PARKAS - INRIA Paris-Rocquencourt , Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis - I3S
%Z Alchemy
%X Software pipelining is a powerful technique to expose fine-grain parallelism, but it results in variables staying alive across more than one kernel iteration. It requires periodic register allocation and is challenging for code generation: the lack of a reliable solution currently restricts the applicability of software pipelining. The classical software solution that does not alter the computation throughput consists in unrolling the loop a posteriori [12], [11]. However, the resulting unrolling degree is often unacceptable and may reach absurd levels. Alternatively, loop unrolling can be avoided thanks to software register renaming. This is achieved through the insertion of move operations, but this may increase the initiation interval (II) which nullifies the benefits of software pipelining. This article aims at tightly controling the post-pass loop unrolling necessary to generate code. We study the potential of live range splitting to reduce kernel loop unrolling, introducing additional move instructions without inscreasing the II. We provide a complete formalisation of the problem, an algorithm, and extensive experiments. Our algorithm yields low unrolling degrees in most cases -- with no increase of the II.
%2 D.: Software/D.3: PROGRAMMING LANGUAGES/D.3.4: Processors/D.3.4.0: Code generation, D.: Software/D.3: PROGRAMMING LANGUAGES/D.3.4: Processors/D.3.4.1: Compilers, D.: Software/D.3: PROGRAMMING LANGUAGES/D.3.4: Processors/D.3.4.6: Optimization
%G English
%8 2012-07-02
%2 international
%B HPCS 2012 : International Conference on High Performance Computing & Simulation
%2 Madrid
%2 Spain
%8 2012-07-02
%8 2012-07-06
%2 Pr Waleed Smari
%E IEEE, ACM

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Peer-reviewed conferences/proceedings</head>
<biblStruct type="inproceedings" xml:id="hal-00716183"><analytic>
<author><persName><forename>Mounira</forename><surname>Bachir</surname></persName>
<affiliation>
<orgName type="laboratory">LIP6</orgName>
<orgName type="team">Laboratoire d'Informatique de Paris 6</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7606</orgName>
<orgName type="institution">Université Pierre et Marie Curie (UPMC) - Paris VI</orgName>
</affiliation>
</author>
<author><persName><forename>Albert</forename><surname>Cohen</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Paris-Rocquencourt</orgName>
<orgName type="team">PARKAS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Ecole normale supérieure de Paris - ENS Paris</orgName>
<orgName type="institution">CNRS : UMR 8548</orgName>
</affiliation>
</author>
<author><persName><forename>Sid-Ahmed-Ali</forename><surname>TOUATI</surname></persName>
<affiliation>
<orgName type="laboratory">I3S</orgName>
<orgName type="team">Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis</orgName>
<country>FR</country>
<orgName type="institution">Université Nice Sophia Antipolis [UNS]</orgName>
<orgName type="institution">CNRS : UMR7271</orgName>
</affiliation>
</author>
<title type="main" level="a">On the Effectiveness of Register Moves to Minimise Post-Pass Unrolling in Software Pipelined Loops</title></analytic><monogr><meeting>HPCS 2012 : International Conference on High Performance Computing & Simulation</meeting><imprint><pubPlace><settlement>Madrid</settlement><country>Spain</country></pubPlace><biblScope type="publicationDate">2012-07-02</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/hal-00716183</idno><idno type="HALFile">http://hal.inria.fr/hal-00716183/PDF/Touati_hpcs_2012.pdf</idno></biblStruct>
</listBibl>
</listBibl>