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

✍ Scribed by Klaus-Jörn Lange; Rolf Niedermeier

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 322 KB
• Volume: 60
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1999.1665

✦ Synopsis

We 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 AC k , bounded fan-in parallelism NC k , and the sequential classes DSPACE(log n) 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 SAC k . In particular, we obtain the first characterizations of NC k and DSPACE(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 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.