Compact Binary Tree Representation of Logic Function with Enhanced Throughput

Authors: Padmanabhan Balasubramanian, C. Ardil

Abstract:

An effective approach for realizing the binary tree structure, representing a combinational logic functionality with enhanced throughput, is discussed in this paper. The optimization in maximum operating frequency was achieved through delay minimization, which in turn was possible by means of reducing the depth of the binary network. The proposed synthesis methodology has been validated by experimentation with FPGA as the target technology. Though our proposal is technology independent, yet the heuristic enables better optimization in throughput even after technology mapping for such Boolean functionality; whose reduced CNF form is associated with a lesser literal cost than its reduced DNF form at the Boolean equation level. For cases otherwise, our method converges to similar results as that of [12]. The practical results obtained for a variety of case studies demonstrate an improvement in the maximum throughput rate for Spartan IIE (XC2S50E-7FT256) and Spartan 3 (XC3S50-4PQ144) FPGA logic families by 10.49% and 13.68% respectively. With respect to the LUTs and IOBUFs required for physical implementation of the requisite non-regenerative logic functionality, the proposed method enabled savings to the tune of 44.35% and 44.67% respectively, over the existing efficient method available in literature [12].

Keywords: Binary logic tree, FPGA based design, Boolean function, Throughput rate, CNF, DNF.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1062576

References:

[1] R. Ashenhurst, "The decomposition of switching functions," Proc. of International Symposium. on Switching Theory, 1959, pp. 74-116.
[2] J. Baer, and D. Bovet, "Compilation of arithmetic expressions for parallel computations," Proc. of IFIP Congress, 1968, pp. 340-346.
[3] J. Beatty, "An axiomatic approach to code optimization for expressions," Journal of ACM, vol. 19(4), 1972, pp. 613-640.
[4] R. Brayton, and C. McMullen, "The decomposition and factorization of Boolean expressions," Proc. of International Symposium on Circuits and Systems, 1982, pp. 49-54.
[5] J. Vasudevamurthy, and J. Rajski, "A method for concurrent decomposition and factorization of Boolean expressions," Proc. of International Conf. on Computed-Aided Design, 1990, pp. 510-513.
[6] D. Kuck, The Structure of Computers and Computation, Wiley, 1978.
[7] K. Singh, A. Wang, R. Brayton, and A. Sangiovanni-Vincentelli, "Timing optimization of combinational logic," Proc. of IEEE/ACM International Conf. on Computer-Aided Design, 1988, pp. 282-285.
[8] K. Chen, and S. Muroga, "Timing optimization for multi-level combinational circuits," Proc. of ACM/IEEE Design Automation Conf., 1990, pp. 339-344.
[9] H.Touati, H.Savoj, and R.Brayton, "Delay optimization of combinational circuits by clustering and partial collapsing," Proc. of IEEE/ACM International Conf. on Computer-Aided Design, 1991, pp. 188-191.
[10] Eric Lehman, and Yosinori Watanabe, "Logic Decomposition during Technology Mapping," Proc. of IEEE/ACM International Conf. on Computer-Aided Design, 1995, pp. 264-271.
[11] E. Lehman, Y. Watanabe, J. Grodstein, and H. Harkness, "Logic decomposition during technology mapping," IEEE Transactions on CAD of Integrated Circuits and Systems, vol. 16(8), August 1997, pp. 813- 834.
[12] J. Cortadella, "Timing-Driven Logic Bi-Decomposition," IEEE Transactions on CAD of Integrated Circuits and Systems, vol. 22(6), June 2003, pp. 675-685.
[13] S. Yamashita, H. Sawada, and A. Nagoya, "New methods to find optimal nondisjoint bi-decompositions," Proc. of ACM/IEEE Design Automation Conf., 1998, pp. 59-68.
[14] A. Mishchenko, B. Steinbach, and M. Perkowski, "An algorithm for bidecomposition of logic functions," Proc. of ACM/IEEE Design Automation Conf., 2001, pp. 282-285.
[15] Zvi Kohavi, Switching and Finite Automata Theory, McGraw Hill, 1999.
[16] Srinivas Devadas, Abhijit Ghosh, and Kurt Kuetzer, Logic Synthesis McGraw-Hill series on Computer Engineering, 1994.
[17] P.C. McGeer, J.V. Sanghavi, R.K. Brayton, and A.L. Sangiovanni- Vincentelli, "ESPRESSO-SIGNATURE: a new exact minimizer for logic functions," IEEE Transactions on VLSI Systems, vol. 1(4), December 1993, pp. 432-440.
[18] S.P. Tomaszewski, I.U. Celik, and G.E. Antoniou, "www based Boolean function minimization," International Journal of Applied Mathematics and Computer Science, vol. 13(4), 2003, pp. 577-583.
[19] Available: http://www.xilinx.com/support/mysupport.htm#Spartan-3