Optimal adder-multiplexer co-optimization for time-multiplexed multiplierless architectures

Many digital signal processing (DSP) applications in multimedia, telecommunications, and artificial intelligence require several multiplications, which are considered among the most expensive arithmetic operations. To optimize these operations, several approaches have been proposed, mainly by representing multiplications with additions and bit-shifts. While these approaches may have limited the number of required adders, they have not given much attention to the overhead of multiplexers, which can grow significantly. In this paper, a comprehensive framework is presented that not only reduces the number of adders as in prior works, but also optimizes the number of multiplexers needed in modern DSP architectures. This framework is based on a new accelerated depth first search (A-DFS) algorithm that yields superior results, both for single input single output (SISO) and single input dual output (SIDO) architectures, the latter of which were not covered by existing approaches. At the initial stage of the proposed approach, all possible directed acyclic graph (DAG) multipliers are generated to produce minimum adder graphs of one or two outputs. Then, a systematic strategy to efficiently merge the produced graphs is presented, while preventing the number of multiplexers from growing exponentially as the set of multiplicands increases. Our experimental results show that when applied on several popular fast Fourier transform (FFT) and discrete cosine transform (DCT) coefficient sets, the proposed framework achieves significant savings in terms of the number of required multiplexers, leading to substantial area, power and power-delay-product (PDP) reduction, compared to existing works and a commercial synthesis tool.