ABSTRACT
In analysis of programs and many other kinds of computation, algorithms are commonly written to have an input P and an output Q, where both P and Q are large and complicated objects. For example, P might be a routing problem and Q might be a solution to P. Although documented and discussed in this exhaustive style, algorithms are sometimes intended for use in contexts with two departures from the one-time analysis of an entire new input. First, the current value of P is the result of a small change to a previous value of P. We want to update the results of the previous analysis without redoing all of the work. Second, accurate information is only wanted in some designated portion of the large output Q. Possibly inaccurate information may appear elsewhere in Q. We want the analysis to be demand-driven: accurate where accuracy is demanded, but not burdened by the cost of providing much more than is demanded. This paper studies demand-driven algorithms capable of updating without extensive reanalysls. Such algorithms are called incremental, in contrast with the one-time analysis of an entire new input contemplated by exhaustive algorithms. In some cases, it is shown that an exhaustive algorithm can be easily recast in an efficient incremental style. Other algorithms for the same problem may be much less amenable to incremental use. It is shown that traditional exhaustive computational complexity bounds are poor predictors of incremental performance. The main examples are taken from global data flow analysis.
- AC76. Allen, F. E., and Cocke, J. A program data flow analysis procedure. Comm. ACM19 (1976), 137-147. Google ScholarDigital Library
- AS78. Auslander, M. A., and Strong, H. R. Systematic recursion removal. Comm. ACM21 (1978), 127-134. Google ScholarDigital Library
- BJ78a. Babich, W. A., and Jazayeri, M. The method of attributes for data flow analysis (Part I. Exhaustive analysis). Acta Informatica10 (1978), 245-264.Google Scholar
- BJ78b. Babich, W. A., and Jazayeri, M. The method of attributes for data flow analysis (Part II. Demand analysis). Acta Informatica10 (1978), 265-272.Google Scholar
- Ca77. Carter, J. L. A case study of a new code generating technique for compilers. Comm. ACM20 (1977), 914-920. Google ScholarDigital Library
- GM79. Ghezzi, C., and Mandrioli, D. Incremental parsing. ACM Trans. on Programming Languages and Systems1 (1979), 58-70. Google ScholarDigital Library
- GM80. Ghezzi, C., and Mandrioli, D. Augmenting parsers to support incrementality. J. ACM27 (1980), 564-579. Google ScholarDigital Library
- GW76. Graham, S. L., and Wegman, M. A fast and usually linear algorithm for global flow analysis. J. ACM23 (1976), 172-202. Google ScholarDigital Library
- HU75. Hecht, M. S., and Ullman, J. D. A simple algorithm for global data flow analysis problems. SIAM J. Computing4 (1975), 519-532.Google Scholar
- Ke75. Kennedy, K. W. Node listings applied to data flow analysis. Proc. 2nd ACM Symp. on Principles of Programming Languages (January 1975), 10-21. Google ScholarDigital Library
- Mo79. Moriconi, M. S. A designer/verifier's assistant. IEEE Trans. on Software Engineering5 (1979), 387-401.Google Scholar
- Pa79. Paige, R. Expression continuity and the formal differentiation of algorithms. Ph. D. Thesis, New York University, September 1979. Google ScholarDigital Library
- Ro77. Rosen, B. K. Applications of high-level control flow. Proc. 4th ACM Symp. on Principles of Programming Languages (January 1977), 38-47. Google ScholarDigital Library
- Ro80. Rosen, B. K. Monoids for rapid data flow analysis. SIAM J. Computing9 (1980), 159-196.Google Scholar
- TR80. Teitelbaum, T., and Reps, T. The Cornell Program Synthesizer: a syntax-directed programming environment. TR 80-421, Computer Sci. Dept., Cornell University, Ithaca NY, May 1980.Google Scholar
- Weg80. Wegman, M. N. Parsing for a structural editor. Proc. 21st IEEE Symp. on Foundations of Computer Science (October, 1980).Google ScholarDigital Library
Recommendations
On linear conic relaxation of discrete quadratic programs
Dedicated to the memory of Professor Xiaoling Sun 1963–2014A special reformulation-linearization technique based linear conic relaxation is proposed for discrete quadratic programming DQP. We show that the proposed relaxation is tighter than the traditional positive semidefinite programming relaxation. More ...
A Lifted Linear Programming Branch-and-Bound Algorithm for Mixed-Integer Conic Quadratic Programs
This paper develops a linear-programming-based branch-and-bound algorithm for mixed-integer conic quadratic programs. The algorithm is based on a known higher-dimensional or lifted polyhedral relaxation of conic quadratic constraints. The algorithm is ...
An efficient compact quadratic convex reformulation for general integer quadratic programs
We address the exact solution of general integer quadratic programs with linear constraints. These programs constitute a particular case of mixed-integer quadratic programs for which we introduce in Billionnet et al. (Math. Program., 2010) a general ...
Comments