skip to main content
10.1145/1345206.1345211acmconferencesArticle/Chapter ViewAbstractPublication PagesppoppConference Proceedingsconference-collections
research-article

Type inference for locality analysis of distributed data structures

Published: 20 February 2008 Publication History

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, and José Nelson Amaral. Shared memory programming for large scale machines. In PLDI ?06: Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, pages 108--117, New York, NY, USA, 2006. ACM Press. ISBN 1-59593-320-4.
[4]
Martin C. Carlisle and Anne Rogers. Software caching and computation migration in Olden. Journal of Parallel and Distributed Computing, 38 (2): 248--255, 1996.
[5]
Philippe Charles, Christian Grothoff, Vijay A. Saraswat, Christopher Donawa, Allan Kielstra, Kemal Ebcioglu, Christoph von Praun, and Vivek Sarkar. X10: an object-oriented approach to non-uniform cluster computing. In OOPSLA, pages 519--538, 2005.
[6]
Sigmund Cherem and Radu Rugina. Region analysis and transformation for Java programs. In ISMM ?04: Proceedings of the 4th international symposium on Memory management, pages 85--96, New York, NY, USA, 2004. ACM. ISBN 1-58113-945-4.
[7]
Cristian Coarfa, Yuri Dotsenko, John Mellor-Crummey, François Cantonnet, Tarek El-Ghazawi, Ashrujit Mohanti, Yiyi Yao, and Daniel Chavarría-Miranda. An evaluation of global address space languages: co-array Fortran and unified parallel C. In PPoPP '05: Proceedings of the tenth ACM SIGPLAN symposium on Principles and Practice of Parallel Programming, pages 36--47, New York, NY, USA, 2005. ACM Press. ISBN 1-59593-080-9.
[8]
L. Damas and R. Milner. Principal type schemes in functional programming. In Proceedings of the 1982 Symposium on Principles of Programming Languages, 1982.
[9]
F. Henglein. Type inference with polymoprphic recursion. ACM Transactions on Programming Languages and Systems, 15, 1993.
[10]
Ben Liblit and Alexander Aiken. Type systems for distributed data structures. In POPL '00: Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 199--213, New York, NY, USA, 2000. ACM Press. ISBN 1-58113-125-9.
[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 and Jean-Pierre Talpin. Region-based memory management. Information and Computation, 1997.
[13]
Yingchun Zhu and L. J. Hendren. Locality analysis for parallel C programs. In PACT '97: Proceedings of the 1997 International Conference on Parallel Architectures and Compilation Techniques, page 2, Washington, DC, USA, 1997. IEEE Computer Society. ISBN 0-8186-8090-3.

Cited By

View all
  • (2024)DRustProceedings of the 18th USENIX Conference on Operating Systems Design and Implementation10.5555/3691938.3691944(97-115)Online publication date: 10-Jul-2024
  • (2024)Bridging Between Active Objects: Multitier Programming for Distributed, Concurrent SystemsActive Object Languages: Current Research Trends10.1007/978-3-031-51060-1_4(92-122)Online publication date: 29-Jan-2024
  • (2020)A Survey of Multitier ProgrammingACM Computing Surveys10.1145/339749553:4(1-35)Online publication date: 26-Sep-2020
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming
February 2008
308 pages
ISBN:9781595937957
DOI:10.1145/1345206
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 February 2008

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. equality-based constraint system
  2. partitioned global address space
  3. type inference
  4. unification
  5. x10

Qualifiers

  • Research-article

Conference

PPoPP08
Sponsor:

Acceptance Rates

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Upcoming Conference

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

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

Other Metrics

Citations

Cited By

View all
  • (2024)DRustProceedings of the 18th USENIX Conference on Operating Systems Design and Implementation10.5555/3691938.3691944(97-115)Online publication date: 10-Jul-2024
  • (2024)Bridging Between Active Objects: Multitier Programming for Distributed, Concurrent SystemsActive Object Languages: Current Research Trends10.1007/978-3-031-51060-1_4(92-122)Online publication date: 29-Jan-2024
  • (2020)A Survey of Multitier ProgrammingACM Computing Surveys10.1145/339749553:4(1-35)Online publication date: 26-Sep-2020
  • (2019)Optimizing Remote Communication in X10ACM Transactions on Architecture and Code Optimization10.1145/334555816:4(1-26)Online publication date: 11-Oct-2019
  • (2018)Distributed system development with ScalaLociProceedings of the ACM on Programming Languages10.1145/32764992:OOPSLA(1-30)Online publication date: 24-Oct-2018
  • (2018)Optimizing remote data transfers in X10Proceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques10.1145/3243176.3243209(1-15)Online publication date: 1-Nov-2018
  • (2018)Competitive parallelism: getting your priorities rightProceedings of the ACM on Programming Languages10.1145/32367902:ICFP(1-30)Online publication date: 30-Jul-2018
  • (2018)LAPPSACM Transactions on Architecture and Code Optimization10.1145/323329915:3(1-26)Online publication date: 28-Aug-2018
  • (2016)Behavioural types for non-uniform memory accessesElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.203.9203(109-120)Online publication date: 10-Feb-2016
  • (2016)X10 and APGAS at PetascaleACM Transactions on Parallel Computing10.1145/28947462:4(1-32)Online publication date: 15-Mar-2016
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media