Рубрики

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

GATE

ЦП имеет кэш с прямым отображением 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:
(А) 0
(Б) 2048
(С) 16384
(D) 262144

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

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

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

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

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

0.00 (0%) 0 votes