SPR: an architecture-adaptive CGRA mapping tool

ABSTRACT

In this paper we present SPR, a new architecture-adaptive mapping tool for use with Coarse-Grained Reconfigurable Architectures (CGRAs). It combines a VLIW style scheduler and FPGA style placement and pipelined routing algorithms with novel mechanisms for integrating and adapting the algorithms to CGRAs. We introduce a latency padding technique that provides feedback from the placer to the scheduler to meet the constraints of a fixed frequency device with configurable interconnect. Using a new dynamic clustering method during placement, we achieved a 1.3x improvement in throughput of mapped designs. Finally, we introduce an enhancement to the PathFinder algorithm for targeting architectures with a mix of dynamically multiplexed and statically configurable interconnects. The enhanced algorithm is able to successfully share statically configured interconnect in a time-multiplexed way, achieving an average channel width reduction of .5x compared to non-shared static interconnect.

REFERENCES

• 1: Electric VLSI Design System. Sun Microsystems and Static Free Software. http://www.staticfreesoft.com/.
• 2: Mosaic Research Group. http://www.cs.washington.edu/research/lis/mosaic/.
• 3: Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
• 4: A. Carroll and C. Ebeling. Reducing the Space Complexity of Pipelined Routing Using Modified Range Encoding. In International Conference on Field-Programmable Logic and Applications, 2006.
• 5: A. Carroll, S. Friedman, B. Van Essen, A. Wood, B. Ylvisaker, C. Ebeling, and S. Hauck. Designing a Coarse-grained Reconfigurable Architecture for Power Efficiency. Technical report, Department of Energy NA-22 University Information Technical Interchange Review Meeting, 2007.
• 6: Carl Ebeling , Darren C. Cronquist , Paul Franklin, RaPiD - Reconfigurable Pipelined Datapath, Proceedings of the 6th International Workshop on Field-Programmable Logic, Smart Applications, New Paradigms and Compilers, p.126-135, September 23-25, 1996
• 7: Ken Eguro , Scott Hauck, Armada: timing-driven pipeline-aware routing for FPGAs, Proceedings of the 2006 ACM/SIGDA 14th international symposium on Field programmable gate arrays, February 22-24, 2006, Monterey, California, USA [doi>10.1145/1117201.1117227]
• 8: S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by Simulated Annealing. Science, 220:671--680, 1983.
• 9: Jong-eun Lee , Kiyoung Choi , Nikil D. Dutt, Compilation Approach for Coarse-Grained Reconfigurable Architectures, IEEE Design & Test, v.20 n.1, p.26-33, January 2003 [doi>10.1109/MDT.2003.1173050]
• 10: S. Li and C. Ebeling. QuickRoute: A Fast Routing Algorithm for Pipelined Architectures. In IEEE International Conference on Field-Programmable Technology, pages 73--80, 2004.
• 11: Larry McMurchie , Carl Ebeling, PathFinder: a negotiation-based performance-driven router for FPGAs, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.111-117, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201328]
• 12: B. Mei, S. Vernalde, D. Verkest, H. De Man, and R. Lauwereins. DRESC: A Retargetable Compiler for Coarse-grained Reconfigurable Architectures. In IEEE International Conference on Field-Programmable Technology, pages 166--173, 2002.
• 13: B. Mei, S. Vernalde, D. Verkest, H. De Man, and R. Lauwereins. ADRES: An Architecture with Tightly Coupled VLIW Processor and Coarse-Grained Reconfigurable Matrix. In International Conference on Field-Programmable Logic and Applications, volume 2778, pages 61--70, 2003.
• 14: E. Mirsky and A. DeHon. MATRIX: a reconfigurable computing architecture with configurable instruction distribution and deployable resources. In IEEE Symposium on Field-Programmable Custom Computing Machines, pages 157--166, 1996.
• 15: M. Mishra and S. C. Goldstein. Virtualization on the Tartan Reconfigurable Architecture. In International Conference on Field-Programmable Logic and Applications, pages 323--330, 2007.
• 16: B. Ramakrishna Rau, Iterative modulo scheduling: an algorithm for software pipelining loops, Proceedings of the 27th annual international symposium on Microarchitecture, p.63-74, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192731]
• 17: A. Sharma, S. Hauck, and C. Ebeling. Architecture-adaptive Routability-driven Placement for FPGAs. In International Conference on Field-Programmable Logic and Applications, pages 427--432, 2005.
• 18: Hartej Singh , Ming-Hau Lee , Guangming Lu , Nader Bagherzadeh , Fadi J. Kurdahi , Eliseu M. Chaves Filho, MorphoSys: An Integrated Reconfigurable System for Data-Parallel and Computation-Intensive Applications, IEEE Transactions on Computers, v.49 n.5, p.465-481, May 2000 [doi>10.1109/12.859540]
• 19: William Tsu , Kip Macy , Atul Joshi , Randy Huang , Norman Walker , Tony Tung , Omid Rowhani , Varghese George , John Wawrzynek , André DeHon, HSRA: high-speed, hierarchical synchronous reconfigurable array, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.125-134, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296442]
• 20: Steven Joseph Edward Wilton , Jonathan Rose , Zvenko Vranesic, Architectures and algorithms for field-programmable gate arrays with embedded memory, University of Toronto, Toronto, Ont., Canada, 1997

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Retargetable compilers

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
clustering, modulo graph, pathfinder, placement, routing, scheduling, spr, static sharing