Логическая организация кэш-памяти процессора

[APri]

Очень интересно. А есть информация, какие варианты отображения у конкретных современных процессоров?

[T0R]

В линуксе это можно посмотреть тут
/sys/devices/system/cpu/cpuX/cache/indexY/Z
где Х — интересующее ядро
Y интересующий кеш (L1 instruction, L1 data, L2, L3)
Z — что конкретно интересует
У меня под рукой, например, xeon X5650, посмотрим как устроен L1 data кеш
cat /sys/devices/system/cpu/cpu0/cache/index0/size
32K — его размер
cat /sys/devices/system/cpu/cpu0/cache/index0/ways_of_associativity
8 — ассоциативность сета
cat /sys/devices/system/cpu/cpu0/cache/index0/number_of_sets
64 — кол-во этих сетов
cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64 — размер кеш линии

[gnomeby]

Топик интересный с точки зрения теории. А практически как можно использовать эту информацию?

[SiGMan]

С точки зрения оптимизации — cache obvious / conscious алгоритмы. Борьба с false sharing.

[kirugan]

Можете расшифровать?

[SiGMan]

Cache obvious — алгоритмы, принимающие во внимание абстрактный кеш (приблизительно размер линеек, выравнивание)
Cache conscious — плюс нюансы работы конкретного железа
False sharing — несколько хардворных нитей состязаются за данные в одной линейке, в результате все идут прямиком в рамять

Как-то так.

[DustCn]

Выравнивать данные на границу кэш линии, например.
Статические данные;
Структуры;
Динамические данные.
Для разных типов у вас будет разные приемы для выравнивания.
К тому же стоит иметь виду — если у вас массив структур, и вы работаете только с одним элементом структуры в цикле, то процессор всегда будет загружать кеш линию целиком — и ваша ПСП просядет соответственно. Поэтому массивы структур переделывают в структуры массивов.

[alexfetisov]

Буквально сегодня утром смотрел лекцию на coursera об этом. Курс супер, так что в продолжение статьи — рекомендую!

[jcmvbkbc]

Вы забыли упомянуть cache aliasing и связанный с ним cache coloring — бич систем с MMU и кешем большого размера с малым количеством веев.

[FeRViD]

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

В качестве примера я написал тестовую программу. Ключевой в этой программе является функция: void xchg (uint8_t slow_factor, uint32_t step). slow_factor — количество сегментов памяти, step — разнос адресов между обрабатываемыми байтами. Увеличивая slow_factor — мы смоделируем ситуацию, когда для обработки одного байта будет считываться новая кэш-линия целиком.

Результаты:
root@proliant:~/cahe# gcc cache.c -O3 -o cache

root@proliant:~/cahe# ./cache
xchg() complited in 3 sec, k = 1400000000.
xchg() complited in 3 sec, k = 1400000000.
xchg() complited in 14 sec, k = 1400000000.
xchg() complited in 13 sec, k = 1400000000.

Отсюда видно что при использовании функции xchg() со slow_factor большим, чем 1, производительность сильно проседает, хотя количество итераций постоянно и не зависит от slow_factor!

А все дело в том, что xchg() со slow_factor большим, чем 1, сильно нагружает системную шину, т.к. через каждые 7 итераций вложенного цикла происходит считывание новой кэш-линии, т.к. после первых 7 итераций сэт кэша забивается.

#include <stddef.h>
#include <inttypes.h>
#include <sys/types.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#define WAY_N 8U				// number of ways
#define LINE_SIZE 64U				// cache line size
#define LINE_N 64U				// number of cache line

#define SPARSE WAY_N*LINE_SIZE*LINE_N
#define DENSE  LINE_SIZE*LINE_N

#define AREA 29U*WAY_N*LINE_SIZE*LINE_N		// allocated memory size

static uint8_t *p, *el, tmp;


void xchg (uint32_t slow_factor, uint32_t step) {
	uint32_t i, j, k;
	struct timeval start, end, diff;

	gettimeofday(&start, NULL);

	for (i = 0U, k = 0U, el = p; i < 200000000U/slow_factor; ++i) {
		for (j = 0U; j < 7U*slow_factor; ++j, el += step, ++k) {
			tmp = *el;
			*el = *(el + step);
			*(el + step) = tmp;
		}
		el = p;
	}

	gettimeofday(&end, NULL);

	diff.tv_sec  = end.tv_sec - start.tv_sec;

	printf (" xchg() complited in %ld sec, k = %u.\n", diff.tv_sec, k);
}


int main(int argc, char const **argv) {
	uint32_t i;
	
	p = el = calloc (1, AREA);

	for (i = 0U; i < AREA; ++i) {
		*el++ = (uint8_t) rand();
	}

	xchg (1U, SPARSE);
	xchg (1U, DENSE);
	xchg (4U, SPARSE);
	xchg (4U, DENSE);

	return 0;
}