Erforschung der Bewertung der Leistung von Cache-Roblivität in der Praxis

Question

Cache-obliven Algorithmen und Datenstrukturen sind eine ziemlich neue Sache, die von Frigo et al. in Cache-obliven Algorithmen, 1999. Prokops These Aus demselben Jahr führt auch die frühen Ideen ein.

Das Papier von Frigo et al. Präsentieren Sie einige experimentelle Ergebnisse, die das Potenzial der Theorie und die Cache-obliven Algorithmen und Datenstrukturen zeigen. Viele Cache-obliven Datenstrukturen basieren auf statischen Suchbäumen. Methoden zur Aufbewahrung und Navigation dieser Bäume wurden ziemlich viel entwickelt, vielleicht vor allem von Bender et al. und auch von Brodal et al. Demaine gibt eine schöne Überblick.

Die experimentelle Arbeit zur Untersuchung des Cache -Verhaltens in der Praxis wurde zumindest von Ladner et al. in Ein Vergleich von Cache -Awes- und Cache -ahnungslosen statischen Suchbäumen unter Verwendung der Programminstrumentation, 2002. Ladner et al. Benchmarked das Cache-Verhalten von Algorithmen, die das Binär-Suchproblem lösen, unter Verwendung des klassischen Algorithmus, des Cache-obliven Algorithmus und des Cache-Award-Algorithmus. Jeder Algorithmus wurde sowohl implizite als auch mit expliziten Navigationsmethoden vergleichbar. Darüber hinaus die These von Thesis von Rønn, 2003 Analysierte die gleichen Algorithmen auf ziemlich hohe Details und führte auch noch gründlichere Tests der gleichen Algorithmen wie Ladner et al.

Meine Frage ist

Hat es neuere Forschungsergebnisse über gegeben? Benchmarking Das Cache-Verhalten von Cache-obliven Algorithmen in trainieren seit? Ich interessiere mich besonders für die Leistung der statischen Suchbäume, aber ich wäre auch mit allen anderen Cache-obliven Algorithmen und Datenstrukturen zufrieden.

Answer 1

Sie haben bereits die Hintergrunduntersuchungen zu Cache-obliven Algorithmen berichtet. In Bezug auf Benchmarking und praktische Ergebnisse sehe ich dieses aktuelle Papier von Intel als interessante Lektüre:

Ein synergetischer Ansatz zum Durchsatz von Computing auf X86-basierten Multicore-Desktops