Safe Approximation of Data Dependencies in Pointer-Based Structures

D.K. Arvind; T.A. Lewis

doi:10.1007/3-540-45574-4_20

Safe Approximation of Data Dependencies in Pointer-Based Structures

D.K. Arvind, T.A. Lewis

School of Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

This paper describes a new approach to the analysis of dependencies in complex, pointer-based data structures. Structural information is provided by the programmer in the form of two-variable finite state automata (2FSA). Our method extracts data dependencies. For restricted forms of recursion, the data dependencies can be exact; however in general, we produce approximate, yet safe (i.e. overestimates dependencies) information. The analysis method has been automated and results are presented in this paper.

Original language	English
Title of host publication	Languages and Compilers for Parallel Computing
Subtitle of host publication	13th International Workshop, LCPC 2000 Yorktown Heights, NY, USA, August 10–12, 2000 Revised Papers
Editors	Samuel P. Midkiff, José E. Moreira, Manish Gupta, Siddhartha Chatterjee, Jeanne Ferrante, Jan Prins, William Pugh, Chau-Wen Tseng
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	304-323
Number of pages	20
ISBN (Print)	978-3-540-45574-5
DOIs	https://doi.org/10.1007/3-540-45574-4_20
Publication status	Published - Dec 2001

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin Heidelberg
Volume	2017
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/3-540-45574-4_20

http://dx.doi.org/10.1007/3-540-45574-4_20

Cite this

Arvind, D. K., & Lewis, T. A. (2001). Safe Approximation of Data Dependencies in Pointer-Based Structures. In S. P. Midkiff, J. E. Moreira, M. Gupta, S. Chatterjee, J. Ferrante, J. Prins, W. Pugh, & C.-W. Tseng (Eds.), Languages and Compilers for Parallel Computing: 13th International Workshop, LCPC 2000 Yorktown Heights, NY, USA, August 10–12, 2000 Revised Papers (pp. 304-323). (Lecture Notes in Computer Science; Vol. 2017). Springer. https://doi.org/10.1007/3-540-45574-4_20

Arvind, D.K. ; Lewis, T.A. / Safe Approximation of Data Dependencies in Pointer-Based Structures. Languages and Compilers for Parallel Computing: 13th International Workshop, LCPC 2000 Yorktown Heights, NY, USA, August 10–12, 2000 Revised Papers. editor / Samuel P. Midkiff ; José E. Moreira ; Manish Gupta ; Siddhartha Chatterjee ; Jeanne Ferrante ; Jan Prins ; William Pugh ; Chau-Wen Tseng. Berlin, Heidelberg : Springer, 2001. pp. 304-323 (Lecture Notes in Computer Science).

@inproceedings{4720458fba644df2a9074018d86b36ec,

title = "Safe Approximation of Data Dependencies in Pointer-Based Structures",

abstract = "This paper describes a new approach to the analysis of dependencies in complex, pointer-based data structures. Structural information is provided by the programmer in the form of two-variable finite state automata (2FSA). Our method extracts data dependencies. For restricted forms of recursion, the data dependencies can be exact; however in general, we produce approximate, yet safe (i.e. overestimates dependencies) information. The analysis method has been automated and results are presented in this paper.",

author = "D.K. Arvind and T.A. Lewis",

year = "2001",

month = dec,

doi = "10.1007/3-540-45574-4_20",

language = "English",

isbn = "978-3-540-45574-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "304--323",

editor = "Midkiff, {Samuel P.} and Moreira, {Jos{\'e} E.} and Manish Gupta and Siddhartha Chatterjee and Jeanne Ferrante and Jan Prins and William Pugh and Chau-Wen Tseng",

booktitle = "Languages and Compilers for Parallel Computing",

address = "United Kingdom",

}

Arvind, DK & Lewis, TA 2001, Safe Approximation of Data Dependencies in Pointer-Based Structures. in SP Midkiff, JE Moreira, M Gupta, S Chatterjee, J Ferrante, J Prins, W Pugh & C-W Tseng (eds), Languages and Compilers for Parallel Computing: 13th International Workshop, LCPC 2000 Yorktown Heights, NY, USA, August 10–12, 2000 Revised Papers. Lecture Notes in Computer Science, vol. 2017, Springer, Berlin, Heidelberg, pp. 304-323. https://doi.org/10.1007/3-540-45574-4_20

Safe Approximation of Data Dependencies in Pointer-Based Structures. / Arvind, D.K.; Lewis, T.A.
Languages and Compilers for Parallel Computing: 13th International Workshop, LCPC 2000 Yorktown Heights, NY, USA, August 10–12, 2000 Revised Papers. ed. / Samuel P. Midkiff; José E. Moreira; Manish Gupta; Siddhartha Chatterjee; Jeanne Ferrante; Jan Prins; William Pugh; Chau-Wen Tseng. Berlin, Heidelberg: Springer, 2001. p. 304-323 (Lecture Notes in Computer Science; Vol. 2017).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Safe Approximation of Data Dependencies in Pointer-Based Structures

AU - Arvind, D.K.

AU - Lewis, T.A.

PY - 2001/12

Y1 - 2001/12

N2 - This paper describes a new approach to the analysis of dependencies in complex, pointer-based data structures. Structural information is provided by the programmer in the form of two-variable finite state automata (2FSA). Our method extracts data dependencies. For restricted forms of recursion, the data dependencies can be exact; however in general, we produce approximate, yet safe (i.e. overestimates dependencies) information. The analysis method has been automated and results are presented in this paper.

AB - This paper describes a new approach to the analysis of dependencies in complex, pointer-based data structures. Structural information is provided by the programmer in the form of two-variable finite state automata (2FSA). Our method extracts data dependencies. For restricted forms of recursion, the data dependencies can be exact; however in general, we produce approximate, yet safe (i.e. overestimates dependencies) information. The analysis method has been automated and results are presented in this paper.

U2 - 10.1007/3-540-45574-4_20

DO - 10.1007/3-540-45574-4_20

M3 - Conference contribution

SN - 978-3-540-45574-5

T3 - Lecture Notes in Computer Science

SP - 304

EP - 323

BT - Languages and Compilers for Parallel Computing

A2 - Midkiff, Samuel P.

A2 - Moreira, José E.

A2 - Gupta, Manish

A2 - Chatterjee, Siddhartha

A2 - Ferrante, Jeanne

A2 - Prins, Jan

A2 - Pugh, William

A2 - Tseng, Chau-Wen

PB - Springer

CY - Berlin, Heidelberg

ER -

Arvind DK, Lewis TA. Safe Approximation of Data Dependencies in Pointer-Based Structures. In Midkiff SP, Moreira JE, Gupta M, Chatterjee S, Ferrante J, Prins J, Pugh W, Tseng CW, editors, Languages and Compilers for Parallel Computing: 13th International Workshop, LCPC 2000 Yorktown Heights, NY, USA, August 10–12, 2000 Revised Papers. Berlin, Heidelberg: Springer. 2001. p. 304-323. (Lecture Notes in Computer Science). doi: 10.1007/3-540-45574-4_20

Safe Approximation of Data Dependencies in Pointer-Based Structures

Abstract

Publication series

Access to Document

Fingerprint

Cite this