Simultaneous resource binding and interconnection optimization based on a distributed register-file microarchitecture

ABSTRACT

Behavior synthesis and optimization beyond the register-transfer level require an efficient utilization of the underlying platform features. This article presents a platform-based resource binding approach based on a Distributed Register-File Microarchitecture (DRFM), which makes efficient use of distributed embedded memory blocks as register files in modern FPGAs. DRFM contains multiple islands, each having a local register file, a functional unit pool, and data-routing logic. Compared to the traditional discrete-register counterpart, a DRFM allows use of the platform-featured on-chip memory or register-file IP blocks to implement its local register files, and this results in a substantial saving of multiplexing logic and global interconnects. DRFM provides a useful architectural template and a direct optimization objective for minimizing interisland connections for synthesis algorithms. Given the scheduling solution and resource (functional units) constraints, two novel algorithms in the resource binding stage are developed based on DRFM: (i) a simultaneous DRFM clustering and binding algorithm, which decides the configuration of DRFM and the assignment of operations into islands with the focus on optimizing global connections; (ii) a data-forwarding scheduling algorithm, which takes advantage of the operation slacks to handle the read-port restriction of register files. On the Xilinx Virtex4 FPGA platform, experimental results with a set of real-life test cases show a 50% logic area reduction achieved by applying our approach, with a 14.6% performance improvement, compared to the traditional discrete-register-based approach. Also, experiments on small-size designs show that our algorithm produces the same number of total connections and at most one more maximum feeding-in connection compared to optimal solutions generated by ILP.

REFERENCES

• 1: Altera. Altera Web site. http://www.altera.com.
• 2: Blazewicz, J. 1979. Deadline scheduling of tasks with ready times and resource constraints. Inf. Process. Lett. 8, 2, 60--63.
• 3: Santithorn Bunchua , D. Scott Wills , Linda M. Wills, Fully distributed register files for heterogeneous clustered microarchitectures, Georgia Institute of Technology, Atlanta, GA, 2004
• 4: Jui-Ming Chang , Massoud Pedram, Register allocation and binding for low power, Proceedings of the 32nd annual ACM/IEEE Design Automation Conference, p.29-35, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217502]
• 5: Deming Chen , Jason Cong, Register binding and port assignment for multiplexer optimization, Proceedings of the 2004 Asia and South Pacific Design Automation Conference, January 27-30, 2004, Yokohama, Japan
• 6: 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]
• 7: Cong, J., Fan, Y., Han, G., Jiang, W., and Zhang, Z. 2006. Platform-based behavior-level and system-level synthesis. In Proceedings of IEEE International SOC Conference (invited paper), 199--202.
• 8: Cong, J., Fan, Y., Han, G., Yang, X., and Zhang, Z. 2004. Architecture and synthesis for on-chip multi-cycle communication. IEEE Trans. Comput.-Aided Des. Integrated Syst. 23, 4, 550--564.
• 9: 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]
• 10: Jason Cong , Junjuan Xu, Simultaneous FU and register binding based on network flow method, Proceedings of the conference on Design, automation and test in Europe, March 10-14, 2008, Munich, Germany [doi>10.1145/1403375.1403629]
• 11: William J. Dally , Steve Lacy, VLSI Architecture: Past, Present, and Future, Proceedings of the 20th Anniversary Conference on Advanced Research in VLSI, p.232, March 21-24, 1999
• 12: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 13: Keith I. Farkas , Paul Chow , Norman P. Jouppi , Zvonko Vranesic, The multicluster architecture: reducing cycle time through partitioning, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.149-159, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 14: FFT. FFT package. http://momonga.t.u-tokyo.ac.jp/~ooura/fft.html.
• 15: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 16: Daniel D. Gajski , Nikil D. Dutt , Allen C.-H. Wu , Steve Y.-L. Lin, High-level synthesis: introduction to chip and system design, Kluwer Academic Publishers, Norwell, MA, 1992
• 17: Catherine H. Gebotys, Low energy memory and register allocation using network flow, Proceedings of the 34th annual Design Automation Conference, p.435-440, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266192]
• 18: Chao Huang , Srivaths Ravi , Anand Raghunathan , Niraj K. Jha, Generation of heterogeneous distributed architectures for memory-intensive applications through high-level synthesis, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.15 n.11, p.1191-1204, November 2007 [doi>10.1109/TVLSI.2007.904096]
• 19: 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 Design Automation Conference, p.499-504, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123350]
• 20: Jinhwan Jeon , Daehong Kim , Dongwan Shin , Kiyoung Choi, High-level synthesis under multi-cycle interconnect delay, Proceedings of the 2001 Asia and South Pacific Design Automation Conference, p.662, January 2001, Yokohama, Japan [doi>10.1145/370155.370576]
• 21: Kernighan, B. W. and Lin, S. 1970. An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49, 2.
• 22: Brucek Khailany , William J. Dally , Ujval J. Kapasi , Peter Mattson , Jinyung Namkoong , John D. Owens , Brian Towles , Andrew Chang , Scott Rixner, Imagine: Media Processing with Streams, IEEE Micro, v.21 n.2, p.35-46, March 2001 [doi>10.1109/40.918001]
• 23: Daehong Kim , Jinyong Jung , Sunghyun Lee , Jinhwan Jeon , Kiyoung Choi, Behavior-to-placed RTL synthesis with performance-driven placement, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 24: Kim, T. and Liu, C. 1995a. An integrated data path synthesis algorithm based on network flow method. Custom Integrated Circuits Conference, Proc. IEEE 1--4, 615--618.
• 25: Taewhan Kim , C. L. Liu, A new approach to the multiport memory allocation problem in data path synthesis, Integration, the VLSI Journal, v.19 n.3, p.133-160, Nov. 1995 [doi>10.1016/0167-9260(95)00009-5]
• 26: Eric Kusse , Jan Rabaey, Low-energy embedded FPGA structures, Proceedings of the 1998 international symposium on Low power electronics and design, p.155-160, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280873]
• 27: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 28: Hae-Dong Lee , Sun-Young Hwang, A scheduling algorithm for multiport memory minimization in datapath synthesis, Proceedings of the 1995 Asia and South Pacific Design Automation Conference, p.16-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan [doi>10.1145/224818.224847]
• 29: Kyoung-Hwan Lim , YongHwan Kim , Taewhan Kim, Interconnect and communication synthesis for distributed register-file microarchitecture, Proceedings of the 44th annual Design Automation Conference, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278672]
• 30: Manev Luthra , Sumit Gupta , Nikil Dutt , Rajesh Gupta , Alex Nicolau, Interface Synthesis using Memory Mapping for an FPGA Platform, Proceedings of the 21st International Conference on Computer Design, p.140, October 13-15, 2003
• 31: Mandal, C. A., Chakrabarti, P. P., and Ghose, S. 1998. Some new results in the complexity of allocation and binding in data path synthesis. Comput. Math. Appl. 35, 10, 93--105.
• 32: Pangrle, B. M. 1991. On the complexity of connectivity binding. IEEE Trans. CAD 10, 11, 1460--1465.
• 33: J. M. Rabaey , C. Chu , P. Hoang , M. Potkonjak, Fast Prototyping of Datapath-Intensive Architectures, IEEE Design & Test, v.8 n.2, p.40-51, April 1991 [doi>10.1109/54.82037]
• 34: Scott Rixner , William J. Dally , Ujval J. Kapasi , Brucek Khailany , Abelardo López-Lagunas , Peter R. Mattson , John D. Owens, A bandwidth-efficient architecture for media processing, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.3-13, November 1998, Dallas, Texas, United States
• 35: Rixner, S., Dally, W. J., Khailany, B., Mattson, P. R., Kapasi, U. J., and Owens, J. D. 2000. Register organization for media processing. In Proceedings of the 6th International Symposium on High-Performance Computer Architecture, 375--386.
• 36: André Seznec , Eric Toullec , Olivier Rochecouste, Register write specialization register read specialization: a path to complexity-effective wide-issue superscalar processors, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 37: Amit Singh , Ganapathy Parthasarathy , Malgorzata Marek-Sadowska, Efficient circuit clustering for area and power reduction in FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.4, p.643-663, October 2002 [doi>10.1145/605440.605448]
• 38: Mani B. Srivastava , Miodrag Potkonjak, Optimum and heuristic transformation techniques for simultaneous optimization of latency and throughput, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.1, p.2-19, March 1995 [doi>10.1109/92.365450]
• 39: L. Stok, False loops through resource sharing, 1992 IEEE/ACM international conference proceedings on Computer-aided design, p.345-348, December 1992, Santa Clara, California, United States
• 40: Stok, L. and Philipsen, W. 1991. Module allocation and comparability graphs. IEEE International Sympoisum on Circuits and Systems vol.5, 2862--2865.
• 41: Jennifer L. Wong , Seapahn Megerian , Miodrag Potkonjak, Forward-looking objective functions: concept & applications in high level synthesis, Proceedings of the 39th annual Design Automation Conference, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514141]
• 42: Xilinx. Xilinx Web site. http://www.xilinx.com.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Data-path design

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
Behavioral synthesis, distributed register file, resource binding