Penghitungan FLOP untuk fungsi perpustakaan

Ketika mengevaluasi jumlah FLOPs dalam fungsi yang sederhana, kita seringkali hanya bisa menurunkan ekspresi penghitungan operator aritmatika dasar. Namun, dalam kasus pernyataan matematis yang melibatkan pembagian yang merata, seseorang tidak dapat melakukan ini dan berharap dapat membandingkan dengan FLOP yang dihitung dari fungsi dengan hanya penambahan dan perkalian. Situasinya bahkan lebih buruk ketika operasi diimplementasikan di perpustakaan. Oleh karena itu, sangat penting untuk memiliki beberapa gagasan yang masuk akal tentang kinerja fungsi-fungsi khusus.

Dengan fungsi khusus, kami maksudkan hal-hal seperti:

• exp ()
• sqrt ()
• sin / cos / tan ()

yang biasanya disediakan oleh pustaka sistem.

Menentukan kerumitan ini dikacaukan lebih jauh oleh fakta bahwa banyak dari mereka yang adaptif dan memiliki kompleksitas yang bergantung pada input. Misalnya, implementasi exp () yang stabil secara numerik sering kali secara adaptif mengubah skala dan menggunakan pencarian. Kesan awal saya di sini adalah yang terbaik yang dapat dilakukan dalam hal ini adalah memastikan perilaku rata-rata fungsi.

Seluruh diskusi ini, tentu saja, sangat bergantung pada arsitektur. Untuk diskusi ini, kita dapat membatasi diri pada arsitektur tujuan umum tradisional dan mengecualikan arsitektur dengan unit fungsi khusus (GPU, dll.)

Orang dapat menemukan upaya yang cukup sederhana untuk membakukan ini untuk arsitektur tertentu demi perbandingan sistem vs sistem, tetapi ini tidak dapat diterima jika orang peduli tentang metode vs kinerja metode. Metodologi apa untuk menentukan kompleksitas FLOP dari fungsi-fungsi ini dianggap dapat diterima? Apakah ada jebakan besar?

Kedengarannya Anda menginginkan cara untuk mengevaluasi seberapa terikat FPU kode Anda, atau seberapa efektif Anda menggunakan FPU, daripada menghitung jumlah flop sesuai dengan definisi anachronistic yang sama dari "flop". Dengan kata lain, Anda menginginkan metrik yang mencapai puncak yang sama jika setiap unit floating point berjalan dengan kapasitas penuh setiap siklus. Mari kita lihat Intel Sandy Bridge untuk melihat bagaimana hal ini bisa terjadi.

Operasi floating point yang didukung perangkat keras

Chip ini mendukung instruksi AVX , jadi register sepanjang 32 byte (memegang 4 ganda). Arsitektur superscalar memungkinkan instruksi untuk tumpang tindih, dengan sebagian besar instruksi aritmatika mengambil beberapa siklus untuk menyelesaikan, meskipun instruksi baru mungkin dapat dimulai pada siklus berikutnya. Semantik ini biasanya disingkat dengan menulis latency / invers throughput, nilai 5/2 akan berarti bahwa instruksi membutuhkan 5 siklus untuk menyelesaikan, tetapi Anda dapat memulai instruksi baru setiap siklus lainnya (dengan asumsi bahwa operan tersedia, sehingga tidak ada data ketergantungan dan tidak menunggu ingatan).

Ada tiga unit aritmatika floating point per inti, tetapi yang ketiga tidak relevan dengan diskusi kita, kita akan memanggil dua unit A dan M yang relevan karena fungsi utamanya adalah penjumlahan dan perkalian. Instruksi contoh (lihat tabel Agner Fog )

• vaddpd: penambahan dikemas, menempati unit A untuk 1 siklus, latensi / keluaran terbalik adalah 3/1
• vmulpd: perkalian paket, unit M, 5/1
• vmaxpd: dikemas pilih maksimum berpasangan, unit A, 3/1
• vdivpd: paket split, unit M (dan beberapa A), 21/20 hingga 45/44 tergantung pada input
• vsqrtpd: dikemas akar kuadrat, beberapa A dan M, 21/21 hingga 43/43 tergantung pada input
• vrsqrtps: dikemas akar kuadrat resiprokal resiprokal rendah untuk input presisi tunggal (8 floats)

Semantik yang tepat untuk apa yang bisa tumpang tindih vdivpddan vsqrtpdtampaknya halus dan AFAIK, tidak didokumentasikan di mana pun. Dalam sebagian besar penggunaan, saya pikir ada sedikit kemungkinan untuk tumpang tindih, meskipun kata-kata dalam manual menunjukkan bahwa beberapa utas mungkin menawarkan lebih banyak kemungkinan untuk tumpang tindih dalam instruksi ini. Kita dapat menekan jepit puncak jika kita memulai vaddpddan vmulpdpada setiap siklus, dengan total 8 jepit per siklus. Multiply matrix-matrix padat ( dgemm) dapat mendekati puncak ini.

Ketika menghitung jepit untuk instruksi khusus, saya akan melihat berapa banyak FPU ditempati. Misalkan untuk argumen bahwa dalam rentang input Anda, vdivpdambil rata-rata 24 siklus untuk menyelesaikan, unit yang sepenuhnya menempati M, tetapi penambahan dapat (jika tersedia) dieksekusi secara bersamaan selama setengah siklus. FPU mampu melakukan 24 penggandaan paket dan 24 penambahan paket selama siklus tersebut (diselingi dengan sempurna vaddpddan vmulpd), tetapi dengan a vdivpd, yang terbaik yang bisa kita lakukan adalah 12 tambahan tambahan yang dikemas. Jika kita mengira bahwa cara terbaik untuk melakukan pembagian adalah dengan menggunakan perangkat keras (wajar), kita dapat menghitung vdivpd36 "jepit" yang dikemas, yang menunjukkan bahwa kita harus menghitung setiap skalar yang dibagi sebagai 36 "jepit".

Dengan root kuadrat resiprokal, kadang-kadang mungkin untuk mengalahkan perangkat keras, terutama jika akurasi penuh tidak diperlukan, atau jika rentang inputnya sempit. Seperti disebutkan di atas, vrsqrtpsinstruksinya sangat murah, jadi (jika dalam presisi tunggal) Anda dapat melakukan satu vrsqrtpsdiikuti oleh satu atau dua iterasi Newton untuk membersihkan. Iterasi Newton ini adil

y *= (3 - x*y*y)*0.5;

Jika banyak dari operasi ini perlu dilakukan, ini bisa secara signifikan lebih cepat daripada evaluasi naif y = 1/sqrt(x). Sebelum ketersediaan perangkat keras perkiraan akar kuadrat resiprokal, beberapa kode peka kinerja menggunakan operasi integer terkenal untuk menemukan tebakan awal untuk iterasi Newton.

Fungsi matematika yang disediakan perpustakaan

Kita bisa menerapkan heuristik yang mirip dengan fungsi matematika yang disediakan perpustakaan. Anda dapat membuat profil untuk menentukan jumlah instruksi SSE, tetapi seperti yang telah kita bahas, itu bukan keseluruhan cerita dan sebuah program yang menghabiskan seluruh waktunya mengevaluasi fungsi-fungsi khusus mungkin tidak tampak mendekati puncak, yang mungkin benar, tetapi tidak berguna untuk memberi tahu Anda bahwa semua waktu dihabiskan di luar kendali Anda di FPU.

Saya sarankan menggunakan perpustakaan vektor matematika yang baik sebagai baseline (misalnya Intel VML, bagian dari MKL). Ukur jumlah siklus untuk setiap panggilan dan kalikan dengan jepit puncak yang dapat dicapai atas jumlah siklus itu. Jadi, jika eksponensial yang dikemas membutuhkan 50 siklus untuk mengevaluasi, hitunglah 100 kali lipat lebar register. Sayangnya, pustaka vektor matematika kadang-kadang sulit untuk dipanggil dan tidak memiliki semua fungsi khusus, sehingga Anda mungkin akhirnya melakukan skalar matematika, dalam hal ini Anda akan menghitung eksponensial skalar hipotetis kami sebagai 100 jepit (walaupun mungkin masih membutuhkan 50 siklus, jadi Anda hanya akan mendapatkan 25% dari "puncak" jika semua waktu dihabiskan untuk mengevaluasi eksponensial ini).

Seperti yang disebutkan orang lain, Anda dapat menghitung siklus dan penghitung acara perangkat keras menggunakan PAPI atau berbagai antarmuka. Untuk penghitungan siklus sederhana, Anda dapat membaca penghitung siklus secara langsung menggunakan rdtscinstruksi dengan potongan rakitan inline.

Anda dapat menghitungnya pada sistem nyata menggunakan PAPI , yang memberikan akses ke penghitung perangkat keras, dan program pengujian sederhana. Antarmuka PAPI favorit saya adalah IPM (Integrated Performance Monitor) tetapi ada solusi lain ( TAU , misalnya). Ini harus memberikan perbandingan metode-ke-metode yang cukup stabil.

Saya akan menjawab pertanyaan ini seolah-olah Anda bertanya:

"Bagaimana saya membandingkan atau memprediksi kinerja algoritma yang sangat bergantung pada fungsi khusus, alih-alih jumlah FLOP multiply-add-carry tradisional yang berasal dari aljabar linear numerik"

Saya setuju dengan premis pertama Anda, bahwa kinerja banyak fungsi khusus bergantung pada arsitektur, dan bahwa meskipun Anda biasanya dapat memperlakukan masing-masing fungsi ini sebagai biaya konstan, ukuran konstanta akan bervariasi, bahkan antara dua prosesor dari perusahaan tetapi dengan arsitektur yang berbeda (lihat tabel waktu instruksi Agner Fog untuk referensi).

Saya tidak setuju, bagaimanapun, bahwa fokus perbandingan harus pada biaya operasi floating point individu. Saya pikir penghitungan FLOP sampai batas tertentu masih berguna, tetapi ada beberapa pertimbangan yang jauh lebih penting yang dapat membuat biaya fungsi khusus kurang relevan ketika membandingkan dua algoritma potensial, dan ini harus diperiksa secara eksplisit terlebih dahulu sebelum pergi ke perbandingan operasi floating-point:

1. Skalabilitas - Algoritma yang menampilkan tugas-tugas yang dapat diimplementasikan secara efisien pada arsitektur paralel akan mendominasi arena komputasi ilmiah untuk masa yang akan datang. Algoritma dengan "skalabilitas" yang lebih baik, baik melalui komunikasi yang lebih rendah, lebih sedikit kebutuhan untuk sinkronisasi, atau keseimbangan beban alami yang lebih baik, dapat menggunakan fungsi khusus yang lebih lambat dan karena itu lebih lambat untuk sejumlah kecil proses, tetapi pada akhirnya akan mengejar ketinggalan sebagai nomor prosesor meningkat.

2. Temporal Locality of Reference - Apakah algoritma menggunakan kembali data di antara tugas, memungkinkan prosesor untuk menghindari lalu lintas memori yang tidak perlu? Setiap tingkat hirarki memori yang dilalui suatu algoritma menambahkan urutan besarnya biaya (kira-kira) untuk setiap akses memori. Sebagai hasilnya, suatu algoritma dengan kepadatan tinggi dari operasi khusus kemungkinan akan secara signifikan lebih cepat daripada suatu algoritma dengan jumlah yang setara dari operasi fungsi sederhana pada wilayah memori yang lebih besar.

3. Memory Footprint - Ini sangat terkait dengan poin sebelumnya, tetapi karena komputer tumbuh lebih besar dan lebih besar, jumlah memori per inti sebenarnya cenderung ke bawah. Ada dua manfaat untuk jejak memori kecil. Yang pertama adalah bahwa sejumlah kecil data program kemungkinan akan dapat sepenuhnya masuk dalam cache prosesor. Yang kedua adalah bahwa, untuk masalah yang sangat besar, suatu algoritma dengan jejak memori yang lebih kecil mungkin dapat masuk ke dalam memori prosesor, yang memungkinkan masalah dipecahkan yang jika tidak akan melebihi kemampuan komputer.

Mengapa repot menghitung jepit? Hitung saja siklus untuk setiap operasi dan Anda akan memiliki sesuatu yang universal.