Организация ЭВМ и систем

 

Лабораторная работа N5

Определение параметров кэш-памяти: объем кэш-памяти

 

Цель:

  1. Сравнить скорости различных способов обхода данных в памяти.
  2. Определить влияние кэш-памяти на скорость доступа к данным.

 

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

Допустим, некоторая программа производит многократную обработку элементов массива. Если построить график зависимости времени обработки массива от размера массива, то он должен иметь нелинейный характер. При превышении размера кэш-памяти время обращения к элементам массива несколько возрастет.

 

Данные из оперативной памяти в кэш-память считываются целыми строками. Размер кэш-строки в большинстве распространенных процессоров составляет 16, 32, 64, 128 байт. При последовательном обходе попытка чтения первого элемента кэш-строки вызывает копирование всей строки из медленной оперативной памяти в кэш. Чтение нескольких последующих элементов выполняется намного быстрее, т.к. они уже находятся в быстрой кэш-памяти.

В большинстве современных микропроцессорах реализована аппаратная предвыборка данных. Она состоит в том, что при последовательном обходе очередные данные считываются из оперативной памяти еще до того, как к ним произошло обращение. За счет этого скорость последовательного обхода данных еще возрастает.

 

Задание

  1. Написать программу, многократно выполняющую чтение элементов массива заданного размера. Элементы массива представляют собой связный список, в котором значение очередного элемента представляет собой номер следующего. Способы обхода массива:

1) Прямой:

2) Обратный:

3) Случайный:

           

  1. Построить графики зависимости среднего времени обращения к элементу массива от размера обрабатываемого массива для трех видов обхода. На графиках должно быть видно влияние кэш-памяти (1 и 2 уровня).
  2. По результатам измерений сделать вывод о скорости различных способов обхода массива, а также о размерах различных уровней кэш-памяти (насколько полученные результаты соответствуют действительности).

 

Число обходов массива для тестирования: 10. Перед замером времени выполнить одиночный обход массива для "разогрева" кэш-памяти. Параметры изменения размеров массива:

Pentium III (кэш L1 - 16KB, кэш L2 - 256 KB):      до 512 KB с шагом 512 B,

Пример графиков, полученных на процессоре Pentium III:

Видна разница в скорости последовательного и непоследовательного обходов массива. На соответствующих местах графиков видно возрастание времени обращения к элементам.

 

Указания по выполнению

  1. Компилируйте программу с ключом оптимизации -O1, чтобы исключить лишние обращения к памяти (чтобы переменные расположились на регистрах).
  2. Для замера времени с большей точностью и меньшими накладными расходами используйте функцию rdtsc (см. Программы à mark3.c).

 

Примечания

  1. Для удобства переноса данных в Excel лучше выводить значения в две колонки: размер массива и время, а при запуске перенаправить вывод в txt-файл. Текстовый файл (*.txt) можно открыть в Excel-е (а не набирать все это вручную).
  2. Результирующий график может оказаться сильно "замусоренным" высокими пиками. Такое бывает, если на машине работают посторонние "тяжелые" программы. Здесь возможны только два варианта:

-     запустить программу в более "спокойное" время, когда будет работать меньше пользователей,

-     запустить программу на более "спокойной" машине, например, на домашнем компьютере.

 

В отчет включить:

-        Титульный лист (-ИО, группа),

-        Подробная информация о запуске программы:

-     на каком процессоре программа запускалась (название, частота, параметры кэш-памяти),

-     используемый компилятор и ключ оптимизации,

-        Результаты

-     графики зависимости среднего времени чтения одного элемента от размера массива для трех способов обхода (все на одной координатной плоскости),

-        Вывод

Программу высылать вместе с отчетом!

 

Параметры кэш-памяти некоторых процессоров:

Pentium III (Coppermine)

Кэш-память

Объем

Ассоциативность

Размер строки

кэш данных L1

16 KB

4

32 B

общий кэш L2

256 KB

8

32 B

Pentium 4 (Willamette, Northwood)

Кэш-память

Объем

Ассоциативность

Размер строки

кэш данных L1

8 KB

4

64 B

общий кэш L2

256 KB, 512KB

8

64 B

Athlon64

Кэш-память

Объем

Ассоциативность

Размер строки

кэш данных L1

64 KB

2

64 B

общий кэш L2

512KB

16

64 B

Opteron

Кэш-память

Объем

Ассоциативность

Размер строки

кэш данных L1

64 KB

2

64 B

общий кэш L2

1024 KB

16

64 B

Alpha 21264

Кэш-память

Объем

Ассоциативность

Размер строки

кэш данных L1

64 KB

2

64 B