This is an archive of the discontinued LLVM Phabricator instance.

[GSoC 2016][Polly] Determination of statements that contain matrix multiplication
ClosedPublic

Authored by gareevroman on May 24 2016, 9:59 AM.

Details

Summary

Add determination of statements that contain, in particular, matrix multiplications and can be optimized with [1] to try to get close-to-peak performance. It can be enabled via polly-pm-based-opts, which is false by default.

Refs:

[1] - http://www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf

Diff Detail

Event Timeline

gareevroman retitled this revision from to [GSoC 2016][Polly][WIP] Determination of statements that contain matrix multiplication.
gareevroman updated this object.
gareevroman added a subscriber: pollydev.

This is a first draft, which contains determination of the following class of statements:

  1. there are exactly three input dimensions
  2. all memory accesses of the statement will have stride 0 or 1, if we interchange loops (switch the variable used in the inner loop to the outer loop)
  3. all memory accesses of the statement except from the last one, are read memory access and the last one is write memory access
  4. all subscripts of the last memory access of the statement don’t contain the variable used in the inner loop

Of course, an algorithm from [1] was designed to optimize a subclass of the class and could possibly cause performance regression, if we try to apply it to all statements of the class. However, I think that determination of the class requires a simpler pattern matching in comparison to determination of statements that contain only matrix multiplication. Furthermore, I think that we can use an algorithm that is similar to the one presented in [1] to optimize statements from the class in future. For example, to find a latency (Lvfma) in general case, we could probably recursively calculate the sum of latencies of all users of an access instruction of the last memory access.

grosser edited edge metadata.May 24 2016, 10:25 AM

Hi Roman,

this looks already nice. Please add comments as well as a test case (conditional on "asserts"). Also, I am unsure what "pm" in the option means. I suggest to just spell it out.

gareevroman edited edge metadata.

Hello Tobias,

thank you for the comments! I’ve tried to address them and also fixed a few small issues. However, I’m not sure what you mean by "test case (conditional on "asserts")". Could you please explain it?

Looks good so far.

However, please add some positive and negative test cases. If you CHECK for the debug output, you need to add an "REQUIRES: asserts" line, as otherwise they will fail in a non-asserts build.

Tobias

Thank you for the explanation! This version of a patch adds positive and negative test cases. I’ve also fixed issues related to the isInputDimUsed and the debug output of the optimizeBand.

LGTM, but please use -instnamer or -metarenamer on the test case.

gareevroman retitled this revision from [GSoC 2016][Polly][WIP] Determination of statements that contain matrix multiplication to [GSoC 2016][Polly] Determination of statements that contain matrix multiplication.

-instnamer was used.

This revision was automatically updated to reflect the committed changes.