Arithmetic Circuit Architectures and Optimization

Ajay Kumar Verma, PhD Assistant, Processor Architecture Laboratory, EPFL

 

Abstract: Part 1 - Towards the automatic exploration of arithmetic-circuit architectures: Logic synthesis has made impressive progresses in the last decade and has pervaded digital design replacing almost universally manual techniques. A remarkable exception is computer arithmetic and datapath design, where designers still rely mostly on well-studied architectures; on datapaths, in most cases, logic synthesis plays at most a minor role in the optimization of netlists. A case in point are multiple additions performed in carry-save form, such as those fundamentally constituting parallel multipliers: column compressors are usually built exploiting the regularity of the circuit and, due to the very large number of XOR operations, are hardly optimized further by logic synthesizers. In fact, due to the shortcomings of algebraic factoring, XOR operations are usually left untouched by logic synthesizers except in the simplest cases. In this paper we show a general technique to optimize XOR dominated circuits and we demonstrate its effectiveness on multiplier-like circuits. We show that it optimizes significantly the best parallel multipliers by exploiting complex dependencies between the addenda that escape known manual optimizations. Netlists corresponding to top arithmetic architectures can either be synthesized directly or preprocessed through our technique before standard logic synthesis: our preprocessing stage makes it possible to achieve some 27% speed improvement for a mere 17% area cost. To our best knowledge, optimizations of the type we show for multiplier-like structures have never been reported-neither manually derived, in computer arithmetic literature, nor automatically derived, in design automation literature.

Part 2 - Improving XOR-dominated arithmetic circuits by exploiting dependencies between operands: The optimization of arithmetic circuits has always been essentially a manual task: arithmetic experts study the best architectures for arithmetic components and write libraries of generators, and designers instantiate library components and rely on logic synthesizers to obtain good implementations. In this paper we look at the capabilities of commercial synthesizers when it comes to arithmetic circuits, and observe that they are essentially unable to switch from one arithmetic architecture to another (e.g., from a ripple-carry to a carry-lookahead adder). Therefore, users relying on logic synthesis miss most optimization potentials. We therefore investigate algorithms for factorization that can prepare structured VHDL or Verilog for synthesizers to implement, and show first steps into pruning the search space from many irrelevant or equivalent solutions. Our results are still very limited in complexity but we show that our techniques successfully concentrate on the automatic exploration of very different solutions, and discover architectures known and unknown to expert designers, such as different types of adders, the carry-save representation, or improved multipliers. This is a first step toward a class of arithmetic optimizers that sit on top of classic logic synthesizers.

About the speaker: Ajay Kumar Verma completed his B. Tech in computer science from Indian Institute of Technology, Kanpur in May 2003. He joined EPFL as a PhD student in January 2004, and is currently working as a PhD Assistant with Prof. Paolo Ienne in the Processor Architecture Laboratory (LAP).