Dependence flow graphs: an algebraic approach to program dependencies

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Dependence flow graphs: an algebraic approach to program dependencies

Full text

Pdf (1.30 MB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

Orlando, Florida, United States

Pages: 67 - 78

Year of Publication: 1991

ISBN:0-89791-419-8

Authors

Keshav Pingali	Department of Computer Science, Cornell University, Ithaca, NY
Micah Beck	Department of Computer Science, Cornell University, Ithaca, NY
Richard Johnson	Department of Computer Science, Cornell University, Ithaca, NY
Mayan Moudgill	Department of Computer Science, Cornell University, Ithaca, NY
Paul Stodghill	Department of Computer Science, Cornell University, Ithaca, NY

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 57, Citation Count: 18

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/99583.99595 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AA89	Zena Ariola , Arvind, P-TAC: a parallel intermediate language, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.230-242, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99388]
	Ack84	W. B. Ackerman, EFFICIENT IMPLEMENTATION OF APPLICATIVE LANGUAGES, Massachusetts Institute of Technology, Cambridge, MA, 1984
	AH82	Marc Auslander , Martin Hopkins, An overview of the PL.8 compiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.22-31, June 23-25, 1982, Boston, Massachusetts, United States
	AM87	Andrew W. Appel , David B. MacQueen, A standard ML compiler, Proc. of a conference on Functional programming languages and computer architecture, p.301-324, October 1987, Portland, Oregon, United States
	ANP89	Arvind , Rishiyur S. Nikhil , Keshav K. Pingali, I-structures: data structures for parallel computing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.598-632, Oct. 1989 [doi>10.1145/69558.69562]
	ASU86	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	Ber66	A.J. Bernstein. Analysis of programs for parallel processing. IEEE Transactions on Computers, 1(5):757-762, October 1966.
	BMO90	Karl J. Ottenstein , Robert A. Ballance , Arthur B. MacCabe, The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages, ACM SIGPLAN Notices, v.25 n.6, p.257-271, Jun. 1990
	BP89	M. Beck and K. Pingali. From control flow to dataflow. Technical Report TR89-1050, Cornell University, October 1989.
	BP90	Micah Beck and Keshav Pingali. From control flow to dataflow. In Proceedings of the 1990 International Conference on Parallel Processing, August 1990.
	CC77	Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
	CC79	Patrick Cousot , Radhia Cousot, Systematic design of program analysis frameworks, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.269-282, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567778]
	CF89	E. Cartwright , M. Felleisen, The semantics of program dependence, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.13-27, June 19-23, 1989, Portland, Oregon, United States
	CFR+89	R. Cytron , J. Ferrante , B. K. Rosen , M. N. Wegman , F. K. Zadeck, An efficient method of computing static single assignment form, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-35, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75280]
	Den74	J. B. Dennis, First version of a data flow procedure language, Programming Symposium, Proceedings Colloque sur la Programmation, p.362-376, April 09-11, 1974
	Eka90	K. Ekanadham. Kudos. IBM Yorktown Heights, 1990.
	FOW87	Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
	Kil73	Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
	Kuc78	David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
	Man81	Zohar Manna, Introduction to Mathematical Theory of Computation, McGraw-Hill, Inc., New York, NY, 1974
	PBJ+90	Keshav Pingali , Micah Beck , Richard C. Johnson , Mayan Moudgill , Paul Stodghill, Dependence Flow Graphs: An Algebraic Approach to Program Dependencies, Cornell University, Ithaca, NY, 1990
	Plo81	Gordon D. Plotkin. A structural approach to operational semantics. Technical Report DAIMI FN-19, Aarhus University, 1981.
	PW86	David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
	RL77	John H. Reif , Harry R. Lewis, Symbolic evaluation and the global value graph, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.104-118, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512961]
	Ste78	Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
	Tra86	K. R. Traub, A COMPILER FOR THE MIT TAGGED-TOKEN DATAFLOW ARCHITECTURE, Massachusetts Institute of Technology, Cambridge, MA, 1986
	WZ84	Mark N. Wegman , Frank Kenneth Zadeck, Constant propagation with conditional branches, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.291-299, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318659]

CITED BY 18

	Han-Saem Yun , Jihong Kim , Soo-Mook Moon, Optimal software pipelining of loops with control flows, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA
	Isabelle Attali , Denis Caromel , Sidi Ould Ehmety, A natural semantics for Eiffel dynamic binding, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.6, p.711-729, Nov. 1996
	Marina Chen , James Cowie, Prototyping Fortran-90 compilers for massively parallel machines, ACM SIGPLAN Notices, v.27 n.7, p.94-105, July 1992
	Richard Johnson , Keshav Pingali, Dependence-based program analysis, ACM SIGPLAN Notices, v.28 n.6, p.78-89, June 1993
	Keshav Pingali , Gianfranco Bilardi, APT: a data structure for optimal control dependence computation, ACM SIGPLAN Notices, v.30 n.6, p.32-46, June 1995
	Han-Saem Yun , Jihong Kim , Soo-Mook Moon, Time optimal software pipelining of loops with control flows, International Journal of Parallel Programming, v.31 n.5, p.339-391, October 2003
	C.-R. Dow , S.-K. Chang , M. L. Soffa, A visualization system for parallelizing programs, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.194-203, November 16-20, 1992, Minneapolis, Minnesota, United States
	Li-Ling Chen , Williams Ludwell Harrison, III, An efficient approach to computing fixpoints for complex program analysis, Proceedings of the 8th international conference on Supercomputing, p.98-106, July 11-15, 1994, Manchester, England
	Dorit Naishlos , Marina Biberstein , Shay Ben-David , Ayal Zaks, Vectorizing for a SIMdD DSP architecture, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA
	J. H. Moreno , V. Zyuban , U. Shvadron , F. D. Neeser , J. H. Derby , M. S. Ware , K. Kailas , A. Zaks , A. Geva , S. Ben-David , S. W. Asaad , T. W. Fox , D. Littrell , M. Biberstein , D. Naishlos , H. Hunter, An innovative low-power high-performance programmable signal processor for digital communications, IBM Journal of Research and Development, v.47 n.2-3, p.299-326, March 2003
	Wolfram Amme , Peter Braun , François Thomasset , Eberhard Zehendner, Data Dependence Analysis of Assembly Code, International Journal of Parallel Programming, v.28 n.5, p.431-467, Oct. 2000
	Mihai Budiu , Girish Venkataramani , Tiberiu Chelcea , Seth Copen Goldstein, Spatial computation, ACM SIGARCH Computer Architecture News, v.32 n.5, December 2004
	Gianfranco Bilardi , Keshav Pingali, Algorithms for computing the static single assignment form, Journal of the ACM (JACM), v.50 n.3, p.375-425, May 2003
	Alexander Aiken , Alexandru Nicolau , Steven Novack, Resource-Constrained Software Pipelining, IEEE Transactions on Parallel and Distributed Systems, v.6 n.12, p.1248-1270, December 1995
	Mark M. Mathis , Darren J. Kerbyson , Adolfy Hoisie, A performance model of non-deterministic particle transport on large-scale systems, Future Generation Computer Systems, v.22 n.3, p.324-335, February 2006
	David A. Berson , Rajiv Gupta , Mary Lou Soffa, GURRR: a global unified resource requirements representation, ACM SIGPLAN Notices, v.30 n.3, p.23-34, March 1993
	Ross Tate , Michael Stepp , Zachary Tatlock , Sorin Lerner, Equality saturation: a new approach to optimization, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
	Mohammad Zalfany Urfianto , Tsuyoshi Isshiki , Arif Ullah Khan , Dongju Li , Hiroaki Kunieda, Decomposition of Task-Level Concurrency on C Programs Applied to the Design of Multiprocessor SoC, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.7, p.1748-1756, July 2008