Развертывание цикла не работает с оставшимися элементами

У меня есть типичный алгоритм умножения матриц. Я пытаюсь применить и понять развертывание цикла, но у меня возникла проблема с реализацией алгоритма, когда я пытаюсь развернуть k раз, когда k не кратно размеру матрицы. (Вместо этого я получаю очень большие числа). Это означает, что я не понимаю, как обращаться с оставшимися элементами после развертывания. Вот что у меня есть:

void Mult_Matx(unsigned long* a, unsigned long* b, unsigned long*c, long n)
{
    long i = 0, j = 0, k = 0;
    unsigned long sum, sum1, sum2, sum3, sum4, sum5, sum6, sum7;

    for (i = 0; i < n; i++)
    {
        long in = i * n;
        for (j = 0; j < n; j++)
        {
            sum = sum1 = sum2 = sum3 = sum4 = sum5 = sum6 = sum7 = 0;

            for (k = 0; k < n; k += 8)
            {
                sum = sum + a[in + k] * b[k * n + j];
                sum1 = sum1 + a[in + (k + 1)] * b[(k + 1) * n + j];
                sum2 = sum2 + a[in + (k + 2)] * b[(k + 2) * n + j];
                sum3 = sum3 + a[in + (k + 3)] * b[(k + 3) * n + j];
                sum4 = sum4 + a[in + (k + 4)] * b[(k + 4) * n + j];
                sum5 = sum5 + a[in + (k + 5)] * b[(k + 5) * n + j];
                sum6 = sum6 + a[in + (k + 6)] * b[(k + 6) * n + j];
                sum7 = sum7 + a[in + (k + 7)] * b[(k + 7) * n + j];
            }

            if (n % 8 != 0)
            {
                for (k = 8 * (n / 8); k < n; k++)
                {
                    sum = sum + a[in + k] * b[k * n + j];
                }
            }
            c[in + j] = sum + sum1 + sum2 + sum3 + sum4 + sum5 + sum6 + sum7;
        }
    }
}

Допустим, размер n равен 12. Когда я разворачиваю его 4 раза, этот код работает, то есть когда он никогда не входит в оставшийся цикл. Но я теряю след того, что происходит, когда это происходит! Если кто-нибудь может указать мне, где я ошибаюсь, я был бы очень признателен. Я новичок в этом, и мне трудно понять.


c matrix-multiplication loop-unrolling
person Luc Aux    schedule 20.11.2017    source источник
comment
ручное развертывание цикла - это так 80-е ... (я бы сказал: не надо. Если вы настаиваете, взгляните на устройство Даффа, обрабатывая оставшуюся часть, переходя куда-то внутрь развернутого кода)   -  person    schedule 20.11.2017
comment
@FelixPalmen, лол. Я посещаю вводный курс по операционным системам. Так....   -  person Luc Aux    schedule 20.11.2017
comment
Возможно, вам следует уделить некоторое время тому, чтобы научиться отлаживать свои программы. ?   -  person Some programmer dude    schedule 20.11.2017
comment
Кроме того, вместо временной переменной sum1 в sum7 почему бы просто не добавить к sum? Например, sum += a[in+(k+5)]* b[(k+5)*n+j]? Или, возможно, тоже пропустить sum и добавить непосредственно к c[in + j]?   -  person Some programmer dude    schedule 20.11.2017
comment
@Someprogrammerdude Я просто пытался визуализировать вещи. У меня не было абсолютно никакой реальной причины использовать столько переменных. Я бы, вероятно, пошел с этим, если бы мне действительно пришлось реализовать что-то подобное.   -  person Luc Aux    schedule 20.11.2017
comment
Различные пробелы для строки sum3 сводят меня с ума :)   -  person Steve    schedule 20.11.2017
comment
@Steve Я тоже, поэтому я изменил его и все остальное, что хотел изменить мой автоматический форматировщик eclipse. ;)   -  person mch    schedule 20.11.2017

Ответы (1)


arrow_upward
2
arrow_downward

Общий способ развертывания цикла на этой фигуре:

for(int i=0; i<N; i++)
    ...

is

int i;
for(i=0; i<N-L; i+=L)
    ...
for(; i<N; i++)
    ...

или если вы хотите сохранить индексную переменную в рамках циклов:

for(int i=0; i<N-L; i+=L)
    ...
for(int i=L*(N/L); i<N; i++)
    ...

Здесь я использую тот факт, что целочисленное деление округляется в меньшую сторону. L — это количество шагов, которые вы делаете в первом цикле.

Пример:

const int N=22;
const int L=6;
int i;
for(i=0; i<N-L; i+=L)
{
    printf("%d\n", i);
    printf("%d\n", i+1);
    printf("%d\n", i+2);
    printf("%d\n", i+3);
    printf("%d\n", i+4);
    printf("%d\n", i+5);
}
for(; i<N; i++)
    printf("%d\n", i);

Но я рекомендую взглянуть на устройство Дафф. Тем не менее, я подозреваю, что это не всегда хорошо. Причина в том, что по модулю — довольно дорогая операция.

Условие if (n % 8 != 0) не должно быть нужно. Заголовок for должен позаботиться об этом, если он написан правильно.

person klutt    schedule 20.11.2017