Department of Computer Science,
University of California at Santa Barbara
Santa Barbara, CA 93106-5110
Abstract
Two operations commute if they generate the same result regardless of the
order in which they execute. Commutativity is an important property ---
commuting operations enable significant optimizations in the fields of
parallel computing, optimizing compilers, parallelizing compilers and
database concurrency control. Algorithms that statically decide if
operations commute can be an important component of systems in these
fields because they enable the automatic application of these optimizations.
In this paper we define the commutativity decision problem and establish
its complexity for a variety of basic instructions and control constructs.
Although deciding commutativity is, in general, undecidable or
computationally intractable, we believe that efficient algorithms exist
that can solve many of the cases that arise in practice.