行列積のループ交換法の簡易ベンチマーク

matmul.cpp

#include <iostream>
#include <iomanip>
#include <random>
#include <cassert>
#include <cstdlib>
#include <sys/time.h>

struct Host {
  Host(int num)
      : num(num), A(num*num), B(num*num), C(num*num) {
    Initialize();
  }
  void Initialize() {
    std::random_device seed_gen;
    std::mt19937 engine(seed_gen());
    std::uniform_real_distribution<float> dist(-1.0, 1.0);
    InitializeMatrix(A, engine, dist);
    InitializeMatrix(B, engine, dist);
  }
  void InitializeMatrix(std::vector<float>& m,
                        std::mt19937& engine,
                        std::uniform_real_distribution<float>& dist) {
    for (int i = 0; i < num; ++i) {
      for (int j = 0; j < num; ++j) {
        m[i*num + j] = dist(engine);
      }
    }
  }
  int num;
  std::vector<float> A, B, C;
};

double to_double(const timeval& t) {
  return t.tv_sec + t.tv_usec * 1e-6;
}

double timeval_diff(const timeval& start, const timeval& end) {
  return to_double(end) - to_double(start);
}

#define MMROW(X, dj, i, j) ((X)[(i)*(dj)+(j)])
double MultiplyMatrixCLoopRow(Host* hst) {
  const int num = hst->num;
  struct timeval st, et;
  // C Loop (row) 部分抜粋
  // hst->A , hst->B , hst->C ともに num×num×sizeof(float) の メモリ領域
  gettimeofday(&st,NULL);
  for(int i=0;i<num;i++)
  {
    for(int j=0;j<num;j++)
    {
      float cc = 0.0;
      for(int k=0;k<num;k++)
      {
        cc += MMROW(hst->A,num,i,k) + MMROW(hst->B,num,k,j);
      }
      MMROW(hst->C,num,i,j) += cc;
    }
  }
  gettimeofday(&et,NULL);
  return timeval_diff(st, et);
}

double MultiplyMatrixCLoopSwap(Host* hst) {
  const int num = hst->num;
  struct timeval st, et;
  // C Loop (row) 部分抜粋
  // hst->A , hst->B , hst->C ともに num×num×sizeof(float) の メモリ領域
  gettimeofday(&st,NULL);
  for(int i=0;i<num;i++)
  {
    for(int j=0;j<num;j++)
    {
      MMROW(hst->C,num,i,j) = 0;
    }

    for(int k=0;k<num;k++)
    {
      for(int j=0;j<num;j++)
      {
         MMROW(hst->C,num,i,j) += MMROW(hst->A,num,i,k) + MMROW(hst->B,num,k,j);
      }
    }
  }
  gettimeofday(&et,NULL);
  return timeval_diff(st, et);
}
#undef MMROW

int main(int argc, char* argv[]) {
  for (int num = 100; num <= 2000; num += 100) {
    double elapsed_times[2];
    {
      Host hst(num);
      elapsed_times[0] = MultiplyMatrixCLoopRow(&hst);
    }
    {
      Host hst(num);
      elapsed_times[1] = MultiplyMatrixCLoopSwap(&hst);
    }
    std::cout << num << "\t"
              << std::fixed << std::setprecision(5)
              << elapsed_times[0] << "\t"
              << elapsed_times[1] << std::endl;
  }

  return 0;
}

$ g++ matmul.cpp -O2
$ ./a.out
100     0.00135 0.00024
200     0.01150 0.00227
300     0.04676 0.00623
400     0.09580 0.01180
500     0.17022 0.02210
600     0.29640 0.03532
700     0.51844 0.05624
800     0.71790 0.09602
900     1.24687 0.15850
1000    1.69872 0.22964
1100    2.83946 0.30027
1200    3.13777 0.46273
1300    4.11474 0.60245
1400    5.01733 0.90974
1500    6.96966 0.93310
1600    14.09880        1.25406
1700    20.28121        1.17932
1800    25.94932        1.79035
1900    41.12512        2.15874
2000    38.00541        2.35436