Comparability graph coloring for optimizing utilization of stream register files in stream processors

ABSTRACT

A stream processor executes an application that has been decomposed into a sequence of kernels that operate on streams of data elements. During the execution of a kernel, all streams accessed must be communicated through the SRF (Stream Register File), a non-bypassing software-managed on-chip memory. Therefore, optimizing utilization of the SRF is crucial for good performance. The key insight is that the interference graphs formed by the streams in stream applications tend to be comparability graphs or decomposable into a set of multiple comparability graphs. We present a compiler algorithm that can find optimal or near-optimal colorings in stream IGs, thereby improving SRF utilization than the First-Fit

bin-packing algorithm, the best in the literature.

REFERENCES

• 1: 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]
• 2: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 3: Fred C. Chow , John L. Hennessy, The priority-based coloring approach to register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.4, p.501-536, Oct. 1990 [doi>10.1145/88616.88621]
• 4: William J. Dally , Francois Labonte , Abhishek Das , Patrick Hanrahan , Jung-Ho Ahn , Jayanth Gummaraju , Mattan Erez , Nuwan Jayasena , Ian Buck , Timothy J. Knight , Ujval J. Kapasi, Merrimac: Supercomputing with Streams, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.35, November 15-21, 2003
• 5: Abhishek Das , William J. Dally , Peter Mattson, Compiling for stream processing, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA [doi>10.1145/1152154.1152164]
• 6: Janet Fabri, Automatic storage optimization, ACM SIGPLAN Notices, v.14 n.8, p.83-91, August 1979
• 7: 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]
• 8: Jordan Gergov, Algorithms for compile-time memory optimization, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.907-908, January 17-19, 1999, Baltimore, Maryland, United States
• 9: Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57), North-Holland Publishing Co., Amsterdam, The Netherlands, 2004
• 10: R. Govindarajan , S. Rengarajan, Buffer Allocation in Regular Dataflow Networks: An Approach Based on Coloring Circular-Arc Graphs, Proceedings of the Third International Conference on High-Performance Computing (HiPC '96), p.419, December 19-22, 1996
• 11: H. A. Kierstead, A polynomial time approximation algorithm for Dynamic Storage Allocation, Discrete Mathematics, v.87 n.2-3, p.231-237, Jan. 31 1991
• 12: Francois Labonte , Peter Mattson , William Thies , Ian Buck , Christos Kozyrakis , Mark Horowitz, The Stream Virtual Machine, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.267-277, September 29-October 03, 2004 [doi>10.1109/PACT.2004.29]
• 13: Vincent Lefebvre , Paul Feautrier, Automatic storage management for parallel programs, Parallel Computing, v.24 n.3-4, p.649-671, May, 1998 [doi>10.1016/S0167-8191(98)00029-5]
• 14: Lian Li , Lin Gao , Jingling Xue, Memory Coloring: A Compiler Approach for Scratchpad Memory Management, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.329-338, September 17-21, 2005 [doi>10.1109/PACT.2005.27]
• 15: Lian Li , Quan Hoang Nguyen , Jingling Xue, Scratchpad allocation for data aggregates in superperfect graphs, Proceedings of the 2007 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 13-15, 2007, San Diego, California, USA
• 16: Lian Li, Hui Feng, Quan Hoang Nguyen, Lin Gao, and Jingling Xue. Compiler-directed scratchpad memory management via graph coloring. ACM Transactions on Architecture and Code Optimization, 2009. To appear.
• 17: John D. Owens. Computer Graphics on a Stream Architecture. PhD thesis, Stanford University, November 2002.
• 18: Ben Serebrin, Media Processing Applications on the Imagine Stream Processor, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.295, September 16-18, 2002
• 19: Michael D. Smith , Norman Ramsey , Glenn Holloway, A generalized algorithm for graph-coloring register allocation, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 20: Michael Bedford Taylor , Jason Kim , Jason Miller , David Wentzlaff , Fae Ghodrat , Ben Greenwald , Henry Hoffman , Paul Johnson , Jae-Wook Lee , Walter Lee , Albert Ma , Arvind Saraf , Mark Seneski , Nathan Shnidman , Volker Strumpen , Matt Frank , Saman Amarasinghe , Anant Agarwal, The Raw Microprocessor: A Computational Fabric for Software Circuits and General-Purpose Programs, IEEE Micro, v.22 n.2, p.25-35, March 2002 [doi>10.1109/MM.2002.997877]
• 21: W. Thies, M. Karczmarek, M. Gordon, D. Maze, J. Wong, H. Ho, M. Brown, and S. Amarasinghe. StreamIt: A compiler for streaming applications, 2001. MIT-LCS Technical Memo TM-622.
• 22: Li Wang , Xuejun Yang , Jingling Xue , Yu Deng , Xiaobo Yan , Tao Tang , Quan Hoang Nguyen, Optimizing scientific application loops on stream processors, Proceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems, June 12-13, 2008, Tucson, AZ, USA
• 23: Samuel Williams , John Shalf , Leonid Oliker , Shoaib Kamil , Parry Husbands , Katherine Yelick, The potential of the cell processor for scientific computing, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128027]
• 24: Nan Wu, Mei Wen, Ju Ren, Yi He, and Chunyuan Zhang. Register allocation on stream processor with local register file. In ACSAC '06: Proceedings of the 11th Asia-Pacific Computer Systems Architecture Conference, pages 545--551, 2006.
• 25: Xuejun Yang , Xiaobo Yan , Zuocheng Xing , Yu Deng , Jiang Jiang , Ying Zhang, A 64-bit stream processor architecture for scientific applications, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 26: Xuejun Yang , Ying Zhang , Jingling Xue , Ian Rogers , Gen Li , Guibin Wang, Exploiting loop-dependent stream reuse for stream processors, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada [doi>10.1145/1454115.1454121]

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Primary memory

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Languages, Performance

Keywords:
comparability graph coloring, software-managed cache, stream processor, stream programming