シリアルおよび Cilk 配列表記バージョンの行列乗算パフォーマンスのベンチマークを行っています。Cilk の実装には、シリアルのほぼ 2 倍の時間がかかりますが、その理由がわかりません。
これはシングルコア実行用です
これが Cilk 乗算の要です。ランクの制限により、各乗算を配列に格納し、次に__sec_reduce_addこの配列を格納してから、目的の行列要素の値を設定する必要があります。
int* sum = new int[VEC_SIZE];
for (int r = 0; (r < rowsThis); r++) {
for (int c = 0; (c < colsOther); c++) {
sum[0:VEC_SIZE] = myData[r][0:VEC_SIZE] * otherData[0:VEC_SIZE][c];
product.data[r][c] = __sec_reduce_add(sum[0:VEC_SIZE]);
}
}
私はキャッシングの問題を理解しており、Cilk バージョンがシリアルよりもキャッシュ ヒットが少ない理由はわかりません。これは、両方とも行要素の一連のミスと共に、キャッシュ内にあることが期待される列配列にアクセスするためです。
私が見落としている明らかな依存関係や、使用すべき Cilk の構文要素はありますか? SIMD 演算を使用した非ブロック行列乗算のパフォーマンスを最大化するには、別の方法で Cilk を使用する必要がありますか?
私は Cilk を初めて使用するので、どんな助けや提案も歓迎します。
編集:
シリアル実装は次のとおりです。
for (int row = 0; (row < rowsThis); row++) {
for (int col = 0; (col < colsOther); col++) {
int sum = 0;
for (int i = 0; (i < VEC_SIZE); i++) {
sum += (matrix1[row][i] * matrix2[i][col]);
}
matrix3[row][col] = sum;
}
}
メモリは適切に割り当て (解放) され、乗算の結果は両方の実装で正しくなります。行列のサイズはコンパイル時には不明であり、ベンチマーク全体でさまざまなサイズが使用されます。
コンパイラ: icpc (ICC) 15.0.0 20140723
コンパイル フラグ: icpc -g Wall -O2 -std=c++11
割り当てられたメモリの使用、ベクトルからバニラ配列への変換などは無視してください。別のプログラムをハックして、実際よりも簡単であると仮定して、これを実行しました。2D ベクトルの両方の次元で cilk 表記をコンパイラに受け入れさせることができなかったので、ベンチマークのために従来の配列を使用することにしました。
適切なファイルはすべて次のとおりです。
MatrixTest.cpp
#include <string>
#include <fstream>
#include <stdlib.h>
#include "Matrix.h"
#define MATRIX_SIZE 2000
#define REPETITIONS 1
int main(int argc, char** argv) {
auto init = [](int row, int col) { return row + col; };
const Matrix matrix1(MATRIX_SIZE, MATRIX_SIZE, init);
const Matrix matrix2(MATRIX_SIZE, MATRIX_SIZE, init);
for (size_t i = 0; (i < REPETITIONS); i++) {
const Matrix matrix3 = matrix1 * matrix2;
std::cout << "Diag sum: " << matrix3.sumDiag() << std::endl;
}
return 0;
}
Matrix.h
#ifndef MATRIX_H
#define MATRIX_H
#include <iostream>
#include <functional>
#include <vector>
using TwoDVec = std::vector<std::vector<int>>;
class Matrix {
public:
Matrix();
~Matrix();
Matrix(int rows, int cols);
Matrix(int rows, int cols, std::function<Val(int, int)> init);
Matrix(const Matrix& src);
Matrix(Matrix&& src);
Matrix operator*(const Matrix& src) const throw(std::exception);
Matrix& operator=(const Matrix& src);
int sumDiag() const;
protected:
int** getRawData() const;
private:
TwoDVec data;
};
#endif
マトリックス.cpp
#include <iostream>
#include <algorithm>
#include <stdexcept>
#include "Matrix.h"
#if defined(CILK)
Matrix
Matrix::operator*(const Matrix& other) const throw(std::exception) {
int rowsOther = other.data.size();
int colsOther = rowsOther > 0 ? other.data[0].size() : 0;
int rowsThis = data.size();
int colsThis = rowsThis > 0 ? data[0].size() : 0;
if (colsThis != rowsOther) {
throw std::runtime_error("Invalid matrices for multiplication.");
}
int** thisRaw = this->getRawData(); // held until d'tor
int** otherRaw = other.getRawData();
Matrix product(rowsThis, colsOther);
const int VEC_SIZE = colsThis;
for (int r = 0; (r < rowsThis); r++) {
for (int c = 0; (c < colsOther); c++) {
product.data[r][c] = __sec_reduce_add(thisRaw[r][0:VEC_SIZE]
* otherRaw[0:VEC_SIZE][c]);
}
}
delete[] thisRaw;
delete[] otherRaw;
return product;
}
#elif defined(SERIAL)
Matrix
Matrix::operator*(const Matrix& other) const throw(std::exception) {
int rowsOther = other.data.size();
int colsOther = rowsOther > 0 ? other.data[0].size() : 0;
int rowsThis = data.size();
int colsThis = rowsThis > 0 ? data[0].size() : 0;
if (colsThis != rowsOther) {
throw std::runtime_error("Invalid matrices for multiplication.");
}
int** thisRaw = this->getRawData(); // held until d'tor
int** otherRaw = other.getRawData();
Matrix product(rowsThis, colsOther);
const int VEC_SIZE = colsThis;
for (int r = 0; (r < rowsThis); r++) {
for (int c = 0; (c < colsOther); c++) {
int sum = 0;
for (int i = 0; (i < VEC_SIZE); i++) {
sum += (thisRaw[r][i] * otherRaw[i][c]);
}
product.data[r][c] = sum;
}
}
delete[] thisRaw;
delete[] otherRaw;
return product;
}
#endif
// Default c'tor
Matrix::Matrix()
: Matrix(1,1) { }
Matrix::~Matrix() { }
// Rows/Cols c'tor
Matrix::Matrix(int rows, int cols)
: data(TwoDVec(rows, std::vector<int>(cols, 0))) { }
// Init func c'tor
Matrix::Matrix(int rows, int cols, std::function<int(int, int)> init)
: Matrix(rows, cols) {
for (int r = 0; (r < rows); r++) {
for (int c = 0; (c < cols); c++) {
data[r][c] = init(r,c);
}
}
}
// Copy c'tor
Matrix::Matrix(const Matrix& other) {
int rows = other.data.size();
int cols = rows > 0 ? other.data[0].size() : 0;
this->data.resize(rows, std::vector<int>(cols, 0));
for(int r = 0; (r < rows); r++) {
this->data[r] = other.data[r];
}
}
// Move c'tor
Matrix::Matrix(Matrix&& other) {
if (this == &other) return;
this->data.clear();
int rows = other.data.size();
for (int r = 0; (r < rows); r++) {
this->data[r] = std::move(other.data[r]);
}
}
Matrix&
Matrix::operator=(const Matrix& other) {
int rows = other.data.size();
this->data.resize(rows, std::vector<int>(0));
for (int r = 0; (r < rows); r++) {
this->data[r] = other.data[r];
}
return *this;
}
int
Matrix::sumDiag() const {
int rows = data.size();
int cols = rows > 0 ? data[0].size() : 0;
int dim = (rows < cols ? rows : cols);
int sum = 0;
for (int i = 0; (i < dim); i++) {
sum += data[i][i];
}
return sum;
}
int**
Matrix::getRawData() const {
int** rawData = new int*[data.size()];
for (int i = 0; (i < data.size()); i++) {
rawData[i] = const_cast<int*>(data[i].data());
}
return rawData;
}