Placement-and-routing-based register allocation for coarse-grained reconfigurable arrays

ABSTRACT

DSP architectures often feature multiple register files with sparse connections to a large set of ALUs. For such DSPs, traditional register allocation algorithms suffer from a lot of problems, including a lack of retargetability and phase-ordering problems. This paper studies alternative register allocation techniques based on placement and routing. Different register file models are studied and evaluated on a state-of-the art coarse-grained reconfigurable array DSP, together with a new post-pass register allocator for rotating register files.

REFERENCES

• 1: AHN, M., AND PAEK, Y. Fast code generation for embedded processors with aliased heterogeneous registers. Trans. on HiPEAC 2, 2 (2007), 40--59.
• 2: Alex Aletà , Josep M. Codina , Antonio González , David Kaeli, Removing communications in clustered microarchitectures through instruction replication, ACM Transactions on Architecture and Code Optimization (TACO), v.1 n.2, p.127-151, June 2004 [doi>10.1145/1011528.1011529]
• 3: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 4: BOUWENS, F., BEREKOVIC, M., GAYDADJIEV, G., AND DE SUTTER, B. Architecture enhancements for the ADRES coarse-grained reconfigurable array. In Proc. of HiPEAC Conf. (2008).
• 5: Preston Briggs , Keith D. Cooper , Linda Torczon, Improvements to graph coloring register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.428-455, May 1994 [doi>10.1145/177492.177575]
• 6: David Callahan , Brian Koblenz, Register allocation via hierarchical graph coloring, ACM SIGPLAN Notices, v.26 n.6, p.192-203, June 1991
• 7: G. Carpaneto , M. Dell'Amico , P. Toth, Exact solution of large-scale, asymmetric traveling salesman problems, ACM Transactions on Mathematical Software (TOMS), v.21 n.4, p.394-409, Dec. 1995 [doi>10.1145/212066.212081]
• 8: CERVERO, T. Analysis, implementation and architectural exploration of the H.264/AVC decoder onto a reconfigurable architecture. Master's thesis, Universidad de Los Palmas de Gran Canaria, 2007.
• 9: CHAINTIN, G., AUSLANDER, M., CHANDRA, A. K., COCKE, J., HOPKINS, M., AND MARKSTEIN, P. Register allocation via coloring. Computer Languages 6, 1 (1981), 47--57.
• 10: Michael Chu , Kevin Fan , Scott Mahlke, Region-based hierarchical operation partitioning for multicluster processors, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 11: EISENBEIS, C., LELAIT, S., AND MARMOL, B. Circular-arc graph coloring and unrolling. In Proceedings of the 5th Twente Workshop on Graphs and Combinatorial Optimization (Twente, Netherlands, May 1997), U. Faigle and C. Hoede, Eds., pp. 71--74.
• 12: Lal George , Andrew W. Appel, Iterated register coalescing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.300-324, May 1996 [doi>10.1145/229542.229546]
• 13: HARAIKAWA, T., SOENO, M., YAMASHITA, Y., AND NAKATA, I. Register allocation frameworks for slide-window architecture. Transactions of Information Processing Society of Japan 39, 9 (1998), 2684--2694. (in Japanese).
• 14: Laurie J. Hendren , Guang R. Gao , Erik R. Altman , Chandrika Mukerji, A Register Allocation Framework Based on Hierarchical Cyclic Interval Graphs, Proceedings of the 4th International Conference on Compiler Construction, p.176-191, October 05-07, 1992
• 15: ITOGA, H., HARAIKAWA, T., YAMASHITA, Y., AND TANAKA, J. Register allocation for software pipelining with predication using spiral graph. In Proceedings of the International Symposium on Future Software Technology (ISFST2001) (2001), pp. 58--65.
• 16: Suhyun Kim , Soo-Mook Moon, Rotating Register Allocation for Enhanced Pipeline Scheduling, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.60-72, September 15-19, 2007 [doi>10.1109/PACT.2007.61]
• 17: David Ryan Koes , Seth Copen Goldstein, A global progressive register allocator, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 18: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 19: Viktor S. Lapinskii , Margarida F. Jacome , Gustavo A. De Veciana, Cluster assignment for high-performance embedded VLIW processors, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.3, p.430-454, July 2002 [doi>10.1145/567270.567274]
• 20: Scott A. Mahlke , David C. Lin , William Y. Chen , Richard E. Hank , Roger A. Bringmann, Effective compiler support for predicated execution using the hyperblock, Proceedings of the 25th annual international symposium on Microarchitecture, p.45-54, December 01-04, 1992, Portland, Oregon, United States
• 21: Dániel Marx, Eulerian disjoint paths problem in grid graphs is NP-complete, Discrete Applied Mathematics, v.143 n.1-3, p.336-341, 30 September 2004 [doi>10.1016/j.dam.2003.12.003]
• 22: MEI, B., VERNALDE, S., VERKEST, D., MAN, H. D., AND LAUWEREINS, R. ADRES: An architecture with tightly coupled VLIW processor and coarse-grained reconfigurable matrix. In Proc. of Field-Programmable Logic and Applications (2003), pp. 61.70.
• 23: MEI, B., VERNALDE, S., VERKEST, D., MAN, H. D., AND LAUWEREINS, R. Exploiting loop-level parallelism for coarse-grained reconfigurable architecture using modulo scheduling. IEE Proceedings: Computer and Digital Techniques 150, 5 (2003).
• 24: Hyunchul Park , Kevin Fan , Manjunath Kudlur , Scott Mahlke, Modulo graph embedding: mapping applications onto coarse-grained reconfigurable architectures, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176778]
• 25: Il Park , Michael D. Powell , T. N. Vijaykumar, Reducing register ports for higher speed and lower energy, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 26: Jinpyo Park , Soo-Mook Moon, Optimistic register coalescing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.4, p.735-765, July 2004 [doi>10.1145/1011508.1011512]
• 27: Massimiliano Poletto , Vivek Sarkar, Linear scan register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.5, p.895-913, Sept. 1999 [doi>10.1145/330249.330250]
• 28: RAU, B. R. Iterative modulo scheduling. Tech. rep., Hewlett-Packard Lab: HPL-94-115, 1995.
• 29: B. R. Rau , C. D. Glaeser, Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing, Proceedings of the 14th annual workshop on Microprogramming, p.183-198, December 01-01, 1981, Chatham, Massachusetts, United States
• 30: B. R. Rau , M. Lee , P. P. Tirumalai , M. S. Schlansker, Register allocation for software pipelined loops, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.283-299, June 15-19, 1992, San Francisco, California, United States
• 31: A. S. Terechko , H. Corporaal, Inter-cluster communication in VLIW architectures, ACM Transactions on Architecture and Code Optimization (TACO), v.4 n.2, p.11-es, June 2007 [doi>10.1145/1250727.1250731]
• 32: TOUATI, S.-A.-A., AND EISENBEIS, C. Cyclic register pressure and allocation for modulo scheduled loops. Tech. Rep. 4442, INRIA, April 2002.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

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

General Terms:
Algorithms, Design, Performance

Keywords:
coarse-grained, placement and routing, reconfigurable arrays, register allocation