Platform-based resource binding using 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 paper presents a platform-based resource-binding approach using a distributed register-file microarchitecture (DRFM) that makes efficient use of distributed embedded memory blocks as register files in modern FPGAs. A DRFM contains multiple islands, each having a local register file, a functional unit pool and data-routing logic. Compared with 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 substantial saving of multiplexing logic and global interconnects. DRFM provides a useful architectural template and a direct optimization objective for minimizing inter-island connections for synthesis algorithms. Based on DRFM, we propose a novel binding algorithm focusing on the minimization of the inter-island connections. By applying our approach, significant reductions on multiplexors and global-interconnections are observed. On the Xilinx Virtex II FPGA platform, our experimental results show a 2X logic area reduction and a 7.8% performance improvement, compared with the traditional discrete-register-based approach.

REFERENCES

• 1: Mohammed Aloqeely , C. Y. Roger Chen, Sequencer-based data path synthesis of regular iterative algorithms, Proceedings of the 31st annual conference on Design automation, p.155-160, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196317]
• 2: Jui-Ming Chang , Massoud Pedram, Register allocation and binding for low power, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.29-35, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217502]
• 3: 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]
• 4: D. Chen, J. Cong, Y. Fan, G. Han, W. Jiang, and Z. Zhang, "xpilot: A platform-based behavioral synthesis system," in SRC TechCon'05, Portland, OR, Nov. 2005.
• 5: Kyumyung Choi , Steven P. Levitan, A flexible datapath allocation method for architectural synthesis, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.4, p.376-404, Oct. 1999 [doi>10.1145/323480.323486]
• 6: J. Cong, Y. Fan, G. Han, X. Yang, and Z. Zhang, "Architecture and synthesis for on-chip multi-cycle communication," IEEE Trans. Computer-Aided Design, pp. 550--564, Apr. 2004.
• 7: 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
• 8: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 9: S. Devadas and A. Newton, "Algorithms for hardware allocation in data path synthesis," IEEE Trans. Computer-Aided Design, vol. 8(7), pp. 768--781, July 1989.
• 10: 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
• 11: 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
• 12: Catherine H. Gebotys, Low energy memory and register allocation using network flow, Proceedings of the 34th annual conference on Design automation, p.435-440, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266192]
• 13: C. Gebotys and M. Elmasry, "Optimal synthesis of high-performance architectures," IEEE J. Solid-State Circuits, vol. 27(3), pp. 389--397, Mar. 1992.
• 14: Altera Website, http://www.altera.com.
• 15: Xilinx Website, http://www.xilinx.com.
• 16: 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]
• 17: Margarida F. Jacome , Gustavo de Veciana , Viktor Lapinskii, Exploring performance tradeoffs for clustered VLIW ASIPs, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 18: Jinhwan Jeon , Daehong Kim , Dongwan Shin , Kiyoung Choi, High-level synthesis under multi-cycle interconnect delay, Proceedings of the 2001 conference on Asia South Pacific design automation, p.662, January 2001, Yokohama, Japan [doi>10.1145/370155.370576]
• 19: B. W. Kernighan and S. Lin, "An efficient heuristic procedure for partitioning graphs," Bell System Technical J., vol. 49, no. 2, Feb. 1970.
• 20: K. Keutzer, S. Malik, A. R. Newton, J. M. Rabaey, and A. Sangiovanni-Vincentelli, "System level design: Orthogonalization of concerns and platform-based design," IEEE Trans. Computer-Aided Design, vol. 19(12), pp. 1523--1543, Dec. 2000.
• 21: 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
• 22: T. Kim and C. L. Liu, "An integrated data path synthesis algorithm based on network flow method," Proc. of the IEEE Custom Integrated Circuits Conference, vol. 1-4, pp. 615--618, May 1995.
• 23: 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]
• 24: P. Kollig and B. M. Al-Hashimi, "Simultaneous scheduling, allocation and binding in high level synthesis," Elect. Let., vol. 33, Aug. 1997.
• 25: 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]
• 26: Dirk Lanneer , Marco Cornero , Gert Goossens , Hugo De Man, Data routing: a paradigm for efficient data-path synthesis and code generation, Proceedings of the 7th international symposium on High-level synthesis, p.17-22, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
• 27: Hae-Dong Lee , Sun-Young Hwang, A scheduling algorithm for multiport memory minimization in datapath synthesis, Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM), p.16-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan [doi>10.1145/224818.224847]
• 28: 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
• 29: T. A. Ly and J. T. Mowchenko, "Applying simulated evolution to high level synthesis," IEEE Trans. Computer-Aided Design, vol. 12(3), pp. 389--409, Mar. 1993.
• 30: Nir Magen , Avinoam Kolodny , Uri Weiser , Nachum Shamir, Interconnect-power dissipation in a microprocessor, Proceedings of the 2004 international workshop on System level interconnect prediction, February 14-15, 2004, Paris, France [doi>10.1145/966747.966750]
• 31: C. A. Mandal, P. P. Chakrabarti, and S. Ghose, "Some new results in the complexity of allocation and binding in data path synthesis," Computers and Mathematics with Applications, vol. 35, no. 10, pp. 93--105, 1998.
• 32: B. M. Pangrle, "On the complexity of connectivity binding," IEEE Trans. Computer-Aided Design, vol. 10(11), pp. 1460--1465, 1991.
• 33: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 34: 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]
• 35: M. Rim , R. Jain , R. De Leone, Optimal allocation and binding in high-level synthesis, Proceedings of the 29th ACM/IEEE conference on Design automation, p.120-123, June 08-12, 1992, Anaheim, California, United States
• 36: S. Rixner, W. J. Dally, B. Khailany, P. R. Mattson, U. J. Kapasi, and J. D. Owens, "Register organization for media processing," in Proc. of the 6th International Symposium on High-Performance Computer Architecture, 2000, pp. 375--386.
• 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: L. Stok and W. Philipsen, "Module allocation and comparability graphs," IEEE International Sympoisum on Circuits and Systems, vol. 11-14 vol.5, pp. 2862--2865, June 1991.
• 39: C.-J. Tseng and D. Siewiorek, "Automated synthesis of data paths in digital systems," IEEE Trans. Computer-Aided Design, vol. 5(3), pp. 379--395, July 1986.

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation

Keywords:
behavior synthesis, distributed register file, resource binding