Optimal chaining in expression trees (Preliminary Version)

Abstract

Chaining is the ability to pipeline two or more vector instructions on Cray-1 like machines. We show how to optimally use this feature to compute (vector) expression trees, in the context of automatic code-generation. We present a lineartime scheduling algorithm for finding an optimal order of evaluation for a machine with a bounded number of registers.