Programming language constructs for highly parallel operations on lists

✍ Scribed by Jon A. Solworth

• Publisher: Springer US
• Year: 1988
• Tongue: English
• Weight: 839 KB
• Volume: 2
• Category: Article
• ISSN: 0920-8542
• DOI: 10.1007/bf00129783

✦ Synopsis

A data structure called ~trips is described for representing linked lists, which enables unit time access of random list elements. Running parallel prefix on strips effectively converts a list into an array. When combined with nondeterministic statement sequencing and data operations, loops for performing iterations over lists, and insertions and deletions on lists can be parallelized ~ielding very efficient algorithms. The strips-based representation also allows efficient serial operations on lists, which is important both when loops cannot be parallelized or when there is more parallelism than processors.