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

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

Определение параметров кэш-памяти: степень ассоциативности кэш-памяти

Цель: научиться определять степень ассоциативности кэш-памяти.

Большинство современных микропроцессоров имеют множественно-ассоциативную (наборно-ассоциативную) организацию кэш-памяти. При множественно-ассоциативной организации кэш-память разделена на несколько банков. Каждый блок данных из оперативной памяти может быть помещен в одну из определенного множества (набора) строк кэш-памяти - по одному на банк. Число строк в множестве определяется числом банков. Схема кэш-памяти данных первого уровня на Pentium III (16 Кб) представлена на рисунке:

		Банки
		0	1	2	3
Множества (наборы)	0	32 B	32 B	32 B	32 B	- 32B * 4 = 128 B
	1	32 B	32 B	32 B	32 B	- 128 B
	2	32 B	32 B	32 B	32 B	- 128 B
	:	:	:	:	:
	126	32 B	32 B	32 B	32 B	- 128 B
	127	32 B	32 B	32 B	32 B	- 128 B
		32B * 128 = = 4 KB	4 KB	4 KB	4 KB	4 KB * 4 = = 128 B * 128 = = 16384 B = 16 KB

Номер множества, в которое будет помещен элемент данных из памяти, определяется адресом этого элемента. Например:

Адрес:	Номер множества	Смещение в строке
	7 бит	5 бит

В какой конкретный элемент множества будут записаны новые данные, определяется алгоритмом замещения (циклический, случайный, LRU, псевдо-LRU, :).

Элементы данных, имеющих одинаковые номера множеств, т.е. отстоящие на определенное расстояние в памяти (в примере: на 2¹²B = 4096 B = 4 KB), помещаются в одно и то же множество строк, вытесняя друг друга. Число элементов в каждом множестве (равное числу банков кэш-памяти) называется степенью ассоциативности кэш-памяти. Например, кэш данных L1 в Pentium III имеет объем 16 KB, степень ассоциативности 4 (4-way set-associative), размер строки 32B:

16KB = 4-way * 4 KB = 4-way * 128 множеств * 32B

Данные, расположенные в памяти с шагом на расстоянии 4KB приходятся на одно множество. На все эти данные приходится всего 4 кэш-строки, т.е. 4 * 64B = 256 B. Если выполнять обход данных с шагом 4 KB, то из всех 16 KB кэша L1 будет использоваться всего 256 B, которые будут постоянно перезаписываться (эффект <буксования> кэша). Производительность при этом будет такая же, как при отсутствии кэш-памяти.

Если вычислительная система имеет несколько уровней кэш-памяти, то у каждого уровня может быть своя степень ассоциативности. Определить степени ассоциативности кэш-памяти можно следующим способом. Выполняется обход N блоков данных суммарным объемом BlockSize, отстоящих друг от друга на величину Offset:

Параметры обхода:

BlockSize - размер обходимого блока данных,

Offset - расстояние между началами соседних блоков.

N - число фрагментов (на картинке N = 4).

Обход элементов следует производить в таком порядке:

BlockSize должен быть не больше объема исследуемого уровня кэш-памяти. Offset должно быть кратно величине <размер кэша> / <ассоциативность>, т.е. кратно размеру банка ассоциативности. Как правило, это степени двоек, так что можно взять заведомо кратное такому значению расстояние (например, 1MB). Изменяя число частей N, мы увидим, как меняется время обхода. Когда N превысит число банков, время обхода сильно возрастет.

Задание

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

BlockSize = размер кэша данных 1 уровня,

Offset = 1 MB.

Число фрагментов N = 1:20.

По полученному графику определить степень ассоциативности кэш-памяти.

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

Видно, что при увеличении числа фрагментов с 4 до 5 произошло сильное замедление. Значит, ассоциативность равна 4, что соответствует действительной ассоциативности кэша данных 1 уровня на PentiumIII.

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

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

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

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

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

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

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

· Результаты

- график зависимости среднего времени чтения одного элемента от числа фрагментов,

· Вывод

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

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

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