Some Techniques for Algorithm Optimization with Application to Matrix Arithmetic Expressions

摘要

Algorithm optimization can be accomplished by an exhaustive search over alternative algorithms for performing some programming task. The resulting algorithms are optimum only with respect to a program technology--the particular set of alternatives investigated. Thus, larger program technologies can be expected to yield better algorithms. This thesis contributes to the production of optimum algorithms in two ways. First, a technique ('loop-fusion') was developed for producing new algorithms equivalent to old algorithms, and thus expanding program technologies. Second, a technique ('comparison') is described which reduces the effort required by certain exhaustive searches over 'well-structured' search spaces. These techniques are applied to the production of algorithms for evaluating matrix arithmetic expressions (MAE). (The operators, + and *, in such arithmetic expressions are interpreted as matrix addition and multiplication, respectively.) A method is described for producing, for any MAE, an algorithm for its evaluation which requires fewest arrays for holding N by N matrices, while not requiring more execution time than the 'standard' MAE evaluation algorithm. Although the algorithm-production method used is basically an exhaustive-search over a large space of program alternatives for each subexpression of the given MAE, the effort this method requires grows only linearly with the number of operators in the given expression. (Author)