Randomized MIS in Scheduling

From: sk prasad (jvmkasi_at_eth.net)
Date: 05/27/04 

Date: 27 May 2004 08:05:12 -0700

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.
Does anyone know if this is worth investigating?

bye
sk prasad