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

Mark Ruvald Pedersen, Jan Madsen

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


    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 languageEnglish
    Title of host publication2012 NORCHIP
    Number of pages6
    Publication date2012
    ISBN (Print)978-1-4673-2221-8
    ISBN (Electronic)978-1-4673-2222-5
    Publication statusPublished - 2012
    Event30th NORCHIP conference - Copenhagen, Denmark
    Duration: 12 Nov 201213 Nov 2012


    Conference30th NORCHIP conference


    • Register allocation
    • High-level synthesis

    Fingerprint Dive into the research topics of 'Optimal Register Allocation by Augmented Left-Edge Algorithm on Arbitrary Control-Flow Structures'. Together they form a unique fingerprint.

    Cite this