Optimizing scientific application loops on stream processors

ABSTRACT

This paper describes a graph coloring compiler framework to allocate on-chip SRF(Stream Register File) storage for optimizing scientific applications on stream processors. Our framework consists of first applying enabling optimizations such as loop unrolling to expose stream reuse and opportunities for maximizing parallelism, i.e., overlapping kernel execution and memory transfers.Then the three SRF management tasks are solved in a unified manner via graph coloring: (1) placing streams in the SRF, (2) exploiting stream use, and (3) maximizing parallelism. We evaluate the performance of our compiler framework by actually running nine representative scientific computing kernels on our FT64 stream processor. Our preliminary results show that compiler management achieves an average speedup of 2.3x compared to First-Fit allocation. In comparison with the performance results obtained from running these benchmarks on Itanium 2, an average speedup of 2.1x is observed.

REFERENCES

• 1: Sitij Agrawal , William Thies , Saman Amarasinghe, Optimizing stream programs using linear state space analysis, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA [doi>10.1145/1086297.1086315]
• 2: 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]
• 3: 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
• 4: Sourav Chatterji , Manikandan Narayanan , Jason Duell , Leonid Oliker, Performance Evaluation of Two Emerging Media Processors: VIRAM and Imagine, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.229.1, April 22-26, 2003
• 5: 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]
• 6: 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
• 7: 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]
• 8: Janet Fabri, Automatic storage optimization, ACM SIGPLAN Notices, v.14 n.8, p.83-91, August 1979
• 9: 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]
• 10: 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
• 11: Michael I. Gordon , William Thies , Saman Amarasinghe, Exploiting coarse-grained task, data, and pipeline parallelism in stream programs, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 12: Jayanth Gummaraju , Mendel Rosenblum, Stream Programming on General-Purpose Processors, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.343-354, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.32]
• 13: 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
• 14: Timothy J. Knight , Ji Young Park , Manman Ren , Mike Houston , Mattan Erez , Kayvon Fatahalian , Alex Aiken , William J. Dally , Pat Hanrahan, Compilation for explicitly managed memory hierarchies, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA [doi>10.1145/1229428.1229477]
• 15: 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]
• 16: V. Lefebvre and P. Feautrier. Storage management in parallel programs. Technical report, Laboratory PRiSM, University of Versailles, France, 1996.
• 17: 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]
• 18: Lian Li , Quan Hoang Nguyen , Jingling Xue, Scratchpad allocation for data aggregates in superperfect graphs, ACM SIGPLAN Notices, v.42 n.7, July 2007
• 19: Peter Mattson , William J. Dally , Scott Rixner , Ujval J. Kapasi , John D. Owens, Communication scheduling, ACM SIGARCH Computer Architecture News, v.28 n.5, p.82-92, Dec. 2000
• 20: Peter Raymond Mattson. phA programming system for the imagine media processor. PhD thesis, Stanford University, Stanford, CA, USA, 2002. Adviser-William J. Dally.
• 21: John D. Owens. phComputer Graphics on a Stream Architecture. PhD thesis, Stanford University, November 2002.
• 22: 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
• 23: 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]
• 24: 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
• 25: 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]
• 26: W. Thies, M. Karczmarek, M. Gordon, D. Maze, J. Wong, H. Ho, M. Brown, and S. Amarasinghe. StreamIt: A compiler for streaming applications, December 2001. MIT-LCS Technical Memo TM-622, Cambridge, MA.
• 27: Shih-wei Liao , Zhaohui Du , Gansha Wu , Guei-Yuan Lueh, Data and Computation Transformations for Brook Streaming Applications on Multiprocessors, Proceedings of the International Symposium on Code Generation and Optimization, p.196-207, March 26-29, 2006 [doi>10.1109/CGO.2006.13]
• 28: 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]
• 29: Nan Wu, Mei Wen, Ju Ren, Yi He, and Chunyuan Zhang. Register allocation on stream processor with local register file. In phACSAC '06: Proceedings of the 11th Asia-Pacific Computer Systems Architecture Conference, pages 545--551, 2006.
• 30: Jingling Xue, Loop tiling for parallelism, Kluwer Academic Publishers, Norwell, MA, 2000
• 31: 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

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:
data reuse, graph coloring, loop optimization, prefetching, software-managed cache, stream processor, streaming