Compilers - Randomized Max Independent Set to Schedule Code

You are viewing an archived Text-only version of the thread. To view this thread in it's original format and/or if you want to reply to this thread please [click here]

Author

Randomized Max Independent Set to Schedule Code

sk prasad

2004-06-03, 7:28 pm

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 pra

Sponsored Links