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

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

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

Цель:

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

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

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

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

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

Задание

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

1) Прямой:

2) Обратный:

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

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

Число обходов массива для тестирования: 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