Abstract
Constraint-based frameworks can provide a foundation for efficient algorithms for analysis and transformation of regular scientific programs. For example, we recently demonstrated that constraint-based analysis of both memory- and value-based array dependences can often be performed in polynomial time. Many of the cases that could not be processed with our polynomial-time algorithm involved negated equality constraints (also known as disequalities).
In this report, we review the sources of disequality constraints in array dependence analysis and give an efficient algorithm for manipulating certain disequality constraints. Our approach differs from previous work in that it performs efficient satisfiability tests in the presence of disequalities, rather than deferring satisfiability tests until more constraints are available, performing a potentially exponential transformation, or approximating. We do not (yet) have an implementation of our algorithms, or empirical verification that our test is either fast or useful, but we do provide a polynomial time bound and give our reasons for optimism regarding its applicability.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Pugh, W., Wonnacott, D.: Constraint-based array dependence analysis. ACM Trans. on Programming Languages and Systems 20(3), 635–678 (1998)
Seater, R., Wonnacott, D.: Polynomial time array dataflow analysis. In: Proceedings of the 14th International Workshop on Languages and Compilers for Parallel Computing (August 2001)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)
Maydan, D.E., Hennessy, J.L., Lam, M.S.: Efficient and exact data dependence analysis. In: ACM SIGPLAN 1991 Conference on Programming Language Design and Implementation, June 1991, pp. 1–14 (1991)
Kelly, W., Maslov, V., Pugh, W., Rosser, E., Shpeisman, T., Wonnacott, D.: The Omega Library interface guide. Technical Report CS-TR-3445, Dept. of Computer Science, University of Maryland, College Park (March 1995), The Omega library is available from http://www.cs.umd.edu/projects/omega
Lassez, J.-L., McAloon, K.: Independence of negative constraints. In: Díaz, J., Orejas, F. (eds.) TAPSOFT 1989 and CCIPL 1989. LNCS, vol. 352. Springer, Heidelberg (1989)
Kreisel, G., Krevine, J.L.: Elements of Mathematical Logic. North-Holland Pub. Co., Amsterdam (1967)
Shostak, R.E.: A practical decision procedure for arithmetic with function symbols. Journal of the ACM 26(2), 351–360 (1979)
Wonnacott, D.G.: Constraint-Based Array Dependence Analysis. PhD thesis, Dept. of Computer Science, The University of Maryland (August 1995), Available as ftp://ftp.cs.umd.edu/pub/omega/davewThesis/davewThesis.ps
Imbert, J.-L.: Variable elimination for disequations in generalized linear constraint systems. The Computer Journal 36(5), 473–484 (1993), Special Issue on Variable Elimination
Pugh, W., Wonnacott, D.: An exact method for analysis of value-based array data dependences. In: Banerjee, U., Gelernter, D., Nicolau, A., Padua, D.A. (eds.) LCPC 1993. LNCS, vol. 768. Springer, Heidelberg (1994)
Gu, J., Li, Z., Lee, G.: Experience with efficient array data flow analysis for array privatization. In: Proceedings of the 6th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Las Vegas, Nevada, June 1997, pp. 157–167 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Seater, R., Wonnacott, D. (2005). Efficient Manipulation of Disequalities During Dependence Analysis. In: Pugh, B., Tseng, CW. (eds) Languages and Compilers for Parallel Computing. LCPC 2002. Lecture Notes in Computer Science, vol 2481. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11596110_20
Download citation
DOI: https://doi.org/10.1007/11596110_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30781-5
Online ISBN: 978-3-540-31612-1
eBook Packages: Computer ScienceComputer Science (R0)