Bagaimana menurunkan hasil kompleksitas paralel ke banyak core secara konstan?

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 . $O(\log^cn)$ $p(n) \in O(n^k)$ $c,k \in \mathbb{N}$

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 . $O(n^k)$ $p \in \mathbb{N}$

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). $O(n^k)$ $p$ $O(n^k)$ $O$

complexity-theory reference-request parallel-computing Raphael
sumber

Teorema Brent?

cic

Apakah maksud Anda

T_{p} < \frac{W}{p} + D

$T_p < \frac{W}{p} + 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

N

$N$

O (N)

$O(N)$

Pemrogram

Jawaban:

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

O

$O$

k

$k$

k / 2

$k/2$

k - 1

$k-1$

n \leq 20

$n \leq 20$

Raphael

@ 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 (\sqrt{n})

$O(\sqrt{n})$

O (\log n)

$O(\log n)$

@ 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

$NC$

$p = 1$ $NC$

Tapi tunggu, masih ada lagi.

$NC$

$P$ $O(n^\epsilon), 0 < \epsilon < 1$ $NC$ $n$ $n$ $\sqrt n < \lg^3 n$ $n \leq 0.5 \times 10^9$ $NC$

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).

$p$ $n$ $p$

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

$n^3$ $n$

Massimo Cafaro
sumber