An algebraic array shape inference system for MATLAB®

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

An algebraic array shape inference system for MATLAB®

Full text

Pdf (1.03 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 28 , Issue 5 (September 2006) table of contents

Pages: 848 - 907

Year of Publication: 2006

ISSN:0164-0925

Authors

Pramod G. Joisha	Northwestern University, Redmond, WA
Prithviraj Banerjee	Northwestern University, Chicago, IL

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 101, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1152649.1152651 What is a DOI?

ABSTRACT

The problem of inferring array shapes ahead of time in languages that exhibit both implicit and dynamic typing is a critical one because the ramifications of its solution are the better organization of array storage through compaction and reuse, and the generation of high-performance code through specialization by shape. This article addresses the problem in a prototypical implicitly and dynamically typed array language called MATLAB. The approach involves modeling the language's shape semantics using an algebraic system, and applying term rewriting techniques to evaluate expressions under this algebra. Unlike prior efforts at array shape determination, this enables the deduction of valuable shape information even when array extents are compile-time unknowns. Furthermore, unlike some previous methods, our approach doesn't impose monotonicity requirements on an operator's shape semantics. The work also describes an inference methodology and reports measurements from a type inference engine called MAGICA. In a benchmark suite of 17 programs, the shape inference subsystem in MAGICA detected the equivalence of over 61% of the symbolic shapes in six programs, and over 57% and 37% of the symbolic shapes in two others. In the remaining nine programs, all array shapes were inferred to be compile-time constants.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Adams, J. C., Brainerd, W. S., Martin, J. T., Smith, B. T., and Wagener, J. L. 1992. FORTRAN 90 Handbook. McGraw-Hill, New York.
	2	Almási, G. 2001. MaJIC: A MATLAB Just-In-Time Compiler. Ph.D. thesis, University of Illinois at Urbana-Champaign.
	3	George Almási , David Padua, MaJIC: compiling MATLAB for speed and responsiveness, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany [doi>10.1145/512529.512564]
	4	Corinne Ancourt , Thi Viet Nga Nguyen, Array resizing for scientific code debugging, maintenance and reuse, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.32-37, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379656]
	5	Utpal K. Banerjee, Loop Transformations for Restructuring Compilers: The Foundations, Kluwer Academic Publishers, Norwell, MA, 1993
	6	Timothy Budd, An APL compiler, Springer-Verlag New York, Inc., New York, NY, 1988
	7	Stéphane Chauveau , François Bodin, Menhir: An Environment for High Performance Matlab, Selected Papers from the 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, p.27-40, May 28-30, 1998
	8	W-M Ching, Program analysis and code generation in an APL/370 compiler, IBM Journal of Research and Development, v.30 n.6, p.594-602, Nov. 1986
	9	Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
	10	Luiz Antonio De Rose , David Padua, Compiler techniques for matlab programs, 1996
	11	Luiz De Rose , David Padua, Techniques for the translation of MATLAB programs into Fortran 90, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.2, p.286-323, March 1999 [doi>10.1145/316686.316693]
	12	Dershowitz, N. and Plaisted, D. A. 2001. Rewriting. In Handbook of Automated Reasoning, A. Robinson and A. Voronkov, eds. vol. 1. Elsevier, Amsterdam, The Netherlands.
	13	Rajiv Gupta, Optimizing array bound checks using flow analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.135-150, March–Dec. 1993 [doi>10.1145/176454.176507]
	14	Hindley, J. R. 1969. The principal type-scheme of an object in combinatory logic. Trans. American Math. Society 146, 29--60.
	15	C. Barry Jay , Paul Steckler, The Functional Imperative: Shape!, Proceedings of the 7th European Symposium on Programming: Programming Languages and Systems, p.139-153, March 28-April 04, 1998
	16	Pramod G. Joisha , Prithviraj Banerjee, A type inference system for matlab with applications to code optimization, 2003
	17	Joisha, P. G. and Banerjee, P. 2001a. Computing array shapes in MATLAB. In Proceedings of the 14th International Workshop on Languages and Compilers for Parallel Computing. Lecture Notes in Computer Science, vol. 2624. Springer Verlag.
	18	Pramod G. Joisha , Prithviraj Banerjee, Correctly detecting intrinsic type errors in typeless languages such as MATLAB, Proceedings of the 2001 conference on APL: an arrays odyssey, p.7-21, June 25-28, 2001, New Haven, Connecticut [doi>10.1145/570407.570408]
	19	Joisha, P. G. and Banerjee, P. 2002. Implementing an array shape inference system for MATLAB using Mathematica. Tech. Rep. CPDC--TR--2002--10--003, Northwestern University.
	20	Pramod G. Joisha , Prithviraj Banerjee, Static array storage optimization in MATLAB, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA [doi>10.1145/781131.781160]
	21	Joisha, P. G. and Banerjee, P. 2003b. The MAGICA type inference engine for MATLAB. In Proceedings of the 12th International Conference on Compiler Construction. Lecture Notes in Computer Science, vol. 2622. Springer Verlag, 121--125.
	22	Joisha, P. G., Shenoy, U. N., and Banerjee, P. 2000. An approach to array shape determination in MATLAB. Tech. Rep. CPDC--TR--2000--10--010, Northwestern University.
	23	Marc A. Kaplan , Jeffrey D. Ullman, A general scheme for the automatic inference of variable types, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.60-75, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512768]
	24	Kevin Knight, Unification: a multidisciplinary survey, ACM Computing Surveys (CSUR), v.21 n.1, p.93-124, March 1989 [doi>10.1145/62029.62030]
	25	Malishevsky, A. 1998. Implementing a runtime library for a parallel MATLAB compiler. M.S. thesis, Oregon State University.
	26	McCosh, C. 2003. Type-Based specialization in a telescoping compiler for MATLAB. Tech. Rep. TR03--412, Rice University.
	27	Milner, R. 1978. A theory of type polymorphism in programming. J. Comput. Syst. Sci. 17, 3 (Dec.), 348--375.
	28	John C. Mitchell, Foundations of programming languages, MIT Press, Cambridge, MA, 1996
	29	Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
	30	Results from a Parallel MATLAB Compiler, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.81, March 30-April 03, 1998
	31	J. A. Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of the ACM (JACM), v.12 n.1, p.23-41, Jan. 1965 [doi>10.1145/321250.321253]
	32	Aaron Melvin Tenenbaum, Type determination for very high level languages., 1974
	33	The MathWorks, Inc. 1997. MATLAB: The Language of Technical Computing. The MathWorks, Inc. Using MATLAB (Version 5).
	34	The MathWorks, Inc. 2002a. Accelerating MATLAB: The MATLAB JIT-Accelerator. At http://www.mathworks.com/company/newsletters/digest/sept02/accel_matlab.pdf.
	35	The MathWorks, Inc. 2002b. The MathWorks announces release 13 with major new versions of MATLAB and Simulink. At http://www.mathworks.com/company/pressroom/index.shtml/article/332.
	36	Jean Paul Tremblay , R. Manohar, Discrete Mathematical Structures with Applications to Computer Science, McGraw-Hill, Inc., New York, NY, 1975
	37	Christoph Walther, Many-sorted unification, Journal of the ACM (JACM), v.35 n.1, p.1-17, Jan. 1988 [doi>10.1145/42267.45071]
	38	Weisstein, E. W. 2005. Hilbert matrix; From MathWorld---A Wolfram web resource. At http://mathworld.wolfram.com/HilbertMatrix.html.
	39	Clark Wiedmann, Steps toward an APL compiler, Proceedings of the international conference on APL: part 1, p.321-328, May 30-June 01, 1979, New York, New York, United States [doi>10.1145/800136.804481]
	40	Stephen Wolfram, The Mathematica book (4th edition), Cambridge University Press, New York, NY, 1999
	41	Hongwei Xi , Frank Pfenning, Eliminating array bound checking through dependent types, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.249-257, June 17-19, 1998, Montreal, Quebec, Canada [doi>10.1145/277650.277732]

CITED BY 2

	Pramod G. Joisha , Prithviraj Banerjee, A translator system for the MATLAB language: Research Articles, Software—Practice & Experience, v.37 n.5, p.535-578, April 2007
	Neil Birkbeck , Jonathan Levesque , Jose Nelson Amaral, A Dimension Abstraction Approach to Vectorization in Matlab, Proceedings of the International Symposium on Code Generation and Optimization, p.115-130, March 11-14, 2007