29 Sep 2001 11:01:10 -0400

Related articles |
---|

Graph colouring with unlimited colours bromage@goaway.cc.monash.edu.au (Andrew Bromage) (2001-09-29) |

Re: Graph colouring with unlimited colours anton@mips.complang.tuwien.ac.at (2001-09-30) |

From: | Andrew Bromage <bromage@goaway.cc.monash.edu.au> |

Newsgroups: | comp.compilers |

Date: | 29 Sep 2001 11:01:10 -0400 |

Organization: | Compilers Central |

Keywords: | optimize, theory, question |

Posted-Date: | 29 Sep 2001 11:01:10 EDT |

G'day all.

I'm interested in references for graph colouring where the maximum

number of colours is in general unbounded (but should be as small as

possible). I need this for a virtual machine where thousands of

instances of a given program may be running at any given time, so

using one less register may save a lot of memory (which is in short

supply in this particular application).

The simplest algorithm is to repeatedly remove the smallest degree

node and assign it the smallest colour possible (inventing a new

colour if necessary). However, this doesn't in general do as well as

delayed colouring.

Has anyone done any work on how badly the "assign a colour to the

smallest degree node" algorithm works in the average/worst case

compared with "optimal" colouring? Or has anyone tried some sort of

delayed colouring algorithm where the number of colours is not fixed

beforehand?

I'm also considering a hybrid approach where you choose a "reasonable"

number of colours, colour with spilling, then repeat the algorithm on

the spilled nodes. Has anyone tried this? How well does it work in

the average/worst case?

Oh, and also, if anyone has any good coalescing heuristics which don't

depend on choosing a number of colours beforehand, that would be

extremely helpful too.

Thanks in advance, etc.

Cheers,

Andrew Bromage

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.