Type inference for locality analysis of distributed data structures

ABSTRACT

In languages with distributed heap data structures, the type system typically conveys only coarse locality information: whether a reference is local or possibly remote. Often, of interest to the optimizing compiler or the user is a more fine-grain information, such as whether two remote references point to objects in the same partition of the distributed heap.

This paper proposes a dependent type system, called place types, to capture such fine-grain locality information. The type of each reference identifies the heap partition, called a place, that the reference points to. This type system is expressive enough to statically type several commonly used distributed data structures. It also accommodates a "dynamic" type when no suitable static type exists. We show how to embed this type system as type annotations in the X10 programming language.

We also present a type inference algorithm for saving programmers from the burden of inserting type annotations. The type inference has been inspired by the use of type inference in functional programming languages such as ML. We have implemented the type inference algorithm in the X10 compiler. Experiments with small programs, but with the full set the relevant language features, have been successful in automatically finding the expected place types in these programs.

REFERENCES

• 1: Watson Libraries for Program Analysis (WALA). URL wala.sf.net.
• 2: Report on the experimental language X10. URL x10.sf.net.
• 3: Christopher Barton , CĆlin Casçaval , George Almási , Yili Zheng , Montse Farreras , Siddhartha Chatterje , José Nelson Amaral, Shared memory programming for large scale machines, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 4: Martin C. Carlisle , Anne Rogers, Software caching and computation migration in Olden, Journal of Parallel and Distributed Computing, v.38 n.2, p.248-255, Nov. 1, 1996 [doi>10.1006/jpdc.1996.0145]
• 5: Philippe Charles , Christian Grothoff , Vijay Saraswat , Christopher Donawa , Allan Kielstra , Kemal Ebcioglu , Christoph von Praun , Vivek Sarkar, X10: an object-oriented approach to non-uniform cluster computing, ACM SIGPLAN Notices, v.40 n.10, October 2005
• 6: Sigmund Cherem , Radu Rugina, Region analysis and transformation for Java programs, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029884]
• 7: Cristian Coarfa , Yuri Dotsenko , John Mellor-Crummey , François Cantonnet , Tarek El-Ghazawi , Ashrujit Mohanti , Yiyi Yao , Daniel Chavarría-Miranda, An evaluation of global address space languages: co-array fortran and unified parallel C, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065950]
• 8: Luis Damas , Robin Milner, Principal type-schemes for functional programs, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-212, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582176]
• 9: Fritz Henglein, Type inference with polymorphic recursion, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.2, p.253-289, April 1993 [doi>10.1145/169701.169692]
• 10: Ben Liblit , Alexander Aiken, Type systems for distributed data structures, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.199-213, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325717]
• 11: N. Nystrom, M. Clarkson, and A. Myers. Polyglot: An extensible compiler framework for Java. In 12th International Conference on Compiler Construction, 2003.
• 12: Mads Tofte , Jean-Pierre Talpin, Region-based memory management, Information and Computation, v.132 n.2, p.109-176, Feb. 1, 1997 [doi>10.1006/inco.1996.2613]
• 13: Yingchun Zhu , L. J. Hendren, Locality Analysis For Parallel C Programs, Proceedings of the 1997 International Conference on Parallel Architectures and Compilation Techniques, p.2, November 11-15, 1997

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Languages, Theory, Verification

Keywords:
equality-based constraint system, partitioned global address space, type inference, unification, x10