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