Почему доступ к основной матрице строки работает медленнее, чем доступ к основной матрице столбца в моем C-коде? - PullRequest
Новая
       62

Почему доступ к основной матрице строки работает медленнее, чем доступ к основной матрице столбца в моем C-коде?

2 голосов
/ 02 ноября 2019

Я реализую код C для сравнения влияния пространственной локальности при доступе к матрице в порядке основной строки и в порядке основной столбца.

Тем не менее, основной ряд получил более медленный результат, чего я не узнал.

Я работаю на Ubuntu-16.04 (на VMware) с 2 ГБ памяти и 2Ядра и я использую gcc 5.4.0 для компиляции кода.

Я создаю целочисленную матрицу 2000 * 2000 и использую "rdtsc" для измерения общего количества тактов во время обхода.

Я также пытался использовать метод clock_gettime () для измерения времени, и он показал аналогичный результат.

Вот код, который я использую для проверки этих случаев: 

typedef enum {
    ROW_MAJOR=1,
    COLUMN_MAJOR
} traverse_type;

static inline unsigned long long read_tsc(void)
{
    unsigned low, high;
    asm volatile("rdtsc" :"=a"(low), "=d"(high));
    return ((low) | ((u64)(high) << 32));
}

void calc_matrix_traverse_clocks(traverse_type type) {
    int mat[ROW][COLUMN];
    int i, j, sum;
    unsigned long long before, after;

    if (type == ROW_MAJOR) {
        before = read_tsc();
        for (i = 0; i < ROW; i++) {
            for (j = 0; j < COLUMN; j++) {
               sum += mat[i][j];
            }
        }
        after = read_tsc();
        printf("ROW Major: %lld\n", after-before);
    } else {
        before  = read_tsc();
        for (i = 0; i < COLUMN; i++) {
            for (j = 0; j < ROW; j++) {
                sum += mat[j][i];
            }
        }
        after = read_tsc();
        printf("COLUMN Major: %lld\n", after-before);
    }
}

int main (int argc, char *argv[]) {

    calc_matrix_traverse_clocks(ROW_MAJOR);
    //calc_matrix_traverse_clocks(COLUMN_MAJOR);    

    return 0;
}

Я запускал программу несколько раз. Даже если бы я поместил эти два случая в два файла и запустил их соответственно, результаты всегда были похожи: 

ROW Major: 9274244
COLUMN Major: 5856220

Чтобы убедиться, что основной ряд строк имеет пространственную локальность, я проверил адреса междудва последовательных доступа к памяти являются непрерывными. И основной путь столбца - нет.

Кроме того, я также проверил количество пропусков кэша этих двух версий. И на самом деле он показывает меньшую частоту пропадания кэша, когда я использовал метод строки-майора. Но на этот раз мера часов в обходе строки становится меньше.

Вот результат valgrind:

Версия строки: 

ROW Major: 124149507
==10786== 
==10786== I   refs:      11,160,797
==10786== I1  misses:           955
==10786== LLi misses:           944
==10786== I1  miss rate:       0.01%
==10786== LLi miss rate:       0.01%
==10786== 
==10786== D   refs:       6,054,374  (6,041,857 rd   + 12,517 wr)
==10786== D1  misses:        65,590  (   64,992 rd   +    598 wr)
==10786== LLd misses:        65,113  (   64,554 rd   +    559 wr)
==10786== D1  miss rate:        1.1% (      1.1%     +    4.8%  )
==10786== LLd miss rate:        1.1% (      1.1%     +    4.5%  )
==10786== 
==10786== LL refs:           66,545  (   65,947 rd   +    598 wr)
==10786== LL misses:         66,057  (   65,498 rd   +    559 wr)
==10786== LL miss rate:         0.4% (      0.4%     +    4.5%  )

Основная версия столбца: 

COLUMN Major: 131878026
==10793== 
==10793== I   refs:      11,160,943
==10793== I1  misses:           952
==10793== LLi misses:           943
==10793== I1  miss rate:       0.01%
==10793== LLi miss rate:       0.01%
==10793== 
==10793== D   refs:       6,054,434  (6,041,899 rd   + 12,535 wr)
==10793== D1  misses:     1,003,086  (1,002,488 rd   +    598 wr)
==10793== LLd misses:        65,104  (   64,545 rd   +    559 wr)
==10793== D1  miss rate:       16.6% (     16.6%     +    4.8%  )
==10793== LLd miss rate:        1.1% (      1.1%     +    4.5%  )
==10793== 
==10793== LL refs:        1,004,038  (1,003,440 rd   +    598 wr)
==10793== LL misses:         66,047  (   65,488 rd   +    559 wr)
==10793== LL miss rate:         0.4% (      0.4%     +    4.5%  )

Как показано в valgrind, версия основной строки на самом деле имеет более низкий уровень промахов. Это смутило меня, и теперь мне интересно, сделал ли я что-то не так с этим кодом или методом измерения.

...