Re:RTX2010 – Radiation-hardened stack machine microprocessor
by s800 on Saturday November 15, 2014 @11:18AM
(#8611955)
Interesting. I agree with your statement regarding it being an NP-complete problem, as intuitively it seems that way, but do you have a reference by chance? Thanks!
[ Parent
| on HN ]
Re:RTX2010 – Radiation-hardened stack machine microprocessor
by CHY872 on Saturday November 15, 2014 @02:20PM
(#8612383)
Ok, so we can view register allocation as being a case of graph colouring; create a graph where the nodes are your 'virtual registers' and there's an edge between two nodes if those registers are both live at the same time. Then we can run on n registers iff we can colour the graph with n colours. This is one of the first identified NP-complete problems.
Re:RTX2010 – Radiation-hardened stack machine microprocessor
by jlarocco on Saturday November 15, 2014 @12:05PM
(#8612056)
I can't find the original paper, but this almost seems more relevant.
http://research.ihost.com/lcpc06/final/7/7_Paper.pdf
Actually, here's the original for sale, but the abstract doesn't explicitly mention being NP-complete.
http://www.sciencedirect.com/science/article/pii/00960551819...