mt/br_matmul/br_matmul.c

   1 //**************************************************************************
   2 // Multi-threaded Matrix Multiply benchmark
   3 //--------------------------------------------------------------------------
   4 // TA     : Christopher Celio
   5 // Student: Benjamin Han
   6 //
   7 //
   8 // This benchmark multiplies two 2-D arrays together and writes the results to
   9 // a third vector. The input data (and reference data) should be generated
  10 // using the matmul_gendata.pl perl script and dumped to a file named
  11 // dataset.h.
  12
  13
  14 // print out arrays, etc.
  15 //#define DEBUG
  16
  17 //--------------------------------------------------------------------------
  18 // Includes
  19
  20 #include <string.h>
  21 #include <stdlib.h>
  22 #include <stdio.h>
  23
  24
  25 //--------------------------------------------------------------------------
  26 // Input/Reference Data
  27
  28 typedef float data_t;
  29 #include "dataset.h"
  30
  31
  32 //--------------------------------------------------------------------------
  33 // Basic Utilities and Multi-thread Support
  34
  35 __thread unsigned long coreid;
  36 unsigned long ncores;
  37
  38 #include "util.h"
  39
  40 #define stringify_1(s) #s
  41 #define stringify(s) stringify_1(s)
  42 #define stats(code) do {                                                \
  43     unsigned long _c = -rdcycle(), _i = -rdinstret();                   \
  44     code;                                                               \
  45     _c += rdcycle(), _i += rdinstret();                                 \
  46     if (coreid == 0)                                                    \
  47       printf("%s: %ld cycles, %ld.%ld cycles/iter, %ld.%ld CPI\n",      \
  48              stringify(code), _c, _c/DIM_SIZE/DIM_SIZE/DIM_SIZE, 10*_c/DIM_SIZE/DIM_SIZE/DIM_SIZE%10, _c/_i, 10*_c/_i%10); \
  49   } while(0)
  50
  51
  52 //--------------------------------------------------------------------------
  53 // Helper functions
  54
  55 void printArrayMT( char name[], int n, data_t arr[] )
  56 {
  57   int i;
  58   if (coreid != 0)
  59     return;
  60
  61   printf( " %10s :", name );
  62   for ( i = 0; i < n; i++ )
  63     printf( " %3ld ", (long) arr[i] );
  64   printf( "\n" );
  65 }
  66
  67 void __attribute__((noinline)) verifyMT(size_t n, const data_t* test, const data_t* correct)
  68 {
  69   if (coreid != 0)
  70     return;
  71
  72   size_t i;
  73   for (i = 0; i < n; i++)
  74     {
  75       if (test[i] != correct[i])
  76         {
  77           printf("FAILED test[%d]= %3ld, correct[%d]= %3ld\n",
  78                  i, (long)test[i], i, (long)correct[i]);
  79           exit(-1);
  80         }
  81     }
  82
  83   return;
  84 }
  85
  86 //--------------------------------------------------------------------------
  87 // matmul function
  88
  89 // single-thread, naive version
  90 void __attribute__((noinline)) matmul_naive(const int lda,  const data_t A[], const data_t B[], data_t C[] )
  91 {
  92   int i, j, k;
  93
  94   if (coreid > 0)
  95     return;
  96
  97   for ( i = 0; i < lda; i++ )
  98     for ( j = 0; j < lda; j++ )
  99       {
 100         for ( k = 0; k < lda; k++ )
 101           {
 102             C[i + j*lda] += A[j*lda + k] * B[k*lda + i];
 103           }
 104       }
 105
 106 }
 107
 108
 109
 110 void __attribute__((noinline)) matmul(const int lda,  const data_t A[], const data_t B[], data_t C[] )
 111 {
 112
 113   // ***************************** //
 114   // **** ADD YOUR CODE HERE ***** //
 115   // ***************************** //
 116   //
 117   // feel free to make a separate function for MI and MSI versions.
 118   int j2, i2, k2, j, i, k;
 119   int tmpC00, tmpC01, tmpC02, tmpC03, tmpC04, tmpC05, tmpC06, tmpC07;
 120   int tmpC10, tmpC11, tmpC12, tmpC13, tmpC14, tmpC15, tmpC16, tmpC17;
 121   int jBLOCK = 32;
 122   int iBLOCK = 16;
 123   int kBLOCK = 32;
 124   static __thread int tB[4096]; //__thread
 125   int startInd = 0;
 126   int endInd = lda >> 1;
 127   if (coreid == 1) {
 128     startInd = lda >> 1;
 129     endInd = lda;
 130   }
 131
 132   //tranpose B (block?)
 133   for (i = 0; i < lda; i += 2) {
 134     for (j = startInd; j < endInd; j += 2) {
 135       tB[j*lda + i] = B[i*lda + j];
 136       tB[(j + 1)*lda + i] = B[i*lda + j + 1];
 137       tB[j*lda + i + 1] = B[(i + 1)*lda + j];
 138       tB[(j + 1)*lda + i + 1] = B[(i + 1)*lda + j + 1];
 139     }
 140   }
 141   barrier(ncores);
 142
 143   // compute C[j*n + i] += A[j*n + k] + Btranspose[i*n + k]
 144   for ( j2 = 0; j2 < lda; j2 += jBLOCK )
 145     for ( i2 = startInd; i2 < endInd; i2 += iBLOCK )
 146       for ( j = j2; j < j2 + jBLOCK; j += 2 )
 147         for ( k2 = 0; k2 < lda; k2 += kBLOCK )
 148           for ( i = i2; i < i2 + iBLOCK; i += 4) {
 149             tmpC00 = C[j*lda + i + 0]; tmpC10 = C[(j + 1)*lda + i + 0];
 150             tmpC01 = C[j*lda + i + 1]; tmpC11 = C[(j + 1)*lda + i + 1];
 151             tmpC02 = C[j*lda + i + 2]; tmpC12 = C[(j + 1)*lda + i + 2];
 152             tmpC03 = C[j*lda + i + 3]; tmpC13 = C[(j + 1)*lda + i + 3];
 153             //tmpC04 = C[j*lda + i + 4]; tmpC14 = C[(j + 1)*lda + i + 4];
 154             //tmpC05 = C[j*lda + i + 5]; tmpC15 = C[(j + 1)*lda + i + 5];
 155             //tmpC06 = C[j*lda + i + 6]; tmpC16 = C[(j + 1)*lda + i + 6];
 156             //tmpC07 = C[j*lda + i + 7]; tmpC17 = C[(j + 1)*lda + i + 7];
 157             for ( k = k2; k < k2 + kBLOCK; k += 4) {
 158               tmpC00 += A[j*lda + k] * tB[(i + 0)*lda + k];
 159               tmpC01 += A[j*lda + k] * tB[(i + 1)*lda + k];
 160               tmpC02 += A[j*lda + k] * tB[(i + 2)*lda + k];
 161               tmpC03 += A[j*lda + k] * tB[(i + 3)*lda + k];
 162               //tmpC04 += A[j*lda + k] * tB[(i + 4)*lda + k];
 163               //tmpC05 += A[j*lda + k] * tB[(i + 5)*lda + k];
 164               //tmpC06 += A[j*lda + k] * tB[(i + 6)*lda + k];
 165               //tmpC07 += A[j*lda + k] * tB[(i + 7)*lda + k];
 166               tmpC10 += A[(j + 1)*lda + k] * tB[(i + 0)*lda + k];
 167               tmpC11 += A[(j + 1)*lda + k] * tB[(i + 1)*lda + k];
 168               tmpC12 += A[(j + 1)*lda + k] * tB[(i + 2)*lda + k];
 169               tmpC13 += A[(j + 1)*lda + k] * tB[(i + 3)*lda + k];
 170               //tmpC14 += A[(j + 1)*lda + k] * tB[(i + 4)*lda + k];
 171               //tmpC15 += A[(j + 1)*lda + k] * tB[(i + 5)*lda + k];
 172               //tmpC16 += A[(j + 1)*lda + k] * tB[(i + 6)*lda + k];
 173               //tmpC17 += A[(j + 1)*lda + k] * tB[(i + 7)*lda + k];
 174
 175               tmpC00 += A[j*lda + k + 1] * tB[(i + 0)*lda + k + 1];
 176               tmpC01 += A[j*lda + k + 1] * tB[(i + 1)*lda + k + 1];
 177               tmpC02 += A[j*lda + k + 1] * tB[(i + 2)*lda + k + 1];
 178               tmpC03 += A[j*lda + k + 1] * tB[(i + 3)*lda + k + 1];
 179               //tmpC04 += A[j*lda + k + 1] * tB[(i + 4)*lda + k + 1];
 180               //tmpC05 += A[j*lda + k + 1] * tB[(i + 5)*lda + k + 1];
 181               //tmpC06 += A[j*lda + k + 1] * tB[(i + 6)*lda + k + 1];
 182               //tmpC07 += A[j*lda + k + 1] * tB[(i + 7)*lda + k + 1];
 183               tmpC10 += A[(j + 1)*lda + k + 1] * tB[(i + 0)*lda + k + 1];
 184               tmpC11 += A[(j + 1)*lda + k + 1] * tB[(i + 1)*lda + k + 1];
 185               tmpC12 += A[(j + 1)*lda + k + 1] * tB[(i + 2)*lda + k + 1];
 186               tmpC13 += A[(j + 1)*lda + k + 1] * tB[(i + 3)*lda + k + 1];
 187               //tmpC14 += A[(j + 1)*lda + k + 1] * tB[(i + 4)*lda + k + 1];
 188               //tmpC15 += A[(j + 1)*lda + k + 1] * tB[(i + 5)*lda + k + 1];
 189               //tmpC16 += A[(j + 1)*lda + k + 1] * tB[(i + 6)*lda + k + 1];
 190               //tmpC17 += A[(j + 1)*lda + k + 1] * tB[(i + 7)*lda + k + 1];
 191
 192               tmpC00 += A[j*lda + k + 2] * tB[(i + 0)*lda + k + 2];
 193               tmpC01 += A[j*lda + k + 2] * tB[(i + 1)*lda + k + 2];
 194               tmpC02 += A[j*lda + k + 2] * tB[(i + 2)*lda + k + 2];
 195               tmpC03 += A[j*lda + k + 2] * tB[(i + 3)*lda + k + 2];
 196               //tmpC04 += A[j*lda + k + 2] * tB[(i + 4)*lda + k + 2];
 197               //tmpC05 += A[j*lda + k + 2] * tB[(i + 5)*lda + k + 2];
 198               //tmpC06 += A[j*lda + k + 2] * tB[(i + 6)*lda + k + 2];
 199               //tmpC07 += A[j*lda + k + 2] * tB[(i + 7)*lda + k + 2];
 200               tmpC10 += A[(j + 1)*lda + k + 2] * tB[(i + 0)*lda + k + 2];
 201               tmpC11 += A[(j + 1)*lda + k + 2] * tB[(i + 1)*lda + k + 2];
 202               tmpC12 += A[(j + 1)*lda + k + 2] * tB[(i + 2)*lda + k + 2];
 203               tmpC13 += A[(j + 1)*lda + k + 2] * tB[(i + 3)*lda + k + 2];
 204               //tmpC14 += A[(j + 1)*lda + k + 2] * tB[(i + 4)*lda + k + 2];
 205               //tmpC15 += A[(j + 1)*lda + k + 2] * tB[(i + 5)*lda + k + 2];
 206               //tmpC16 += A[(j + 1)*lda + k + 2] * tB[(i + 6)*lda + k + 2];
 207               //tmpC17 += A[(j + 1)*lda + k + 2] * tB[(i + 7)*lda + k + 2];
 208
 209               tmpC00 += A[j*lda + k + 3] * tB[(i + 0)*lda + k + 3];
 210               tmpC01 += A[j*lda + k + 3] * tB[(i + 1)*lda + k + 3];
 211               tmpC02 += A[j*lda + k + 3] * tB[(i + 2)*lda + k + 3];
 212               tmpC03 += A[j*lda + k + 3] * tB[(i + 3)*lda + k + 3];
 213               //tmpC04 += A[j*lda + k + 3] * tB[(i + 4)*lda + k + 3];
 214               //tmpC05 += A[j*lda + k + 3] * tB[(i + 5)*lda + k + 3];
 215               //tmpC06 += A[j*lda + k + 3] * tB[(i + 6)*lda + k + 3];
 216               //tmpC07 += A[j*lda + k + 3] * tB[(i + 7)*lda + k + 3];
 217               tmpC10 += A[(j + 1)*lda + k + 3] * tB[(i + 0)*lda + k + 3];
 218               tmpC11 += A[(j + 1)*lda + k + 3] * tB[(i + 1)*lda + k + 3];
 219               tmpC12 += A[(j + 1)*lda + k + 3] * tB[(i + 2)*lda + k + 3];
 220               tmpC13 += A[(j + 1)*lda + k + 3] * tB[(i + 3)*lda + k + 3];
 221               //tmpC14 += A[(j + 1)*lda + k + 3] * tB[(i + 4)*lda + k + 3];
 222               //tmpC15 += A[(j + 1)*lda + k + 3] * tB[(i + 5)*lda + k + 3];
 223               //tmpC16 += A[(j + 1)*lda + k + 3] * tB[(i + 6)*lda + k + 3];
 224               //tmpC17 += A[(j + 1)*lda + k + 3] * tB[(i + 7)*lda + k + 3];
 225             }
 226             C[j*lda + i + 0] = tmpC00; C[(j + 1)*lda + i + 0] = tmpC10;
 227             C[j*lda + i + 1] = tmpC01; C[(j + 1)*lda + i + 1] = tmpC11;
 228             C[j*lda + i + 2] = tmpC02; C[(j + 1)*lda + i + 2] = tmpC12;
 229             C[j*lda + i + 3] = tmpC03; C[(j + 1)*lda + i + 3] = tmpC13;
 230             //C[j*lda + i + 4] = tmpC04; C[(j + 1)*lda + i + 4] = tmpC14;
 231             //C[j*lda + i + 5] = tmpC05; C[(j + 1)*lda + i + 5] = tmpC15;
 232             //C[j*lda + i + 6] = tmpC06; C[(j + 1)*lda + i + 6] = tmpC16;
 233             //C[j*lda + i + 7] = tmpC07; C[(j + 1)*lda + i + 7] = tmpC17;
 234           }
 235 }
 236
 237 //--------------------------------------------------------------------------
 238 // Main
 239 //
 240 // all threads start executing thread_entry(). Use their "coreid" to
 241 // differentiate between threads (each thread is running on a separate core).
 242
 243 void thread_entry(int cid, int nc)
 244 {
 245   coreid = cid;
 246   ncores = nc;
 247
 248   // static allocates data in the binary, which is visible to both threads
 249   static data_t results_data[ARRAY_SIZE];
 250
 251
 252 //  // Execute the provided, naive matmul
 253 //  barrier(nc);
 254 //  stats(matmul_naive(DIM_SIZE, input1_data, input2_data, results_data); barrier(nc));
 255 //
 256 //
 257 //  // verify
 258 //  verifyMT(ARRAY_SIZE, results_data, verify_data);
 259 //
 260 //  // clear results from the first trial
 261 //  size_t i;
 262 //  if (coreid == 0)
 263 //    for (i=0; i < ARRAY_SIZE; i++)
 264 //      results_data[i] = 0;
 265 //  barrier(nc);
 266
 267
 268   // Execute your faster matmul
 269   barrier(nc);
 270   stats(matmul(DIM_SIZE, input1_data, input2_data, results_data); barrier(nc));
 271
 272 #ifdef DEBUG
 273   printArrayMT("results:", ARRAY_SIZE, results_data);
 274   printArrayMT("verify :", ARRAY_SIZE, verify_data);
 275 #endif
 276
 277   // verify
 278   verifyMT(ARRAY_SIZE, results_data, verify_data);
 279   barrier(nc);
 280
 281   exit(0);
 282 }
 283