skip to main content
article
Open access

Dynamic memory interval test vs. interprocedural pointer analysis in multimedia applications

Published: 01 June 2005 Publication History

Abstract

Techniques to detect aliasing between access patterns of array elements are quite effective for many numeric applications. However, although multimedia codes usually follow very regular memory access patterns, current commercial compilers remain unsuccessful in disambiguating them due mainly to complex pointer references. The Dynamic Memory Interval Test is a runtime memory disambiguation technique that takes advantage of the specific behavior of multimedia memory access patterns. It evaluates whether or not the full loop is disambiguated by analyzing the region domain of each load or store before each invocation of the loop.This paper provides a detailed evaluation of the approach, compares it against an advanced interprocedural pointer analysis framework, and analyzes the possibility of using both techniques at the same time. Both techniques achieve similar speedups separately (1.25X in average for a 8-issue width architecture). Furthermore, they can be used together to improve performance (reaching an average speed-up of 1.32X). Results also confirm that memory disambiguation is a key optimization to exploit the available parallelism in multimedia codes, especially for wide-issue architectures (1.50X average speed-up when scaling from 4- to 12-issue width in contrast to a low 1.10X for the baseline compiler).

Supplementary Material

ZIP File (p199-salami.zip)
This zip file contains three structured document full-text XML representations of the article plus the final, self-contained source LaTeX file, which can be compiled on most LaTeX systems. The three XML files all present images as gifs. They differ in their representations of math: one has gifs, one has embedded LaTeX, and one has MathML. Save the zip to disk and expand into its four folders.

References

[1]
Aditya, S., Kathail, V., and Rau, B. R. 1998. Elcor's machine description system: Version 3.0. Technical Report HPL-98-128, Information Technology Center.
[2]
Andersen, L. O. 1994. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen.
[3]
Bernstein, D., Cohen, D., and Maydan, D. E. 1994. Dynamic memory disambiguation for array references. In Proceedings of the 27th Annual International Symposium on Microarchitecture. 105--111.
[4]
Blume, W. and Eigenmann, R. 1994. The range test: a dependence test for symbolic, non-linear expressions. In Proceedings of the 1994 Conference on Supercomputing. 528--537.
[5]
Carr, S., McKinley, K. S., and Tseng, C.-W. 1994. Compiler optimizations for improving data locality. In Proceedings of the 6th International Conference on Architectural Support for Programming Languages and Operating Systems. 252--262.
[6]
Choi, J.-D., Burke, M., and Carini, P. 1993. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Charleston, SC). 232--245.
[7]
Emami, M., Ghiya, R., and Hendren, L. J. 1994. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In Proceedings of the ACM SIGPLAN'94 Conference on Programming Language Design and Implementation. 242--256.
[8]
Feautrier, P. 1991. Dataflow analysis of array and scalar references. International Journal of Parallel Programming 20, 1, 23--53.
[9]
Gallagher, D. M. 1995. Memory Disambiguation to Facilitate Instruction-Level Parallelism Compilation. PhD thesis, Dept. of Electrical and Computer Engineering, University of Illinois.
[10]
Gallagher, D. M., Chen, W. Y., Mahlke, S. A., Gyllenhaal, J. C., and Hwu, W. W. 1994. Dynamic memory disambiguation using the memory conflict buffer. ACM SIGPLAN Notices 29, 11, 183--193.
[11]
Goff, G., Kennedy, K., and Tseng, C. 1991. Practical dependence testing. In Proceedings of the ACM SIGPLAN'91 Conference on Programming Language Design and Implementation. 15--29.
[12]
Hind, M. and Pioli, A. 2000. Which pointer analysis should I use? In Proceedings of the 2000 ACM SIGSOFT International Symposium on Software Testing and Analysis. 113--123.
[13]
Huang, A., Slavenburg, G., and Shen, J. 1994. Speculative disambiguation: A compilation technique for dynamic memory disambiguation. In Proceedings of the 21st International Symposium on Computer Architecture. 200--210.
[14]
Hwu, W. W., Mahlke, S. A., Chen, W. Y., Chang, P. P., Warter, N. J., Bringmann, R. A., Ouellette, R. G., Hank, R. E., Kiyohara, T., Haab, G. E., Holm, J. G., and Lavery, D. M. 1993. The superblock: An effective technique for vliw and superscalar compilation. The J. Supercomputing 7, 229--248.
[15]
Hwu, W. W., Hank, R., Gallagher, D., Mahlke, S., Lavery, D., Haab, G., Gyllenhaal, J., and August, D. 1995. Compiler technology for future microprocessors. Proceedings of the IEEE 83, 625--1640.
[16]
Kathail, V., Schlansker, M., and Rau, B. R. 2000. Hpl-pd architecture specification: Version 1.1. Technical Report HPL-93-80(R.1), Hewlett--Packard Lab.
[17]
Lab., H. P., Group, R.-I., and Group, I. 1998. Trimaran user manual. http://www.trimaran.org/docs.html.
[18]
Landi, W. 1992. Undecidability of static analysis. ACM Lett. Programming Languages Systems 1, 4 (Dec.), 323--337.
[19]
Landi, W. and Ryder, B. G. 1992. A safe approximate algorithm for interprocedural pointer aliasing. SIGPLAN Notices 27, 7 (June), 235--248.
[20]
Lee, C., Potkonjak, M., and Mangione-Smith, W. H. 1997. Mediabench: A tool for evaluating and synthesizing multimedia and communicatons systems. In Proceedings of the 30th International Symposium on Microarchitecture. 330--335.
[21]
Mahlke, S. A., Lin, D. C., Chen, W. Y., Hank, R. E., and Bringmann, R. A. 1992. Effective compiler support for predicated execution using the hyperblock. In Proceedings of the 25th International Symposium on Microarchitecture. 45--54.
[22]
Maydan, D., Hennessy, J., and Lam, M. 1991. Efficient and exact data dependence analysis. In Proceedings of the ACM SIGPLAN'91 Conference on Programming Language Design and Implementation. 1--14.
[23]
Moon, S. and Hall, M. W. 1999. Evaluation of predicated array data-flow analysis for automatic parallelization. In Proceedings of the ACM Symposium on Principles Practice of Parallel Programming. 84--95.
[24]
Nicolau, A. 1989. Run-time disambiguation: Coping with statically unpredictable dependencies. IEEE Trans. Computers 38, 5 (May), 663--678.
[25]
Paek, Y., Hoeflinger, J., and Padua, D. 1998. Simplification of array access patterns for compiler optimizations. In Proceedings of the ACM SIGPLAN'98 Conference on Programming Language Design and Implementation. 60--71.
[26]
Pugh, W. and Wonnacott, D. 1998. Constraint-based array dependence analysis. ACM Transactions on Programming Languages and Systems 20, 3 (May), 635--678.
[27]
Ramalingam, G. 1994. The undecidability of aliasing. ACM Trans. Programming Languages and Systems 16, 5 (Sept.), 1467--1471.
[28]
Rau, B. R. 1995. Iterative modulo scheduling. Technical Report HPL-94-115, Hewlett--Packard Lab.
[29]
Rauchwerger, L. and Padua, D. 1994. The PRIVATIZING DOALL test: A run-time technique for DOALL loop identification and array privatization. In Proceedings of the ACM International Conference on Supercomputing (Manchester, England).
[30]
Salamí, E., Corbal, J., Alvarez, C., and Valero, M. 2002. Cost effective memory disambiguation for multimedia codes. In Proceedings of the International Conference on Compilers, Architecture, and Synthesis for Embedded Systems. 117--126.
[31]
Salamí, E., Corbal, J., Espasa, R., and Valero, M. 1999. An evaluation of different dlp alternatives for the embedded media domain. In Proceedings of the 1st Workshop on Media Processors and DSPs. 100--109.
[32]
Shapiro, M. and Horwitz, S. 1997. Fast and accurate flow-insensitive points-to analysis. In Proceedings of the ACM Symposium on Principles of Programming Languages. 1--14.
[33]
Steensgaard, B. 1996. Points-to analysis in almost linear time. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 32--41.
[34]
Wilson, R. P. and Lam, M. S. 1995. Efficient context-sensitive pointer analysis for c programs. In Proceedings of the ACM SIGPLAN'95 Conference on Programming Language Design and Implementation. 1--12.
[35]
Wolf, M. E. and Lam, M. S. 1991. A data locality optimizing algorithm. In Proceedings of the ACM SIGPLAN'91 Conference on Programming Language Design and Implementation. 30--44.
[36]
Yong, S. H., Horwitz, S., and Reps, T. W. 1999. Pointer analysis for programs with structures and casting. In SIGPLAN Conference on Programming Language Design and Implementation. 91--103.

Cited By

View all
  • (2014)Simulation-based memory dependence checker for CGRA-mapped code verification2014 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS.2014.6865365(1235-1238)Online publication date: Jun-2014
  • (2007)Automatic Discovery of Coarse-Grained Parallelism in Media ApplicationsTransactions on High-Performance Embedded Architectures and Compilers I10.1007/978-3-540-71528-3_13(194-213)Online publication date: 21-Jul-2007

Index Terms

  1. Dynamic memory interval test vs. interprocedural pointer analysis in multimedia applications

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Transactions on Architecture and Code Optimization
    ACM Transactions on Architecture and Code Optimization  Volume 2, Issue 2
    June 2005
    111 pages
    ISSN:1544-3566
    EISSN:1544-3973
    DOI:10.1145/1071604
    Issue’s Table of Contents
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 01 June 2005
    Published in TACO Volume 2, Issue 2

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Memory disambiguation
    2. VLIW
    3. multimedia

    Qualifiers

    • Article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)35
    • Downloads (Last 6 weeks)9
    Reflects downloads up to 15 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2014)Simulation-based memory dependence checker for CGRA-mapped code verification2014 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS.2014.6865365(1235-1238)Online publication date: Jun-2014
    • (2007)Automatic Discovery of Coarse-Grained Parallelism in Media ApplicationsTransactions on High-Performance Embedded Architectures and Compilers I10.1007/978-3-540-71528-3_13(194-213)Online publication date: 21-Jul-2007

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Full Access

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media