Optimal chaining in expression trees. (English) Zbl 0659.68053
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 liner time scheduling algorithm for finding an optimal order of evaluation for a machine with a bounded number of registers.
MSC:
68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
68N99 | Theory of software |
90C39 | Dynamic programming |