Randomized Max Independent Set to Schedule Code

I was reading abt Maximal Independet set from Randomized Algorithms
book. I was wondering whether anyone has thought abt using Independet
set for Instruction scheduling.Compilers need to exploit parallelism
in code(this is true especially when we talk abt VLIW/EPIC
architectures).I thought one could model the instructions as a DAG,
where nodes represent instructions and the edges represent
dependecies(we can model this as needed). Now finding the Maximal
Indepndet set will allow compiler to execute those instructions
parallely. Parallelism is more important in the context of loops where
a small rescheduling can result in huge savings.Also since there are
some pretty easy randomized algorithms for MIS this is not tough. Do
modern day compilers exploit this algorithm?


Bye
sk prasad

Return to the comp.compilers page.
Search the comp.compilers archives again.