Optimizing Pipelined Networks of Associative and Commutative Operators

Abstract

A method of tree-height minimization of networks of commutative and associative operators is described. The algorithm aims at minimizing latency and shimming delays in a synchronous data flow architecture such as that used in bit/digit-serial computation. The algorithm rearranges adder/subtractor trees to meet the joint goals, often allowing otherwise impossible scheduling constraints to be met. The algorithmic methods are found to apply also to trees of adders and shifters, such as those found in shift/add multipliers. Show more