Algoritma dan struktur data yang tidak memperhatikan cache adalah hal yang agak baru, diperkenalkan oleh Frigo et al. dalam algoritma Cache-oblivious, 1999 . Tesis Prokop dari tahun yang sama memperkenalkan ide-ide awal juga.
Makalah oleh Frigo et al. menyajikan beberapa hasil eksperimen yang menunjukkan potensi teori dan algoritma cache-lupa dan struktur data. Banyak struktur data yang tidak memperhatikan cache didasarkan pada pohon pencarian statis. Metode menyimpan dan menavigasi pohon-pohon ini telah dikembangkan sedikit, mungkin terutama oleh Bender et al. dan juga oleh Brodal et al. Demaine memberikan gambaran yang bagus .
Pekerjaan eksperimental menyelidiki perilaku cache dalam praktiknya dilakukan setidaknya oleh Ladner et al. dalam Perbandingan Cache, Sadar dan Cache. Pohon Pencarian Statis yang Terlupakan Menggunakan Instrumentasi Program, 2002 . Ladner et al. membandingkan perilaku cache algoritma memecahkan masalah pencarian biner, menggunakan algoritma klasik, algoritma cache-terlupakan dan algoritma cache-aware. Setiap algoritma dipatok dengan metode navigasi implisit dan eksplisit. Selain itu, tesis oleh Rønn, 2003 menganalisis algoritma yang sama hingga detail yang cukup tinggi dan juga melakukan pengujian yang lebih teliti terhadap algoritma yang sama seperti Ladner et al.
Pertanyaanku adalah
Apakah sudah ada penelitian baru tentang benchmarking perilaku cache dari algoritma cache-lupa dalam praktek sejak itu? Saya terutama tertarik pada kinerja pohon pencarian statis, tapi saya juga akan senang dengan algoritma cache-lupa lainnya dan struktur data.
Jawaban:
Anda telah membahas penelitian latar belakang tentang algoritma yang tidak memperhatikan cache dengan cukup baik. Dalam hal pembandingan dan hasil praktis, saya melihat makalah baru-baru ini oleh Intel sebagai bacaan yang menarik:
Pendekatan Sinergis untuk Komputasi Throughput pada Desktop Multicore berbasis x86
sumber