Рубрики

ВОРОТА | GATE-CS-2006 | Вопрос 81

ЦП имеет кэш с прямым отображением 32 КБ и размером блока 128 байт. Предположим, что A — это двумерный массив размером 512 × 512 с элементами, каждый из которых занимает 8 байтов. Рассмотрим следующие два сегмента кода C, P1 и P2.
P1:

   

for (i=0; i<512; i++) {

   for (j=0; j<512; j++) {

      x += A[i][j];

   }

}

P2:

   

for (i=0; i<512; i++) {

   for (j=0; j<512; j++) {

      x += A[j][i];

   }

}

P1 и P2 выполняются независимо с одинаковым начальным состоянием, а именно, массив A не находится в кэше, а i, j, x находятся в регистрах. Пусть число пропущенных кеш-памяти для P1 равно M1, а для P2 — M2.

Значение отношения М1 / М2 составляет:
(А) 0
(Б) 1/16
(С) 1/8
(D) 16

Ответ: (Б)
Объяснение: [P2] запускает циклы таким образом, что обращается к элементам A в главном порядке строк, а [P2] обращается к элементам в главном порядке столбцов.
Нет блоков кэша = CacheSize / BlockSize = 32 КБ / 128 байт = 256
Число элементов массива в каждом блоке = BlockSize / ElementSize = 128 байт / 8 байт = 16

Всего промахов для [P1] = ArraySize * (количество элементов массива в каждом блоке) / (количество блоков кеша) = 512 * 512 * 16/256 = 16384

Всего пропусков для [P2] = Общее количество элементов в массиве (для каждого элемента будет пропущено) = 512 * 512 = 262144.

Рацион м1 / м2 = 16384/262144 = 1/16.

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2006 | Вопрос 81

0.00 (0%) 0 votes