[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(
     "polly-target-throughput-vector-fma",
     cl::desc("A throughput of the processor floating-point arithmetic units "
              "expressed in the number of vector fused multiply-add "
              "instructions per clock cycle."),
     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::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));
+// This option, along with --polly-target-2nd-cache-level-associativity,
+// --polly-target-1st-cache-level-size, and --polly-target-2st-cache-level-size
+// represent the parameters of the target cache, which do not have typical
+// values that can be used by default. However, to apply the pattern matching
+// optimizations, we use the values of the parameters of Intel Core i7-3820
+// SandyBridge in case the parameters are not specified. Such an approach helps
+// also to attain the high-performance on IBM POWER System S822 and IBM Power
+// 730 Express server.
+static cl::opt<int> FirstCacheLevelAssociativity(
+    "polly-target-1st-cache-level-associativity",
+    cl::desc("The associativity of the first cache level."), cl::Hidden,
+    cl::init(8), cl::ZeroOrMore, cl::cat(PollyCategory));
+
+static cl::opt<int> SecondCacheLevelAssociativity(
+    "polly-target-2nd-cache-level-associativity",
+    cl::desc("The associativity of the second cache level."), cl::Hidden,
+    cl::init(8), cl::ZeroOrMore, cl::cat(PollyCategory));
+
+static cl::opt<int> FirstCacheLevelSize(
+    "polly-target-1st-cache-level-size",
+    cl::desc("The size of the first cache level specified in bytes."),
+    cl::Hidden, cl::init(32768), cl::ZeroOrMore, cl::cat(PollyCategory));
+
+static cl::opt<int> SecondCacheLevelSize(
+    "polly-target-2nd-cache-level-size",
+    cl::desc("The size of the second level specified in bytes."), cl::Hidden,
+    cl::init(262144), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 static cl::opt<int> FirstLevelDefaultTileSize(
     "polly-default-tile-size",
     cl::desc("The default tile size (if not enough were provided by"
              " --polly-tile-sizes)"),
     cl::Hidden, cl::init(32), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 static cl::list<int> FirstLevelTileSizes(

 static struct MacroKernelParamsTy
 getMacroKernelParams(const MicroKernelParamsTy &MicroKernelParams) {
   // 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))
+        FirstCacheLevelSize > 0 && SecondCacheLevelSize > 0 &&
+        FirstCacheLevelAssociativity > 2 && SecondCacheLevelAssociativity > 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) /
+      (FirstCacheLevelAssociativity - 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 * FirstCacheLevelSize) /
+           (MicroKernelParams.Mr * FirstCacheLevelAssociativity * 8);
+  double Cac = static_cast<double>(Kc * 8 * SecondCacheLevelAssociativity) /
+               SecondCacheLevelSize;
+  int Mc = floor((SecondCacheLevelAssociativity - 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/mat_mul_pattern_data_layout.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 -polly-target-cache-level-associativity=8,8 -polly-target-cache-level-sizes=32768,262144 -polly-optimized-scops < %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 -polly-target-1st-cache-level-associativity=8 -polly-target-2nd-cache-level-associativity=8 -polly-target-1st-cache-level-size=32768 -polly-target-2nd-cache-level-size=262144 -polly-optimized-scops < %s 2>&1 | FileCheck %s
 ;
 ;    /* 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)
 ;      C[i][j] += alpha * A[i][k] * B[k][j];

test/ScheduleOptimizer/mat_mul_pattern_data_layout_2.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 -polly-target-cache-level-associativity=8,8 -polly-target-cache-level-sizes=32768,262144 -polly-ast -analyze < %s | 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 -polly-target-1st-cache-level-associativity=8 -polly-target-2nd-cache-level-associativity=8 -polly-target-1st-cache-level-size=32768 -polly-target-2nd-cache-level-size=262144 -polly-ast -analyze < %s | FileCheck %s
 ;
 ;    /* C := alpha*A*B + beta*C */
 ;    /* _PB_NK % Kc != 0 */
 ;    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)

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-target-cache-level-associativity=8,8 -polly-target-cache-level-sizes=32768,262144 < %s 2>&1 | FileCheck %s --check-prefix=EXTRACTION-OF-MACRO-KERNEL
+; 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-1st-cache-level-size=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-1st-cache-level-associativity=8 -polly-target-2nd-cache-level-associativity=8 -polly-target-1st-cache-level-size=32768 -polly-target-2nd-cache-level-size=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)
 ;      C[i][j] += alpha * A[i][k] * B[k][j];