Pull to refresh

Экспериментальное определение характеристик кэш-памяти: практикум

Computer hardware
Первая статья об экспериментальном определении характеристик кэш-памяти появилась на свет несколько необычным образом. Играясь с утилитами из lmbench, я получил те самые три графика, и задался вопросом, сколько же информации об исследуемой системе можно из них вытянуть. Определив некоторые характеристики кэша и TLB, я затем задал эти графики студентам как домашнее задание — предвкушая, что им удастся обнаружить что-то такое, что я проглядел. В целом, студенты меня разочаровали, и не заметили даже связь ассоциативности с наклоном ступенек на графике. В конце семестра я собираюсь рассказать им своё решение; а чтобы оно к тому времени не забылось, я написал на скорую руку ту статью.

Затем Yekver предложил мне идею простой программы для Windows, которая определяла бы характеристики кэша автоматически, не требуя ручного анализа графиков. (Тем более, что версии lmbench для Windows не существует.) Для замера времени будем использовать функцию __rdtsc, которая возвращает 64-битное количество тактов с момента последнего сброса процессора. Сначала определим тактовую частоту процессора, замерив на произвольной нагрузке время выполнения и количество потребовавшихся тактов. Затем для расчёта времени доступа к памяти будем делить количество потраченных тактов на тактовую частоту процессора.

Подобно прошлому эксперименту, мы будем брать данные различного объёма от 4КБ до 512МБ, и проходить по массиву миллионы раз с последующим усреднением результата. Чтобы минимизировать влияние дополнительных операций в цикле нагрузки, следуя примеру авторов lat_mem_rd, используем для тела нагрузки операцию p=(void**)*p;, которая компилируется в одну машинную команду, и развернём её 256 раз, чтобы возврат к началу цикла выполнялся относительно редко.

Во время эксперимента будем хранить историю из трёх последних полученных результатов, и обнаруживать в них скачки более, чем на 10% — это края ступенек. Сохраним все обнаруженные ступеньки для всех испробованных размеров шага, и после окончания замеров времени займёмся анализом полученных данных. Методика определения характеристик стека по положению ступенек на графике подробно описана в прошлой статье. Для более точного обнаружения ступенек можно было бы использовать среднеквадратичное отклонение вместо фиксированного порога.

Программа тестировалась на трёх компьютерах, с разной конфигурацией и размерами кэша. Как можно видеть, крупные массивы не поместились целиком в физическую память, и поэтому время доступа к ним не вполне предсказуемо: оно определяется задержкой на подкачку данных с диска. Поэтому, в отличие от прошлого эксперимента, на массивах крупнее 512МБ замер не проводился.
В данной таблице приведены результаты запуска программы на различных компьютерах.

Pentium4 630, 1GB RAM
Clock rate: 2993 MHz
L1 size: 16 KB, latency: 4.10 cycles (1.37 ns)
way size: min. 2 KB, max. 2 KB
TLB size: 64, latency: 18.37 cycles (6.14 ns)
way size: min. 1, max. 8
L2 size: 1920 KB, latency: 28.98 cycles (9.68 ns)
way size: min. 384 KB, max. 384 KB
Core2 T7200, 1GB RAM
Clock rate: 1995 MHz
L1 size: 32 KB, latency: 3.02 cycles (1.51 ns)
way size: min. 8 KB, max. 8 KB
L2 size: 1024 KB, latency: 14.87 cycles (7.45 ns)
way size: min. 256 KB, max. 256 KB
L3 size: 3840 KB, latency: 14.62 cycles (7.33 ns)
way size: min. 2816 KB, max. 2816 KB
Core2 Duo T5250, 1GB RAM
Clock rate: 1496 MHz
L1 size: 32 KB, latency: 3.04 cycles (2.03 ns)
way size: min. 8 KB, max. 8 KB
L2 size: 1280 KB, latency: 14.82 cycles (9.91 ns)
way size: min. 4 KB, max. 0 KB


Дополнительная задержка, вызываемая доступом к TLB на процессорах Core, оказалась настолько незначительной, что в одном из случаев программа сочла её пренебрежимо малой, и вовсе не заметила TLB; в другом случае колебания времени доступа оказались того же порядка величины, что и сама дополнительная задержка, и поэтому программа не заметила закономерностей времени доступа, характерных для TLB. Иными словами, остаётся простор для совершенствования заложенного в программу механизма анализа графиков времени доступа.

Вероятно, это первая свободная программа для Windows, автоматически определяющая характеристики кэша. Если вы будете запускать её самостоятельно, имейте в виду: она довольно чувствительна к помехам, вносимым в графики фоновой нагрузкой. Чтобы получить более достоверные результаты, закройте все остальные программы на время замера.

#include <math.h>
#include <stdio.h>
#include <intrin.h>
#include <windows.h>

// следующий размер массива: взято из lat_mem_rd
int step(int k) {
	if(k < 1024) k = k * 2;
    else if(k < 4*1024) k += 1024;
	else {
		int s;
		for (s = 32*1024; s <= k; s *= 2)	;
		k += s / 16;
	}
	return k;
}

#define TWICE(x) x x
#define MB (1024*1024)

int main()
{
	// ОПРЕДЕЛЕНИЕ ТАКТОВОЙ ЧАСТОТЫ
	LARGE_INTEGER perfcnt1, perfcnt2; __int64 tsc1, tsc2;
	QueryPerformanceCounter(&perfcnt1); tsc1=__rdtsc();
	// нагрузка (не обязательно нашим процессом)
	Sleep(500);
	// замер
	QueryPerformanceCounter(&perfcnt2); tsc2=__rdtsc();
	perfcnt2.QuadPart -= perfcnt1.QuadPart;
	QueryPerformanceFrequency(&perfcnt1);
	// результат
	const double MHz = (double)(tsc2-tsc1)*perfcnt1.QuadPart/perfcnt2.QuadPart/1e6;
	printf("Clock rate: %.0f MHz\n", MHz);

	// ЗАМЕР ВРЕМЕНИ ДОСТУПА К ПАМЯТИ
	// информация о горизонтальном сегменте графика
	typedef struct segment_t segment;
	struct segment_t {
		int size_l, size_r;  // размеры краёв, в байтах
		double level, total; // время доступа, в циклах
		int width;			 // ширина, в замеренных точках
		segment* next;
	};
	// график с постоянной величиной шага
	typedef struct {
		int step_size_bytes;
		segment data;
	} segments;

	// пробуем шесть величин шага
	segments allsegs[]={{128}, {256}, {512}, {1024}, {2048}, {4096}, {0}};
	for(segments *cursegs = allsegs;
			int step_size = cursegs->step_size_bytes/sizeof(void*);
			cursegs++) {

		printf("\rTesting stride: %d          \n", cursegs->step_size_bytes);

		int iters = 1<<28; // обращений к массиву на каждом проходе
		int state = 0;	   // начальное состояние - снаружи ступеньки
		segment* curseg = &(cursegs->data); // текущий сегмент

		// предыдущие два размера массива, и результаты на них
		int a_size_bytes, b_size_bytes;
		double a, b; 

		// на каждой итерации данного цикла выделяется всё большая память
		for(int arr_size_bytes = 1<<12; arr_size_bytes <= 1<<29;
										arr_size_bytes = step(arr_size_bytes)) {
			const int arr_size = arr_size_bytes / sizeof(void*);

			void **x = (void**)malloc(arr_size_bytes); // выделяем память

			// заполняем память указателями с шагом step_size
			int k;
			for(k = 0; k < arr_size; k += step_size) {
				x[k] = x + k + step_size;
			}
			x[k-step_size] = x;
			const int arr_iters = k / step_size; // число заполненных элементов массива

			// не меньше четырёх полных проходов по массиву
			if(iters < 4*arr_iters) iters = 4*arr_iters;

			// указатель для обращения к массиву в основном цикле
			void **p = x;

			// счётчик тактов до выполнения команд
			const __int64 ticks_start = __rdtsc();

			// основной цикл -- его время выполнения мы замеряем
			for(int j = 0; j < iters; j+=256) {
				TWICE(TWICE(TWICE(TWICE(TWICE(TWICE(TWICE(TWICE( p=(void**)*p; ))))))))
			}

			// счётчик тактов после выполнения команд
			const __int64 ticks_end = __rdtsc();

			// количество затраченных тактов процессора, в среднем на одно обращение
			// множим на !!p (единицу), чтобы оптимизатор не выкинул её как неиспользуемую
			const double cycles = (double)!!p * (ticks_end-ticks_start) / iters;

			// отображение результатов
			printf("\r%f MB - %.2f cycles    ", (double)arr_size_bytes/MB, cycles);

			free(x); // освобождаем память

			// скорректируем число итераций, чтобы каждый проход занимал меньше секунды
			while(cycles/MHz*iters > 1e6) iters >>= 1;

			// левый край ступеньки?
			if(!state && (curseg->width>2) && (fabs(a-curseg->level)<(a*.1)) &&
					(b>(curseg->level*1.1)) && (cycles>(curseg->level*1.1))) {
				curseg->size_r = a_size_bytes;
				curseg = curseg->next = (segment*)calloc(1, sizeof(segment));
				state = 1;
				b = 0; // правый край должен быть строго правее левого
			}
			// правый край ступеньки?
			if(state && (fabs(cycles-a)<(a*.1)) && (fabs(cycles-b)<(b*.1))) {
				curseg->size_l = a_size_bytes;
				state = 0;
			}
			// первые две точки учитываем всегда
			if(!state && ((curseg->width<=2) || (fabs(cycles-curseg->level)<cycles*.1))) {
				curseg->total += cycles;
				curseg->width++;
				curseg->level = curseg->total / curseg->width;
			}
			// приняли широкий всплеск за ступеньку?
			if(!state && (cycles<curseg->level*.9) && (fabs(cycles-a)<(a*.1)) && (fabs(cycles-b)<(b*.1))) {
				curseg->total = a + b + cycles;
				curseg->width = 3;
				curseg->level = curseg->total / curseg->width;
			}

			// сдвигаем историю
			a_size_bytes = b_size_bytes; b_size_bytes = arr_size_bytes;
			a = b; b = cycles;
		}
	}

	// АНАЛИЗ ПОЛУЧЕННЫХ ДАННЫХ
	int TLB = 0; // последний проанализированный уровень -- TLB?
	for(int cache_level = 1;;cache_level++) {

		// размер и время доступа к кэшу
		int cache_size = allsegs[0].data.size_r, step_count = 0;
		if(!cache_size) break; // самый высший уровень (основная память)

		double latency, total = 0;
		if(TLB) // время доступа к кэшу следующего уровня уже определено
			cache_level--;
		else
			latency = allsegs[0].data.level;

		int less=0, same=0, more=0; // для определения медианы "на ходу"

		// для всех испробованных размеров шага
		for(segments *cursegs = allsegs; cursegs->step_size_bytes; cursegs++) {
			segment* next = cursegs->data.next; // следующий уровень кэша
			if(!next) { // с текущим размером шага, натыкаемся на основную память
				printf("Missing results for L%d! Step size %d, array size %f MB\n",
						cache_level, cursegs->step_size_bytes, (double)cursegs->data.size_l/MB);
				cache_size = 0;
				break;
			}
			// если следующий уровень мало отличается, объединим
			while(fabs(cursegs->data.level-next->level)<cursegs->data.level*.2) {
				cursegs->data.size_r = next->size_r;
				cursegs->data.total += next->total;
				cursegs->data.width += next->width;
				cursegs->data.level = cursegs->data.total / cursegs->data.width;
				cursegs->data.next = next->next;
				free(next);
				next = cursegs->data.next;
				// реинициализация
				if(cursegs==allsegs) {
					cache_size = cursegs->data.size_r;
					if(!TLB) latency = cursegs->data.level;
				}
			}
			// если очередная ступенька совпала с расчётной
			if(cursegs->data.size_r == cache_size)
				same++;
			// если очередная ступенька чуть отличается от расчётной
			else if(cursegs->data.size_r == step(cache_size))
				more++;
			else if(step(cursegs->data.size_r) == cache_size)
				less++;
			// если ступенька намного левее расчётной: эффект TLB
			else if(cursegs->data.size_r < cache_size/2) {
				// измеренный до сих пор размер -- ненастоящий
				cache_size = cursegs->data.size_r;
				more = less = 0; same = 1;
				// добавим фиктивные ступеньки с тем же уровнем
				for(segments *prevsegs = allsegs; prevsegs<cursegs; prevsegs++) {
					segment* second = (segment*)malloc(sizeof(segment));
					*second = prevsegs->data;
					prevsegs->data.next = second;
					prevsegs->data.size_r = second->size_l = cache_size;
				}
			}
			// если отличающихся ступенек больше, чем расчётных
			if(less>same) {
				cache_size = cursegs->data.size_r;
				more = same; same = less; less = 0;
			} else if (more>same) {
				cache_size = cursegs->data.size_r;
				less = same; same = more; more = 0;
			}
			if(!TLB && fabs(latency-cursegs->data.level)<latency*.1) {
				total += cursegs->data.level;
				latency = total / ++step_count;
			}
		}
		if(!cache_size) break; // определение размера кэша не удалось

		// ассоциативность кэша и параметры TLB
		int min_way_size = 0, max_way_size = 0, next_step_at = 2*cache_size;
		// задержка, добавляемая временем доступа к TLB
		double additional = (allsegs[0].data.next->level - latency) / 2;
		if(additional<0) additional=0; // в пределах погрешности
		TLB = 1; // считаем за TLB, пока не убедимся в противном
		for(segments *cursegs = allsegs; cursegs->step_size_bytes; cursegs++) {
			segment* next = cursegs->data.next; // следующий уровень кэша
			// если все веи заполнены, левые границы ступенек совпадают
			if(cursegs->data.size_r <= cache_size) {
				if(max_way_size && (max_way_size != next->size_l - cache_size)) {
					printf("Inconsistent results for L%d! Step size %d, array size %f MB\n",
							cache_level, cursegs->step_size_bytes, (double)next->size_l/MB);
				}
				min_way_size = cursegs->step_size_bytes; // шаг не больше вея
				max_way_size = next->size_l - cache_size; // размер вея -- ширина ступеньки
				// если ступенька не вертикальная, значит известен точный размер вея
				if(next->size_l > step(cache_size)) min_way_size = max_way_size;
			// при недополнении веев, ступенька сдвинута вдвое вправо
			} else if(cursegs->data.size_r > step(cache_size)) {
				if(cursegs->data.size_r != next_step_at)
					printf("Inconsistent results for L%d! Step size %d, array size %f MB\n",
							cache_level, cursegs->step_size_bytes, (double)cursegs->data.size_r/MB);
				if (!max_way_size)
					max_way_size = cursegs->step_size_bytes / 2; // шаг как минимум в два вея
				next_step_at *= 2; // следующая ступенька должна быть ещё вдвое правее
			}

			// похоже на TLB, если дополнительная задержка удваивается при удвоении шага
			double new_additional = cursegs->data.next->level - latency;
			if((fabs(new_additional - additional*2) < new_additional*.1) ||	(additional<latency*.1))
				additional = new_additional;
			else // не похоже на TLB
				TLB = 0;

			// закончили с первым сегментом
			cursegs->data = *next;
			free(next);
		}
		if(TLB)
			printf("TLB size: %d, latency: %.2f cycles (%.2f ns)\n"
				   "    way size: min. %d, max. %d\n",
				cache_size/4096, additional/2, (additional/2)/MHz*1000,
				min_way_size/4096, max_way_size/4096);
		else
			printf("L%d size: %d KB, latency: %.2f cycles (%.2f ns)\n"
				   "   way size: min. %d KB, max. %d KB\n",
				cache_level, cache_size/1024, latency, latency/MHz*1000,
				min_way_size/1024, max_way_size/1024);
	}
	return 0;
}
Tags: кэшбенчмарктестированиеустройство памяти
Hubs: Computer hardware
Total votes 23: ↑22 and ↓1 +21
Comments 21
Comments Comments 21

Popular right now