Pre-synthesis optimization of multiplications to improve circuit performance

ABSTRACT

Conventional high-level synthesis uses the worst case delay to relate all inputs to all outputs of an operation. This is a very conservative approximation of reality, especially in arithmetic operations (where some bits are required later than others and some bits are produced earlier than others). This paper proposes a pre-synthesis optimization algorithm that takes advantage of this feature for more efficient high-level synthesis of data-flow graphs formed by additions and multiplications. The presented pre-processor analyzes the critical path at bit-granularity and splits the arithmetic operations into sub-words fragments. In particular, some of the specification multiplications are broken up into several smaller multiplications, additions, and other operations of three new types specially defined to reduce the clock cycle duration. These fragments become the input to any regular high-level synthesis tool to speed up circuit execution times. The experimental results carried out show that implementations obtained from the optimized specification are on average 70% faster and in most cases substantial area reductions are also achieved.

REFERENCES

• 1: Zhan Yu , Kei-Yong Khoo , Alan N. Willson, Jr., The use of carry-save representation in joint module selection and retiming, Proceedings of the 37th conference on Design automation, p.768-773, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337773]
• 2: V. Raghunathan, S. Ravi, and G. Lakshminarayana. "Integrating Variable-Latency Components into High-Level Synthesis". IEEE Transactions on Computer Aided Design, October 2000.
• 3: Jianwen Zhu , Daniel D. Gajski, Soft scheduling in high level synthesis, Proceedings of the 36th ACM/IEEE conference on Design automation, p.219-224, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309917]
• 4: S. Park, and K. Choi. "Performance-Driven High-Level Synthesis with Bit-Level Chaining and Clock Selection". IEEE Transactions on Computer Aided Design, February 2001.
• 5: P. Marwedel, B. Landwehr, and R. Dömer. "Built-in Chaining: Introducing Complex Components into Architectural Synthesis". In Proc. of Asia Pacific Design Automation Conference, ASPDAC 1997.
• 6: M. C. Molina , J. M. Mendías , R. Hermida, Bit-level scheduling of heterogeneous behavioural specifications, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.602-608, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774661]
• 7: R. Ruiz-Sautua , M. C. Molina , J. M. Mendias , R. Hermida, Behavioural Transformation to Improve Circuit Performance in High-Level Synthesis, Proceedings of the conference on Design, Automation and Test in Europe, p.1252-1257, March 07-11, 2005 [doi>10.1109/DATE.2005.81]
• 8: N. Dutt, "High-level Synthesis Workshop Benchmarks". Univ. California, Irvine, CA, Technical Report, 1992.