optimized static padding for strassen's odd matrices

Question

I'm trying to address the issue of odd matrices for strassen's algorithm. My implementation truncates the recursion at a certain point, call it Q, and switches over to the standard implementation. Therefore in doing static padding, I don't actually need to pad up to the next power of 2. I just need to pad up to the least m*2^k greater than the input matrix dimension such that m < Q.

I'm having some trouble implementing this - mainly because I'm not sure what would be most efficient. Do I need to loop through all possible m values, or do I increment from each given input, testing if they fulfill the criteria?

score 0 · Answer 1 · answered Nov 02 '16 at 17:58

Using the above as inspiration, I believe to have found a more concise algorithm for finding the minimum padding

It works by repeatedly making the number divisible by 2 until it is below the threshold, then multiplying it by 2**counter to get the size the matrix must be padded to, in order to be repeatedly divisible by two until it is less than the threshold

unsigned int minPad(unsigned int inSize, unsigned int threshold) {
    unsigned int counter = 0;
    while (inSize > threshold) {
        inSize++;
        inSize >>= 1;
        counter ++;
    }
    return inSize << counter;
}

Note the inSIze++ could be replaced with if (inSize % 2) inSize++; however since an even number plus 1 integer division / 2 is equal to itself it's harmless to always add one — Warren Spencer, Nov 02 '16 at 17:59

Jarosław Gomułka · Accepted Answer · 2012-03-28T18:05:25.470

0

You are correct. Padding up to m * 2^k should perform much better than padding up to next power of 2.

I think you should pad up to value calculated by this function:

int get_best_pud_up_value(int actual_size, int Q) {
    int cnt = 0;
    int n = actual_size;
    while(n > Q) {
        cnt++;
        n /= 2;
    }

    // result should be smallest value such that:
    // result >= actual_size AND
    // result % (1<<cnt) == 0

    if (actual_size % (1<<cnt) == 0) {
        return actual_size;
    } else {
        return actual_size + (1<<cnt) - actual_size % (1<<cnt);
    }
}

edited Mar 28 '12 at 18:05

answered Mar 28 '12 at 14:56

Jarosław Gomułka

4,935
18
24

For actual_size = 258, Q = 17, this is returning 256, which I think is incorrect. I would want it to pad to 272. The issue is when you get an odd number by dividing by 2, but before you've reached the threshold. – Yiren Lu Mar 28 '12 at 17:49
You are correct. My previous solution was wrong. I have corrected it. Now for actual_size = 258 and Q=17 returning value is 272 :) – Jarosław Gomułka Mar 28 '12 at 18:09

optimized static padding for strassen's odd matrices

2 Answers2