Saya telah membuat profil beberapa matematika inti kami pada Intel Core Duo, dan ketika melihat berbagai pendekatan untuk akar kuadrat, saya telah melihat sesuatu yang aneh: menggunakan operasi skalar SSE, lebih cepat mengambil akar kuadrat timbal balik dan mengalikannya untuk mendapatkan sqrt, daripada menggunakan opcode sqrt asli!
Saya mengujinya dengan loop seperti:
inline float TestSqrtFunction( float in );
void TestFunc()
{
#define ARRAYSIZE 4096
#define NUMITERS 16386
float flIn[ ARRAYSIZE ]; // filled with random numbers ( 0 .. 2^22 )
float flOut [ ARRAYSIZE ]; // filled with 0 to force fetch into L1 cache
cyclecounter.Start();
for ( int i = 0 ; i < NUMITERS ; ++i )
for ( int j = 0 ; j < ARRAYSIZE ; ++j )
{
flOut[j] = TestSqrtFunction( flIn[j] );
// unrolling this loop makes no difference -- I tested it.
}
cyclecounter.Stop();
printf( "%d loops over %d floats took %.3f milliseconds",
NUMITERS, ARRAYSIZE, cyclecounter.Milliseconds() );
}
Saya sudah mencoba ini dengan beberapa badan berbeda untuk TestSqrtFunction, dan saya punya beberapa pengaturan waktu yang benar-benar menggaruk kepala saya. Yang terburuk dari semuanya sejauh ini adalah menggunakan fungsi sqrt () asli dan membiarkan kompiler "pintar" "mengoptimalkan". Pada 24ns / float, menggunakan x87 FPU, ini sangat buruk:
inline float TestSqrtFunction( float in )
{ return sqrt(in); }
Hal berikutnya yang saya coba adalah menggunakan intrinsik untuk memaksa kompiler menggunakan opcode sqrt skalar SSE:
inline void SSESqrt( float * restrict pOut, float * restrict pIn )
{
_mm_store_ss( pOut, _mm_sqrt_ss( _mm_load_ss( pIn ) ) );
// compiles to movss, sqrtss, movss
}
Ini lebih baik, pada 11.9ns / float. Saya juga mencoba teknik perkiraan Newton-Raphson yang aneh dari Carmack , yang berjalan bahkan lebih baik daripada perangkat kerasnya, pada 4.3ns / float, meskipun dengan kesalahan 1 dalam 2 10 (yang terlalu berlebihan untuk tujuan saya).
Doozy adalah ketika saya mencoba operasi SSE untuk akar kuadrat timbal balik , dan kemudian menggunakan perkalian untuk mendapatkan akar kuadrat (x * 1 / √x = √x). Meskipun ini membutuhkan dua operasi yang bergantung, ini adalah solusi tercepat sejauh ini, pada 1,24ns / float dan akurat hingga 2 -14 :
inline void SSESqrt_Recip_Times_X( float * restrict pOut, float * restrict pIn )
{
__m128 in = _mm_load_ss( pIn );
_mm_store_ss( pOut, _mm_mul_ss( in, _mm_rsqrt_ss( in ) ) );
// compiles to movss, movaps, rsqrtss, mulss, movss
}
Pertanyaan saya pada dasarnya adalah apa yang memberi ? Mengapa opcode akar kuadrat bawaan ke perangkat keras SSE lebih lambat daripada menyintesisnya dari dua operasi matematika lainnya?
Saya yakin ini benar-benar biaya operasi itu sendiri, karena saya telah memverifikasi:
- Semua data cocok dengan cache, dan aksesnya berurutan
- fungsinya sebaris
- membuka gulungan loop tidak ada bedanya
- bendera kompiler disetel ke optimasi penuh (dan perakitannya bagus, saya centang)
( edit : stephentyrone dengan benar menunjukkan bahwa operasi pada string angka yang panjang harus menggunakan operasi yang dikemas SIMD vektor, seperti rsqrtps
- tetapi struktur data array di sini hanya untuk tujuan pengujian: apa yang sebenarnya saya coba ukur adalah kinerja skalar untuk digunakan dalam kode yang tidak dapat divektorisasi.)
sumber
inline float SSESqrt( float restrict fIn ) { float fOut; _mm_store_ss( &fOut, _mm_sqrt_ss( _mm_load_ss( &fIn ) ) ); return fOut; }
. Tetapi ini adalah ide yang buruk karena dapat dengan mudah menyebabkan kemacetan pemuatan-hit-store jika CPU menulis float ke stack dan kemudian segera membacanya kembali - beralih dari register vektor ke register float untuk nilai kembalian khususnya adalah berita buruk. Selain itu, opcode mesin yang mendasari yang diwakili oleh SSE intrinsik take address operand.eax
) sangat buruk, sementara perjalanan bolak-balik antara xmm0 dan stack dan tidak kembali, karena penerusan toko Intel. Anda bisa mengatur waktunya sendiri untuk memastikannya. Umumnya cara termudah untuk melihat potensi LHS adalah dengan melihat rakitan yang dipancarkan dan melihat di mana data disulap di antara set register; kompiler Anda mungkin melakukan hal yang cerdas, atau mungkin juga tidak. Untuk menormalkan vektor, saya menulis hasil saya di sini: bit.ly/9W5zoUJawaban:
sqrtss
memberikan hasil yang benar.rsqrtss
memberikan perkiraan ke timbal balik, akurat sekitar 11 bit.sqrtss
menghasilkan hasil yang jauh lebih akurat, karena diperlukan akurasi.rsqrtss
ada untuk kasus-kasus ketika perkiraan sudah cukup, tetapi kecepatan diperlukan. Jika Anda membaca dokumentasi Intel, Anda juga akan menemukan urutan instruksi (pendekatan akar kuadrat timbal balik diikuti oleh langkah Newton-Raphson tunggal) yang memberikan presisi hampir penuh (~ 23 bit akurasi, jika saya ingat dengan benar), dan masih agak lebih cepat darisqrtss
.sunting: Jika kecepatan sangat penting, dan Anda benar-benar memanggil ini dalam satu lingkaran untuk banyak nilai, Anda harus menggunakan versi vektor dari instruksi ini,
rsqrtps
atausqrtps
, keduanya memproses empat pelampung per instruksi.sumber
sqrtss
adalah benar bulat , yang membutuhkan ~ 50 bit sebelum pembulatan, dan tidak dapat dicapai dengan menggunakan sederhana N / R iterasi dalam presisi tunggal.Ini juga berlaku untuk divisi. MULSS (a, RCPSS (b)) jauh lebih cepat dari DIVSS (a, b). Nyatanya masih lebih cepat bahkan saat Anda meningkatkan presisi dengan iterasi Newton-Raphson.
Intel dan AMD sama-sama merekomendasikan teknik ini dalam manual pengoptimalan mereka. Dalam aplikasi yang tidak memerlukan kepatuhan IEEE-754, satu-satunya alasan untuk menggunakan div / sqrt adalah keterbacaan kode.
sumber
div
bukan satu-satunya operasi, jadi total throughput uop sering kali menjadi bottleneck bahkan ketika adadivps
ataudivss
. Lihat pembagian floating point vs perkalian floating point , di mana jawaban saya memiliki bagian tentang mengaparcpps
throughput tidak lagi menang. (Atau kemenangan latensi), dan angka pada pembagian throughput / latensi.a * rcpss(b)
bisa lebih cepat, tetapi masih lebih uops daripadaa/b
!Alih-alih memberikan jawaban, itu sebenarnya mungkin salah (saya juga tidak akan memeriksa atau berdebat tentang cache dan hal lainnya, katakanlah keduanya identik) Saya akan mencoba mengarahkan Anda ke sumber yang dapat menjawab pertanyaan Anda.
Perbedaannya mungkin terletak pada bagaimana akar dan akar dihitung. Anda dapat membaca lebih lanjut di sini http://www.intel.com/products/processor/manuals/ . Saya sarankan untuk memulai dari membaca tentang fungsi prosesor yang Anda gunakan, ada beberapa info, terutama tentang rsqrt (cpu menggunakan tabel pencarian internal dengan perkiraan besar, yang membuatnya lebih mudah untuk mendapatkan hasilnya). Tampaknya, rsqrt jauh lebih cepat daripada sqrt, sehingga 1 operasi mul tambahan (yang tidak terlalu mahal) mungkin tidak mengubah situasi di sini.
Sunting: Beberapa fakta yang mungkin layak untuk disebutkan:
1. Setelah saya melakukan beberapa optimalisasi mikro untuk perpustakaan grafik saya dan saya telah menggunakan rsqrt untuk menghitung panjang vektor. (alih-alih sqrt, saya telah mengalikan jumlah kuadrat saya dengan rsqrt, yang persis seperti yang telah Anda lakukan dalam pengujian), dan hasilnya lebih baik.
2. Menghitung rsqrt menggunakan tabel lookup sederhana mungkin lebih mudah, seperti untuk rsqrt, ketika x pergi ke tak terhingga, 1 / sqrt (x) pergi ke 0, jadi untuk x kecil nilai fungsinya tidak berubah (banyak), sedangkan untuk sqrt - itu menuju tak terbatas, jadi itu kasus sederhana itu;).
Juga, klarifikasi: Saya tidak yakin di mana saya menemukannya di buku yang saya tautkan, tetapi saya cukup yakin saya telah membaca bahwa rsqrt menggunakan beberapa tabel pencarian, dan itu harus digunakan hanya, ketika hasilnya tidak perlu persisnya, meskipun - saya mungkin juga salah, seperti beberapa waktu lalu :).
sumber
Newton-Raphson konvergen ke nol
f(x)
menggunakan kenaikan sama dengan di-f/f'
manaf'
turunannya.Karena
x=sqrt(y)
, Anda dapat mencoba memecahkanf(x) = 0
untukx
menggunakanf(x) = x^2 - y
;Kemudian kenaikannya adalah:
dx = -f/f' = 1/2 (x - y/x) = 1/2 (x^2 - y) / x
yang memiliki pembagian lambat di dalamnya.Anda dapat mencoba fungsi lain (seperti
f(x) = 1/y - 1/x^2
) tetapi akan sama rumitnya.Mari kita simak
1/sqrt(y)
sekarang. Anda dapat mencobaf(x) = x^2 - 1/y
, tetapi akan sama rumitnya:dx = 2xy / (y*x^2 - 1)
misalnya. Satu pilihan alternatif yang tidak jelasf(x)
adalah:f(x) = y - 1/x^2
Kemudian:
dx = -f/f' = (y - 1/x^2) / (2/x^3) = 1/2 * x * (1 - y * x^2)
Ah! Ini bukan ekspresi yang sepele, tetapi Anda hanya memiliki perkalian di dalamnya, tidak ada pembagian. => Lebih cepat!
Dan: langkah pembaruan penuh
new_x = x + dx
kemudian berbunyi:x *= 3/2 - y/2 * x * x
yang juga mudah.sumber
Ada sejumlah jawaban lain untuk ini dari beberapa tahun yang lalu. Inilah yang konsensusnya benar:
Inilah yang salah konsensus:
Algoritme NR untuk menghitung akar kuadrat timbal balik memiliki langkah pembaruan ini, seperti yang telah dicatat orang lain:
Itu banyak perkalian bergantung data dan satu pengurangan.
Berikut ini adalah algoritme yang sebenarnya digunakan oleh FPU modern.
Diberikan
b[0] = n
, misalkan kita dapat menemukan serangkaian angkaY[i]
sedemikian rupa sehinggab[n] = b[0] * Y[0]^2 * Y[1]^2 * ... * Y[n]^2
mendekati 1. Kemudian pertimbangkan:Jelas
x[n]
pendekatansqrt(n)
dany[n]
pendekatan1/sqrt(n)
.Kita bisa menggunakan langkah pembaruan Newton-Raphson untuk akar kuadrat timbal balik untuk mendapatkan barang
Y[i]
:Kemudian:
dan:
Pengamatan kunci berikutnya adalah itu
b[i] = x[i-1] * y[i-1]
. Begitu:Kemudian:
Artinya, diberi inisial x dan y, kita dapat menggunakan langkah pembaruan berikut:
Atau, lebih bagus lagi, kita bisa atur
h = 0.5 * y
. Ini adalah inisialisasi:Dan ini adalah langkah pembaruannya:
Ini adalah algoritme Goldschmidt, dan memiliki keuntungan besar jika Anda menerapkannya di perangkat keras: "loop dalam" terdiri dari tiga penambahan-perkalian dan tidak ada yang lain, dan dua di antaranya independen dan dapat disambungkan.
Pada tahun 1999, FPU sudah membutuhkan sirkuit add / substract pipelined dan sirkuit multiply pipelined, jika tidak SSE tidak akan terlalu "streaming". Hanya satu dari setiap sirkuit yang dibutuhkan pada tahun 1999 untuk mengimplementasikan loop dalam ini dengan cara yang sepenuhnya terhubung tanpa membuang banyak perangkat keras hanya pada akar kuadrat.
Hari ini, tentu saja, kami telah menyatukan multiply-add yang diekspos ke programmer. Sekali lagi, loop dalam adalah tiga FMA pipelined, yang (sekali lagi) umumnya berguna bahkan jika Anda tidak menghitung akar kuadrat.
sumber
_mm256_rsqrt_ps
, dengan analisis kinerja Haswell. Biasanya hanya merupakan ide yang bagus jika Anda tidak memiliki pekerjaan lain dalam loop dan akan menghambat throughput pembagi. HW sqrt adalah single uop jadi tidak apa-apa dicampur dengan pekerjaan lain.Ini lebih cepat karena instruksi ini mengabaikan mode pembulatan, dan tidak menangani pengecualian titik floatin atau angka yang dinormalisasi. Untuk alasan ini, jauh lebih mudah untuk melakukan pipeline, berspekulasi, dan mengeksekusi instruksi fp lainnya Rusak.
sumber
rsqrt
's banyak akurasi yang lebih rendah, yang berarti lebih sedikit pekerjaan yang harus dilakukan (atau tidak sama sekali?) Setelah meja-lookup untuk mendapatkan menebak mulai.