Optimal Register Allocation by Augmented Left-Edge Algorithm on Arbitrary Control-Flow Structures

Mark Ruvald Pedersen; Jan Madsen

doi:10.1109/NORCHP.2012.6403107

Optimal Register Allocation by Augmented Left-Edge Algorithm on Arbitrary Control-Flow Structures

Mark Ruvald Pedersen, Jan Madsen

Technical University of Denmark

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

A new algorithm for optimal register allocation in context of high-level synthesis is presented. In this paper we show how the greedy left-edge algorithm can be leveraged to obtain a globally optimal allocation, that is computed in polynomial time. By splitting variables at block boundaries, allows for allocation to be done using only quasi-local and local allocation - avoiding the complexity of true global allocation. As local allocation is much simpler than global allocation, this approach emphasizes efficiency and ease of implementation - at a cost of an increased number of register transfers compared to other allocators. Experiments show that runtime is linear for all practical purposes.

Original language	English
Title of host publication	2012 NORCHIP
Number of pages	6
Publisher	IEEE
Publication date	2012
ISBN (Print)	978-1-4673-2221-8
ISBN (Electronic)	978-1-4673-2222-5
DOIs	https://doi.org/10.1109/NORCHP.2012.6403107
Publication status	Published - 2012
Event	2012 IEEE 30th NORCHIP Conference - Hotel Richmond, Copenhagen, Denmark Duration: 12 Nov 2012 → 13 Nov 2013 Conference number: 30 https://ieeexplore.ieee.org/xpl/conhome/6385345/proceeding

Conference

Conference	2012 IEEE 30th NORCHIP Conference
Number	30
Location	Hotel Richmond
Country/Territory	Denmark
City	Copenhagen
Period	12/11/2012 → 13/11/2013
Internet address	https://ieeexplore.ieee.org/xpl/conhome/6385345/proceeding

Keywords

Register allocation
High-level synthesis

Access to Document

10.1109/NORCHP.2012.6403107

OpenUrl availability

Full text

Cite this

@inproceedings{906f31545dae42518bb1b18c431f7749,

title = "Optimal Register Allocation by Augmented Left-Edge Algorithm on Arbitrary Control-Flow Structures",

abstract = "A new algorithm for optimal register allocation in context of high-level synthesis is presented. In this paper we show how the greedy left-edge algorithm can be leveraged to obtain a globally optimal allocation, that is computed in polynomial time. By splitting variables at block boundaries, allows for allocation to be done using only quasi-local and local allocation - avoiding the complexity of true global allocation. As local allocation is much simpler than global allocation, this approach emphasizes efficiency and ease of implementation - at a cost of an increased number of register transfers compared to other allocators. Experiments show that runtime is linear for all practical purposes.",

keywords = "Register allocation, High-level synthesis",

author = "{Ruvald Pedersen}, Mark and Jan Madsen",

year = "2012",

doi = "10.1109/NORCHP.2012.6403107",

language = "English",

isbn = "978-1-4673-2221-8",

booktitle = "2012 NORCHIP",

publisher = "IEEE",

address = "United States",

note = "2012 IEEE 30th NORCHIP Conference ; Conference date: 12-11-2012 Through 13-11-2013",

url = "https://ieeexplore.ieee.org/xpl/conhome/6385345/proceeding",

}

TY - GEN

T1 - Optimal Register Allocation by Augmented Left-Edge Algorithm on Arbitrary Control-Flow Structures

AU - Ruvald Pedersen, Mark

AU - Madsen, Jan

N1 - Conference code: 30

PY - 2012

Y1 - 2012

N2 - A new algorithm for optimal register allocation in context of high-level synthesis is presented. In this paper we show how the greedy left-edge algorithm can be leveraged to obtain a globally optimal allocation, that is computed in polynomial time. By splitting variables at block boundaries, allows for allocation to be done using only quasi-local and local allocation - avoiding the complexity of true global allocation. As local allocation is much simpler than global allocation, this approach emphasizes efficiency and ease of implementation - at a cost of an increased number of register transfers compared to other allocators. Experiments show that runtime is linear for all practical purposes.

AB - A new algorithm for optimal register allocation in context of high-level synthesis is presented. In this paper we show how the greedy left-edge algorithm can be leveraged to obtain a globally optimal allocation, that is computed in polynomial time. By splitting variables at block boundaries, allows for allocation to be done using only quasi-local and local allocation - avoiding the complexity of true global allocation. As local allocation is much simpler than global allocation, this approach emphasizes efficiency and ease of implementation - at a cost of an increased number of register transfers compared to other allocators. Experiments show that runtime is linear for all practical purposes.

KW - Register allocation

KW - High-level synthesis

U2 - 10.1109/NORCHP.2012.6403107

DO - 10.1109/NORCHP.2012.6403107

M3 - Article in proceedings

SN - 978-1-4673-2221-8

BT - 2012 NORCHIP

PB - IEEE

T2 - 2012 IEEE 30th NORCHIP Conference

Y2 - 12 November 2012 through 13 November 2013

ER -

Optimal Register Allocation by Augmented Left-Edge Algorithm on Arbitrary Control-Flow Structures

Abstract

Conference

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this