devito icon indicating copy to clipboard operation
devito copied to clipboard

Improve data dependence analysis with SubDimensions

Open FabioLuporini opened this issue 5 years ago • 0 comments

This is a non-trivial optimisation.

Basically, the compiler, in doing data dependence analysis, abstracts away SubDimensions as pure Dimensions; so yleft, yi, yright they all become y to the eyes of the dependence checker, which works conservatively to be sure that correct code is generated.

We might know that yleft U yi U yright == y and that the pairwise interesection of yleft, yi, yright is the empty set, in which case what the compiler currently assumes as dependences could actually be ignored.

However, in the general case one could have overlapping SubDimensions, in which case the above isn't true. So what is missing is this concept of non-overlapping SubDimensions

Potential solution. Currently we have

class SubDimension(Dimension):

    @classmethod
    def left(...)
        ...
    @classmethod
    def middle(...)
        ...
    @classmethod
    def right(...)
        ...

We should/could add

    @classmethod
    def split(...)
        ...

so that one in user code can do

yleft, yi, yright = SubDimension.split(...)

and split automatically attaches a property to yleft/yi/yright which essentially says that these three SubDimensions do not overlap with each other. We could then exploit this information while doing data dependence analysis.

FabioLuporini avatar Apr 16 '19 13:04 FabioLuporini