Не обращающие внимания на кэш алгоритмы и структуры данных - довольно новая вещь, представленная Frigo et al. в алгоритмах кеширования, 1999 . Тезис Прокопа того же года знакомит и с ранними идеями.
Бумага Frigo et al. представить некоторые экспериментальные результаты, показывающие потенциал теории и забывающих о кеше алгоритмов и структур данных. Многие не учитывающие кэш структуры данных основаны на статических деревьях поиска. Методы хранения и навигации по этим деревьям были разработаны совсем немного, возможно, наиболее заметно Bender et al. а также Brodal et al. Демейн дает хороший обзор .
Экспериментальная работа по исследованию поведения кэша на практике была сделана по крайней мере Ladner et al. в сравнение кэша Aware и Cache Oblivious Static деревьев поиска с помощью программы Instrumentation, 2002 . Ladner et al. тестировал поведение кеша алгоритмов, решающих проблему двоичного поиска, используя классический алгоритм, не обращающий внимания к кешу алгоритм и алгоритм с учетом кеша. Каждый алгоритм сравнивался как с неявными, так и с явными методами навигации. В дополнение к этому, в диссертации Rønn, 2003 был проанализирован тот же алгоритм с достаточно высокой детализацией, а также проведено еще более тщательное тестирование тех же алгоритмов, что и у Ladner et al.
Мой вопрос
Были ли какие-либо более новые исследования по сравнительному анализу поведения кэша забывающих о кеше алгоритмов на практике с тех пор? Меня особенно интересует производительность деревьев статического поиска, но я также был бы рад любым другим не обращающим внимания на кэш алгоритмам и структурам данных.
Ответы:
Вы уже достаточно хорошо изучили фоновые исследования забытых в кеше алгоритмов. С точки зрения сравнительного анализа и практических результатов, я считаю эту недавнюю статью Intel интересной для чтения:
Синергетический подход к пропускной способности вычислений на многоядерных десктопах на базе x86
источник