Pattern-based behavior synthesis for FPGA resource reduction

ABSTRACT

Pattern-based synthesis has drawn wide interest from researchers who tried to utilize the regularity in applications for design optimizations. In this paper we present a general pattern-based behavior synthesis framework which can efficiently extract similar structures in programs. Our approach is very scalable in benefit of advanced pruning techniques that include locality sensitive hashing and characteristic vectors. The similarity of structures is captured by a mismatch-tolerant metric: graph edit distance. The edit distance between two graphs is the minimum number of vertex/edge insertion, deletion, substitution operations to transform one graph into the other. Graph edit distance can naturally handle various program variations such as bit-width variations, structure variations and port variations. In addition, we apply our pattern-based synthesis system to FPGA resource optimization with the observation that multiplexors are particularly expensive on FPGA platforms. Considering knowledge of discovered patterns, the resource binding step can intelligently generate the data-path to reduce interconnect costs. Experiments show our approach can, on average, reduce the total area by about 20% with 7% latency overhead on the Xilinx Virtex-4 FPGAs, compared to the traditional behavior synthesis flow

REFERENCES

• 1: GMT toolkit. http://www.cs.sunysb.edu/~algorith/implement/gmt/implement.shtml.
• 2: M.A. Abdulrahim and M. Misra. A graph isomorphism algorithm for object recognition. Pattern Analysis and Applications, 1(3), 1998.
• 3: C. Alias. Program Optimization by Template Recognition and Replacement. PhD thesis, 2005.
• 4: Kubilay Atasu , Laura Pozzi , Paolo Ienne, Automatic application-specific instruction-set extensions under microarchitectural constraints, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775897]
• 5: Paolo Bonzini , Laura Pozzi, Polynomial-time subgraph enumeration for automated instruction set extension, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 6: Oliver Bringmann , Wolfgang Rosenstiel, Resource sharing in hierarchical synthesis, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.318-325, November 09-13, 1997, San Jose, California, United States
• 7: Philip Brisk , Adam Kaplan , Ryan Kastner , Majid Sarrafzadeh, Instruction generation and regularity extraction for reconfigurable processors, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France [doi>10.1145/581630.581672]
• 8: Deming Chen , Jason Cong , Yiping Fan, Low-power high-level synthesis for FPGA architectures, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871541]
• 9: J. Cong, Y. Fan, G. Han, W. Jiang, and Z. Zhang. Platform-based behavior-level and system-level synthesis. In Proceedings of IEEE SOCC, 2006.
• 10: Jason Cong , Yiping Fan , Guoling Han , Zhiru Zhang, Application-specific instruction generation for configurable processor architectures, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA [doi>10.1145/968280.968307]
• 11: Jason Cong , Yiping Fan , Wei Jiang, Platform-based resource binding using a distributed register-file microarchitecture, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233648]
• 12: Jason Cong , Zhiru Zhang, An efficient and versatile scheduling algorithm based on SDC formulation, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147025]
• 13: M.R. Corazao, M.A. Khalaf, L.M. Guerra, M. Potkonjak, and J.M. Rabaey. Performance optimization using template mapping for datapath-intensive high-level synthesis. IEEE Trans. on CAD of Integrated Circuits and Systems, 15(8):877--888, 1996.
• 14: Mayur Datar , Nicole Immorlica , Piotr Indyk , Vahab S. Mirrokni, Locality-sensitive hashing scheme based on p-stable distributions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997857]
• 15: http://www.mit.edu/~andoni/LSH/. LSH Algorithm and Implementation.
• 16: http://www.xilinx.com. Xilinx Website.
• 17: Jun Huan , Wei Wang , Jan Prins, Efficient Mining of Frequent Subgraphs in the Presence of Isomorphism, Proceedings of the Third IEEE International Conference on Data Mining, p.549, November 19-22, 2003
• 18: Chu-Yi Huang , Yen-Shen Chen , Youn-Long Lin , Yu-Chin Hsu, Data path allocation based on bipartite weighted matching, Proceedings of the 27th ACM/IEEE conference on Design automation, p.499-504, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123350]
• 19: Akihiro Inokuchi , Takashi Washio , Hiroshi Motoda, An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.13-23, September 13-16, 2000
• 20: Christoph W. Kessler, Pattern-driven automatic parallelization, Scientific Programming, v.5 n.3, p.251-274, Fall 1996
• 21: 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]
• 22: T. Kim and C. Liu. An integrated data path synthesis algorithm based on network flow method. Custom Integrated Circuits Conference, 1995., Proc. of the IEEE 1995, 1--4:615--618, May 1995.
• 23: Michihiro Kuramochi , George Karypis, Frequent Subgraph Discovery, Proceedings of the 2001 IEEE International Conference on Data Mining, p.313-320, November 29-December 02, 2001
• 24: Thomas Kutzschebauch , Leon Stok, Regularity driven logic synthesis, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 25: Tai Ly , David Knapp , Ron Miller , Don MacMillen, Scheduling using behavioral templates, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.101-106, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217514]
• 26: Beniamino Di Martino , Giulio Iannello, PAP Recognizer: A Tool for Automatic Recognition of Parallelizable Patterns, Proceedings of the 4th International Workshop on Program Comprehension (WPC '96), p.164, March 29-31, 1996
• 27: Bruno T. Messmer , Horst Bunke, A New Algorithm for Error-Tolerant Subgraph Isomorphism Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.5, p.493-504, May 1998 [doi>10.1109/34.682179]
• 28: Automatic algorithm recognition and replacement: a new approach to program optimization, MIT Press, Cambridge, MA, 2000
• 29: D. Rao and F.J. Kurdahi. On clustering for maximal regularity extraction. IEEE Trans. Computer Aided Design, 12(8), Aug. 1993.
• 30: Sergios Theodoridis , Konstantinos Koutroumbas, Pattern Recognition, Third Edition, Academic Press, Inc., Orlando, FL, 2006
• 31: C.-J. Tseng and D. Siewiorek. Automated synthesis of data paths in digital systems. 5(3):379--395, July 1986.
• 32: Linda Mary Wills, Automated program recognition by graph parsing, Massachusetts Institute of Technology, Cambridge, MA, 1992
• 33: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.721, December 09-12, 2002
• 34: Rui Yang , Panos Kalnis , Anthony K. H. Tung, Similarity evaluation on tree-structured data, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066243]
• 35: Pan Yu , Tulika Mitra, Scalable custom instructions identification for instruction-set extensible processors, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023844]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Automatic synthesis

General Terms:
Algorithms

Keywords:
FPGA, behavior synthesis, pattern