Biaya pencarian versus perhitungan

Saya tertarik dalam mendirikan perhitungan untuk memeriksa apakah kriteria jarak puas: yaitu, jarak antara vektor dan vektor anter x j harus kurang dari beberapa nilai r m a x . Data saya dipartisi berdasarkan kisi koordinat ortogonal. Karena cutoff saya lebih kecil dari jarak antara titik akhir koordinat tetangga terdekat, saya ingin menambahkan variabel "oktan" untuk memeriksa apakah semuanya diatur dengan benar:${\bf x}_i$${\bf x}_j$$r_{\rm max}$

if octant[j] in allowed_list continue

sebagai "hubungan arus pendek" ke

if dist(x[i], x[j]) < r_max

Pertanyaan saya adalah: seberapa efisien komputasi boolean lookups dan perbandingan relatif terhadap operasi floating-point? Apakah ini layak dilakukan pada arsitektur modern?

Aturan praktis saya adalah bahwa jika Anda dapat menghitung beberapa kuantitas secara efisien (pemanfaatan FPU yang baik) dalam waktu kurang dari 50 jepit per nilai presisi ganda, lebih baik untuk menghitung ulang daripada menyimpan. Tren, yang telah stabil selama beberapa dekade, adalah untuk kemampuan floating point untuk meningkatkan lebih cepat daripada kinerja memori, dan tidak mungkin mengalah karena kendala fisik dan kebutuhan energi dari memori cepat. Nilai 50 adalah besarnya yang tepat untuk semua platform komputasi populer (Intel / AMD, Blue Gene, dan GPU).

Perkiraan biaya perkiraan per inti

[pedoman untuk mesin berbasis Intel dan AMD 2011/2012]

• $0.05$
• $0.2$
• $0.4$
• $0.4$$0.8$
• $2$
• $3$$5$
• $3$$5$
• $5$
• $4$$8$
• $12$
• $12$
• $30$$50$
• $100$
• $10^3$$1$ $\mu$
• $10^4$$10$ $\mu$
• $10^6$
• $2\cdot 10^6$MPI_Allreduce
• $10^7$
• $5\cdot 10^8$
• $1.8\cdot 10^{12}$

Bacaan lebih lanjut

• Tabel instruksi Agner Fog
• Nomor Latensi yang Harus Diketahui Setiap Programmer
• Paul McKenney slide pada threading