Prediksi runtime untuk aljabar linier padat

9

Saya ingin memprediksi runtimes untuk operasi aljabar linier padat pada arsitektur tertentu menggunakan perpustakaan tertentu. Saya ingin mempelajari model yang mendekati fungsinya

$F_{op} \;::\;$ ukuran input runtime $\rightarrow$

untuk operasi seperti matrik-gandakan, tambahkan elemen-bijaksana, pecahkan segitiga, dll ....

Saya menduga bahwa runtime ini sebagian besar dapat diprediksi karena keteraturan operasi setelah Anda melampaui ukuran masalah yang cocok dengan nyaman dalam cache.

Pertanyaan:

Apakah asumsi ini realistis? Apakah fungsi runtime cenderung hampir deterministik?
Dapatkah saya berasumsi bahwa fungsi ini polinomial dalam ukuran input? (Yaitu saya perkirakan matriks padat dikalikan agar terlihat seperti untuk dan beberapa koefisien skalar) $\alpha n\times k\times m$ $A_{nk}\times B_{km}$ $\alpha$
Apakah ada pekerjaan yang sudah ada sebelumnya di suatu tempat?
Rencana saya saat ini adalah melakukan regresi kuadrat terkecil dengan regulator . Ada saran lain? $L_1$

Sunting: Agar jelas saya sedang mencari runtimes, bukan FLOPs atau metrik kinerja umum lainnya. Saya bersedia membatasi diri pada satu arsitektur tertentu.

linear-algebra machine-learning MRocklin
sumber

10

Saya baru-baru ini mengerjakan topik ini dengan tepat. Anda mungkin ingin melihat makalah kami: http://arxiv.org/abs/1209.2364 .

Mengapa Anda tertarik dengan prediksi runtime dari rutinitas aljabar linier? Apakah Anda bermaksud menggunakan model untuk tujuan tertentu?

Elmar Peise
sumber

Terima kasih untuk tautannya. Aku akan melihatnya. Saya tertarik pada ini karena saya curiga alasan yang sama Anda. Pemilihan algoritma otomatis dan penjadwalan untuk ekspresi matriks. Banyak masalah yang tidak mungkin terjadi seharusnya terjadi dalam domain yang sangat teratur dan dapat diprediksi ini.

MRocklin

6

Ada banyak pekerjaan yang sudah ada sebelumnya. Kebanyakan pengembang perpustakaan aljabar linier memublikasikan hasil kinerja dalam hal kinerja floating-point yang dapat dikonversi menjadi waktu berjalan.

Googling untuk "kinerja DGEMM" misalnya, menghasilkan yang berikut: http://math-atlas.sourceforge.net/timing/3_5_10/index.html .

Secara umum, Anda dapat mengharapkan jawabannya tidak mulus. Akan ada lompatan atau lonjakan di sekitar ukuran masalah tertentu (yang berhubungan dengan ukuran cache). Anda juga harus mengharapkan dataran tinggi dalam tingkat, dan, oleh karena itu, daerah linear-ish untuk berbagai ukuran masalah. Saya tidak berharap polinomial sangat membantu.

Mengingat upaya pembandingan berbasis luas, mungkin lebih mudah untuk mentabulasi hasil dan menginterpolasi seperlunya. Apa tujuanmu

Bill Barth
sumber

1

DGEMM

n^{3}

$n^3$

Mengonversi jepit ke runtimes, menurut pengalaman saya, sulit. Saya benar-benar hanya peduli tentang runtimes dalam kasus saya. Saya sedang menguji kelayakan penjadwalan statis.

MRocklin

Dalam pengalaman saya lonjakan / dataran tinggi hanya terjadi untuk ukuran masalah kecil. Setelah Anda keluar dari cache, semuanya cukup lancar. Saya setuju bahwa menambahkan fungsi piecewise mungkin akan meningkatkan kecocokan.

MRocklin

Prediksi runtime untuk aljabar linier padat

Jawaban: