Exploiting loop-dependent stream reuse for stream processors

ABSTRACT

The memory access limits the performance of stream processors. By exploiting the reuse of data held in the Stream Register File (SRF), an on-chip storage, the number of memory accesses can be reduced. In current stream compilers reuse is only attempted for simple stream references, those whose start and end are known. Compiler analysis from outside of stream processors does not directly enable the consideration of other complex stream references. In this paper we propose a transformation to automatically optimize stream programs to exploit the reuse supplied by loop-dependent stream references. The transformation is based on three results: algorithms to recognize the reuse supplied by stream references, a new abstract expression called the Stream Reuse Graph (SRG) to depict the reuse and the optimization of the SRG for the transformation. Both the reuse between whole sequences accessed by stream references and that between partial sequences are exploited in the paper. In particular, the problem of exploiting partial stream reuse does not have its parallel in the traditional data reuse exploitation setting (for scalars and arrays). Finally, we have implemented our techniques using the StreamC/KernelC compiler for Imagine. Experimental results show a resultant speedup of 1.14 to 2.54 times using a range of typical stream processing application kernels.

REFERENCES

• 1: Jung Ho Ahn , Mattan Erez , William J. Dally, The design space of data-parallel memory systems, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188540]
• 2: John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, Rice University, Houston, TX, 1983
• 3: Randy Allen , Ken Kennedy, Vector Register Allocation, IEEE Transactions on Computers, v.41 n.10, p.1290-1317, October 1992 [doi>10.1109/12.166606]
• 4: Ian Buck , Tim Foley , Daniel Horn , Jeremy Sugerman , Kayvon Fatahalian , Mike Houston , Pat Hanrahan, Brook for GPUs: stream computing on graphics hardware, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 5: David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.53-65, June 1990, White Plains, New York, United States
• 6: Steve Carr , Ken Kennedy, Scalar replacement in the presence of conditional control flow, Software—Practice & Experience, v.24 n.1, p.51-77, Jan. 1994 [doi>10.1002/spe.4380240104]
• 7: T. F. Chan , E. Gallopoulos , V. Simoncini , T. Szeto , C. H. Tong, A quasi-minimal residual variant of the Bi-CGSTAB algorithm for nonsymmetric systems, SIAM Journal on Scientific Computing, v.15 n.2, p.338-347, March 1994 [doi>10.1137/0915023]
• 8: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. K Zadeck, Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, Brown University, Providence, RI, 1991
• 9: 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
• 10: 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]
• 11: Dennis Gannon , William Jalby , Kyle Gallivan, Strategies for cache and local memory management by global program transformation, Journal of Parallel and Distributed Computing, v.5 n.5, p.587-616, October 1988 [doi>10.1016/0743-7315(88)90014-7]
• 12: Nuwan Jayasena , Mattan Erez , Jung Ho Ahn , William J. Dally, Stream Register Files with Indexed Access, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.60, February 14-18, 2004 [doi>10.1109/HPCA.2004.10007]
• 13: J. A. Kahle , M. N. Day , H. P. Hofstee , C. R. Johns , T. R. Maeurer , D. Shippy, Introduction to the cell multiprocessor, IBM Journal of Research and Development, v.49 n.4/5, p.589-604, July 2005
• 14: The Imagine Stream Processor, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.282, September 16-18, 2002
• 15: Ujval J. Kapasi , Scott Rixner , William J. Dally , Brucek Khailany , Jung Ho Ahn , Peter Mattson , John D. Owens, Programmable Stream Processors, Computer, v.36 n.8, p.54-62, August 2003 [doi>10.1109/MC.2003.1220582]
• 16: 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]
• 17: Raymond Lo , Fred Chow , Robert Kennedy , Shin-Ming Liu , Peng Tu, Register promotion by sparse partial redundancy elimination of loads and stores, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.26-37, June 17-19, 1998, Montreal, Quebec, Canada
• 18: John Lu , Keith D. Cooper, Register promotion in C programs, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.308-319, June 16-18, 1997, Las Vegas, Nevada, United States
• 19: Peter Raymond Mattson , William J. Dally, A programming system for the imagine media processor, Stanford University, Stanford, CA, 2002
• 20: P. Mattson and et al. Imagine Programming System Developer's Guide, 2004.
• 21: M. Narayanan, L. Oliker, A. Janin, P. Husbands, X Ye, and S. Li. Scientific kernels on viram and imagine media processors. Lawrence Berkeley National Laboratory, 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: Scott Rixner, Stream processor architecture, Kluwer Academic Publishers, Norwell, MA, 2001
• 24: A. V. S. Sastry , Roy D. C. Ju, A new algorithm for scalar register promotion based on SSA form, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.15-25, June 17-19, 1998, Montreal, Quebec, Canada
• 25: R. Stephens. A survey of stream processing. Acta Informatica, 34(7):491--541, 1997.
• 26: 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]
• 27: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
• 28: Wm. A. Wulf , Sally A. McKee, Hitting the memory wall: implications of the obvious, ACM SIGARCH Computer Architecture News, v.23 n.1, p.20-24, March 1995 [doi>10.1145/216585.216588]
• 29: Jingling Xue , Chua-Huang Huang, Reuse-Driven Tiling for Data Locality, Proceedings of the 10th International Workshop on Languages and Compilers for Parallel Computing, p.16-33, August 07-09, 1997
• 30: 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:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Specialized application languages

General Terms:
Algorithms, Design, Experimentation, Management, Performance

Keywords:
StreamC, stream professor, stream programming model, stream register file, stream reuse