В чём суть понятия cache conscious?

Question

[SHLAKBAUM]

В статьях связанных с алгоритмами встретил такое понятие как cache conscious, но к сожалению не могу понять, что оно означает и его перевод понимания не добавляет.

Вроде как суть связана с удобством алгоритма для кеширования, но хотелось бы более подробно и возможные варианты перевода понятия.

Answer 1

[Roman_Kh]

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

Таким образом cache conscious алгоритмы:
- обращаются к данные в легко предсказуемой манере (например, строго последовательно)
- хранят данные компактным образом (т.е. минимально необходимый набор данных оптимального типа с правильным выравниванием).

Обычно когда говорят о cache conscious алгоритмах имеют в виду кэш процессора (и даже все уровни процессорных кэшей, каждый из которых больше, но и медленнее предыдущего). Хотя это также относится и к распределенным вычислениям, когда алгоритм должен учитывать, что обращение к данным расположенным на другом компьютере может быть очень долгим и дорогим.

Answer 2

[SeptiM]

Есть два вещи: cache conscious и cache oblivious. Обе относятся к уточненной модели памяти.

В обычных алгоритмах у нас есть одна RAM память, к которой есть равноценный доступ. В уточненной -- между процессором и основной памятью есть кэш, доступ к которому существенно быстрее чем к основной памяти. Теоретическая модель кэша обычно выглядит так: это H строчек по W байт в каждой. Алгоритмы запрашивают чтение кусочка памяти в кэш, а потом оперируют с тем, что есть в кэше. Эффективность алгоритма определяется числом чтений основной памяти в кэш (+ стандартные характеристики)

Собственно алгоритмы делятся на те, которым важны параметры кэша W и H -- cache concious, и те, которым они не важны -- cache oblivious.

P.S. Вот на хабре подгоняют бинарный поиск с учетом кэша, а в update-е там же делают подсказку как сделать cache oblivious.