Matematika dan komputasi

Eksperimen matriks acak

Matriks besar berisi bilangan acak, didiagonalisasi berulang kali untuk mempelajari statistik nilai eigennya.

Pertanyaan yang dijawabnya: Pola apa yang akhirnya dibentuk nilai eigen sebuah matriks acak, dan apakah cocok dengan bidang matematika dan fisika lain?

Mengabaikan: Hanya mengambil sampel sudut kecil dari ruang tak hingga matriks yang mungkin.

Berjalan di: sekitar 10¹² FLOPS kasar klaster universitas yang menghasilkan dan mendiagonalkan banyak matriks besarSejak: 1955 Karya awal Wigner tentang statistik nilai eigen matriks acak

Eksperimen graf acak

Graf yang dibangkitkan dengan aturan acak, simpul demi simpul atau sisi demi sisi, untuk melihat sifat apa yang biasanya muncul, seperti keterhubungan atau pengelompokan.

Pertanyaan yang dijawabnya: Seperti apa jaringan yang ‘tipikal’ di bawah aturan penambahan simpul dan sisi ini?

Mengabaikan: Jaringan dunia nyata jarang sebersih aturan yang menghasilkan model.

Berjalan di: sekitar 10¹⁰ FLOPS kasar berjalan di desktop untuk graf hingga jutaan simpulSejak: 1959 Model graf acak Erdos dan Renyi

Simulasi perkolasi

Kisi atau jaringan dengan situs atau ikatan yang dibuka secara acak, diamati sampai titik ketika jalur terhubung tiba-tiba membentang di seluruh sistem.

Pertanyaan yang dijawabnya: Pada kepadatan berapa jaringan acak tiba-tiba terhubung dari ujung ke ujung?

Mengabaikan: Kisi yang diidealkan berperilaku lebih bersih daripada material berpori atau jaringan nyata mana pun.

Berjalan di: sekitar 10¹⁰ FLOPS kasar mesin desktop untuk penyapuan kisi yang besarSejak: 1957 Pengenalan teori perkolasi oleh Broadbent dan Hammersley

Pencarian matematika eksperimental

Pencarian numerik kekuatan kasar untuk pola, contoh tandingan, atau hubungan tepat di antara bilangan, dijalankan jauh melampaui yang bisa diperiksa dengan tangan.

Pertanyaan yang dijawabnya: Apakah dugaan ini benar untuk setiap kasus yang sanggup diperiksa siapa pun, dan apakah sebuah pola muncul?

Mengabaikan: Sebanyak apa pun kasus yang diperiksa, itu bukan bukti, walau banyak yang ternyata berlaku.

Berjalan di: sekitar 10¹¹ FLOPS kasar klaster universitas yang berjalan berhari-hari untuk satu pencarianSejak: 1963 paling lambat 1963, pencarian komputer untuk hubungan bilangan bulat dan pola bilangan prima

Pendugaan konstanta dengan Monte Carlo

Pengambilan sampel acak dipakai untuk memperkirakan konstanta atau integral matematis, seperti menebar titik untuk memperkirakan luas, sebagai latihan, bukan untuk model fisik.

Pertanyaan yang dijawabnya: Seberapa akurat pengambilan sampel acak buta saja bisa memastikan besaran matematis yang eksak?

Mengabaikan: Konvergen jauh lebih lambat daripada hampir semua metode numerik yang lebih canggih.

Berjalan di: sekitar 10⁹ FLOPS kasar berjalan di laptop dalam hitungan detik hingga menitSejak: 1946 Gagasan Ulam tahun 1946; von Neumann mengusulkan versi komputer elektronik pada Maret 1947, dan metodenya pertama kali diterbitkan pada 1949 sumberDi pohon simulasi: Metode Monte Carlo

Jalankan model interaktif

Pencarian teori bilangan komputasi

Bilangan besar diuji keprimaannya, difaktorkan, atau dicari sifat khususnya seperti bilangan sempurna, memakai algoritma yang dijalankan berskala besar, bukan dengan tangan.

Pertanyaan yang dijawabnya: Apakah bilangan raksasa ini memiliki sifat yang kita cari, dan seberapa jauh pencarian bisa mendorong rekor?

Mengabaikan: Pencarian pemecah rekor tak banyak berkata tentang bilangan yang belum terpikir untuk diperiksa siapa pun.

Berjalan di: sekitar 10¹³ FLOPS kasar proyek komputasi sukarela terdistribusi di banyak mesin sumbanganSejak: 1951 Uji tangan Lucas untuk bilangan prima Mersenne, pertama kali dijalankan dengan komputer pada 1951

Numerik atraktor kacau

Sekumpulan kecil persamaan nonlinier diintegrasikan langkah demi langkah untuk memperlihatkan ketergantungan sensitif pada kondisi awal dan atraktor fraktal.

Pertanyaan yang dijawabnya: Mengapa sistem deterministik yang sederhana menjadi tak terprediksi?

Mengabaikan: Pembulatan numerik membuat lintasan panjang bukan orbit sejati, hanya yang tetap dekat dengannya.

Berjalan di: sekitar 10³ FLOPS kasar beberapa persamaan, beberapa detik di laptop.Sejak: 1963 Aliran nonperiodik deterministik Lorenz, model konveksi yang dijalankan di komputer. sumberDi pohon simulasi: Konveksi kacau Lorenz

Eksperimen kisi nonlinier

Rantai massa dengan pegas nonlinier dimulai dari satu mode lalu diikuti untuk melihat apakah energinya menyebar merata, seperti yang disarankan termodinamika.

Pertanyaan yang dijawabnya: Apakah rantai nonlinier membagi energinya secara merata di antara semua geraknya?

Mengabaikan: Hasilnya bergantung pada rantai dan keadaan awal yang dipilih.

Berjalan di: sekitar 10³ FLOPS kasar kecil menurut standar modern; yang aslinya memakai beberapa lusin massa.Sejak: 1955 Studi Fermi, Pasta, dan Ulam tentang masalah nonlinier pada komputer digital awal. sumber

Eksperimen numerik soliton

Persamaan gelombang nonlinier diselesaikan pada grid untuk melihat denyut saling melewati dan mempertahankan bentuknya, yang tidak dilakukan gelombang linier.

Pertanyaan yang dijawabnya: Mengapa sebagian gelombang nonlinier saling melewati tanpa berubah?

Mengabaikan: Ia menunjukkan satu keluarga persamaan, bukan perilaku umum gelombang nonlinier.

Berjalan di: sekitar 10⁴ FLOPS kasar grid satu dimensi, sepele saat ini.Sejak: 1965 Interaksi soliton dalam plasma tanpa tumbukan dan kembalinya keadaan awal oleh Zabusky dan Kruskal. sumber

Perenderan himpunan fraktal

Rumus iteratif sederhana diuji di setiap titik pada bidang kompleks untuk melihat apakah ia lolos menuju tak hingga, menggambar batas himpunan titik stabil.

Pertanyaan yang dijawabnya: Seperti apa bentuk himpunan tempat sebuah iterasi sederhana tetap terbatas?

Mengabaikan: Uji lolos hanya menyarankan keanggotaan, dan gambarnya adalah pengambilan sampel beresolusi terhingga dari himpunan yang detailnya tak terhingga.

Berjalan di: sekitar 10⁹ FLOPS kasar pembesaran dalam membutuhkan iterasi presisi diperluas pada jutaan titik.Sejak: 1980 Aspek fraktal iterasi z ke lambda z(1-z) oleh Mandelbrot, citra komputer pertama himpunan Mandelbrot. sumber

Kekritisan swa-organisasi tumpukan pasir

Butiran dijatuhkan di atas kisi dan roboh bila terlalu curam, menghasilkan longsoran dari segala ukuran tanpa penyetelan, sebagai model bagaimana sistem mencapai keadaan kritis.

Pertanyaan yang dijawabnya: Mengapa longsoran dari segala ukuran muncul tanpa penyetelan apa pun?

Mengabaikan: Apakah sistem nyata berbagi penskalaan yang sama masih diperdebatkan.

Berjalan di: sekitar 10⁹ FLOPS kasar simulasi panjang pada kisi besar untuk melihat penskalaan.Sejak: 1987 Kekritisan swa-atur Bak, Tang, dan Wiesenfeld: penjelasan untuk derau 1/f. sumber

Perhitungan nol zeta Riemann

Nilai fungsi zeta di sepanjang garis kritisnya dihitung untuk menemukan dan menghitung nolnya, memeriksa bahwa semuanya berada di tempat yang dikatakan hipotesis.

Pertanyaan yang dijawabnya: Apakah semua nol takremeh fungsi zeta terletak pada satu garis?

Mengabaikan: Pemeriksaan terbatas, sepanjang apa pun, tidak bisa membuktikan bahwa tidak ada nol di luar garis itu setelahnya.

Berjalan di: sekitar 10¹⁸ FLOPS kasar puluhan tahun waktu CPU pada pencarian terbesar.Sejak: 1953 Perhitungan Turing atas fungsi zeta Riemann. sumber

Digit pi lewat komputer

Deret untuk pi dijumlahkan sampai digit yang sangat banyak dengan aritmetika eksak, menguji angka sekaligus mesinnya.

Pertanyaan yang dijawabnya: Apakah digit pi tampak acak, dan bisakah mesin dipercaya pada skala ini?

Mengabaikan: Digit-digit itu tidak menjawab pertanyaan terbuka mana pun, dan pemeriksaan hanya menangkap galat perangkat keras jika metodenya independen.

Berjalan di: sekitar 10¹⁷ FLOPS kasar bulan di server untuk ratusan triliun digit.Sejak: 1950 Penentuan pi dan e hingga lebih dari 2000 tempat desimal oleh Reitwiesner dengan ENIAC (terbit 1950, dicetak ulang dalam Pi: A Source Book). sumber

Penemuan konjektur dipandu AI

Pembelajaran mesin pada tabel besar objek matematika menemukan sifat mana yang saling terkait, untuk menyarankan dugaan yang kemudian dicoba dibuktikan para matematikawan.

Pertanyaan yang dijawabnya: Hubungan tak terlihat mana di antara besaran matematis ini yang layak dibuktikan?

Mengabaikan: Ia hanya menyarankan pola dan tidak membuktikan apa pun sendiri, dan beberapa keteraturan dalam data bisa jadi artefak dari cara data dibuat.

Berjalan di: sekitar 10¹⁵ FLOPS kasar berhari-hari di beberapa GPU per set data.Sejak: 2021 Davies dan rekan-rekannya, memajukan matematika dengan memandu intuisi manusia memakai AI. sumber

Pencarian algoritma dan konstruksi terlatih

Sistem pemain permainan atau model bahasa mencari prosedur atau objek matematika baru, dengan komputer memeriksa kebenaran setiap kandidat.

Pertanyaan yang dijawabnya: Bisakah program menemukan algoritma yang lebih cepat atau contoh yang lebih besar daripada yang ditemukan manusia?

Mengabaikan: Setiap hasil hanyalah satu contoh baru, dan pencariannya hanya mencakup jenis objek yang dirumuskan perancangnya sebagai permainan.

Berjalan di: sekitar 10¹⁷ FLOPS kasar berhari-hari hingga berminggu-minggu di klaster akselerator.Sejak: 2022 AlphaTensor oleh Fawzi dan rekan-rekannya, menemukan algoritma perkalian matriks yang lebih cepat dengan pembelajaran penguatan. sumber

Pemeriksaan model

Setiap keadaan yang dapat dicapai dari sistem terhingga, seperti protokol atau desain sirkuit, dienumerasi komputer untuk memeriksa bahwa suatu sifat berlaku di semuanya.

Pertanyaan yang dijawabnya: Adakah keadaan terjangkau tempat rancangan ini melanggar aturannya sendiri?

Mengabaikan: Ruang keadaan meledak melampaui apa yang bisa diperiksa, sehingga rancangan nyata disederhanakan lebih dulu.

Berjalan di: sekitar 10¹² FLOPS kasar klaster universitas yang menelusuri tuntas ruang keadaan yang besar tapi terbatasSejak: 1981 Pengenalan pemeriksaan model oleh Clarke dan Emerson

Pencarian pembuktian teorema otomatis

Pencarian melalui rantai inferensi logis, dihasilkan komputer langkah demi langkah, mencari bukti atau sanggahan sebuah pernyataan matematika.

Pertanyaan yang dijawabnya: Apakah ada rantai langkah logis yang sah dari aksioma ke pernyataan ini?

Mengabaikan: Menemukan bukti yang tak akan dipilih manusia, dan kadang tidak ada sama sekali dalam jangkauan.

Berjalan di: sekitar 10¹¹ FLOPS kasar klaster universitas yang mencari selama berjam-jam hingga berhari-hariSejak: 1956 Logic Theorist, program pencarian bukti otomatis yang awal

SAT dan penyelesaian kendala

Jutaan kombinasi nilai benar atau salah dicari secara sistematis untuk memenuhi himpunan besar kendala logis, dipakai untuk menjadwalkan, merutekan, atau memverifikasi rancangan.

Pertanyaan yang dijawabnya: Adakah penetapan nilai yang memenuhi semua kendala ini sekaligus?

Mengabaikan: Beberapa kasus begitu sulit sehingga tidak ada solver, sebaik apa pun, yang selesai tepat waktu.

Berjalan di: sekitar 10¹¹ FLOPS kasar workstation hingga klaster, tergantung ukuran masalahSejak: 1962 prosedur Davis-Putnam untuk pencarian satisfiabilitas

Pemodelan serangan kriptografis

Skema sandi atau pertukaran kunci diserang jutaan kali dalam simulasi, dengan kekuatan kasar, bias statistik, atau kelemahan yang dimodelkan, untuk mengukur seberapa besar usaha yang sebenarnya dibutuhkan untuk menjebolnya.

Pertanyaan yang dijawabnya: Berapa banyak operasi yang sebenarnya dibutuhkan untuk memecahkan ini, dan apakah angka itu masih cukup besar untuk aman?

Mengabaikan: Hanya menguji serangan yang terpikir oleh analis untuk dimodelkan, bukan yang belum ditemukan siapa pun.

Berjalan di: sekitar 10¹⁴ FLOPS kasar klaster terdistribusi dari banyak mesin yang menjalankan percobaan seranganSejak: 1976 paling lambat 1976, analisis komputasi kekuatan sandi dan pertukaran kunci

Simulasi kebocoran saluran samping

Daya yang terpakai, waktu, atau emisi elektromagnetik sebuah perangkat dimodelkan saat menjalankan operasi kriptografi, untuk melihat apa yang bisa dipelajari pendengar di luar darinya.

Pertanyaan yang dijawabnya: Seberapa banyak kunci rahasia yang bocor lewat perilaku fisik perangkat, bukan lewat matematikanya?

Mengabaikan: Kondisi laboratorium menangkap sinyal yang lebih bersih daripada yang biasanya diberikan perangkat nyata yang berderau.

Berjalan di: sekitar 10¹⁰ FLOPS kasar workstation yang memodelkan jejak daya atau waktu satu perangkatSejak: 1996 Demonstrasi serangan pewaktuan pada implementasi kriptografi oleh Kocher

Verifikasi protokol keamanan

Setiap pesan yang bisa dikirim, diputar ulang, atau dipalsukan penyerang dalam protokol komunikasi, dienumerasi komputer untuk memeriksa apakah rahasia atau identitas bisa dipaksa keluar darinya.

Pertanyaan yang dijawabnya: Bisakah urutan pesan apa pun menipu protokol ini sehingga membocorkan rahasia atau menerima identitas palsu?

Mengabaikan: Memverifikasi protokol sebagaimana dispesifikasikan, bukan jalan pintas yang diambil implementasi nyata.

Berjalan di: sekitar 10¹¹ FLOPS kasar workstation hingga klaster yang memeriksa ruang pesan satu protokolSejak: 1989 model Dolev-Yao, dasar fondasional untuk verifikasi protokol

Pembuktian berbantuan komputer dengan pemeriksaan kasus menyeluruh

Teorema diringkas menjadi daftar kasus terbatas, masing-masing diverifikasi oleh program, karena tidak ada manusia yang sanggup memeriksa semuanya.

Pertanyaan yang dijawabnya: Bisakah bukti diselesaikan oleh mesin yang memeriksa setiap kasus?

Mengabaikan: Kepercayaan berpindah ke programnya, perangkat kerasnya, dan argumen reduksi kasusnya.

Berjalan di: sekitar 10⁹ FLOPS kasar sekitar seribu jam di mainframe untuk yang asli; jauh lebih sedikit sekarang.Sejak: 1977 Bukti Appel dan Haken bahwa setiap peta planar dapat diwarnai empat warna, dengan reduksibilitas yang diperiksa komputer. sumber

Numerik tervalidasi

Perhitungan yang dilakukan dengan batas terjamin, sehingga hasil numerik membuktikan pernyataan matematika, seperti keberadaan atraktor kacau.

Pertanyaan yang dijawabnya: Bisakah jawaban hasil komputasi dibuktikan benar, bukan sekadar mungkin akurat?

Mengabaikan: Batas bisa meledak dalam waktu panjang, sehingga pembuktian terbatas pada masalah yang pendek atau berperilaku baik.

Berjalan di: sekitar 10⁹ FLOPS kasar aritmetika interval mengalikan biaya dengan faktor yang sederhana.Sejak: 2002 Solver ODE yang ketat dari Tucker dan masalah ke-14 Smale, membuktikan bahwa atraktor Lorenz ada. sumber

Pencacahan mesin Turing

Setiap program kecil dari mesin minimal dijalankan untuk melihat mana yang berhenti dan mana yang berjalan selamanya, untuk menemukan yang berhenti dengan waktu terlama pada setiap ukuran.

Pertanyaan yang dijawabnya: Berapa lama program kecil bisa berjalan sebelum berhenti?

Mengabaikan: Ketidakterputusan berarti sebagian mesin tidak akan pernah bisa digolongkan, selama apa pun mereka berjalan.

Berjalan di: sekitar 10¹⁵ FLOPS kasar miliaran mesin, dengan bukti untuk yang tidak berhenti.Sejak: 1965 Studi komputer Lin dan Rado tentang masalah mesin Turing. sumber

Pemeriksaan model statistik

Sistem berperilaku acak disimulasikan berkali-kali untuk memperkirakan dengan keyakinan statistik seberapa besar kemungkinan ia melanggar suatu sifat.

Pertanyaan yang dijawabnya: Seberapa besar kemungkinan sistem acak melanggar aturan keselamatan?

Mengabaikan: Simulasi statistik memberi probabilitas dengan tingkat kepercayaan, bukan bukti, dan kegagalan langka memerlukan importance sampling.

Berjalan di: sekitar 10⁹ FLOPS kasar ribuan hingga jutaan eksekusi yang disampel.Sejak: 2002 Verifikasi probabilistik sistem peristiwa diskret dengan pengambilan sampel penerimaan oleh Younes dan Simmons. sumber

Pengujian fuzz

Program diberi masukan acak atau termutasi dalam jumlah besar untuk menemukan yang membuatnya macet, pada dasarnya mensimulasikan dunia yang bermusuhan atau ceroboh.

Pertanyaan yang dijawabnya: Masukan apa yang akan membuat perangkat lunak ini gagal?

Mengabaikan: Ia hanya menemukan kegagalan yang dijangkau masukan acak, dan sebuah program bisa lolos bertahun-tahun sambil menyembunyikan bug di balik kasus langka.

Berjalan di: sekitar 10¹⁴ FLOPS kasar tahun-mesin waktu CPU untuk basis kode besar.Sejak: 1990 Studi empiris keandalan utilitas UNIX oleh Miller, Fredriksen, dan So. sumber

Eksekusi simbolik

Program dijalankan dengan masukan tak diketahui yang ditulis sebagai simbol, mengumpulkan syarat pada setiap jalur, lalu pemecah mencari nilai yang menempuh setiap cabang.

Pertanyaan yang dijawabnya: Masukan apa yang menjalankan setiap jalur program ini, dan adakah yang mencapai bug?

Mengabaikan: Jumlah jalur tumbuh secara eksponensial terhadap ukuran program, sehingga program besar hanya tercakup sebagian.

Berjalan di: sekitar 10¹² FLOPS kasar jam waktu solver per program, naik tajam seiring jumlah lintasan.Sejak: 1976 Eksekusi simbolik dan pengujian program oleh King. sumber

Interpretasi abstrak

Program dijalankan pada set nilai yang mungkin, seperti rentang, bukan nilai tunggal, untuk membuktikan sifat yang berlaku bagi setiap masukan.

Pertanyaan yang dijawabnya: Bisakah program ini pernah membagi dengan nol atau mengalami overflow, untuk masukan apa pun?

Mengabaikan: Pendekatan aman menimbulkan alarm palsu, sehingga orang tetap harus memeriksa setiap peringatan.

Berjalan di: sekitar 10¹¹ FLOPS kasar jam di workstation untuk basis kode avionik yang besar.Sejak: 1977 Interpretasi abstrak Cousot dan Cousot, model kisi terpadu untuk analisis statis program. sumber

Pemeriksaan model terbatas

Perilaku sebuah rancangan hingga sejumlah langkah tertentu ditulis sebagai rumus logika dan diserahkan ke solver satisfiabilitas untuk mencari jalur pendek apa pun menuju bug.

Pertanyaan yang dijawabnya: Bisakah sirkuit atau program ini mencapai keadaan galat dalam sejumlah langkah tertentu?

Mengabaikan: Ia tidak membuktikan apa pun di luar batas langkah kecuali argumen terpisah menunjukkan bahwa itu cukup.

Berjalan di: sekitar 10¹³ FLOPS kasar jam di server per properti.Sejak: 1999 Pemeriksaan model simbolik tanpa BDD oleh Biere, Cimatti, Clarke, dan Zhu. sumber

Pengujian acak berbasis properti

Aturan yang seharusnya selalu berlaku dinyatakan, dan komputer menghasilkan banyak kasus acak serta mengecilkan setiap kegagalan menjadi contoh tandingan yang kecil.

Pertanyaan yang dijawabnya: Apakah kode ini menaati spesifikasinya sendiri pada beragam masukan?

Mengabaikan: Kasus acak mungkin tak pernah mencapai kondisi langka, dan properti yang dituliskan mungkin bukan yang penting.

Berjalan di: sekitar 10⁹ FLOPS kasar menit di laptop untuk ribuan kasus.Sejak: 2000 QuickCheck oleh Claessen dan Hughes, alat ringan untuk pengujian acak program Haskell. sumber

Verifikasi jaringan saraf

Pemecah kendala membuktikan bahwa untuk setiap masukan dalam suatu wilayah, keluaran jaringan saraf tetap dalam batas, bukan menguji sampel.

Pertanyaan yang dijawabnya: Bisakah perubahan kecil pada masukan membuat jaringan memberi jawaban yang salah?

Mengabaikan: Bukti hanya berskala ke jaringan kecil, dan himpunan gangguan yang bisa diperiksa sempit.

Berjalan di: sekitar 10¹³ FLOPS kasar jam hingga hari di server untuk jaringan kecil.Sejak: 2017 Reluplex Katz dan rekan, pemecah SMT untuk memverifikasi jaringan saraf dalam. sumber

Simulasi arsitektur komputer

Pipeline, cache, dan prediktor cabang sebuah prosesor yang diusulkan dimodelkan instruksi demi instruksi, untuk memperkirakan kecepatan cip sebelum dibuat.

Pertanyaan yang dijawabnya: Seberapa cepat rancangan prosesor ini menjalankan program nyata, sebelum silikon apa pun dipotong?

Mengabaikan: Menyederhanakan cukup banyak dari chip nyata sehingga silikon akhir selalu sedikit berbeda dari model.

Berjalan di: sekitar 10¹¹ FLOPS kasar klaster universitas yang menjalankan program tolok ukur melalui modelSejak: 1990 paling lambat 1990, simulator prosesor akurat siklus untuk riset arsitektur

Simulasi sistem terdistribusi dan konsensus

Banyak komputer dimodelkan saling mengirim pesan dengan penundaan, kehilangan, dan kegagalan, untuk menguji apakah algoritma terdistribusi tetap bersepakat pada jawaban yang benar.

Pertanyaan yang dijawabnya: Apakah algoritma ini tetap mencapai kesepakatan yang benar saat pesan hilang, tertunda, atau simpul macet?

Mengabaikan: Kegagalan yang disuntikkan adalah yang diantisipasi perancang, bukan yang muncul tak terduga di produksi.

Berjalan di: sekitar 10¹⁰ FLOPS kasar klaster yang mensimulasikan ratusan simpul virtualSejak: 1978 Karya awal Lamport tentang pengurutan dan kegagalan dalam sistem terdistribusi

Simulasi sistem penyimpanan

Disk, drive, dan sistem berkas dimodelkan menurut cara mereka menata data, gagal, dan pulih, untuk menguji desain penyimpanan sebelum drive sungguhan dibeli dan diisi.

Pertanyaan yang dijawabnya: Bagaimana desain penyimpanan ini berkinerja dan bertahan dari kegagalan, pada skala yang terlalu mahal untuk diuji sungguhan lebih dulu?

Mengabaikan: Drive nyata gagal dengan cara yang lebih berantakan dan lebih berkorelasi daripada laju kegagalan acak model.

Berjalan di: sekitar 10¹⁰ FLOPS kasar workstation hingga klaster kecil yang memodelkan susunan penyimpananSejak: 1988 paling lambat 1988, model simulasi keandalan susunan disk

Simulasi penjadwal sistem operasi

Aliran tugas komputasi dimodelkan datang dan bersaing memperebutkan prosesor, dijalankan dengan aturan penjadwalan yang berbeda untuk melihat mana yang paling adil atau tercepat.

Pertanyaan yang dijawabnya: Cara mengurutkan antrean tugas mana yang menyelesaikan pekerjaan terbanyak, atau paling adil bagi setiap tugas?

Mengabaikan: Beban kerja sintetis jarang cocok dengan campuran tugas yang tidak teratur yang dihadapi mesin sungguhan.

Berjalan di: sekitar 10⁹ FLOPS kasar berjalan di laptop atau workstation dalam hitungan detik hingga menitSejak: 1968 paling lambat 1968, studi simulasi kebijakan penjadwalan prosesor

Pencarian optimisasi kompiler dan program

Sangat banyak variasi kecil dari sepotong kode dicoba dan diukur, mencari versi tercepat atau terpendek yang tetap melakukan pekerjaan yang sama.

Pertanyaan yang dijawabnya: Dari semua cara setara untuk menulis potongan kode kecil ini, mana yang sebenarnya tercepat?

Mengabaikan: Program yang ditemukan kadang begitu tak lazim sehingga tak ada penjelasan mengapa ia bekerja.

Berjalan di: sekitar 10¹⁰ FLOPS kasar klaster yang mencari di ruang besar varian kodeSejak: 2006 paling lambat 2006, pencarian superoptimisasi atas urutan instruksi pendek

Pengujian empiris kinerja algoritma

Algoritma dijalankan ribuan kali pada masukan acak atau dunia nyata dengan ukuran yang makin besar, mengukur bagaimana waktu jalannya benar-benar tumbuh, bukan membuktikannya di atas kertas.

Pertanyaan yang dijawabnya: Bagaimana waktu jalan algoritma ini sebenarnya bertambah dalam praktik, pada masukan yang akan benar-benar dilihatnya?

Mengabaikan: Kasus terburuk yang tidak ada dalam masukan uji tetap tak terdeteksi sampai benar-benar terjadi.

Berjalan di: sekitar 10⁹ FLOPS kasar berjalan di workstation atas banyak masukan uji yang dibangkitkanSejak: 1970 paling lambat 1970, pengujian empiris sistematis atas waktu jalan algoritma

Eksekusi program oleh model bahasa

Model bahasa menuliskan keadaan-keadaan antara langkah demi langkah saat menelusuri apa yang akan dihitung sebuah program.

Pertanyaan yang dijawabnya: Bisakah model bahasa mengemulasi kode yang berjalan?

Mengabaikan: Keluarannya tidak dijamin benar, dan program panjang gagal.

Berjalan di: sekitar 10¹⁴ FLOPS kasar Inferensi per kueriSejak: 2021 Show your work: scratchpads for intermediate computation with language models (2021) sumber

Simulasi konsensus blockchain

Jaringan simpul yang memproduksi dan membagikan blok di bawah penundaan, untuk menguji bagaimana ukuran blok, waktu, dan penyerang memengaruhi keamanan dan throughput.

Pertanyaan yang dijawabnya: Seberapa aman dan cepat sebuah blockchain di bawah penundaan jaringan dan serangan?

Mengabaikan: Perilaku simpul dan topologi jaringan nyata hanya sebagian terukur.

Berjalan di: sekitar 10⁸ FLOPS kasar simulasi berbasis peristiwa dengan ribuan simpul.Sejak: 2016 Analisis keamanan dan kinerja blockchain bukti kerja dengan simulator oleh Gervais dan rekan-rekannya. sumber

Simulasi peristiwa diskret paralel

Simulasi peristiwa dalam waktu dibagi ke banyak prosesor yang masing-masing memajukan jamnya sendiri dan mundur jika ada yang datang terlambat.

Pertanyaan yang dijawabnya: Bagaimana simulasi besar berbasis peristiwa, seperti jaringan atau medan pertempuran, bisa berjalan cepat di banyak mesin?

Mengabaikan: Pemutaran balik bisa berkaskade, dan percepatannya sangat bergantung pada seberapa erat peristiwa saling terkait.

Berjalan di: sekitar 10¹⁴ FLOPS kasar jam di superkomputer untuk miliaran peristiwa.Sejak: 1985 Waktu virtual Jefferson, mekanisme Time Warp untuk sinkronisasi optimistis. sumber

Simulasi arsitektur prosesor grafis

Inti, warp, dan memori prosesor grafis dimodelkan siklus demi siklus, menjalankan program sungguhan untuk menilai sebuah desain sebelum dibangun.

Pertanyaan yang dijawabnya: Bagaimana perubahan rancangan akan memengaruhi kecepatan program paralel pada chip grafis?

Mengabaikan: Detail cip sungguhan dirahasiakan atau tidak diketahui, sehingga model hanya kira-kira cocok dengan angka desain yang ada.

Berjalan di: sekitar 10¹² FLOPS kasar jam hingga hari waktu host per detik eksekusi yang disimulasikan.Sejak: 2009 Analisis Bakhoda dan rekan-rekannya atas beban kerja CUDA memakai simulator GPU terperinci. sumber

Simulasi sistem yang dipercepat FPGA

Desain cip dimuat ke banyak sirkuit yang dapat dikonfigurasi ulang, yang menjalankannya persis siklus demi siklus pada kecepatan megahertz, mensimulasikan seluruh server dan jaringannya.

Pertanyaan yang dijawabnya: Bagaimana prosesor ini dan klasternya akan berperilaku menjalankan perangkat lunak nyata, sebelum dibuat?

Mengabaikan: Ia jauh lebih lambat daripada chip aslinya, dan rancangan yang tidak muat di sirkuitnya tidak bisa dijalankan.

Berjalan di: sekitar 10¹⁵ FLOPS kasar berhari-hari di cloud berisi ratusan sirkuit yang dapat dikonfigurasi ulang.Sejak: 2018 FireSim oleh Karandikar dan rekan, simulasi sistem skala besar tepat siklus berakselerasi FPGA di cloud publik. sumber

Simulasi seluruh sistem

Seluruh komputer, dengan prosesor, memori, disk, dan kartu jaringan, disimulasikan cukup baik untuk mem-boot sistem operasi tanpa modifikasi dan menjalankan programnya.

Pertanyaan yang dijawabnya: Bagaimana perangkat lunak nyata berperilaku di mesin yang belum ada, atau yang bisa dijeda dan diputar ulang sesuka hati?

Mengabaikan: Pewaktuan didekati demi kecepatan, sehingga tidak bisa memberi kinerja yang persis, hanya perilaku fungsionalnya.

Berjalan di: sekitar 10¹¹ FLOPS kasar hampir waktu nyata di server per mesin tersimulasi.Sejak: 2002 Simics oleh Magnusson dan rekan, platform simulasi sistem penuh. sumber

Emulasi jaringan ringan

Puluhan atau ratusan host dan switch virtual menjalankan perangkat lunak jaringan sungguhan di satu laptop, dihubungkan oleh kabel yang diemulasikan dengan kecepatan dan penundaan tertentu.

Pertanyaan yang dijawabnya: Akankah program kendali jaringan ini bekerja pada seluruh topologi sebelum dikerahkan?

Mengabaikan: Prosesor inang dibagi oleh semua simpul virtual, sehingga tautan cepat diperlambat.

Berjalan di: sekitar 10¹⁰ FLOPS kasar waktu nyata di satu workstation.Sejak: 2010 Lantz, Heller, dan McKeown, 'A network in a laptop', pembuatan prototipe cepat untuk jaringan yang ditentukan perangkat lunak. sumber

Simulated annealing

Komputer mendinginkan model atom atau sebuah desain secara perlahan, sesekali menerima susunan yang lebih buruk, untuk menemukan solusi yang baik bagi masalah optimisasi yang sulit.

Pertanyaan yang dijawabnya: Apa tata letak atau jadwal yang mendekati terbaik di antara kemungkinan yang jumlahnya astronomis?

Mengabaikan: Ia tidak menjamin jawaban terbaik, dan hasilnya bergantung pada jadwal pendinginan.

Berjalan di: sekitar 10¹² FLOPS kasar jam di workstation untuk satu penempatan chip.Sejak: 1983 Optimasi dengan simulated annealing oleh Kirkpatrick, Gelatt, dan Vecchi. sumber

Komputasi Bayesian aproksimasi

Simulator dijalankan dengan banyak nilai parameter percobaan, dan yang menghasilkan data mendekati data pengamatan dipertahankan, memberi gambaran nilai mana yang masuk akal.

Pertanyaan yang dijawabnya: Pengaturan model rumit mana yang bisa menghasilkan data yang kita amati?

Mengabaikan: Hasilnya bergantung pada ringkasan data mana yang dipakai dan seberapa dekat kecocokan agar dianggap sah.

Berjalan di: sekitar 10¹³ FLOPS kasar jutaan simulasi dengan simulator di klaster.Sejak: 1997 Inferensi waktu koalesensi dari data urutan DNA dengan simulasi oleh Tavaré dan rekan. sumber