Title :
Optimal chaining in expression trees
Author :
Bernstein, D. ; Boral, H. ; Pinter, Ron Y.
Author_Institution :
IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA
fDate :
11/1/1988 12:00:00 AM
Abstract :
Chaining is the ability to pipeline two or more vector instructions on Cray-1 like machines. The authors show how to optimally use this feature to compute (vector) expression trees in the context of automatic code generation. They present a linear time scheduling algorithm for finding an optimal order of evaluation for a machine with a bounded number of registers
Keywords :
automatic programming; computational complexity; dynamic programming; parallel programming; pipeline processing; scheduling; Cray-1; automatic code generation; complexity analysis; dynamic programming algorithms; explicit pipelining; expression trees; linear time scheduling algorithm; optimal chaining; vector instructions pipelining; Algorithm design and analysis; Approximation algorithms; Dynamic programming; Linear approximation; Optimal scheduling; Parallel processing; Pipeline processing; Registers; Scheduling algorithm; Vectors;
Journal_Title :
Computers, IEEE Transactions on
