Parallelizing programs with recursive data structures

Author

Hendren, Laurie J. ; Nicolau, Alexandru

Author_Institution

Dept. of Comput. Sci., Cornell Univ., Ithaca, NY, USA

Volume

1

Issue

1

fYear

1990

fDate

1/1/1990 12:00:00 AM

Firstpage

35

Lastpage

47

Abstract

A study is made of the problem of estimating interference in an imperative language with dynamic data structures. The authors focus on developing efficient and implementable methods for recursive data structures. In particular, they present interference analysis tools and parallelization techniques for imperative programs that contain dynamically updatable trees and directed acyclic graphs. The analysis methods are based on a regular-expression-like representation of the relationship between accessible nodes in the data structure. They authors have implemented their analysis, and they present some concrete examples that have been processed by this system

Keywords

data structures; directed graphs; parallel programming; program compilers; trees (mathematics); accessible nodes; automatic parallelization; directed acyclic graphs; disambiguation techniques; dynamic data structures; dynamically updatable trees; imperative language; imperative programs; interference; interference analysis tools; parallel programming languages; parallelization techniques; parallelizing compilers; recursive data structures; regular-expression-like representation; Computer languages; Computer science; Concurrent computing; Data structures; Information analysis; Interference; Parallel processing; Parallel programming; Program processors; Programming profession;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.80123

Filename

80123