Apa yang memotivasi model RAM?

Aug 17 2020

Sepertinya sebagian besar analisis algoritme saat ini dilakukan dalam model dengan akses acak waktu konstan, seperti kata model RAM. Saya tidak tahu banyak tentang fisika, tetapi dari sumber populer saya pernah mendengar bahwa seharusnya ada batasan penyimpanan informasi per volume dan kecepatan perjalanan informasi, sehingga RAM tampaknya tidak dapat disadari secara fisik. Komputer modern memiliki semua level cache ini yang menurut saya membuatnya tidak seperti RAM. Jadi mengapa algoritme teoretis harus diatur dalam RAM?

Jawaban

3 6005 Aug 18 2020 at 13:47

Izinkan saya memberikan pandangan yang berbeda dari vonbrand. Semua yang Anda katakan benar: model RAM tidak realistis karena sejumlah alasan, dan meskipun dimungkinkan untuk mempertahankan aspek yang berbeda darinya, pertahanan seperti itu tidak benar-benar menyentuh inti permasalahan.

Inti masalahnya - dan jawaban atas pertanyaan Anda - adalah bahwa model RAM adalah hal terbaik yang kami miliki. Dibandingkan dengan model lain yang diterima, model ini lebih akurat memodelkan komputasi kehidupan nyata. Secara khusus, alasan kami mengadopsi model RAM terutama karena respons terhadap mesin Turing, karena kami menemukan bahwa penggunaan mesin Turing menyebabkan masalah yang secara artifisial sulit dipecahkan dalam hal kompleksitas waktu. Model RAM dengan jelas memecahkan masalah mencolok ini, dan dengan demikian telah diterima, meskipun masih jauh dari sempurna.

Contoh klasik yang menggambarkan masalah mencolok dengan mesin Turing adalah masalah persamaan string: masukan yang diberikan

$$ w_1 \# w_2$$

dimana $w_1, w_2$ adalah urutan biner dan $\#$ adalah pemisah, menentukan apakah $w_1 = w_2$. Dapat ditunjukkan bahwa mesin Turing apa pun untuk masalah kesetaraan membutuhkan$O(n^2)$waktu. Ini tidak nyaman, karena mesin Turing adalah apa yang semua orang anggap sebagai model komputasi universal - namun tidak ada insinyur perangkat lunak atau peneliti algoritme yang percaya bahwa kesetaraan string benar-benar diperlukan.$O(n^2)$waktu. Jadi apa yang menyebabkannya? Persamaan string harus linier, jadi kami menemukan model baru di mana itu, dan solusi terbaik yang tersedia saat ini adalah mesin RAM kata.

Mungkin suatu hari nanti kita akan menghasilkan model yang lebih baik - model yang sederhana, jelas secara konseptual, dan meningkatkan kemampuan RAM untuk memodelkan kompleksitas komputasi kehidupan nyata. Untuk saat ini, kita hanya bisa melakukan yang terbaik yang kita miliki.

1 vonbrand Aug 17 2020 at 23:02

Sebagai pendekatan pertama, kasar, Anda dapat meluangkan waktu untuk mengakses kata dalam memori sebagai sesuatu yang konstan, tidak bergantung pada akses sebelumnya. Yakni model RAM.

Anda benar, mesin saat ini sangat tidak seperti RAM, itu memang terbayar (bahkan mahal) untuk mengatur akses data menjadi sekuensial mungkin atau mencicit informasi terakhir dari segmen memori (pendek!) Sebelum menangani selanjutnya. Tetapi Anda jarang memiliki kelonggaran untuk melakukannya, akses memori Anda pada dasarnya acak dan modelnya tidak terlalu jauh dari kebenaran. Ditambah mesin saat ini memiliki lebih dari satu CPU, model hanya memiliki satu. Dan kemudian ada pemrosesan vektor (melakukan operasi yang sama pada data vektor, tidak satu per satu) seperti yang dilakukan "instruksi multimedia" (dan bahkan lebih banyak menggunakan kartu grafis untuk pemrosesan).

Sedikit diskusi diberikan misalnya oleh pencarian Biner Khoung adalah kasus patologis untuk cache . Seperti yang Anda lihat, menganalisis algoritme yang sederhana dan dipahami dengan baik di bawah model waktu akses memori yang lebih realistis memang menakutkan.

1 DmitriUrbanowicz Aug 19 2020 at 10:19

Model RAM dimotivasi oleh analisis asimtotik algoritme yang dirancang sebagai komputasi dalam memori utas tunggal.

Mengoptimalkan kinerja untuk set instruksi tertentu, cache dan yang lainnya adalah satu hal. Hal lainnya adalah bersiap untuk pertumbuhan ukuran masalah. Untuk memperkirakan seberapa baik algoritme dalam memori Anda berskala, Anda mungkin ingin mengabaikan faktor kecil dan fokus pada faktor besar$\mathcal{O}$notasi. Besar$\mathcal{O}$ tidak akan mengoptimalkan segalanya untuk Anda, tetapi setidaknya ini dapat memberi tahu Anda bahwa solusi Anda berskala baik (atau Anda harus mencoba sesuatu yang berbeda).

RAM mengasumsikan set instruksi tetap kecil, di mana setiap operasi bekerja $\mathcal{O}(1)$. Perhatikan bahwa ini adalah model yang baik jika kita hanya peduli pada pertumbuhan asimtotik:

  1. Set instruksi dari CPU modern tidak kecil, tetapi kita dapat berpura-pura bahwa itu sebenarnya. Kode-op tambahan tersebut tidak membuat perbedaan besar$\mathcal{O}$ notasi.

  2. CPU mungkin memiliki instruksi yang runtime-nya bergantung pada input. Sekali lagi, kita bisa mengabaikannya, karena kita bisa memodelkannya menggunakan instruksi yang lebih sederhana tanpa mempengaruhi besar$\mathcal{O}$kompleksitas. Hal yang sama berlaku untuk level cache: kinerjanya masih dibatasi oleh beberapa konstanta kecil, sehingga berfungsi$\mathcal{O}(1)$ Menurut definisi.

  3. Ya, Anda tidak dapat mengakses memori dalam waktu yang konstan jika terus bertambah. Untungnya, ini tidak pernah diperlukan berkat akal sehat. Tidak ada yang mengindeks seluruh Internet ke dalam memori non-persisten dari mesin single-threaded yang sunyi.