[Polly] Change the determination of parameters of macro-kernel

[gareevroman]

Summary

Typically processor architectures do not include an L3 cache, which means that Nc, the parameter of the micro-kernel, is, for all practical purposes, redundant ([1]). However, its small values can cause the redundant packing of the same elements of the matrix A, the first operand of the matrix multiplication. At the same time, big values of the parameter Nc can cause segmentation faults in case the available stack is exceeded.

This patch adds an option to specify the parameter Nc as a multiple of the parameter of the micro-kernel Nr.

In case of Intel Core i7-3820 SandyBridge and the following options,

clang -O3 gemm.c -I utilities/ utilities/polybench.c -DPOLYBENCH_TIME -march=native -mllvm -polly -mllvm -polly-pattern-matching-based-opts=true -DPOLYBENCH_USE_SCALAR_LB -mllvm -polly-target-cache-level-associativity=8,8 -mllvm -polly-target-cache-level-sizes=32768,262144 -mllvm -polly-target-latency-vector-fma=8

it helps to improve the performance from 11.303 GFlops/sec (39,247% of theoretical peak) to 17.896 GFlops/sec (62,14% of theoretical peak).

Refs.:

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

[grosser]

LGTM, but can you add a test case?

[gareevroman]

Update according to the comments.

lib/Transform/ScheduleOptimizer.cpp

static cl::opt<bool> RegisterTiling("polly-register-tiling",
                                     cl::cat(PollyCategory));
 
 static cl::opt<int> RegisterDefaultTileSize(
     "polly-register-tiling-default-tile-size",
     cl::desc("The default register tile size (if not enough were provided by"
              " --polly-register-tile-sizes)"),
     cl::Hidden, cl::init(2), cl::ZeroOrMore, cl::cat(PollyCategory));
 
+static cl::opt<int> PollyPatternMatchingNcQuotient(
+  "polly-pattern-matching-nc-quotient",
+  cl::desc("Quotient that is obtained by dividing Nc, the parameter of the"
+           "macro-kernel, by Nr, the parameter of the micro-kernel"),
+  cl::Hidden, cl::init(256), cl::ZeroOrMore, cl::cat(PollyCategory));
+
 static cl::list<int>
     RegisterTileSizes("polly-register-tile-sizes",
                       cl::desc("A tile size for each loop dimension, filled "
                                "with --polly-register-tile-size"),
                       cl::Hidden, cl::ZeroOrMore, cl::CommaSeparated,
                       cl::cat(PollyCategory));
 
 static cl::opt<bool>
getMacroKernelParams(const MicroKernelParamsTy &MicroKernelParams) {
   // all the parameters of a macro-kernel. It also checks that an associativity
   // degree of a cache level is greater than two. Otherwise, another algorithm
   // for determination of the parameters should be used.
   if (!(MicroKernelParams.Mr > 0 && MicroKernelParams.Nr > 0 &&
         CacheLevelSizes.size() >= 2 && CacheLevelAssociativity.size() >= 2 &&
         CacheLevelSizes[0] > 0 && CacheLevelSizes[1] > 0 &&
         CacheLevelAssociativity[0] > 2 && CacheLevelAssociativity[1] > 2))
     return {1, 1, 1};
+  // The quotient should be greater than zero.
+  if (PollyPatternMatchingNcQuotient <= 0)
+    return {1, 1, 1};
   int Car = floor(
       (CacheLevelAssociativity[0] - 1) /
       (1 + static_cast<double>(MicroKernelParams.Nr) / MicroKernelParams.Mr));
   int Kc = (Car * CacheLevelSizes[0]) /
            (MicroKernelParams.Mr * CacheLevelAssociativity[0] * 8);
   double Cac = static_cast<double>(Kc * 8 * CacheLevelAssociativity[1]) /
                CacheLevelSizes[1];
   int Mc = floor((CacheLevelAssociativity[1] - 2) / Cac);
-  int Nc = floor(1 / Cac);
+  int Nc = PollyPatternMatchingNcQuotient * MicroKernelParams.Nr;
   return {Mc, Nc, Kc};
 }
 
 /// Identify a memory access through the shape of its memory access relation.
 ///
 /// Identify the unique memory access in @p Stmt, that has an access relation
 /// equal to @p ExpectedAccessRelation.
 ///