Randomized Max Independent Set to Schedule Code

jvmkasi@eth.net (sk prasad)
30 May 2004 13:26:23 -0400

          From comp.compilers

Related articles
Randomized Max Independent Set to Schedule Code jvmkasi@eth.net (2004-05-30)
| List of all articles for this month |

From: jvmkasi@eth.net (sk prasad)
Newsgroups: comp.compilers
Date: 30 May 2004 13:26:23 -0400
Organization: http://groups.google.com
Keywords: code, optimize, question
Posted-Date: 30 May 2004 13:26:23 EDT

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?

sk prasad

Post a followup to this message

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