LINUX.ORG.RU

Вопрос о влиянии кешей ЦП на доступ к памяти.


0

1

Прошу прощения за плохую формулировку - ночь уже.

C++, линукс, винда, разное железо.

Есть два вычислительных алгоритма, обращающихся к константам в ОЗУ, общим объёмом примерно 150 метров. Алгоритмы различаются схемой доступа к данным в ОЗУ и схемой их расположения там. Например один алгоритм одновременно читает данные из нескольких блоков по 320 байт из разных удалённых мест. Второй алгоритм - те же данные, но запакованные в один последовательный блок в 8КБ, т.к. везде меняются паттерны чтения памяти.

При этом на разном железе - однопроцессорном и многопроцессорном, одноядерном и многоядерном (древние пни, core i5, серверные матери с несколькими Xeon-ами с огромными кешами...) не находится лучшего алгоритма по производительности.

Наблюдается такая закономерность - чем древнее и однопроцессорнее машина, тем больше она любит последовательный доступ к памяти (настольные древние P4, Core i5..., core2duo). Чем сервернее и многопроцессорнее девайс (Xeon-сервера), тем хуже работает алгоритм с «очень последовательным» доступом.

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

Спасибо.

http://rus-linux.net/lib.php?name=/MyLDP/hard/memory/memory.html

Там много букв, тебе нужно про кеши и их влияние.

P.S. Дреппер, конечно, временами совсем невменяем, но технарь он мегаквалафицированный. Его статьи про память - обязательны к прочтению.

x_hash ()

т.к. номер линии кеша - это адрес с отброшенными младшими битами

Если под линией кэша понимается именно строка, то если бы это было так, то кэш бы фактически не работал. Вообще, если данные целиком влезают в кэш, то скорее всего при многократном обходе оно будет работать в идеальном случае примерно одинаково. Но у разрозненных шанс того, что как раз таки всё-таки младшие биты совпадут, но вероятность падает при увеличении размера и ассоциативности кэша. http://upload.wikimedia.org/wikipedia/commons/4/41/Cache_nway.jpg http://upload.wikimedia.org/wikipedia/commons/0/07/Cache,missrate.png Так что скорее не «тем хуже работает алгоритм с «очень последовательным» доступом», а наоборот, алгоритм с произвольным доступом лучше.

Q3164 ()

Может быть, читая одновременно несколько разнесённых блоков я более вероятно использую разные линии кеша

Тут важна только [не]выровненность этих блоков на адрес, кратный большой степени двойки. Скажем, не очень хорошо, если все эти блоки начинаются с начала страницы виртуальной памяти (4K), еще хуже, если с границы кратной 32K.
Типичный пример, скажем --- доступ к соседним строкам матрицы:
double A[1024][1024]; - совсем плохое решение
double A[1024][1025]; - чуть лучше
double A[1024][1032]; - лучшее, что можно сделать без существенных изменений алгоритма

Это называется проблемой алиасинга и приводит к «ситуации, когда одна линия кеша постоянно переписывается целиком двумя разными блоками».

алгоритм одновременно читает данные из нескольких блоков по 320 байт из разных удалённых мест

Если таких мест не очень много <=8, то будет работать аппаратная предзагрузка (hw prefetch). Если больше --- надо частично читать последовательно.

запакованные в один последовательный блок в 8КБ

последовательное (точнее, поточное) чтение при прочих равных всегда быстрее, но меня несколько смущает тут «запакованные данные». Как бы не пришлось тратить время на их «распаковку».

VLev ()

Наблюдается такая закономерность - чем древнее и однопроцессорнее машина, тем больше она любит последовательный доступ к памяти (настольные древние P4, Core i5..., core2duo). Чем сервернее и многопроцессорнее девайс (Xeon-сервера), тем хуже работает алгоритм с «очень последовательным» доступом.

Да, примерно так и должно происходить.
«Идеальный» алгоритм написать можно, но надо больше знать о задаче.

VLev ()
Ответ на: комментарий от kiverattes

«просто конкатенация», если это дополнительная операция --- бессмысленна.
По возможности --- надо хранить данные так, как они используются.

VLev ()
Ответ на: комментарий от VLev

Они хранятся так, как используются, причём читаются в том же порядке, в котором используются. Я имел ввиду, что блок 8кб - по структуре выглядит как много 320байтовых блоков друг за другом.

В разных вариантах «8kb» - алгоритма данные из этого блока читаются по-разному - например в одном они читаются ровно в том порядке, в котором используются, в другом варианте идёт чтение разных блоков по 320 байт, находящихся в пределах этих 8KB. Оба этих «8kb» - варианта дают производительность немного хуже, чем чтение 320-блоков из гораздо более удалённых мест, чем «окрестность 8 кб».

Да, я тут ничего не пишу про выравнивание - можно сказать так, что каждый 320-блок выровнен по границе 16 байт.

kiverattes ★☆ ()
Ответ на: комментарий от kiverattes

Я имел ввиду, что блок 8кб - по структуре выглядит как много 320байтовых блоков друг за другом.

ага, понятно. Тогда 8K-алгоритм, при прочих равных --- лучше для кэширования, точнее, просто идеален.

Оба этих «8kb» - варианта дают производительность немного хуже, чем чтение 320-блоков из гораздо более удалённых мест, чем «окрестность 8 кб».

это скорее всего эффект, связанный не с кэшированием, а с конфигурацией каналов памяти и/или памяти NUMA-нод. Для ускорения доступа надо ставить interleave-режимы, хотя для NUMA interleave идёт по 4kb страницам, так что ускорение будет не более чем вдвое (реально --- меньше).

anonymous ()
Ответ на: комментарий от anonymous

Ну вот получается, что «при прочих равных» Xeon-у меньше нравится моя реализация последовательного чтения, чем Core i5-у (-;

Интересно, а можно ли, имея 4 NUMA-блока каким-то образом гарантировать, что привязанный к данному процессору или ядру ПОТОК будет использовать только тот банк ОЗУ, который соответствует данному ЦП? Чтобы не гонять чужие данные через меж-процессорные связи.

kiverattes ★☆ ()
Ответ на: комментарий от kiverattes

можно ли, имея 4 NUMA-блока каким-то образом гарантировать, что привязанный к данному процессору или ядру ПОТОК будет использовать только тот банк ОЗУ, который соответствует данному ЦП?

да, конечно.
libnuma содержит все необходимое для этого.
причём это можно делать как в исходном коде, так и на стадии исполнения.

VLev ()
Ответ на: комментарий от kiverattes

Xeon E7 4830 2.13 Ghz

угу. там до 16 каналов памяти на 4 numa ноды.
Можно чуть ли не каждый 320байт блок из своего канала тащить.
но это будет очень специфичная оптимизация...

VLev ()
Ответ на: комментарий от VLev

Немного не по теме: а на что прежде всего рассчитаны такие системы (по 4 numa блока), на какой «паттерн» использования ресурсов?

kiverattes ★☆ ()
Ответ на: комментарий от kiverattes

в такую систему можно поставить до 2ТБ оперативной памяти.
И вся эта память будет:
1. в одном адресном пространстве
2. доступна с относительно низкой латентностью (<~100нсек)

То, что это numa система, ну дык SMP сейчас не делают, и впредь вряд ли будут. Связанная с этим особенность:
3. высокая пропускная способность достигается только при обмене процессора данными со «своей» памятью.

Соответственно, наиболее эффективный «паттерн»: привязка групп потоков, обрабатывающих некое подмножество данных к той numa ноде, в памяти которой эти данные в основном хранятся.
libnuma IMHO удобный инструмент для этого.

VLev ()
12 июня 2013 г.
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.