Pramod G. Joisha. A Type Inference System for MATLAB with Applications to Code Optimization. Electrical and Computer Engineering Department, Northwestern University. December 2003. [ ps ] [ ps.gz ]

Abstract This thesis presents techniques for deducing valuable array shape information in typeless array-based languages like MATLAB, even when the shapes may be statically unknown. The approach is based on an algebraical modelling of the language's array shape semantics.

The dissertation makes five primary contributions: (1) it shows how to model shape semantics so as to enable precise characterizations that are independent of an array's dimensionality; (2) it presents a rewriting methodology that uses the characterizations to symbolically determine an array expression's shape in O(R||s||³log||s||) time, where ||s|| is the number of nodes in a rooted ordered tree representation of a shape term s, and R is an upper bound on an array's canonical rank; (3) it presents a shape-tracking optimization that detects equivalent shapes, permitting a translator to eliminate redundant shape checks, and to generate specialized code even when the shapes may be compile-time unknowns; (4) it shows a preallocation optimization that determines the set of all possible shapes that an expression may assume during program execution; and (5) it presents an interference graph-based algorithm that uses type and control-flow information to coalesce array storage. The dissertation also substantiates the techniques by presenting performance numbers of an implementation on a benchmark suite.

1. Samuel P. Midkiff, Pramod G. Joisha, Mauricio J. Serrano, Manish Gupta, Anthony Bolmarcich, Peng Wu. Quicksilver: A Quasi-Static Java Compiler for Embedded Systems.
   
   In Java Microarchitectures, edited by Vijaykrishnan Narayanan, Mario L. Wolczko. Kluwer International Series in Engineering and Computer Science. Vol., 679, ISBN 1-4020-7034-9. April 2002.
   

1. Pramod G. Joisha, Samuel P. Midkiff, Mauricio J. Serrano, Manish Gupta. Efficiently Adapting Java Binaries in Limited Memory Contexts. Special Issue of the International Journal of Parallel Programming, Vol., 30, Issue 4. Kluwer Academic Publishers. August 2002. [ pdf ]
   
   
2. Pramod G. Joisha, P. Banerjee. The Efficient Computation of Ownership Sets in HPF. IEEE Transactions on Parallel and Distributed Systems, Vol., 12, No., 8. August 2001. [ pdf ]
   

1. Pramod G. Joisha, Prithviraj Banerjee. Static Array Storage Optimization in MATLAB. Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), San Diego, USA. June 2003. [ pdf ]
   
   
2. Pramod G. Joisha, Prithviraj Banerjee. The MAGICA Type Inference Engine for MATLAB. Proceedings of the 12th International Conference on Compiler Construction (CC), Warsaw, Poland. April 2003. (Tool demonstration paper.) In Springer-Verlag Lecture Notes in Computer Science Series, Vol., 2622. [ pdf ]
   
   
3. Pramod G. Joisha, Prithviraj Banerjee. Computing Array Shapes in MATLAB. Proceedings of the International Workshop on Languages and Compilers for Parallel Computing (LCPC), Cumberland Falls, USA. August 2001. In Springer-Verlag Lecture Notes in Computer Science Series, Vol., 2624. [ pdf ]
   
   
4. Pramod G. Joisha, Prithviraj Banerjee. Correctly Detecting Intrinsic Type Errors in Typeless Languages such as MATLAB. ACM SIGAPL International Conference on Array Processing Languages (APL), Yale University, New Haven, USA. June 2001.
   
   
5. Pramod G. Joisha, Samuel P. Midkiff, Mauricio J. Serrano, Manish Gupta. A Framework for Efficient Reuse of Binary Code in Java. ACM SIGARCH International Conference on Supercomputing (ICS), Naples, Italy. June 2001.
   

   Also presented at the 9th Workshop on Compilers for Parallel Computers (CPC), Edinburgh, UK. June 2001.

6. Anshuman Nayak, Malay Haldar, Abhay Kanhere, Pramod G. Joisha, U. Nagaraj Shenoy, Alok Choudhary, Prithviraj Banerjee. A Library-Based Compiler to Execute MATLAB Programs on a Heterogeneous Platform. IEEE International Conference on Parallel and Distributed Computing Systems (PDCS), Las Vegas, USA. August 2000.
   
   
7. Pramod G. Joisha, Prithviraj Banerjee. Exploiting Ownership Sets in HPF. Proceedings of the International Workshop on Languages and Compilers for Parallel Computing, IBM T. J. Watson Research Center, Yorktown Heights, USA. August 2000. In Springer-Verlag Lecture Notes in Computer Science Series, Vol., 2017.
   
   
8. Malay Haldar, Anshuman Nayak, Abhay Kanhere, Pramod G. Joisha, U. Nagaraj Shenoy, Alok Choudhary, Prithviraj Banerjee. MATCH Virtual Machine: An Adaptive Run-Time System to Execute MATLAB in Parallel. International Conference on Parallel Processing (ICPP), Toronto, Canada. IEEE Computer Society Press. August 2000.
   
   
9. Pramod G. Joisha, Abhay Kanhere, Prithviraj Banerjee, U. Nagaraj Shenoy, Alok Choudhary. Handling Context Sensitive Syntactic Issues in the Design of a Front-End for a MATLAB Compiler. ACM SIGAPL International Conference on Array Processing Languages, Technischen Universitat, Berlin, Germany. July 2000. [ pdf ]
   
   
10. Prithviraj Banerjee, U. Nagaraj Shenoy, Alok Choudhary, Scott Hauck, Christopher Bachmann, Malay Haldar, Pramod G. Joisha, Alexander K. Jones, Abhay Kanhere, Anshuman Nayak, Suresh Periyacheri, Michael Walkden, David Zaretsky. A MATLAB Compiler for Distributed, Heterogeneous, Reconfigurable Computing Systems. IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), Napa Valley, USA. April 2000.
    
    
11. Pramod G. Joisha, Prithviraj Banerjee. PARADIGM (version 2.0): A New HPF Compilation System. IEEE International Parallel Processing Symposium and the Symposium on Parallel and Distributed Processing (IPPS/SPDP), San Juan, Puerto Rico. April 1999.
    
    
12. Dhruva R. Chakrabarti, Pramod G. Joisha, John A. Chandy, D. Krishnaswamy, V. Krishnaswamy, Prithviraj Banerjee. WADE: A Web-Based Automated Parallel CAD Environment. International Conference on High Performance Computing (HiPC), Chennai, India. IEEE Computer Society Press. December 1998.
    

1. Pramod G. Joisha, Prithviraj Banerjee. MAGICA: A Software Tool for Inferring Types in MATLAB. (CPDC-TR-2002-10-004). October 2002. [ pdf ]
   
   
2. Pramod G. Joisha, Prithviraj Banerjee. Implementing an Array Shape Inference System for MATLAB Using Mathematica. (CPDC-TR-2002-10-003). October 2002. [ pdf ]
   
   
3. Pramod G. Joisha, U. Nagaraj Shenoy, Prithviraj Banerjee. An Approach to Array Shape Determination in MATLAB. (CPDC-TR-2000-10-010). October 2000. [ pdf ]
   
   
4. Pramod G. Joisha, Abhay Kanhere, Prithviraj Banerjee, U. Nagaraj Shenoy, Alok Choudhary. The Design and Implementation of a Parser and Scanner for the MATLAB Language in the MATCH Compiler. (CPDC-TR-9909-017). September 1999. [ pdf ]