On a graph-theoretical model for cyclic register allocation

In the process of compiling a computer programme, we consider the problem of allocating variables to registers within a loop. It can be formulated as a coloring problem in a circular arc graph (intersection graph of a family F of intervals on a circle). We consider the meeting graph of F introduced...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 1999-07, Vol.93 (2), p.191-203
Main Authors: de Werra, D., Eisenbeis, Ch, Lelait, S., Marmol, B.
Format: Article
Language:English
Subjects:
Applied sciences
Circular arc graphs
Coloring
Combinatorics
Combinatorics. Ordered structures
Compilation
Cyclic scheduling
Exact sciences and technology
Graph theory
Mathematics
Microprocessor design
Operational research and scientific management
Operational research. Management science
Register allocation
Scheduling, sequencing
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In the process of compiling a computer programme, we consider the problem of allocating variables to registers within a loop. It can be formulated as a coloring problem in a circular arc graph (intersection graph of a family F of intervals on a circle). We consider the meeting graph of F introduced by Eisenbeis, Lelait and Marmol. Proceedings of the Fifth Workshop on Compilers for Parallel Computers, Malaga, June 1995, pp. 502–515. Characterizations of meeting graphs are developed and their basic properties are derived with graph theoretical arguments. Furthermore some properties of the chromatic number for periodic circular arc graphs are derived.
ISSN:0166-218X
1872-6771
DOI:10.1016/S0166-218X(99)00105-5