В высокопроизводительных вычислениях часто говорят, что стоимость промахов кэша — самое большое снижение производительности для алгоритма. На протяжении многих лет увеличение скорости наших процессоров значительно опережало прирост латентности основной памяти. Пропускная способность основной памяти значительно возросла благодаря более широким и многоканальным шинам, однако задержка существенно не уменьшилась. Чтобы скрыть эту задержку, наши процессоры используют все более сложные подсистемы кеша, которые имеют много уровней.
В статье 1994 года «Удариться о стену памяти: последствия очевидного» описывается проблема и далее утверждается, что кэши в конечном итоге не помогают из-за принудительных промахов кэша. Я хочу показать, что при использовании шаблонов доступа, которые учитывают иерархию кэша, этот вывод не является неизбежным.
Давайте начнем рассматривать проблему с нескольких примеров. Наше оборудование пытается скрыть задержку основной памяти с помощью ряда методов. В основном три основных ставки принимаются на модели доступа к памяти:
- Temporal: Память, к которой недавно обращались, вероятно, скоро потребуется снова.
- Пространственный: скорее всего потребуется соседняя память.
- Шаг за шагом: доступ к памяти, вероятно, будет следовать предсказуемой схеме.
Чтобы проиллюстрировать эти три ставки в действии, давайте напишем некоторый код и измерим результаты.
- Прогулка по памяти линейным образом, будучи полностью предсказуемой.
- Псевдо случайным образом обходит память в пределах ограниченной области и затем движется дальше. Эта ограниченная область — это то, что обычно называют страницей памяти операционной системы.
- Псевдо случайным образом обходит большую область кучи.
Код
Следующий код должен быть запущен с опцией -Xmx4g JVM.
|
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
|
public class TestMemoryAccessPatterns{ private static final int LONG_SIZE = 8; private static final int PAGE_SIZE = 2 * 1024 * 1024; private static final int ONE_GIG = 1024 * 1024 * 1024; private static final long TWO_GIG = 2L * ONE_GIG; private static final int ARRAY_SIZE = (int)(TWO_GIG / LONG_SIZE); private static final int WORDS_PER_PAGE = PAGE_SIZE / LONG_SIZE; private static final int ARRAY_MASK = ARRAY_SIZE - 1; private static final int PAGE_MASK = WORDS_PER_PAGE - 1; private static final int PRIME_INC = 514229; private static final long[] memory = new long[ARRAY_SIZE]; static { for (int i = 0; i < ARRAY_SIZE; i++) { memory[i] = 777; } } public enum StrideType { LINEAR_WALK { public int next(final int pageOffset, final int wordOffset, final int pos) { return (pos + 1) & ARRAY_MASK; } }, RANDOM_PAGE_WALK { public int next(final int pageOffset, final int wordOffset, final int pos) { return pageOffset + ((pos + PRIME_INC) & PAGE_MASK); } }, RANDOM_HEAP_WALK { public int next(final int pageOffset, final int wordOffset, final int pos) { return (pos + PRIME_INC) & ARRAY_MASK; } }; public abstract int next(int pageOffset, int wordOffset, int pos); } public static void main(final String[] args) { final StrideType strideType; switch (Integer.parseInt(args[0])) { case 1: strideType = StrideType.LINEAR_WALK; break; case 2: strideType = StrideType.RANDOM_PAGE_WALK; break; case 3: strideType = StrideType.RANDOM_HEAP_WALK; break; default: throw new IllegalArgumentException("Unknown StrideType"); } for (int i = 0; i < 5; i++) { perfTest(i, strideType); } } private static void perfTest(final int runNumber, final StrideType strideType) { final long start = System.nanoTime(); int pos = -1; long result = 0; for (int pageOffset = 0; pageOffset < ARRAY_SIZE; pageOffset += WORDS_PER_PAGE) { for (int wordOffset = pageOffset, limit = pageOffset + WORDS_PER_PAGE; wordOffset < limit; wordOffset++) { pos = strideType.next(pageOffset, wordOffset, pos); result += memory[pos]; } } final long duration = System.nanoTime() - start; final double nsOp = duration / (double)ARRAY_SIZE; if (208574349312L != result) { throw new IllegalStateException(); } System.out.format("%d - %.2fns %s\n", Integer.valueOf(runNumber), Double.valueOf(nsOp), strideType); }} |
Полученные результаты
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
Intel U4100 @ 1.3GHz, 4GB RAM DDR2 800MHz, Windows 7 64-bit, Java 1.7.0_05===========================================0 - 2.38ns LINEAR_WALK1 - 2.41ns LINEAR_WALK2 - 2.35ns LINEAR_WALK3 - 2.36ns LINEAR_WALK4 - 2.39ns LINEAR_WALK0 - 12.45ns RANDOM_PAGE_WALK1 - 12.27ns RANDOM_PAGE_WALK2 - 12.17ns RANDOM_PAGE_WALK3 - 12.22ns RANDOM_PAGE_WALK4 - 12.18ns RANDOM_PAGE_WALK0 - 152.86ns RANDOM_HEAP_WALK1 - 151.80ns RANDOM_HEAP_WALK2 - 151.72ns RANDOM_HEAP_WALK3 - 151.91ns RANDOM_HEAP_WALK4 - 151.36ns RANDOM_HEAP_WALKIntel i7-860 @ 2.8GHz, 8GB RAM DDR3 1333MHz, Windows 7 64-bit, Java 1.7.0_05=============================================0 - 1.06ns LINEAR_WALK1 - 1.05ns LINEAR_WALK2 - 0.98ns LINEAR_WALK3 - 1.00ns LINEAR_WALK4 - 1.00ns LINEAR_WALK0 - 3.80ns RANDOM_PAGE_WALK1 - 3.85ns RANDOM_PAGE_WALK2 - 3.79ns RANDOM_PAGE_WALK3 - 3.65ns RANDOM_PAGE_WALK4 - 3.64ns RANDOM_PAGE_WALK0 - 30.04ns RANDOM_HEAP_WALK1 - 29.05ns RANDOM_HEAP_WALK2 - 29.14ns RANDOM_HEAP_WALK3 - 28.88ns RANDOM_HEAP_WALK4 - 29.57ns RANDOM_HEAP_WALKIntel i7-2760QM @ 2.40GHz, 8GB RAM DDR3 1600MHz, Linux 3.4.6 kernel 64-bit, Java 1.7.0_05=================================================0 - 0.91ns LINEAR_WALK1 - 0.92ns LINEAR_WALK2 - 0.88ns LINEAR_WALK3 - 0.89ns LINEAR_WALK4 - 0.89ns LINEAR_WALK0 - 3.29ns RANDOM_PAGE_WALK1 - 3.35ns RANDOM_PAGE_WALK2 - 3.33ns RANDOM_PAGE_WALK3 - 3.31ns RANDOM_PAGE_WALK4 - 3.30ns RANDOM_PAGE_WALK0 - 9.58ns RANDOM_HEAP_WALK1 - 9.20ns RANDOM_HEAP_WALK2 - 9.44ns RANDOM_HEAP_WALK3 - 9.46ns RANDOM_HEAP_WALK4 - 9.47ns RANDOM_HEAP_WALK |
Анализ
Я запустил код на 3 разных архитектурах ЦП, иллюстрирующих шаги вперед для Intel. Из результатов видно, что каждое поколение становилось все лучше и лучше при скрытии задержки в основной памяти на основе 3 ставок, описанных выше, для относительно небольшой кучи. Это потому, что размер и сложность различных кешей продолжают улучшаться. Однако с увеличением объема памяти они становятся менее эффективными. Например, если массив удваивается до 4 ГБ, то средняя задержка увеличивается с ~ 30 нс до ~ 55 нс для i7-860, выполняющего случайное обход кучи.
Похоже, что для случая линейного блуждания задержка памяти не существует. Однако, когда мы обходим память все более случайным образом, задержка начинает становиться очень очевидной.
Случайная кучная прогулка дала интересный результат. Это наш наихудший сценарий, и, учитывая аппаратные характеристики этих систем, мы могли бы рассчитывать на 150 нс, 65 нс и 75 нс для вышеуказанных тестов соответственно, исходя из задержек контроллера памяти и модуля памяти. Для Nehalem (i7-860) я могу дополнительно разрушить подсистему кеша, используя массив 4 ГБ, что в среднем дает ~ 55 нс на одну итерацию. I7-2760QM имеет большие буферы загрузки, TLB-кеши, а Linux работает с прозрачными огромными страницами, которые работают, чтобы еще больше скрыть задержку. Играя с разными простыми числами для шага, результаты могут сильно отличаться в зависимости от типа процессора, например, попробуйте PRIME_INC = 39916801 для Nehalem. Я хотел бы проверить это на гораздо большей куче с Sandy Bridge.
Главное, что нужно сделать, — это чем более предсказуемым будет шаблон доступа к памяти, тем лучше подсистемы кеша будут скрывать задержку основной памяти. Давайте посмотрим на эти подсистемы кеша немного подробнее, чтобы попытаться понять наблюдаемые результаты.
Компоненты оборудования
У нас есть много уровней кеша и средства предварительной выборки, чтобы рассмотреть, как скрывается задержка. В этом разделе я постараюсь охватить основные компоненты, используемые для сокрытия задержки, которую установили наши друзья по аппаратному и системному программному обеспечению. Мы исследуем эти скрывающие задержку компоненты и используем утилиты Linux perf и Google Lightweight Performance Counters для извлечения счетчиков производительности из наших процессоров, которые сообщают, насколько эффективны эти компоненты при выполнении наших программ. Счетчики производительности зависят от процессора, а то, что я здесь использовал, относится к Sandy Bridge.
Кэши данных
Процессоры обычно имеют 2 или 3 слоя кеша данных. Каждый слой по мере нашего продвижения постепенно увеличивается с увеличением задержки. Последние процессоры Intel имеют 3 уровня (L1D, L2 и L3); с размерами 32 КБ, 256 КБ и 4-30 МБ; и ~ 1 нс, ~ 4 нс и ~ 15 нс задержки соответственно для процессора 3,0 ГГц.
Кэши данных — это аппаратные хеш-таблицы с фиксированным числом слотов для каждого хеш-значения. Эти слоты известны как «пути». В 8-стороннем ассоциативном кеше будет 8 слотов для хранения значений адресов, которые хэшируются в одном и том же месте кэша. В этих слотах кэши данных не хранят слова, они хранят строки кэша из нескольких слов. Для процессора Intel эти строки кэша обычно составляют 64 байта, то есть 8 слов на 64-битной машине. Это подтверждает пространственную ставку на то, что смежная память, вероятно, скоро потребуется, что обычно имеет место, если мы думаем о массивах или полях объекта.
Кэши данных обычно высвобождаются в виде LRU. Кэши работают с использованием алгоритма обратной записи, когда хранилища должны распространяться только в основную память, когда модифицированная строка кэша исключается. Это вызывает интересное явление, когда загрузка может вызвать обратную запись во внешние слои кэша и, в конечном итоге, в основную память.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
perf stat -e L1-dcache-loads,L1-dcache-load-misses java -Xmx4g TestMemoryAccessPatterns $ Performance counter stats for 'java -Xmx4g TestMemoryAccessPatterns 1': 1,496,626,053 L1-dcache-loads 274,255,164 L1-dcache-misses # 18.32% of all L1-dcache hits Performance counter stats for 'java -Xmx4g TestMemoryAccessPatterns 2': 1,537,057,965 L1-dcache-loads 1,570,105,933 L1-dcache-misses # 102.15% of all L1-dcache hits Performance counter stats for 'java -Xmx4g TestMemoryAccessPatterns 3': 4,321,888,497 L1-dcache-loads 1,780,223,433 L1-dcache-misses # 41.19% of all L1-dcache hits likwid-perfctr -C 2 -g L2CACHE java -Xmx4g TestMemoryAccessPatterns $java -Xmx4g TestMemoryAccessPatterns 1+-----------------------+-------------+| Event | core 2 |+-----------------------+-------------+| INSTR_RETIRED_ANY | 5.94918e+09 || CPU_CLK_UNHALTED_CORE | 5.15969e+09 || L2_TRANS_ALL_REQUESTS | 1.07252e+09 || L2_RQSTS_MISS | 3.25413e+08 |+-----------------------+-------------++-----------------+-----------+| Metric | core 2 |+-----------------+-----------+| Runtime [s] | 2.15481 || CPI | 0.867293 || L2 request rate | 0.18028 || L2 miss rate | 0.0546988 || L2 miss ratio | 0.303409 |+-----------------+-----------+java -Xmx4g TestMemoryAccessPatterns 2+-----------------------+-------------+| Event | core 2 |+-----------------------+-------------+| INSTR_RETIRED_ANY | 1.48772e+10 || CPU_CLK_UNHALTED_CORE | 1.64712e+10 || L2_TRANS_ALL_REQUESTS | 3.41061e+09 || L2_RQSTS_MISS | 1.5547e+09 |+-----------------------+-------------++-----------------+----------+| Metric | core 2 |+-----------------+----------+| Runtime [s] | 6.87876 || CPI | 1.10714 || L2 request rate | 0.22925 || L2 miss rate | 0.104502 || L2 miss ratio | 0.455843 |+-----------------+----------+java -Xmx4g TestMemoryAccessPatterns 3+-----------------------+-------------+| Event | core 2 |+-----------------------+-------------+| INSTR_RETIRED_ANY | 6.49533e+09 || CPU_CLK_UNHALTED_CORE | 4.18416e+10 || L2_TRANS_ALL_REQUESTS | 4.67488e+09 || L2_RQSTS_MISS | 1.43442e+09 |+-----------------------+-------------++-----------------+----------+| Metric | core 2 |+-----------------+----------+| Runtime [s] | 17.474 || CPI | 6.4418 || L2 request rate | 0.71973 || L2 miss rate | 0.220838 || L2 miss ratio | 0.306835 |+-----------------+----------+ |
Примечание. Частота пропадания кэша в сочетании L1D и L2 значительно возрастает, поскольку схема доступа становится более случайной.
Трансляционные Lookaside Buffers
Наши программы работают с адресами виртуальной памяти, которые необходимо преобразовать в адреса физической памяти. Системы виртуальной памяти делают это путем отображения страниц. Нам нужно знать смещение для данной страницы и ее размер для любой операции с памятью. Обычно размеры страниц составляют 4 КБ и постепенно увеличиваются до 2 МБ и более. Linux представил прозрачные огромные страницы в ядре 2.6.38, что дает нам 2 МБ страниц. Перевод страниц виртуальной памяти на физические страницы поддерживается таблицей страниц. Этот перевод может иметь несколько обращений к таблице страниц, что является огромным снижением производительности. Чтобы ускорить этот поиск, процессоры имеют небольшой аппаратный кеш на каждом уровне кеша, называемый кешем TLB. Промах в кеше TLB может быть очень дорогим, потому что таблица страниц может отсутствовать в соседнем кеше данных. При перемещении на большие страницы кэш TLB может охватывать больший диапазон адресов для того же числа записей.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
|
perf stat -e dTLB-loads,dTLB-load-misses java -Xmx4g TestMemoryAccessPatterns $ Performance counter stats for 'java -Xmx4g TestMemoryAccessPatterns 1': 1,496,128,634 dTLB-loads 310,901 dTLB-misses # 0.02% of all dTLB cache hits Performance counter stats for 'java -Xmx4g TestMemoryAccessPatterns 2': 1,551,585,263 dTLB-loads 340,230 dTLB-misses # 0.02% of all dTLB cache hits Performance counter stats for 'java -Xmx4g TestMemoryAccessPatterns 3': 4,031,344,537 dTLB-loads 1,345,807,418 dTLB-misses # 33.38% of all dTLB cache hits |
Примечание. Мы получаем значительные пропуски TLB только при случайном обходе всей кучи, когда используются огромные страницы.
Аппаратные пре-сборщики
Аппаратные средства попытаются предсказать следующий доступ к памяти, который будут сделаны нашими программами, и спекулятивно загрузят эту память в буферы заполнения. Это делается на самом простом уровне путем предварительной загрузки смежных строк кэша для пространственной ставки или путем распознавания регулярных шаблонов доступа на основе шага, обычно длиной шага менее 2 КБ. В тестах ниже мы измеряем количество нагрузок, попавших в буфер заполнения из аппаратной предварительной выборки.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
|
likwid-perfctr -C 2 -t intel -g LOAD_HIT_PRE_HW_PF:PMC0 java -Xmx4g TestMemoryAccessPatterns $java -Xmx4g TestMemoryAccessPatterns 1+--------------------+-------------+| Event | core 2 |+--------------------+-------------+| LOAD_HIT_PRE_HW_PF | 1.31613e+09 |+--------------------+-------------+java -Xmx4g TestMemoryAccessPatterns 2+--------------------+--------+| Event | core 2 |+--------------------+--------+| LOAD_HIT_PRE_HW_PF | 368930 |+--------------------+--------+java -Xmx4g TestMemoryAccessPatterns 3+--------------------+--------+| Event | core 2 |+--------------------+--------+| LOAD_HIT_PRE_HW_PF | 324373 |+--------------------+--------+ |
Примечание. У нас значительный процент успешных попыток загрузки при использовании средства предварительной выборки при линейном обходе.
Контроллеры памяти и рядные буферы
Помимо нашего последнего уровня кеша (LLC) находятся контроллеры памяти, которые управляют доступом к банкам SDRAM. Память организована в строки и столбцы. Чтобы получить доступ к адресу, сначала нужно выбрать адрес строки (RAS), а затем выбрать адрес столбца (CAS) в этой строке, чтобы получить слово. Строка обычно имеет размер страницы и загружается в буфер строк. Даже на этом этапе аппаратное обеспечение все еще помогает скрыть задержку. Очередь запросов на доступ к памяти поддерживается и переупорядочивается, так что несколько слов могут быть выбраны из одной строки, если это возможно.
Неравномерный доступ к памяти (NUMA)
Системы теперь имеют контроллеры памяти на сокете процессора. Этот переход к встроенным контроллерам памяти дал снижение задержки примерно на 50 нс по сравнению с существующей передней шиной (FSB) и внешними контроллерами памяти северного моста . Системы с несколькими сокетами используют межсоединения памяти, QPI от Intel, которые используются, когда один процессор хочет получить доступ к памяти, управляемой другим сокетом процессора. Наличие этих межсоединений приводит к неоднородному характеру доступа к памяти сервера. В 2-сокетной системе память может быть локальной или в 1 переходе. В 8-сокетной системе память может занимать до 3 переходов, каждый переход добавляет задержку 20 нс в каждом направлении.
Что это значит для алгоритмов?
Разница между попаданием в кэш L1D и полным отсутствием, приводящим к доступу к основной памяти, составляет 2 порядка; то есть <1 нс против 65-100 нс. Если алгоритмы случайным образом обойдут наше постоянно увеличивающееся адресное пространство, мы вряд ли получим выгоду от аппаратной поддержки, которая скрывает эту задержку.
Есть ли что-нибудь, что мы можем сделать с этим при разработке алгоритмов и структур данных? Да, мы можем многое сделать. Если мы выполняем большую часть работы над данными, находящимися в одном месте, и предсказуемо перемещаемся по памяти, то наши алгоритмы могут быть во много раз быстрее. Например, вместо того, чтобы использовать хэш-таблицы сегмента и корзины, как в JDK, мы можем использовать хеш- таблицы, используя открытую адресацию и линейное зондирование. Вместо того чтобы использовать связанные списки или деревья с отдельными элементами в каждом узле, мы можем хранить массив из множества элементов в каждом узле.
Исследования продвигаются на алгоритмических подходах, которые работают в гармонии с подсистемами кэша. Одна область, которую я нахожу увлекательной, это алгоритмы кеширования . Название немного вводит в заблуждение, но здесь есть несколько отличных понятий, как улучшить производительность программного обеспечения и лучше выполнять параллельно. Эта статья является отличной иллюстрацией преимуществ производительности, которые можно получить.
Вывод
Для достижения высокой производительности важно иметь симпатию к подсистемам кеша. В этой статье мы увидели, что может быть достигнуто путем доступа к памяти в шаблонах, которые работают с этими кэшами, а не против них. При разработке алгоритмов и структур данных теперь гораздо важнее учитывать потери в кеше, возможно, даже больше, чем подсчет шагов в алгоритме. Это не то, чему нас учили в теории алгоритмов при изучении информатики. В последнее десятилетие произошли некоторые фундаментальные изменения в технологии. Для меня два наиболее значительных — это рост числа многоядерных и теперь больших систем памяти с 64-битным адресным пространством.
Одно можно сказать наверняка: если мы хотим, чтобы программное обеспечение работало быстрее и масштабировалось лучше, нам нужно лучше использовать многие ядра наших процессоров и уделять внимание шаблонам доступа к памяти.
Ссылка: Шаблоны доступа к памяти важны от нашего партнера JCG Мартина Томпсона из блога Mechanical Sympathy .