[Polly] Specify the default values of the cache parameters

[gareevroman]

Summary

If the parameters of the target cache (i.e., cache level sizes, cache level associativities) are not specified or have wrong values, we use ones for parameters of the macro-kernel and do not perform data-layout optimizations of the matrix multiplication. In this patch we specify the default values of the cache parameters to be able to apply the pattern matching optimizations even in this case. Since there is no typical values of this parameters, we use the parameters of Intel Core i7-3820 SandyBridge that also help to attain the high-performance on IBM POWER System S822 and IBM Power 730 Express server.

[grosser]

Hi Roman,

thanks for the patch. I like the idea of this patch, but two comments:

1. Please specify in the commit message and as comment in the code where/how you derived these values.

2. I do not understand why you introduce new command line parameters. Could you not just add cl::init(num) to the existing parameters?

[gareevroman]

Hi Roman,

thanks for the patch. I like the idea of this patch, but two comments:

1. Please specify in the commit message and as comment in the code where/how you derived these values.

Hi Tobias,

thanks for the comments! I've updated it.

2. I do not understand why you introduce new command line parameters. Could you not just add cl::init(num) to the existing parameters?

As far as I understand, the cl::init attribute can specify an initial value only for a scalar option. Is there a workaround to use cl::init with the cl::list class?

[grosser]

In D28090#630809, @gareevroman wrote:

Hi Roman,

thanks for the patch. I like the idea of this patch, but two comments:

1. Please specify in the commit message and as comment in the code where/how you derived these values.

Hi Tobias,

thanks for the comments! I've updated it.

2. I do not understand why you introduce new command line parameters. Could you not just add cl::init(num) to the existing parameters?

As far as I understand, the cl::init attribute can specify an initial value only for a scalar option. Is there a workaround to use cl::init with the cl::list class?

Right. I did not see this. I see two options to work around this. Either we split the options into "-polly-target-1st-level-cache-associativity", "-polly-target-2nd-level-cache-associativity", or you add a static constant that contains the default cache sizes and use it in case the cache associativity list is of length zero.

But adding more options seems to be unnecessary (even though we have this with the cache size).

[gareevroman]

Update according to the comments.

lib/Transform/ScheduleOptimizer.cpp

static cl::opt<int> ThroughputVectorFma(
     cl::Hidden, cl::init(1), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 static cl::list<int>
     CacheLevelAssociativity("polly-target-cache-level-associativity",
                             cl::desc("The associativity of each cache level."),
                             cl::Hidden, cl::ZeroOrMore, cl::CommaSeparated,
                             cl::cat(PollyCategory));
 
+static cl::opt<int> DefaultCacheLevelAssociativity(
+    "polly-target-default-cache-level-associativity",
+    cl::desc("The default cache level associativity (if not enough were "
+             "provided by --polly-target-cache-level-associativity)."),
+    cl::Hidden, cl::init(8), cl::ZeroOrMore, cl::cat(PollyCategory));
+
+static cl::opt<int> DefaultFirstCacheLevelSize(
+    "polly-target-first-cache-level-size",
+    cl::desc(
+        "The default size of the first cache level specified in bytes (if not "
+        "enough were provided by --polly-target-cache-level-sizes)."),
+    cl::Hidden, cl::ZeroOrMore, cl::init(32768), cl::cat(PollyCategory));
+
+static cl::opt<int> DefaultSecondCacheLevelSize(
+    "polly-target-second-cache-level-size",
+    cl::desc(
+        "The default size of the second cache level specified in bytes (if "
+        "not enough were provided by --polly-target-cache-level-sizes)."),
+    cl::Hidden, cl::ZeroOrMore, cl::init(262144), cl::cat(PollyCategory));
+
 static cl::list<int> CacheLevelSizes(
     "polly-target-cache-level-sizes",
     cl::desc("The size of each cache level specified in bytes."), cl::Hidden,
     cl::ZeroOrMore, cl::CommaSeparated, cl::cat(PollyCategory));
 
 static cl::opt<int> FirstLevelDefaultTileSize(
     "polly-default-tile-size",
     cl::desc("The default tile size (if not enough were provided by"

 ///
 /// @param MicroKernelParams Parameters of the micro-kernel
 ///                          to be taken into account.
 /// @return The structure of type MacroKernelParamsTy.
 /// @see MacroKernelParamsTy
 /// @see MicroKernelParamsTy
 static struct MacroKernelParamsTy
 getMacroKernelParams(const MicroKernelParamsTy &MicroKernelParams) {
+  // The quotient should be greater than zero.
+  if (!(MicroKernelParams.Mr > 0 && MicroKernelParams.Nr > 0 &&
+        PollyPatternMatchingNcQuotient > 0))
+    return {1, 1, 1};
+
   // According to www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf,
   // it requires information about the first two levels of a cache to determine
   // 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};
+  // degree of a cache level is greater than two. Otherwise, the default values
+  // are used. Since there is no typical values of this parameters, we use the
+  // parameters of Intel Core i7-3820 SandyBridge that also help to attain the
+  // high-performance on IBM POWER System S822 and IBM Power 730 Express server.
+  int Associativity[2] = {DefaultCacheLevelAssociativity,
+                          DefaultCacheLevelAssociativity};
+  int Sizes[2] = {DefaultFirstCacheLevelSize, DefaultSecondCacheLevelSize};
+  for (unsigned i = 0; i < 2; i++) {
+    if (CacheLevelAssociativity.size() > i && CacheLevelAssociativity[i] > 2)
+      Associativity[i] = CacheLevelAssociativity[i];
+    if (CacheLevelSizes.size() > i && CacheLevelSizes[i] > 0)
+      Sizes[i] = CacheLevelSizes[i];
+  }
+
   int Car = floor(
-      (CacheLevelAssociativity[0] - 1) /
+      (Associativity[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 Kc = (Car * Sizes[0]) / (MicroKernelParams.Mr * Associativity[0] * 8);
+  double Cac = static_cast<double>(Kc * 8 * Associativity[1]) / Sizes[1];
+  int Mc = floor((Associativity[1] - 2) / 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.

test/ScheduleOptimizer/pattern-matching-based-opts_3.ll

-; RUN: opt %loadPolly -polly-opt-isl -polly-pattern-matching-based-opts=true -polly-target-throughput-vector-fma=1 -polly-target-latency-vector-fma=8 -analyze -polly-ast < %s 2>&1 | FileCheck %s
+; RUN: opt %loadPolly -polly-opt-isl -polly-pattern-matching-based-opts=true -polly-target-throughput-vector-fma=1 -polly-target-latency-vector-fma=8 -analyze -polly-ast -polly-pattern-matching-nc-quotient=0  < %s 2>&1 | FileCheck %s
 ; RUN: opt %loadPolly -polly-opt-isl -polly-pattern-matching-based-opts=true -polly-target-throughput-vector-fma=1 -polly-target-latency-vector-fma=8 -analyze -polly-ast -polly-target-cache-level-associativity=8,8 -polly-target-cache-level-sizes=32768,262144 < %s 2>&1 | FileCheck %s --check-prefix=EXTRACTION-OF-MACRO-KERNEL
 ;
 ;    /* C := alpha*A*B + beta*C */
 ;    for (i = 0; i < _PB_NI; i++)
 ;      for (j = 0; j < _PB_NJ; j++)
 ;        {
 ;    C[i][j] *= beta;
 ;    for (k = 0; k < _PB_NK; ++k)