article

Free access

Array form representation of idiom recognition system for numerical programs

Author:

Sato HiroyukiAuthors Info & Claims

ACM SIGAPL APL Quote Quad, Volume 31, Issue 2

Pages 87 - 98

https://doi.org/10.1145/570406.570418

Published: 01 December 2000 Publication History

Abstract

Today, PSE emerges as a promising approach for providing programmers with high-level abstract functions Particularly for numerical programs which essentially handle large arrays, abstract representation of array-handling functions is very important. Idiom recognition can be a bridge between abstract source programs and concrete architectures. It can remove obstacles of gaps between the two that cannot be bridged by today's state of the art compilers. A major problem in idiom recognition is intermediate representation. This paper applies term rewriting theory---a very general framework --- to an idiom recognition system. Specifically, we apply it to the idiom recognition problem of Fortran90/95 matrix manipulations, and show that the Fortran90/95 system is never a trivial system. Straight forms are introduced to make the idiom recognition system more powerful. We make a completion procedure based on this Fortran90/95 system, and show some non-trivial idiom recognition using our theory.

References

[1]

Aho, A., Ganapathi, M. Tjiang, W.: "Code Generation Using Tree Pattern Matching and Dynamic Programming," ACM Trans. Programming Lang. and Syst., vol. 11, 1989, 491-516.

Digital Library

[2]

Anderson, E. et al.: LAPACK User's Guide, 1994.

Digital Library

[3]

Appel, A.: Compiling with Continuations, 1992.

Digital Library

[4]

Bergstra, J., Klop, J.: "Conditional Rewrite Rules: Confluence and Termination," J. Computer and System Sciences," vol. 32, 1986, 323-- 362.

Digital Library

[5]

Bik, A., Wijshoff, H.: "Automatic Data Selection and Transformation for Sparse Matrix Computations," IEEE Trans. Parallel and Distributed Systems, Vol. 7, 1996, 109-126.

Digital Library

[6]

Bilmes, J., Asanovic, K. Chin, C.W., Demmel, J.: "Optimizing Matrix Multiply using PhiPac: a Portable High-Performance ANSI C Coding Methodology," Proc. International Conference Supercomputing '97, 1997, 340-347.

Digital Library

[7]

Chamberlain, B., Lewis, E., Snyder, L.: "Problem Space Promotion and Its Evaluation as a Technique for Efficient Parallel Computation," Proc. 1999 Int'l Conf. Supercomputing, 1999, 311-318.

Digital Library

[8]

DeRose, L., Gallivan, K., Gallopoulos, B.: "FALCON:A MATLAB Interactive Restructuring Compiler," Proc. Language and Compilers for Parallel Computing, 1995, 269-288.

Digital Library

[9]

Glanville, R., Graham, S., Graham, S.: "A New Model for Compiler Code Generation," Proc. 1979 Principles of Programming Languages, 1979, 231-240.

Digital Library

[10]

Gomez, C., Scott T.: "Maple programs for generating efficient Fortran code for serial and vectorized machines," Computer Physics Communications, vol. 115, 1998, 648-562.

[11]

Haghighat, M. and Polychronopoulos, C.: "Symbolic analysis for parallelizing compilers," ACM Trans. Programming Lang. and Syst., vol. 18, 1997, 477-511.

Digital Library

[12]

HPF Forum: HPF Standard 2.0, 1995.

[13]

Huet, G.: "A complete proof of correctness of the Knuth-Bendix completion procedure," Journal Computer and System Sciences, vol. 23, 1981, 11-21.

[14]

ISO/IECJTC1/SC22/WG5:Fortran95 Standard, 1996.

[15]

Knuth, D., and Bendix, P.: "Simple word problems in universal algebra," Computational Problems in Abstract Algebra, 1970, 263-297.

[16]

Lam, M., Rothberg, E., Wolf, M.: "The Cache Performance and Optimizations of Blocked Algorithms," Proc. 1991 Arch. Support for Prog. Lang. and OS, 1991, 63-74.

Digital Library

[17]

Lincoln, P., Christian, J.: "Adventures in associative-commutative unification," J. Symbolic Computation, vol. 8, 1989, 217-240.

Digital Library

[18]

Menon, V., Pingali, K.: "High-Level Semantic Optimization of Numerical Codes," Proc. 1999 Int'l Conf. Supercomputing, 1999, 434-443.

Digital Library

[19]

Muchnick, S.: Advanced Compiler Design and Implementation, 1997.

Digital Library

[20]

Pinter, S., Pinger, R.: "Program Optimization and Parallelization Using Idioms," ACM Trans. Programming Lang. and Syst., vol. 14, 1994, 305-327.

Digital Library

[21]

Stickel, M.: "A Unification Algorithm for Associative-Commutative Functions," Journal ACM, vol. 28, 1981, 423-434.

Digital Library

[22]

Thinking Machines Corp.: "Using the CMAX Converter," 1994.

[23]

van de Geijn, R., Watt, J.: "SUMMA: Scalable universal matrix manipulation implication algorithm," Concurrency: Practice and Experience, vol. 9, 1997, 255-274.

[24]

Whaley, R., Dontarra, J.: "Automatically Tuned Linear Algebra Software, Atlas Project," http://www.netlib.org/atlas/

[25]

Wolfe, M.: "Beyond Induciton Variables," Proc. 1992 Programming Language Design and Implementation, 1992, 162-174.

Digital Library

[26]

The MATCH: http://www.ece.nwu.edu/cpdc/Match/Match.html

[27]

http://www.netlib-org/blas/

Cited By

De Carvalho JKuzma BKorostelev IAmaral JBarton CMoreira JAraujo G(2021)KernelFaRerACM Transactions on Architecture and Code Optimization10.1145/345901018:3(1-22)Online publication date: 28-Jun-2021
https://dl.acm.org/doi/10.1145/3459010
Kawahito MKomatsu HMoriyama TInoue HNakatani T(2013)Idiom recognition framework using topological embeddingACM Transactions on Architecture and Code Optimization10.1145/251243110:3(1-34)Online publication date: 16-Sep-2013
https://dl.acm.org/doi/10.1145/2512431
Olschanowsky CSnavely AMeswani MCarrington L(2010)PIRProceedings of the 2010 39th International Conference on Parallel Processing Workshops10.1109/ICPPW.2010.36(189-196)Online publication date: 13-Sep-2010
https://dl.acm.org/doi/10.1109/ICPPW.2010.36
Show More Cited By

Index Terms

Array form representation of idiom recognition system for numerical programs
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
      2. Language types
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs

Recommendations

Array form representation of idiom recognition system for numerical programs
APL '01: Proceedings of the 2001 conference on APL: an arrays odyssey

Today, PSE emerges as a promising approach for providing programmers with high-level abstract functions Particularly for numerical programs which essentially handle large arrays, abstract representation of array-handling functions is very important. ...
Latent Idiom Recognition for a Minimalist Functional Array Language Using Equality Saturation
CGO '24: Proceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization

Accelerating programs is typically done by recognizing code idioms matching high-performance libraries or hardware interfaces. However, recognizing such idioms automatically is challenging. The idiom recognition machinery is difficult to write and ...
Japanese idiom recognition: drawing a line between literal and idiomatic meanings
COLING-ACL '06: Proceedings of the COLING/ACL on Main conference poster sessions

Recognizing idioms in a sentence is important to sentence understanding. This paper discusses the lexical knowledge of idioms for idiom recognition. The challenges are that idioms can be ambiguous between literal and idiomatic meanings, and that they ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGAPL APL Quote Quad

ACM SIGAPL APL Quote Quad Volume 31, Issue 2

December 2000

116 pages

ISSN:0163-6006

DOI:10.1145/570406

Issue’s Table of Contents

APL '01: Proceedings of the 2001 conference on APL: an arrays odyssey
July 2001
127 pages
ISBN:1581134193
DOI:10.1145/570407
Conference Chair:
Ed Shaw
Qualedi, Inc.
,
Program Chair:
Lynne Shaw

Copyright © 2000 Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2000

Published in SIGAPL Volume 31, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
437
Total Downloads

Downloads (Last 12 months)46
Downloads (Last 6 weeks)7

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

De Carvalho JKuzma BKorostelev IAmaral JBarton CMoreira JAraujo G(2021)KernelFaRerACM Transactions on Architecture and Code Optimization10.1145/345901018:3(1-22)Online publication date: 28-Jun-2021
https://dl.acm.org/doi/10.1145/3459010
Kawahito MKomatsu HMoriyama TInoue HNakatani T(2013)Idiom recognition framework using topological embeddingACM Transactions on Architecture and Code Optimization10.1145/251243110:3(1-34)Online publication date: 16-Sep-2013
https://dl.acm.org/doi/10.1145/2512431
Olschanowsky CSnavely AMeswani MCarrington L(2010)PIRProceedings of the 2010 39th International Conference on Parallel Processing Workshops10.1109/ICPPW.2010.36(189-196)Online publication date: 13-Sep-2010
https://dl.acm.org/doi/10.1109/ICPPW.2010.36
Birkbeck NLevesque JAmaral J(2007)A Dimension Abstraction Approach to Vectorization in MatlabProceedings of the International Symposium on Code Generation and Optimization10.1109/CGO.2007.1(115-130)Online publication date: 11-Mar-2007
https://dl.acm.org/doi/10.1109/CGO.2007.1
Kawahito MKomatsu HMoriyama TInoue HNakatani T(2006)A new idiom recognition framework for exploiting hardware-assist instructionsACM SIGARCH Computer Architecture News10.1145/1168919.116890534:5(382-393)Online publication date: 20-Oct-2006
https://dl.acm.org/doi/10.1145/1168919.1168905
Kawahito MKomatsu HMoriyama TInoue HNakatani T(2006)A new idiom recognition framework for exploiting hardware-assist instructionsACM SIGPLAN Notices10.1145/1168918.116890541:11(382-393)Online publication date: 20-Oct-2006
https://dl.acm.org/doi/10.1145/1168918.1168905
Kawahito MKomatsu HMoriyama TInoue HNakatani T(2006)A new idiom recognition framework for exploiting hardware-assist instructionsACM SIGOPS Operating Systems Review10.1145/1168917.116890540:5(382-393)Online publication date: 20-Oct-2006
https://dl.acm.org/doi/10.1145/1168917.1168905
Kawahito MKomatsu HMoriyama TInoue HNakatani TShen JMartonosi M(2006)A new idiom recognition framework for exploiting hardware-assist instructionsProceedings of the 12th international conference on Architectural support for programming languages and operating systems10.1145/1168857.1168905(382-393)Online publication date: 23-Oct-2006
https://dl.acm.org/doi/10.1145/1168857.1168905

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents