Project 0 C++ Primer

Lab 1 Summary

cmu15445第一个项目是学习C++，包括C++的面向对象、C++11/14/17特性，如智能指针等。同时也是对计算机基础知识的一个基本检验。

实验地址（以后可能用不了）：https://15445.courses.cs.cmu.edu/fall2021/project0/

首先说一下这个部分用到的基本原理：

• 1、CPU cache会将一维数组进行缓存，因此对RowMatrix中二维数组内存的开辟和使用Matrix中的linear一维数组，这样可以更好的使用CPU cache这一机制，提升代码速度；
• 2、C++多态，以及智能指针unique_ptr独占指针实现安全；

具体实现

接下来是每个部分的实现，可能会有错误的地方，C++语言特性目前还不是特别的熟悉，菜~

TODO 1 Construct a new Matrix instance

Matrix(int rows, int cols) {
    rows_ = rows;
    cols_ = cols;
    int len = rows * cols;
    linear_ = new T[len];
    memset(linear_, 0, sizeof(T) * len);
  }

TODO 2 Destroy a matrix instance

virtual ~Matrix() { delete[] linear_; }

TODO 3 Construct a new RowMatrix instance

RowMatrix(int rows, int cols) : Matrix<T>(rows, cols) {
    data_ = new T *[rows];
    for (int i = 0; i < rows; ++i) {
      data_[i] = this->linear_ + i * cols;
    }
  }

TODO 4 Implementation getter and setter

int GetRowCount() const override { return this->rows_; }

int GetColumnCount() const override { return this->cols_; }

T GetElement(int i, int j) const override {
    if (i < 0 || i >= this->rows_ || j < 0 || j >= this->cols_) {
      throw Exception(ExceptionType::OUT_OF_RANGE, "Void Get Element: index is out of range.");
    }
    return data_[i][j];
  }

void SetElement(int i, int j, T val) override {
    if (i < 0 || i >= this->rows_ || j < 0 || j >= this->cols_) {
      throw Exception(ExceptionType::OUT_OF_RANGE, "Void Set Element: index out of range");
    }
    data_[i][j] = val;
  }

TODO 5 Fill from source container

void FillFrom(const std::vector<T> &source) override {
    int size = source.size();
    if (size != this->rows_ * this->cols_) {
      throw Exception(ExceptionType::OUT_OF_RANGE, "source does not contain the required number of elements");
    }
    for (int i = 0; i < size; ++i) {
      this->linear_[i] = source[i];
    }
  }

TODO 6 Destroy a RowMatrix instance

~RowMatrix() override { delete[] data_; }

TODO 7 RowMatrix ADD

static std::unique_ptr<RowMatrix<T>> Add(const RowMatrix<T> *matrixA, const RowMatrix<T> *matrixB) {
    // TODO(P0): Add implementation

    if (matrixA->GetRowCount() != matrixB->GetRowCount() || matrixA->GetColumnCount() != matrixB->GetColumnCount()) {
      return std::unique_ptr<RowMatrix<T>>(nullptr);
    }

    int rows = matrixA->GetRowCount();
    int cols = matrixA->GetColumnCount();
    std::unique_ptr<RowMatrix<T>> ret = std::make_unique<RowMatrix<T>>(rows, cols);

    for (int i = 0; i < rows; ++i) {
      for (int j = 0; j < cols; ++j) {
        ret->SetElement(i, j, matrixA->GetElement(i, j) + matrixB->GetElement(i, j));
      }
    }
    return ret;
  }

TODO 8 RowMatrix Multiply

static std::unique_ptr<RowMatrix<T>> Multiply(const RowMatrix<T> *matrixA, const RowMatrix<T> *matrixB) {
    // TODO(P0): Add implementation

    if (matrixA->GetColumnCount() != matrixB->GetRowCount()) {
      return std::unique_ptr<RowMatrix<T>>(nullptr);
    }

    int rows = matrixA->GetRowCount();
    int lines = matrixA->GetColumnCount();
    int cols = matrixB->GetColumnCount();

    std::unique_ptr<RowMatrix<T>> ret = std::make_unique<RowMatrix<T>>(rows, cols);

    for (int i = 0; i < rows; ++i) {
      for (int j = 0; j < cols; ++j) {
        for (int k = 0; k < lines; ++k) {
          ret->SetElement(i, j, ret->GetElement(i, j) + matrixA->GetElement(i, k) * matrixB->GetElement(k, j));
        }
      }
    }
    return ret;
  }

TODO 9 RowMatrix GEMM

static std::unique_ptr<RowMatrix<T>> GEMM(const RowMatrix<T> *matrixA, const RowMatrix<T> *matrixB,
                                            const RowMatrix<T> *matrixC) {
    // TODO(P0): Add implementation

    if (matrixA->GetColumnCount() != matrixB->GetRowCount()) {
      return std::unique_ptr<RowMatrix<T>>(nullptr);
    }

    if (matrixA->GetRowCount() != matrixC->GetRowCount() || matrixB->GetColumnCount() != matrixC->GetColumnCount()) {
      return std::unique_ptr<RowMatrix<T>>(nullptr);
    }

    auto ret = Multiply(matrixA, matrixB);
    if (ret == nullptr) {
      return nullptr;
    }

    return Add(ret.get(), matrixC);
  }

Tests

cd build
make start_test
./test/start_test

Gradescope

make format
make check-lint
make check-clang-tidy
cd ..
zip -q -r project0-submission.zip src/include/primer/p0_starter.h