Apa model teoritis yang tepat untuk merancang algoritma untuk komputer berkinerja tinggi saat ini dan yang akan datang

20

Pertanyaan ini mirip dengan pertanyaan yang lebih umum tentang apa model teoritis yang tepat dari komputer untuk merancang algoritma dan struktur data.
Di sini, saya bertanya secara khusus tentang komputer berkinerja tinggi saat ini (seperti yang terdaftar sebagai Top 500 ) atau bahkan tentang superkomputer mendatang.

Mengingat bahwa komputer ini biasanya bekerja pada kumpulan data yang sangat besar (tampaknya beberapa orang menggunakan mesin tersebut terutama karena mereka memiliki memori utama gabungan yang sangat besar) aspek model I / O (diperkenalkan oleh Aggarwal dan Vitter pada tahun 1988 ) dan versi paralelnya. , PEM ( Arge, Goodrich, Nelson dan Sitchinava pada 2008 ) harus hadir. Di sisi lain, harus ada sesuatu tentang komunikasi, khususnya menghukum paket ultra kecil ke semua node komputasi lainnya.

Seperti yang mungkin Anda bayangkan, saya tidak takut kehabisan ide ketika membuat model baru, tetapi saya sedikit khawatir bahwa saya mungkin mengabaikan upaya sebelumnya dalam melakukannya, khususnya karena saya memiliki kesan bahwa tahun 1980- 1995 atau lebih melihat banyak upaya pemodelan seperti itu (seperti BSP atau model bridging) yang tampaknya belum banyak digunakan.

Model apa yang harus saya perhatikan lebih dekat?

reference-request soft-question machine-models Riko Jacob
sumber
ini tidak menjawab sama sekali, tetapi model apa pun untuk superkomputer saat ini dan yang akan datang tetapi menanamkan kesalahan / toleransi kesalahan.
Sylvain Peyronnet
Lihat taksonomi Flynn. Menurut Wikipedia, "Semua top 10 dan sebagian besar superkomputer TOP500 didasarkan pada arsitektur MIMD". en.wikipedia.org/wiki/MIMD
Mohammad Al-Turkistany
dapatkah Anda mengklarifikasi kalimat: "Di sisi lain, harus ada sesuatu tentang komunikasi, khususnya menghukum paket ultra kecil ke semua node komputasi lainnya." apakah itu salah cetak? haruskah itu mendorong ? dapatkah satu jawaban untuk pertanyaan ini berupa pola desain paralel misalnya mapreduce, CSP Hoare? lihat juga cache lupa algoritma, wikipedia
vzn

Jawaban:

9

Di PODC 2009, Bruce Hendrickson memberikan sambutan yang fenomenal tentang masalah ini. (Slide-nya sepertinya tidak online, tetapi Anda mungkin ingin bertanya padanya apakah Anda bisa melihatnya.) Saya belum berpikir ada model yang "tepat" - bonus untuk Anda! - tapi saya sarankan Anda melihat makalahnya, terutama yang ada di halaman Grafik dan Arsitektur , di mana ia mencoba mencari cara untuk menangani grafik besar dengan struktur kecil (yaitu dataset "modern") pada mesin multithreaded besar-besaran.

Aaron Sterling
sumber
Terima kasih untuk penunjuknya. Melirik melalui itu, saya memiliki kesan bahwa dia tidak begitu banyak mendefinisikan model yang akan memungkinkan analisis teoritis. Apakah saya mengabaikan sesuatu? Mungkin saya harus menghubunginya secara langsung.
Riko Jacob
@Riko Jacob: Saya setuju bahwa Hendrickson lebih merupakan seorang praktisi daripada seorang model. Tapi saya pikir dia punya intuisi hebat untuk apa yang dibutuhkan. Jika Anda ingin makalah tentang model, Anda mungkin lebih tertarik pada Workshop on Theory and Many-Cores . Saya tidak menemukan model yang memuaskan, dan saya akan sangat tertarik untuk melihat apa yang Anda dapatkan. :-)
Aaron Sterling
8

Satu masalah yang tidak jelas adalah bagaimana cache akan berkembang. 2009 tesis Nikos Hardavellas menganggap hal-hal ini dari perspektif sistem, termasuk pertimbangan dari batas fisik dengan sistem memori scalable. Tesis ini tidak menyajikan model seperti itu, tetapi dapat memberi Anda beberapa petunjuk.

Rasmus Pagh
sumber
4

⌈log⁡x⌉

Suresh Venkat
sumber
Setelah meliriknya, bagiku itu tampak seperti pendahulu dari model yang tidak memperhatikan cache. Saya juga tidak melihat ide tentang pemrosesan paralel. Apakah saya melewatkan sesuatu di sini?
Riko Jacob
Saya pikir ini lebih tentang model memori hirarkis, itu benar.
Suresh Venkat