Data independence of read, write, and control structures in PRAM computations

We introduce the notions of control and communication structures in PRAM co mputations and relate them to the concept of data independence. Our main re sult is to characterize differences between unbounded fan-in parallelism AC (k), bounded fan-in parallelism NCk, and the sequential classes DSPACE(log n) and LOGDCFL in terms of a PRAM's communication structure sind instructio n set. Our findings give a concrete indication that in parallel computation s writing is more powerful than reading. Further characterizations are give n for parallel pointer machines and the semiunbounded fan-in circuit classe s SAC(k). In particular, we obtain the first characterizations of NCk and D SPACE(log n) in terms of PRAMs. Finally, we introduce Index-PRAMs, which in some sense have built-in data independence. We propose Index-PRAMs as a to ol for the development of data-independent parallel algorithms. Index-PRAMs serve for studying the essential differences between the above mentioned c omplexity classes with respect to the underlying instruction set used. (C) 2000 Academic Press.