Baru-baru ini saya tertarik pada masalah umum dalam mengoptimalkan penggunaan memori dalam situasi di mana ada lebih dari satu jenis memori yang tersedia, dan ada pertukaran antara kapasitas segmen memori yang diberikan dan kecepatan mengaksesnya.
Contoh yang umum adalah program memutuskan kapan untuk membaca dari / menulis ke cache prosesor, RAM dan hard drive (melalui memori virtual).
Saya sangat tertarik pada kasus khusus di mana jumlah data (termasuk program itu sendiri) yang perlu dimuat secara signifikan melebihi kapasitas penyimpanan tercepat yang tersedia (yaitu solusi sepele dari "hanya memuat semuanya" tidak dapat diterapkan).
Saya menemukan bahwa halaman Wikipedia menggambarkan beberapa algoritma cache yang umum, yang hampir seperti yang saya inginkan. Sayangnya, ini agak level rendah:
- Banyak, seperti LRU atau MRU hanya masuk akal jika Anda memiliki subrutin yang dapat diakses berkali-kali. Jika saya memiliki program dengan sejumlah besar subrutin, beberapa di antaranya tidak pernah diakses dalam jangka waktu tertentu, dan beberapa di antaranya diakses satu atau dua kali, strategi ini tidak akan pernah berhasil karena tidak dapat mengumpulkan cukup data tentang apa umumnya digunakan dan apa yang tidak.
- Lainnya, seperti CLOCK, tampaknya berurusan dengan kekhasan implementasi, daripada benar-benar menyerang akar masalah.
- Saya tahu ada strategi di mana satu profil pertama program selama uji coba, kemudian memberikan profil untuk sistem operasi untuk mengoptimalkan sesuai. Namun, kita masih harus menyelesaikan masalah dengan memberikan "contoh penggunaan" yang benar-benar representatif saat membangun profil.
Apa yang benar-benar ingin saya pelajari adalah ini: Ketika kita memisahkan semua teknis perangkat keras dan perangkat lunak, dan berbicara dalam konteks teoretis murni, mungkinkah untuk menganalisis struktur suatu algoritma, untuk mengetahui strategi cache yang efektif untuk itu didasarkan pada pemahaman tingkat tinggi tentang apa yang dilakukan algoritma?
Jawaban:
Saya tidak tahu tentang metode untuk menganalisis algoritma yang diberikan sewenang-wenang untuk menghasilkan kebijakan cache secara umum (ini terdengar cukup sulit), tetapi ini pada dasarnya adalah apa yang telah dilakukan (secara optimal, dalam arti asimptotik) pada kasus-oleh dasar -kasus untuk algoritma cache- diketahui paling dikenal , dengan menganalisis struktur divide-and-conquer mereka. Algoritma yang tidak diketahui cache dikenal untuk FFT, perkalian matriks, pengurutan, dan beberapa lainnya. Lihat halaman Wikipedia dan referensi di dalamnya.
sumber