#StackBounty: #graphs #optimization #scheduling #loops Is the RecMII really important?

Bounty: 100

Recently I’ve asked a question on SO about dependence graph and modulo scheduling, because I’m not able to get the distance of some loop carried dependency and I needed some help.

I’m building a dependence graph so that I can implement the modulo scheduler of this paper and aside for some problem that blocks me I have a question about the importance of some parameters.

In particular about the recurrence-constrained MII (RecMII).
I noticed that in some case you probably can’t get the loop carried distance of some dependency (for example a[i]=a[f(a[i-1])] +a[i*i-2*i-1]), so I’m asking:

  • Is the RecMII really important in the modulo scheduling algorithm? If yes how much? (It just seems a way to reduce the try needed to find a valid II)
  • What happens if I neglect it? Just some increase execution time of
    the main loop that try to find the II or I also decrease the quality
    of my scheduler?
  • Can the Modulo scheduler be used only on the data dependency graph? (I’m asking this because it’s really easy to build such graph, you only need to go through the def-use chain)


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.