[Mesa-dev] GSOC 2013

[Ian Romanick]

On 04/20/2013 10:26 PM, Piyush Tiwari wrote:
> Hello,
> I am really interested in doing the GSOC 2013 project "Find common
> patterns in real GLSL shaders".
>
>
> Implementation:
> Algorithm:- Max-miner algorithm as it uses the same data structure as
> Apriori i.e. hash tree.

I've only skimmed the Bayardo paper on Max-Miner, and I think it may be 
overkill.  It is optimized for finding very long patterns in a database. 
  In this context "very long" is likely longer than any GLSL shader our 
compiler has ever encountered.  That's not to say it's a bad idea, it 
just might be more work to implement than is necessary for this problem. 
  Doing a quick search, I don't see any papers about applying this 
algorithm to this problem, so, from a pure research perspective, it may 
be interesting none the less.

I think the difficulty of this project will be finding a representation 
of programs that will allow them to be mined.  We need to be able to 
detect that "a + b * c" in one shader is the same pattern as "d + e * f" 
in another shader.  For longer programs with lots of variables, this 
becomes challenging.

> The following implementation has been found faster than normal ways:
> Max-Miner uses the hash tree to quickly look up all candidate groups
> whose head appears in the transaction. Then, for each candidate
> group "g" identified, it traverses down its tail items one by one.
> (Efficiently mining long patterns from database).
>
> I would like some reviews on my idea.
>
> Thanks
> Piyush
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/mesa-dev