Tree-height minimization in pipelined architectures

A method of tree-height minimization for networks of commutative and associative operators is proposed. An algorithm is described for minimizing latency and shimming delays in a synchronous data-flow architecture such as that used in pipelined or bit- or digit-serial computation. The algorithm rearranges operator trees to meet the joint goals, often allowing otherwise impossible scheduling constraints to be met. It may also be applied to word-parallel pipelined architectures to optimize operator trees within pipelined stages. The method is evaluated by testing it on several filter examples for which it finds optimal network topologies and schedules.<>