Chong, Han dan Lam menunjukkan bahwa st-konektivitas tanpa arah dapat diselesaikan pada EREW PRAM dalam waktu dengan prosesor O ( m + n ) . Apa algoritma paralel paling dikenal untuk st-konektivitas diarahkan ? Silakan sebutkan waktu berjalan, algoritma deterministik / acak dan model PRAM yang digunakan (dengan asumsi jumlah prosesor adalah polinomial). Apakah ada algoritma paralel waktu o ( log 2 n ) yang dikenal untuk kasus khusus konektivitas st langsung?
dc.parallel-comp
Siwa Kintali
sumber
sumber
Jawaban:
Keterjangkauan yang terarah dapat dengan mudah dilakukan menggunakan prosesor O ( ) dan waktu O ( log n ) pada CRCW-PRAM, atau dalam prosesor O ( n ω ) dan waktu O ( log 2 n ) pada EREW-PRAM di mana ω < 2.376 adalah eksponen perkalian matriks dan n adalah jumlah simpul. Makalah berikut ini mengklaim O ( n ω ) dan O ( log nn3 (logn nω log2n ω<2.376 n nω logn ) waktu pada CREW-PRAM: "Algoritma Paralel Optimal untuk Penutupan Transitif dan Lokasi Titik dalam Struktur Planar" oleh Tamassia dan Vitter. Makalah lain mengklaim hal yang sama dan mengutip survei Karp dan Ramachandran (Algoritma paralel untuk mesin memori bersama, dalam: J. van Leeuwen (Ed.), Handbook of Theoretical Computer Science). Survei itu sendiri menyebutkan bahwa penutupan transitif ada dalam AC1 dan karenanya dapat diselesaikan dalam waktu O (log n) pada CRCW-PRAM, tetapi bagian tentang CREW-PRAM tidak ada.
Semua algoritma seperti Strassen untuk perkalian matriks (termasuk yang oleh Coppersmith-Winograd) pada dasarnya adalah algoritma paralel yang berjalan dalam waktu O ; Penutupan transitif menghasilkan log ekstra (tetapi jika Anda mengizinkan kipas tanpa batas dalam matriks O ( n 3 ) sepele, mult dapat dilakukan dalam kedalaman konstan dan karenanya jangkauannya dalam waktu O ( log n ) pada CRCW-PRAM). Ini masalah terbuka untuk meningkatkan jumlah prosesor dari yang terbaik saat ini ~ n 2,376 ; itu juga merupakan masalah terbuka utama jika jangkauan di NC1, karena akan menyiratkan L = NL di antara hal-hal lain.(logn) n3 (logn) n2.376
sumber
Buku "An Introduction to Parallal Algorithms" oleh Joseph Jája (1992) berisi daftar hasil berikut untuk penutupan transitif:
sumber
Apakah Anda peduli untuk menjaga pekerjaan kecil, bukan hanya jumlahnya banyak, ada algoritma yang elegan oleh Ullman dan Yannakakis yang memungkinkan pertukaran waktu / pekerjaan. Tabel 1 dalam makalah saya tentang komputasi komponen yang sangat terhubung secara paralel merangkum hasil konektivitas diarahkan paralel yang saya ketahui: http://www.cs.brown.edu/~ws/papers/scc.pdf .
sumber