Motiverade av den betydligt högre kostnaden för att skriva än att läsa i nya minnestekniker, anser vi parallell algoritmdesign under sådana asymmetriska läs- och skrivkostnader, med målet att minska antalet skrifter samtidigt som arbetseffektivitet och låg spännvidd bevaras. Vi presenterar en inbäddad modell av beräkning som kombinerar (i) små stack-allokerade minnen med symmetriska avläsningskostnader och (ii) ett obundet hög-allokerat delat minne med asymmetriska avläsningskostnader, och visar hur kostnaderna i modellkartan effektivt på en mer betong maskinmodell under en arbets-stjälkning schemaläggare. Vi använder den nya modellen för att designa reducerade skriv-, arbets-effektiva, lågspann parallella algoritmer för ett antal grundläggande problem såsom minska, lista sammandragning, träd kontraktion, bredd-första sökning, beställda filter, och planar konvex skrov. För de senare två problemen, våra algoritmer är output-känsliga genom att arbetet och antalet skriver minska med utdatastorleken. Vi presenterar också en reducerad skriv-, låg-spann minimum spanning trädalgoritm som är nästan arbetseffektiv (av av den inversa Ackermann-funktionen). Våra algoritmer avslöjar flera intressanta tekniker för att avsevärt minska delat minne skriver i parallella algoritmer utan att asymptotiskt öka antalet delade minnesavläsningar.
För parallella algoritmer använder vi modellen REF (Asymmetric Nested-Parallel), som är utformad för att karakterisera både parallellism och memory read-write asymmetri.
Parallel Algorithms for Asymmetric Read-Write Costs
{'venue': "SPAA '16", 'journal': None, 'mag_field_of_study': ['Computer Science']}