Data Independence of Read, Write, and Control Structures in PRAM Computations

AbstractWe introduce the notions of control and communication structures in PRAM computations and relate them to the concept of data independence. Our main result is to characterize differences between unbounded fan-in parallelism ACk, bounded fan-in parallelism NCk, and the sequential classes DSPACE(logn) and LOGDCFL in terms of a PRAM's communication structure and instruction set. Our findings give a concrete indication that in parallel computations writing is more powerful than reading. Further characterizations are given for parallel pointer machines and the semiunbounded fan-in circuit classes SACk. In particular, we obtain the first characterizations of NCk and DSPACE(logn) in terms of PRAMs. Finally, we introduce Index-PRAMs, which in some sense have built-in data independence. We propose Index-PRAMs as a tool for the development of data-independent parallel algorithms. Index-PRAMs serve for studying the essential differences between the above mentioned complexity classes with respect to the underlying instruction set used