問(wèn)題描述

? 使用文件和內(nèi)存模擬系統(tǒng)緩存，并利用矩陣乘法驗(yàn)證實(shí)際和理論情況。

算法思想

設(shè)計(jì)一個(gè)Matrix類，其中Matrix是存在磁盤中的一個(gè)二進(jìn)制文件，類通過(guò)保存的矩陣屬性來(lái)讀取磁盤。前八個(gè)字節(jié)為兩個(gè)int32，保存矩陣的行列數(shù)。

Matrix中有一個(gè)buffer成員為讀取到的數(shù)據(jù)緩存，通過(guò)pos屬性來(lái)確定其在矩陣中的位置。其映射邏輯為$row=?pos÷colSize?,col=pos\mathrm{mod}colSize$。而緩存的管理模型則是模仿CPU的內(nèi)存緩存模型，采用寫回法。當(dāng)讀取矩陣中row行col列時(shí)，判斷邏輯如下。

? 完成磁盤交互后，其余操作即為正常的矩陣操作

功能模塊設(shè)計(jì)

矩陣類的成員變量，：

    Buffer buffer;
    const int rowSize;
    const int colSize;
    long cacheMissCount; // cache miss 次數(shù)
    long cacheCount;     // cache 訪問(wèn)次數(shù)
    int pos;             // pos = -1 means invalid buffer
    const int offset = 2 * INT_BYTE;
    fstream file;

? 矩陣值獲取和修改的函數(shù)

    int get(int row, int col)
    {
        int index = row * colSize + col;
        assert(index < rowSize * colSize && index >= 0);
        cacheCount++;
        if (index >= pos && index < pos + buffer.size && pos != -1)
            return buffer.get(index - pos);
        else
        {
            cacheMissCount++;
            readBuffer(index);
            return buffer.get(0);
        }
    }
    void set(int row, int col, int val)
    {
        assert(row <= rowSize && col <= colSize);
        if (pos <= indexOf(row, col) && indexOf(row, col) < pos + buffer.size)
            buffer.set(indexOf(row, col) - pos, val);
        else
        {
            cacheMissCount++;
            readBuffer(indexOf(row, col));
            buffer.set(0, val);
        }
        buffer.dirty = true;
    }

? 磁盤操作函數(shù)

    void writeBuffer()
    {
        file.seekp(pos * INT_BYTE + offset, ios::beg);
        for (int i = 0; i < buffer.size; i++)
        {
            file.write((char *)&buffer.get(i), INT_BYTE);
        }
        buffer.dirty = false;
    }

    void readBuffer(int startIndex)
    {
        if (buffer.dirty)
        {
            writeBuffer();
        }

        file.seekg(startIndex * INT_BYTE + offset, ios::beg);
        buffer.size = 0;
        for (int i = 0; i < buffer.capacity && startIndex + i < rowSize * colSize; i++)
        {
            int value;
            file.read((char *)&value, INT_BYTE);
            buffer.set(i, value);
            buffer.size++;
        }
        pos = startIndex;
    }

? 矩陣乘法函數(shù)

    Matrix *multiple_ijk(Matrix &right)
    {
        Matrix *t = new Matrix(rowSize, right.colSize, buffer.capacity);
        int i, j, k;
        for (i = 0; i < rowSize; i++)
        {
            for (j = 0; j < right.colSize; j++)
            {
                for (k = 0; k < right.rowSize; k++)
                {
                    t->set(i, j, t->get(i, j) + get(i, k) * right.get(k, j));
                }
            }
        }
        return t;
    }

    Matrix *multiple_ikj(Matrix &right)
    {
        Matrix *t = new Matrix(rowSize, right.colSize, buffer.capacity);
        int i, j, k;
        for (i = 0; i < rowSize; i++)
        {
            for (k = 0; k < right.rowSize; k++)
            {
                for (j = 0; j < right.colSize; j++)
                {
                    t->set(i, j, t->get(i, j) + get(i, k) * right.get(k, j));
                }
            }
        }
        return t;
    }

測(cè)試結(jié)果與分析

測(cè)試用例

class MatrixTest
{
public:
    void test1()
    {
        Matrix m(10, 10, 3, "m.txt");
        m.randomize();
        cout << m << endl;
        cout << "cache miss:" << m.getCacheMissCount() << endl;
        Matrix m1(10, 10, 3);
        m1.randomize();
        cout << m1 << endl;
        cout << "cache miss:" << m1.getCacheMissCount() << endl;
    }

    void test2()
    {
        Matrix m(10, 10, 3);
        cout << m << endl;
        m.set(0, 0, 9999);
        cout << m << endl;
        m.set(5, 0, 9999);
        cout << m << endl;
        m.set(3, 7, 9999);
        cout << m << endl;
    }
    void test3()
    {
        Matrix m1(2, 3, 5, "m1.txt");
        m1.randomize(100);
        cout << m1 << endl;
        Matrix m2(3, 4, 7, "m2.txt");
        m2.randomize(100);
        cout << m2 << endl;
        Matrix *m3 = m1.multiple_ijk(m2);
        cout << *m3 << endl;
        Matrix *m4 = m1.multiple_ikj(m2);
        cout << *m4 << endl;
        assert(m3->toString() == m4->toString());
    }
    void test4(int n, int cacheSize)
    {
        cout << "cache size is " << cacheSize << endl;
        Matrix m1(n, n, cacheSize, "m1.txt");
        cout << "initial m1(size is " << n << ")finished" << endl;
        Matrix m2(n, n, cacheSize, "m2.txt");
        cout << "initial m2(size is " << n << ")finished" << endl;
        Matrix *m3 = m1.multiple_ijk(m2);
        cout << "m1 ijk m2 finished" << endl;
        cout << "cache coutnt of m1: " << m1.getCacheCount() << ",	cache miss count of m1:" << m1.getCacheMissCount() << endl;
        cout << "cache coutnt of m2: " << m2.getCacheCount() << ",	cache miss count of m2:" << m2.getCacheMissCount() << endl;
        cout << "cache coutnt of m3: " << m3->getCacheCount() << ",	cache miss count of m3:" << m3->getCacheMissCount() << endl;
        cout << endl;
    }
    void test5(int n, int cacheSize)
    {
        cout << "cache size is " << cacheSize << endl;
        Matrix m1(n, n, cacheSize, "m1.txt");
        cout << "initial m1(size is " << n << ")finished" << endl;
        Matrix m2(n, n, cacheSize, "m2.txt");
        cout << "initial m2 finished" << endl;
        Matrix *m3 = m1.multiple_ikj(m2);
        cout << "m1 ijk m2(size is " << n << ")finished" << endl;
        cout << "cache coutnt of m1: " << m1.getCacheCount() << ",	cache miss count of m1:" << m1.getCacheMissCount() << endl;
        cout << "cache coutnt of m2: " << m2.getCacheCount() << ",	cache miss count of m2:" << m2.getCacheMissCount() << endl;
        cout << "cache coutnt of m3: " << m3->getCacheCount() << ",	cache miss count of m3:" << m3->getCacheMissCount() << endl;
        cout << endl;
    }
    void runTest()
    {
        for (int i = 5; i < 35; i += 5)
        {
            for (int j = 1; j < 5; j++)
            {
                test4(i, i / j);
                test5(i, i / j);
            }
        }
    }
};

實(shí)驗(yàn)測(cè)試

實(shí)驗(yàn)分析

假設(shè)矩陣為$C=A\times B$，且cache大小小于矩陣的一行或一列,且A、B、C都是大小為n的方陣

對(duì)于ijk的情況：

? 每次讀取時(shí)發(fā)生一次磁盤訪問(wèn)，而若cache當(dāng)中有臟數(shù)據(jù)，則有另一次的寫入訪問(wèn)。對(duì)于矩陣C，因?yàn)槠渥鳛椴僮骶仃?（總是進(jìn)行+=操作）*，所以只要是C矩陣發(fā)生了cache miss其實(shí)是進(jìn)行了兩次磁盤訪問(wèn)，而對(duì)于AB矩陣，發(fā)生cache miss 時(shí)只發(fā)生一次磁盤訪問(wèn)。

? cache miss 發(fā)生次數(shù)如下
$$\begin{gathered} C_{cachemiss}=\frac{n^2}{cachesize} \\ {A}_{cachemiss}=\frac{n^3}{cachesize} \\ {B}_{cachemiss}=n^3 \end{gathered}$$
? 所消耗的總時(shí)間
$$\begin{gathered} t_{total}=2T_{diskaccesstime}{C}_{cachemiss}+T_{diskaccesstime}{A}_{cachemiss}+T_{diskaccesstime}{B}_{cachemiss} \\ =\frac{n^3{T}_{diskaccesstime}}{cachesize(1+\frac{1}{n}+cachesize)} \end{gathered}$$
? 而當(dāng)順序化為ijk的時(shí)候，B矩陣的cache hit 率有所提高
$$\begin{gathered} C_{cachemiss}=\frac{n^3}{cachesize} \\ {A}_{cachemiss}=\frac{n^2}{cachesize} \\ {B}_{cachemiss}=\frac{n^3}{cachesize} \end{gathered}$$
所消耗的總時(shí)間變?yōu)榱?br>$$\begin{gathered} t_{total}=2T_{diskaccesstime}{C}_{cachemiss}+T_{diskaccesstime}{A}_{cachemiss}+T_{diskaccesstime}{B}_{cachemiss} \\ =\frac{n^3{T}_{diskaccesstime}}{cachesize(2+\frac{1}{n})} \end{gathered}$$文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-678391.html

到了這里，關(guān)于【矩陣乘法】C++實(shí)現(xiàn)外部矩陣乘法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！