I den här artikeln visar vi hur parallella algoritmer kan omvandlas till effektiva streamingalgoritmer för flera klassiska kombinatoriska problem i W-Stream-modellen. I denna modell, vid varje pass en ingångsström läses, en utgångsström skrivs, och dataobjekt måste behandlas med hjälp av begränsat utrymme; strömmar rörs på ett sådant sätt att den utgående ström som produceras vid pass i anges som ingångsström vid pass i + 1. Vi introducerar först en simuleringsteknik som gör det möjligt att omvandla effektiva PRAM-algoritmer till optimala W-Stream-algoritmer, för många klassiska kombinatoriska problem, inklusive listrankning och Eulerturné i ett träd. För andra problem, främst graf problem, dock denna teknik leder till suboptimala algoritmer. För att övervinna denna svårighet introducerar vi beräkningsmodellen Relaxed PRAM (RPRAM), som en mellanmodell mellan PRAM och W-Stream. RPRAM gör det möjligt för varje processor att komma åt ett icke-konstant antal minnesceller per parallell runda, om än med vissa begränsningar. RPRAM-modellen, samtidigt som den är kraftfullare än PRAM-modellen, kan simuleras i W-Stream inom samma asymptotiska gränser. Den extra kraft som tillhandahålls av RPRAM gör att vi i många fall avsevärt kan minska antalet processorer, samtidigt som samma antal parallella rundor bibehålls, vilket leder till effektivare W-Stream-simuleringar av parallella algoritmer. Vår RPRAM-teknik ger nya insikter om att utveckla streamingalgoritmer och ger effektiva algoritmer för flera klassiska problem i denna modell, inklusive sortering, konnektivitet, minsta spännviddsträd, bianslutna komponenter och maximal oberoende uppsättning. Förutom att tillåta smidiga rymdpasses kompromisser, våra algoritmer visas också, genom att bevisa nästan tight kommunikation komplexitet-baserade nedre gränser i W-Stream, att vara optimal upp till polylog faktorer.
Demeterscu et al. REF presenterar en simulering av en PRAM-algoritm på W-Stream-modellen, så att befintliga PRAM-algoritmer kan köras sekventiellt i W-Stream-modellen.
Adapting parallel algorithms to the W-Stream model, with applications to graph problems
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}