Fast module mapping and placement for datapaths in FPGAs

ABSTRACT

By tailoring a compiler tree-parsing tool for datapath module mapping, we produce good quality results for datapath synthesis in very fast run time. Rather than flattening the design to gates, we preserve the datapath structure; this allows exploitation of specialized datapath features in FPGAs, retains regularity, and also results in a smaller problem size. To further achive high mapping speed, we formulate the problem as tree covering and solve it efficiently with a linear-time dynamic programming algorithm. In a novel extension to the tree-covering algorithm, we perform module placement simultaneously with the mapping, still in linear time. Integrating placement has the potential to increase the quality of the result since we can optimize total delay including routing delays. To our knowledge this is the first effort to leverage a grammar-based tree covering tool for datapath module mapping. Further, it is the first work to integrate simultaneous placement with module mapping in a way that preserves linear time complexity.

REFERENCES

• 1: Alfred V. Aho , Mahadevan Ganapathi, Efficient tree pattern matching (extended abstract): an aid to code generation, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.334-340, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318663]
• 2: A. V. Aho , S. C. Johnson , J. D. Ullman, Code Generation for Expressions with Common Subexpressions, Journal of the ACM (JACM), v.24 n.1, p.146-160, Jan. 1977 [doi>10.1145/321992.322001]
• 3: Saman P. Amarasinghe , Jennifer M. Anderson , Christopher S. Wilson , Shih-Wei Liao , Brian R. Murphy , Robert S. French , Monica S. Lam , Mary W. Hall, Multiprocessors from a Software Perspective, IEEE Micro, v.16 n.3, p.52-61, June 1996 [doi>10.1109/40.502406]
• 4: K. Chaudhary , M. Pedram, A near optimal algorithm for technology mapping minimizing area under delay constraints, Proceedings of the 29th ACM/IEEE conference on Design automation, p.492-498, June 08-12, 1992, Anaheim, California, United States
• 5: DEHON, A. DPGA-Coupled Microprocessors: Commodity ICs for the Early 21st Century. In Proceedings IEEE Workshop on FPGAs for Custom Computing Machines (Cat. No. 94TH0611-4) (1994), IEEE Comput. Soc. Press, pp. 31-9. AN4754544.
• 6: FRANCIS, R. Technology Mappingfi~r lamkup.Table Based Field- Programmable Gate Arrays. PhD thesis, University of Toronto, 1992.
• 7: Christopher W. Fraser , David R. Hanson, A Retargetable C Compiler: Design and Implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 8: J. R. Hauser , J. Wawrzynek, Garp: a MIPS processor with a reconfigurable coprocessor, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.12, April 16-18, 1997
• 9: K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
• 10: Andreas Koch, Module compaction in FPGA-based regular datapaths, Proceedings of the 33rd annual conference on Design automation, p.471-476, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240608]
• 11: Andreas Koch, Structured design implementation: a strategy for implementing regular datapaths on FPGAs, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.151-157, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228392]
• 12: LOU, J., SALEK, A. H., AND PEDRAM, M. AnExact Solution to Simultaneous Technology Mapping and Linear Placement Problem for Trees. In Prec. International Workshop on Logic Synthesis (May 1997), pp. 1--4.
• 13: A. R. Naseer , M. Balakrishnan , Anshul Kumar, An Efficient Technique for Mapping RTL Structures onto FPGAs, Proceedings of the 4th International Workshop on Field-Programmable Logic and Applications: Field-Programmable Logic, Architectures, Synthesis and Applications, p.99-110, September 07-09, 1994
• 14: NATIONAL SEMICONDUCTOR CORPORATION. NAPAi000 Data Sheet, 1996.
• 15: TJiANG, S. Twig Reference Manual. Comp. Sci. Tech. Rep. 120, AT&T Bell Laboratories, January 1986.
• 16: XILINX. The Programmable Logic Data Book. 1994.

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.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing
  B.8 Performance and Reliability

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

  J. Computer Applications

General Terms:
Algorithms, Design, Performance