Placement based multiplier rewiring for cell-based designs

ABSTRACT

We present an algorithm for improving the performance of Carry-Save-Adder (CSA) style multipliers. Based on placement information, the algorithm exploits the arithmetic equivalence in the CSA multipliers and rewires to improve the slack of the multiplier.

REFERENCES

• 1: C. S. Wallace, "A suggestion for a fast multiplier", IEEE Trans. On Computers, vol. 13, 1964, pages 14--17.
• 2: L. Dadda, "Some schemes for parallel multipliers", Alta Frequenza, vol. 34, 1965, pages 349--356.
• 3: L. Dadda, "On parallel digital multipliers", Alta Frequenza, vol. 45, 1976, pages 574--580.
• 4: W. J. Townsend, E. E. Swartzlander, Jr., and J. A. Abraham, "A comparison of Dadda and Wallace multiplier delays", Advanced Signal Processing Algorithms, Architectures and Implementations XIII. Proceedings of the SPIE, vol. 5205, 2003, pages 552--560.
• 5: J. Hopcroft and R. M. Karp, "An n5/2 algorithm for maximum matchings in bipartite graphs", SIAM Journal. Computing, 2(4), 1973, pages 225--231.
• 6: Jarrod A. Roy , David A. Papa , Saurabh N. Adya , Hayward H. Chan , Aaron N. Ng , James F. Lu , Igor L. Markov, Capo: robust and scalable open-source min-cut floorplacer, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055184]
• 7: William Swartz , Carl Sechen, Timing driven placement for large standard cell circuits, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.211-215, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217531]
• 8: Vojin G. Oklobdzija , David Villeger , Simon S. Liu, A Method for Speed Optimized Partial Product Reduction and Generation of Fast Parallel Multipliers Using an Algorithmic Approach, IEEE Transactions on Computers, v.45 n.3, p.294-306, March 1996 [doi>10.1109/12.485568]
• 9: Charles Martel , Vojin Oklobdzija , R. Ravi , Paul Stelling, Design Strategies for Optimal Multiplier Circuits, Proceedings of the 12th Symposium on Computer Arithmetic, p.42, July 19-21, 1995
• 10: Junhyung Um , Taewhan Kim, Layout-aware synthesis of arithmetic circuits, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513971]
• 11: Keoncheol Shin , Taewhan Kim, Tight integration of timing-driven synthesis and placement of parallel multiplier circuits, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.7, p.766-775, July 2004 [doi>10.1109/TVLSI.2004.830914]
• 12: Automatic Generation of Tree Multipliers Using Placement-Driven Netlists, Proceedings of the 1999 IEEE International Conference on Computer Design, p.285, October 10-13, 1999
• 13: L. P. P. P. van Ginneken, "Buffer Placement in Distributed RC-Tree Networks for Minimal Elmore Delay", International Symposium on Circuits and Systems, 1990, pages 865--868.
• 14: Ingmar Neumann , Wolfgang Kunz, Placement driven retiming with a coupled edge timing model, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California