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@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev
