Простой пример разбиения цикла для умножения матриц
Я пытаюсь понять, что на самом деле происходит (шаг за шагом), когда я использую циклическое разбиение или блокировку для умножения двух матриц. Например, я понимаю, что делает код на http://en.wikipedia.org/wiki/Loop_tiling. Однако я не могу представить, что происходит внутри кеша. Допустим, я хочу умножить две матрицы 4х4. AxB = C.
Теперь я хочу создать 4 подматрицы (2x2) для каждого A и B. поэтому A = [A1 A2; A3 A4] и B = [B1 B2; B3 B4]. Все элементы в памяти для C инициализируются нулями. например, используя calloc.
1) Предположим, что матрицы хранятся в памяти в главном порядке строк: row1, row2, row3, row4...
2) давайте предположим, что у меня есть две cachline с 4 матричными элементами каждый. Таким образом, при выполнении умножения наивной матрицы для первого элемента в c C[0,0] я получу доступ к памяти для A[0,0] и скопирую всю строку матрицы в строку кэша. Тогда у меня есть второй доступ к памяти для B[0,0]. Тогда C[0,0] = A[0,0] * B[0,0] + C[0,0]. Следующим шагом будет C[0,0] = A[0,1] * B[1,0] + C[0,0]. Поскольку A [0,1] находится в первой строке кэша, у меня будет попадание в кэш. Тем не менее, B[1,0] не находится во второй строке кэша, и у меня будет доступ к памяти.
Поможет ли Loop tiling в этом примере? Может ли кто-нибудь объяснить (шаг за шагом), что происходит внутри кеша и почему доступ к памяти уменьшается? Если этот пример не подходит, может ли кто-нибудь придумать, где видны преимущества блокировки?
Заранее спасибо.