Algoritma paralel untuk st-konektivitas diarahkan

13

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?O(logn)O(m+n)o(log2n)

Siwa Kintali
sumber
Wikipedia mengatakan poly (n) prosesor + waktu polylog pada PRAM EREW sama dengan NC. Saya tidak terlalu terbiasa dengan model EREW PRAM, tetapi apakah ada hubungan antara waktu (dan banyak prosesor secara polinomi) dan N C i ? Dengan kata lain, apakah ada cara untuk mengulangi pertanyaan Anda dalam hal sirkuit dengan kedalaman terbatas? (logn)iNCi
Robin Kothari
model RAM paralel yang berbeda setara dengan faktor log upto, jadi sementara EREW PRAM cocok dengan NC, ini mungkin tidak berlaku untuk kekuatan log tertentu.
Suresh Venkat
Dengan pembatasan yang tepat pada set intruksi, waktu O (log ^ in) pada PRAM CRCW persis sama dengan AC ^ i, untuk i> = 1.
Kristoffer Arnsfelt Hansen
Jika ada jalur terarah , apakah mungkin menemukannya? st
Kumar

Jawaban:

13

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(lognnωlog2nω<2.376nnω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

virgi
sumber
1
Bisakah Anda menambahkan referensi?
Shiva Kintali
Saya hanya tahu tentang waktu O (log n) pada PRAM CRCW. Itukah yang kamu maksud?
Kristoffer Arnsfelt Hansen
O (logn) di CREW hebat. Itulah yang saya cari. Saya ingin menerima jawaban Anda. Silakan tambahkan referensi.
Shiva Kintali
Kita membutuhkan iterasi (perkalian) dari perkalian matriks untuk menyelesaikan st-konektivitas.
Shiva Kintali
Dalam hal algoritma paralel Anda memang membutuhkan O (log n) iterasi matriks mult untuk menyelesaikan jangkauan; ini bukan kasus untuk algoritma sekuensial karena Anda dapat melakukan beberapa hal rekursif pintar (lihat Fisher & Meyer'71). Namun, jika model komputasi Anda memungkinkan fan-in tanpa batas (seperti halnya AC1 dan karenanya CRCW PRAM), matriks mult dapat dilakukan dalam kedalaman konstan sehingga penutupan transitif dapat dilakukan dalam kedalaman logaritmik.
virgi
7

Buku "An Introduction to Parallal Algorithms" oleh Joseph Jája (1992) berisi daftar hasil berikut untuk penutupan transitif:

  • O(logn)O(n3logn)
  • O(log2n)O(nωlogn)

O(logn)

  • uvuv
Kristoffer Arnsfelt Hansen
sumber
Jadi, tampaknya menemukan algoritma paralel waktu o (log ^ 2 {n}) pada CREW PRAM untuk grafik berarah umum adalah masalah terbuka.
Shiva Kintali
Perhatikan bahwa saya mengatakan o (log ^ 2 {n}) bukan O (log ^ 2 {n}).
Shiva Kintali
5

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 .

Warren Schudy
sumber