Data flow analysis of communicating processes

ABSTRACT

Data flow analysis is a technique essential to the compile-time optimization of computer programs, wherein facts relevant to program optimizations are discovered by the global propagation of facts obvious locally.This paper extends flow analysis techniques developed for sequential programs to the analysis of communicating, concurrent processes.

REFERENCES

• 1: Ball, J. E., Williams, G. J. and Low, J. R., "Preliminary ZENO language description", TR41, Computer Science Department, University of Rochester, October 1978.
• 2: Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976 [doi>10.1145/321921.321939]
• 3: Feldman, J. A., "A programming methodology for distributed computing (among other things)", TR9, Computer Science Dept., University of Rochester, Rochester, New York, (1976).
• 4: Per Brinch Hansen, Concurrent Programming Concepts, ACM Computing Surveys (CSUR), v.5 n.4, p.223-245, Dec. 1973 [doi>10.1145/356622.356624]
• 5: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 6: Hecht, M. S. and Ullman, J. D., "Analysis of a simple algorithm for global flow problems", SIAM J. of Computing, Vol. 4, No. 4 (Dec. 1975). pp. 519-532.
• 7: Hoare, C. A. R., "Communicating sequential processes", Computer Science Dept., Queen's University, Belfast (March, 1977).
• 8: Jones, N. D., Landweber, C. H., and Lien, Y. E., "Compexity of some problems in Petri nets" Theoretical Computer Science, No. 4 (1977), pp. 277-309.
• 9: Kam, J. B. and Ullman, J. D., "Monotone data flow analysis frameworks", TR167, Computer Science Dept., Princeton University (Jan. 1976).
• 10: Killdall, G. A., "A unified approach to program optimization", Proc. ACM, Symp. on Principles of Programming Languages (Jan. 1975), pp. 10-21.
• 11: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 12: Lipton, R., "The reachability problem and boundedness problem for Petri nets and exponential-space hard", Conf. on Petri nets and Related Methods, M.I.T. (July, 1975); also Yale Research Report #62, (1976).
• 13: Minsky, M., "Recursive unsolvability of Post's Problem", Ann. of Math., 74 (1961), pp. 437-454.
• 14: James L. Peterson, Petri Nets, ACM Computing Surveys (CSUR), v.9 n.3, p.223-252, Sept. 1977 [doi>10.1145/356698.356702]
• 15: Tarjan, R. E., "Depth-first search and linear graph algorithms", SIAM J. of Computing, Vol. 1, No. 2 (June 1972), pp. 46-100.
• 16: Wegbreit, B., "Property extraction in well-founded property sets", IEEE Trans. on Software Engg. 1, 3, 1975, pp. 270-285.