Batas untuk Komputasi Paralel

Saya ingin tahu dalam arti luas tentang apa yang diketahui tentang memparalelkan algoritma dalam P. Saya menemukan artikel wikipedia berikut tentang subjek:

http://en.wikipedia.org/wiki/NC_%28complexity%29

Artikel tersebut berisi kalimat berikut:

Tidak diketahui apakah NC = P, tetapi sebagian besar peneliti menduga ini salah, yang berarti bahwa mungkin ada beberapa masalah yang bisa dilacak yang "secara inheren berurutan" dan tidak dapat secara signifikan dipercepat dengan menggunakan paralelisme

Apakah ini masuk akal? Apakah ada kasus yang diketahui di mana masalah dalam P tidak dapat dipercepat menggunakan paralelisme?

Bahkan tidak diketahui apakah NC = P, tetapi masalah P-complete tampaknya sulit untuk diparalelkan. Ini termasuk Linear Programming dan Horn-SAT. (Sebaliknya, masalah di NC tampaknya cukup mudah diparalelkan.)

Lihat pertanyaan Masalah antara NC dan P: Berapa banyak yang telah diselesaikan dari daftar ini? untuk bahan referensi (termasuk tautan ke buku teks klasik yang sekarang tersedia untuk diunduh gratis), dan diskusi lebih lanjut tentang masalah yang ada di P tetapi tidak diketahui dapat diparalelkan.

Lihat pertanyaan Teorema Generalized Ladner untuk struktur kelas kompleksitas antara NC dan P. Secara singkat, jika mereka berbeda maka ada banyak kelas kompleksitas yang sangat jauh antara NC dan P.

Lihat pertanyaan NC = P konsekuensi? untuk demonstrasi yang bagus oleh Ryan Williams bahwa dimungkinkan untuk memperbesar keruntuhan dalam hierarki kelas kompleksitas dalam P ke dalam keruntuhan yang mungkin lebih tidak mungkin seperti PSPACE = EXP .

Perlu menunjukkan bahwa salah satu konsekuensi dari Horn-SAT menjadi P-complete, dan tautan di atas, adalah bahwa tampaknya tidak mungkin untuk memaralelkan kueri SQL umum dalam basis data, kecuali kita juga dapat menulis ulang perhitungan skala besar untuk hanya menggunakan jumlah penyimpanan yang wajar. Ini adalah perbedaan yang membingungkan - saya pikir itu cukup tidak kontroversial untuk menyatakan ada batasan pada kompresi , tetapi saya sering melihat artikel yang tampaknya dibangun dengan asumsi bahwa mungkin untuk memparalelkan kueri basis data apa pun .

Nah, jika ada kasus yang diketahui, maka kita akan dapat memisahkan P dan NC. Tetapi ada banyak masalah yang dikenal sebagai P-complete (yaitu di bawah pengurangan logspace), dan mereka menghadirkan jenis hambatan yang sama untuk menunjukkan P = NC seperti masalah NP-complete untuk P = NP. Di antara mereka termasuk pemrograman linier dan pencocokan (dan aliran maks pada umumnya).

Ketan Mulmuley membuktikan hasil yang memisahkan P dan bentuk NC yang lemah (tanpa operasi bit) pada tahun 1994. Dalam beberapa hal, programnya saat ini untuk P vs NP lepas landas dari tempat yang ditinggalkan ( dengan cara yang sangat longgar ).

Buku ' Limits on Parallel Computation ' memiliki lebih banyak tentang ini.

Saya menjawab pertanyaan yang sama Apakah ada masalah / algoritma terkenal dalam komputasi ilmiah yang tidak dapat dipercepat oleh paralisis di situs Ilmu Komputasi . Biarkan saya kutip di sini, karena ia menawarkan perspektif praktis pada contoh yang sangat konkret dari masalah seperti itu:

Metode marching cepat (terkenal) untuk memecahkan persamaan Eikonal tidak dapat dipercepat dengan paralelisasi. Ada metode lain (misalnya metode penyapuan cepat) untuk menyelesaikan persamaan Eikonal yang lebih dapat menerima paralelisasi, tetapi bahkan di sini potensi percepatan (paralel) terbatas.

Masalah dengan persamaan Eikonal adalah bahwa arus informasi tergantung pada solusi itu sendiri. Secara longgar, informasi mengalir sepanjang karakteristik (yaitu sinar cahaya dalam optik), tetapi karakteristik tergantung pada solusi itu sendiri. Dan aliran informasi untuk persamaan Eikon yang didiskritisasi bahkan lebih buruk, membutuhkan perkiraan tambahan (seperti yang secara implisit hadir dalam metode penyapuan cepat) jika ada peningkatan paralel yang diinginkan.

Untuk melihat kesulitan untuk paralelisasi, bayangkan labirin yang bagus seperti dalam beberapa contoh di halaman web Sethian . Jumlah sel pada jalur terpendek melalui labirin (mungkin) adalah batas bawah untuk jumlah minimal langkah / iterasi dari setiap algoritma (paralel) yang memecahkan masalah yang sesuai.

(Saya menulis "(mungkin) adalah", karena batas bawah terkenal sulit untuk dibuktikan, dan seringkali memerlukan beberapa asumsi yang masuk akal pada operasi yang digunakan oleh suatu algoritma.)