CODEWITHSUNDEEP
c++matrixtranspose
Ponsietta
Ponsietta

Reputation: 319

Cache Oblivious Matrix Transposition Implementation in C++

I have implemented an in-place cache-oblivious matrix transposition algorithm in C++ as below:

void CacheObliviousTransposition(int x, int delx, int y, int dely, int N, int* matrix) {
    if ((delx == 1) && (dely == 1)) {
        int tmp = matrix[(N*y) + x];
        matrix[(N*y) + x] = matrix[(N*x) + y];
        matrix[(N*x) + y] = tmp;
        return;
    }

    if (delx >= dely) {
        int xmid = delx / 2;
        CacheObliviousTransposition(x, xmid, y, dely, N, matrix);
        CacheObliviousTransposition(x + xmid, delx - xmid, y, dely, N, matrix);
        return;
    }

    int ymid = dely / 2;
    CacheObliviousTransposition(x, delx, y, ymid, N, matrix);
    CacheObliviousTransposition(x, delx, y + ymid, dely - ymid, N, matrix);
}

However, when I called the below method after transposition to ensure that it worked correctly, the if loop is being entered so I'm assuming something must be wrong with the implementation.

void CheckTransposition(int N, int* matrix)
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (matrix[(i*N) + j] != (j*N) + i + 42)
            {
                cout << "Transposition failed at i=" << i << ", j=" << j << "\n";
            } 
        }
    }
}

Can anyone help me identify what is wrong?

Note: variable matrix is a dynamically assigned integer array as below, as matrix is stored row by row in N*N consecutive memory locations

int* MatrixInit(int N)
{

    int* matrix = new int[N*N];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            matrix[(i*N) + j] = (i*N) + j + 42;
        }
    }

    return matrix;
}

Upvotes: 1

Views: 2698

Answers (1)

Mike2208
Mike2208

Reputation: 36

The above code will transpose your elements twice. For example, once CacheObliviousTransposition reaches the single element [0,1], it will transpose it with [1,0]. However, a separate recursion will later on reach [1,0], and transpose that with [0,1] again. Ultimately, all elements will be back in their original places.

To ensure that elements are only transposed once, you could check that x is less than y before switching:

void CacheObliviousTransposition(int x, int delx, int y, int dely, int N, int* matrix) {
    if ((delx == 1) && (dely == 1)) {
        if(x<y)
        {
            int tmp = matrix[(N*y) + x];
            matrix[(N*y) + x] = matrix[(N*x) + y];
            matrix[(N*x) + y] = tmp;
        }
        return;
    }

    if (delx >= dely) {
        int xmid = delx / 2;
        CacheObliviousTransposition(x, xmid, y, dely, N, matrix);
        CacheObliviousTransposition(x + xmid, delx - xmid, y, dely, N, matrix);
        return;
    }

    int ymid = dely / 2;
    CacheObliviousTransposition(x, delx, y, ymid, N, matrix);
    CacheObliviousTransposition(x, delx, y + ymid, dely - ymid, N, matrix);
}

Upvotes: 2

Related Questions