Bagaimana menurunkan hasil kompleksitas paralel ke banyak core secara konstan?

20

Saya mengalami masalah dalam menerima pandangan teoritik kompleksitas "dipecahkan secara efisien oleh algoritma paralel" yang diberikan oleh kelas NC :

NC adalah kelas masalah yang dapat diselesaikan dengan algoritma paralel dalam waktu pada prosesor dengan .p ( n ) O ( n k ) c , k NO(logcn)p(n)O(nk)c,kN

Kita dapat menganggap PRAM .

Masalah saya adalah bahwa ini sepertinya tidak banyak bicara tentang mesin "nyata", yaitu mesin dengan jumlah prosesor yang terbatas. Sekarang saya diberitahu bahwa "diketahui" bahwa kita dapat "secara efisien" mensimulasikan algoritma prosesor prosesor .p NO(nk)pN

Apa yang dimaksud dengan "efisien" di sini? Apakah cerita rakyat ini atau adakah teorema yang keras yang mengkuantifikasi overhead yang disebabkan oleh simulasi?

Apa yang saya khawatirkan terjadi adalah bahwa saya mempunyai masalah yang memiliki algoritma sekuensial dan juga algoritma paralel "efisien" yang, ketika disimulasikan pada prosesor , juga membutuhkan waktu (yang adalah semua yang dapat diharapkan pada tingkat analisis granularitas ini jika algoritma sekuensial optimal asimtotik). Dalam hal ini, tidak ada speedup apa pun sejauh yang bisa kita lihat; pada kenyataannya, algoritma paralel yang disimulasikan mungkin lebih lambat daripada algoritma sekuensial. Itu adalah saya benar-benar mencari pernyataan yang lebih tepat daripada batas- (atau pernyataan tidak adanya hasil seperti itu).p O ( n k )O(nk)pO(nk)O

Raphael
sumber
Teorema Brent?
cic
Apakah maksud Anda Tp<Wp+D? Jika demikian, ini (afaik) hanya berlaku dalam keadaan tertentu dan juga tidak segera memungkinkan untuk menerjemahkan runtimes. Atau jika ya, jelaskan jawabannya.
Raphael
NC menjawab pertanyaan "apakah mungkin untuk menukar lebih banyak perangkat keras dengan waktu yang lebih singkat?" Anda mungkin ingin membatasi diri Anda pada perangkat keras yang konstan dan ini mirip dengan membatasi diri Anda pada memori yang konstan, pemodelan yang lebih baik dari beberapa masalah. Untuk penggunaan praktis, lihat carry addhead lookers, lebih banyak perangkat keras sehingga penambahan bit dilakukan di O ( N ) . NO(N)
Pemrogram

Jawaban:

13

Jika Anda menganggap bahwa jumlah prosesor dibatasi oleh konstanta, maka Anda benar bahwa masalah yang ada di NC tidak banyak berarti dalam praktiknya. Karena setiap algoritma pada PRAM dengan prosesor k dan t waktu paralel dapat disimulasikan dengan RAM prosesor tunggal dalam waktu O ( kt ), waktu paralel dan waktu berurutan dapat berbeda hanya dengan faktor konstan jika k adalah konstanta.

Namun, jika Anda berasumsi bahwa Anda dapat menyiapkan komputer dengan lebih banyak prosesor saat ukuran input bertambah, maka masalah berada di NC berarti bahwa selama Anda dapat menyiapkan lebih banyak prosesor, waktu pengoperasian akan “sangat singkat” atau, lebih tepatnya, polylogarithmic dalam ukuran input. Jika Anda berpikir bahwa asumsi ini tidak realistis, bandingkan dengan asumsi memori tidak terbatas: komputer yang sebenarnya hanya memiliki jumlah ruang terbatas, tetapi dalam studi algoritma dan kompleksitas, kami hampir selalu menganggap bahwa perangkat komputasi tidak memiliki bagian atas yang konstan. terikat pada ruang. Dalam praktiknya, ini berarti bahwa kita dapat menyiapkan komputer dengan memori lebih banyak saat ukuran input bertambah, yang biasanya kita gunakan di dunia nyata. NC memodelkan situasi analog dalam komputasi paralel.

Tsuyoshi Ito
sumber
1
Okk/2k1n20
Raphael
4
@ Raphael: Pertanyaan apakah masalah tertentu milik NC atau tidak tidak memodelkan pertanyaan Anda. Saya tidak mengatakan bahwa pertanyaan Anda tidak menarik; Saya hanya mengatakan bahwa NC bukan kelas kompleksitas yang tepat untuk memodelkan itu.
Tsuyoshi Ito
Saya sebenarnya senang mendengarnya; seseorang mengklaim sebaliknya. Tidak harus dengan NC tetapi dengan hasil teori kompleksitas pada umumnya. Bagaimana dengan kelas lain?
Raphael
O(n)O(logn)
@ Jeffe: Itu bukan koreksi. Saya hanya menulis "menyiapkan lebih banyak prosesor" tanpa memberikan maknanya yang ketat (karena saya pikir hal itu akan mengaburkan intinya).
Tsuyoshi Ito
10

NC

p=1NC

Tapi tunggu, masih ada lagi.

NC

PO(nϵ),0<ϵ<1NCnnn<lg3nn0.5×109NC

Dalam salah satu jawaban, telah diamati bahwa "Dalam prakteknya, ini berarti bahwa kita dapat menyiapkan komputer dengan lebih banyak memori seiring dengan bertambahnya ukuran input, yaitu bagaimana kita biasanya menggunakan komputer di dunia nyata. NC memodelkan situasi analog dalam perhitungan paralel ".

Saya sebagian setuju dengan sudut pandang ini. Kami membeli komputer paralel baru dengan lebih banyak memori ketika superkomputer yang lebih lama dinonaktifkan juga karena chip DRAM lebih murah pada waktu dan untuk menyeimbangkan komputer paralel sehubungan dengan komponen utamanya (prosesor, memori, interkoneksi dll).

pnp

Oleh karena itu, semakin penting untuk merancang algoritma paralel yang dapat diskalakan memori, karena ini praktis untuk masalah besar.

n3n

Massimo Cafaro
sumber