Series-parallel functions and FPGA logic module design

ABSTRACT

The need for a two-way interaction between logic synthesis and FPGA logic module design has been stressed recently. Having a logic module that can implement many functions is a good idea only if one can also give a synthesis strategy that makes efficient use of this functionality. Traditionally, technology mapping algorithms have been developed after the logic architecture has been designed. We follow a dual approach, by focusing on a specific technology mapping algorithm, namely, the structural tree-based mapping algorithm, and designing a logic module that can be mapped efficiently by this algorithm. It is known that the tree-based mapping algorithm makes optimal use of a library of functions, each of which can be represented by a tree of AND, OR, and NOT gates (series-parallel or SP functions). We show how to design a SP function with a minimum number of inputs that can implement all possible SP functions with a specified number of inputs. For instances, we demonstrate a seven-input SP function that can implement all four-input SP functions. Mapping results show that, on an average, the number blocks of this function needed to map benchmark circuits are 12% less than those for Actel's ACT1 logic modules. Our logic modules show a 4% improvement over ACT1, if the block count is scaled to take into account the number of transistors needed to implement different logic modules.

REFERENCES

• 1: ACM 1995. Proceedings of the International Symposium on Field-Programmable Gate Arrays. ACM, New York.
• 2: ACTEL CORP. 1994. FPGA Data Book and Design Guide.
• 3: ALTERA CORP. 1993. Data Book.
• 4: AT&T 1993. Optimized Reconfigurable Cell Array (ORCA) Series Field Programmable Gate Arrays.
• 5: CONG g. AND DING, Y. 1994. An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs. IEEE Trans. CAD/ICAS 13, 1 (Jan.), 1-12.
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: DETJENS, E., GANNOT, a., RUDELL, R., SANGIOVANNI-VINCENTELLI, A., AND WANG, A. 1987. Technology mapping in MIS. In Proceedings of ICCAD, IEEE, 116-119.
• 8: Kevin Karplus, Amap: A technology mapper for selector-based field-programmable gate arrays, Proceedings of the 28th conference on ACM/IEEE design automation, p.244-247, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127673]
• 9: Kevin Karplus, Xmap: A technology mapper for table-lookup field-programmable gate arrays, Proceedings of the 28th conference on ACM/IEEE design automation, p.240-243, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127672]
• 10: KNUTH, D.E. 1973. Fundamental Algorithms, 2nd ed. Addison-Wesley, Reading, MA.
• 11: Chih-chang Lin , Malgorzata Marek-Sadowska , Duane Gatlin, Universal logic gate for FPGA design, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.164-168, November 06-10, 1994, San Jose, California, United States
• 12: R. Murgai , R. K. Brayton , A. L. Sangiovanni-Vincentelli, An improved synthesis algorithm for multiplexor-based PGA's, Proceedings of the 29th ACM/IEEE conference on Design automation, p.380-386, June 08-12, 1992, Anaheim, California, United States
• 13: MURGAI, R., SHENOY, N., BRAYTON, R. K., AND SANGIOVANNI-VINCENTELLI, A.L. 1991. Improved logic synthesis algorithms for table lookup up architectures. In Proceedings of ICCAD, IEEE, 564-567.
• 14: PATT, Y.N. 1973. Optimal and near-optimal universal logic modules with interconnected external terminals. IEEE Trans. Comput. C-22, 10 (Oct.), 903-907.
• 15: PREPARATA, F.P. 1971. On the design of universal Boolean functions. IEEE Trans. Comput. C-20, 4 (April), 418-423.
• 16: PREPARATA, F. P. AND MULLER, D.E.1970. Generation of near-optimal universal Boolean functions. JCCS 4 (April), 93-102.
• 17: Richard L. Rudell , Alberto Sangiovanni-Vincentelli, Logic synthesis for vlsi design, 1989
• 18: Shashidhar Thakur , D. F. Wong, On designing ULM-based FPGA logic modules, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.3-9, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201311]
• 19: XILINX CORP. 1994. The Programmable Logic Data Book.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Combinational logic
      B.6.3 Design Aids

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Experimentation, Performance, Theory, Verification

Keywords:
field programmable gate arrays, series-parallel technology mapping, tree-based technology mapping algorithm, universal logic modules