Skip to main content
SpringerLink
Log in

Type Systems for Distributed Data Sharing

  • Conference paper
  • First Online:
Static Analysis (SAS 2003)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2694))

Included in the following conference series:

Abstract

Parallel programming languages that let multiple processors access shared data provide a variety of sharing mechanisms and memory models. Understanding a language’s support for data sharing behavior is critical to understanding how the language can be used, and is also a component for numerous program analysis, optimization, and runtime clients. Languages that provide the illusion of a global address space, but are intended to work on machines with physically distributed memory, often distinguish between different kinds of pointers or shared data. The result can be subtle rules about what kinds of accesses are allowed in the application programs and implicit constraints on how the language may be implemented. This paper develops a basis for understanding the design space of these sharing formalisms, and codifies that understanding in a suite of type checking/inference systems that illustrate the trade-offs among various models.

This research was supported in part by NASA under NAG2-1210; NSF under EIA-9802069, CCR-0085949, and ACI-9619020; DOE under DE-FC03-01ER25509; and an NDSEG fellowship. The information presented here does not necessarily reflect the position or the policy of the Government and no official endorsement should be inferred.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. A. Agarwal, R. Bianchini, D. Chaiken, K. Johnson, D. Kranz, J. Kubiatowicz, B.-H. Lim, K. Mackenzie, and D. Yeung. The MIT Alewife machine: Architecture and performance. In Proc. of the 22nd Annual Int’l Symp. on Computer Architecture (ISCA’95), pages 2–13, June 1995.

    Google Scholar 

  2. A. Aiken and D. Gay. Barrier inference. In Conference Record of POPL’98: The 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 342–354, San Diego, California, January 19–21, 1998.

    Google Scholar 

  3. J. Aldrich, E. G. Sirer, C. Chambers, and S. J. Eggers. Comprehensive synchronization elimination for Java. Science of Computer Programming, to appear. Also published as University of Washington Technical Report UW-CSE-00-10-01, October 2000.

    Google Scholar 

  4. G. T. Balls. A Finite Difference Domain Decomposition Method Using Local Corrections for the Solution of Poisson’s Equation. PhD thesis, Department of Mechanical Engineering, University of California at Berkeley, 1999.

    Google Scholar 

  5. M. Berger and P. Colella. Local adaptive mesh refinement for shock hydrodynamics. Journal of Computational Physics, 82(1):64–84, May 1989. Lawrence Livermore Laboratory Report No. UCRL-97196.

    Article  MATH  Google Scholar 

  6. B. Blanchet. Escape analysis for object oriented languages. Application to Java. In OOPSLA [27], pages 20–34.

    Article  Google Scholar 

  7. J. Bogda and U. Hölzle. Removing unnecessary synchronization in Java. In OOPSLA [27], pages 35–46.

    Article  Google Scholar 

  8. E. D. Brooks, III. PCP: A parallel extension of C that is 99% fat free. Technical Report UCRL-99673, Lawrence Livermore National Laboratory, Sept. 1988.

    Google Scholar 

  9. M. C. Carlisle. Olden: Parallelizing Programs with Dynamic Data Structures on Distributed-Memory Machines. PhD thesis, Department of Computer Science, Princeton University, June 1996.

    Google Scholar 

  10. W. W. Carlson and J. M. Draper. Distributed data access in AC. In Proc. 5th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP’95, pages 39–47, Santa Barbara, California, July 1995. IDA Supercomputing Research Center.

    Google Scholar 

  11. W. W. Carlson, J. M. Draper, D. E. Culler, K. Yelick, E. Brooks, and K. Warren. Introduction to UPC and language specification. Technical Report CCS-TR-99-157, IDA Center for Computing Sciences, May 13 1999.

    Google Scholar 

  12. K. M. Chandy and C. Kesselman. Compositional C++: Compositional parallel programming. Lecture Notes in Computer Science, 757:124–144, 1993.

    Google Scholar 

  13. J.-D. Choi, M. Gupta, M. Serrano, V. C. Sreedhar, and S. Midkiff. Escape analysis for Java. In OOPSLA [27], pages 1–19.

    Article  Google Scholar 

  14. D. E. Culler, A. Dusseau, S. C. Goldstein, A. Krishnamurthy, S. Lumetta, T. von Eicken, and K. Yelick. Parallel programming in Split-C. In IEEE, editor, Proceedings, Supercomputing’ 93: Portland, Oregon, November 15–19, 1993, pages 262–273, 1109 Spring Street, Suite 300, Silver Spring, MD 20910, USA, 1993. IEEE Computer Society Press.

    Google Scholar 

  15. J. Foster. cqual. Available at <http://bane.cs.berkeley.edu/cqual>, Nov. 2001.

    Google Scholar 

  16. J. S. Foster, M. Fähndrich, and A. Aiken. A theory of type qualifiers. In Proceedings of the ACM SIGPLAN’ 99 Conference on Programming Language Design and Implementation, pages 192–203, Atlanta, Georgia, May 1–4, 1999. SIGPLAN Notices, 34(5), May 1999.

    Article  Google Scholar 

  17. D. P. Helmbold and C. E. McDowell. Computing reachable states of parallel programs. ACM SIGPLAN Notices, 26(12):76–84, Dec. 1991.

    Article  Google Scholar 

  18. L. J. Hendren, X. Tang, Y. Zhu, S. Ghobrial, G. R. Gao, X. Xue, H. Cai, and P. Ouellet. Compiling C for the EARTH multithreaded architecture. International Journal of Parallel Programming, 25(4):305–338, Aug. 1997.

    Article  Google Scholar 

  19. F. Henglein and J. Rehof. The complexity of subtype entailment for simple types. In Proceedings, Twelth Annual IEEE Symposium on Logic in Computer Science, pages 352–361, Warsaw, Poland, 29 June–2 July 1997. IEEE Computer Society Press.

    Google Scholar 

  20. P. N. Hilfinger, D. Bonachea, D. Gay, S. Graham, B. Liblit, and K. Yelick. Titanium language reference manual. Technical Report CSD-01-1163, University of California, Berkeley, Nov. 2001.

    Google Scholar 

  21. B. Liblit and A. Aiken. Type systems for distributed data structures. In Conference Record of POPL’00: The 27th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 199–213, Boston, Massachusetts, January 19–21, 2000.

    Google Scholar 

  22. B. Liblit and A. Aiken. Type systems for distributed data structures. Technical Report CSD-99-1072, University of California, Berkeley, Jan. 2000. Available at <http://sunsite.berkeley.edu/TechRepPages/CSD-99-1072>.

    Google Scholar 

  23. B. Liblit, A. Aiken, and K. Yelick. Data sharing analysis for Titanium. Technical Report CSD-01-1165, University of California, Berkeley, Nov. 2001. Available at <http://sunsite.berkeley.edu/TechRepPages/CSD-01-1165>.

    Google Scholar 

  24. J. Mellor-Crummey. Compile-time support for efficient data race detection in shared-memory parallel programs. ACM SIGPLAN Notices, 28(12):129–139, Dec. 1993.

    Article  Google Scholar 

  25. S. P. Midkiff and D. A. Padua. Issues in the optimization of parallel programs. In Proceedings of the 1990 International Conference on Parallel Processing, volume II, Software, pages II-105–II-113, University Park, Penn, Aug. 1990. Penn State U. Press. CSRD TR#993, U. Ill.

    Google Scholar 

  26. Myricom Inc. The GM Message Passing System, July 18 2000. Version 1.1.

    Google Scholar 

  27. OOPSLA’99 ACM Conference on Object-Oriented Systems, Languages and Applications, volume 34(10) of ACM SIGPLAN Notices, Denver, CO, Oct. 1999. ACM Press.

    Google Scholar 

    Google Scholar 

  28. C. S. Peskin and D. M. McQueen. A three-dimensional computational method for blood flow in the heart. I. Immersed elastic fibers in a viscous incompressible fluid. Journal of Computational Physics, 81(2):372–405, Apr. 1989.

    Article  MATH  MathSciNet  Google Scholar 

  29. G. Pike, L. Semenzato, P. Colella, and P. N. Hilfinger. Parallel 3D adaptive mesh refinement in Titanium. In Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing, San Antonio, Texas, Mar. 1999.

    Google Scholar 

  30. D. Plainfossé and M. Shapiro. A survey of distributed garbage collection techniques. In H. Baker, editor, Proceedings of International Workshop on Memory Management, volume 986 of Lecture Notes in Computer Science, ILOG, Gentilly, France, and INRIA, Le Chesnay, France, Sept. 1995. Springer-Verlag.

    Google Scholar 

  31. M. C. Rinard and M. S. Lam. The design, implementation, and evaluation of Jade. ACM Transactions on Programming Languages and Systems, 20(3):483–545, May 1998.

    Article  Google Scholar 

  32. S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM Transactions on Computer Systems, 15(4):391–411, Nov. 1997.

    Article  Google Scholar 

  33. B. Steensgaard. Thread-specific heaps for multi-threaded programs. In T. Hosking, editor, ISMM 2000 Proceedings of the Second International Symposium on Memory Management, volume 36(1) of ACM SIGPLAN Notices, Minneapolis, MN, Oct. 2000. ACM Press.

    Google Scholar 

  34. Supercomputing Technologies Group, MIT Laboratory for Computer Science. Cilk 5.3.1 Reference Manual, June 24 2000.

    Google Scholar 

  35. J. Whaley and M. Rinard. Compositional pointer and escape analysis for Java programs. In OOPSLA [27], pages 187–206.

    Article  Google Scholar 

  36. Y. Zhu and L. Hendren. Locality analysis for parallel C programs. IEEE Transactions on Parallel and Distributed Systems, 10(2):99–114, Feb. 1999.

    Article  Google Scholar 

  37. Y. Zhu and L. J. Hendren. Communication optimizations for parallel C programs. ACM SIGPLAN Notices, 33(5):199–211, May 1998.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of California, Berkeley, Berkeley, CA, 94720-1776

    Ben Liblit, Alex Aiken & Katherine Yelick

Authors
  1. Ben Liblit
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alex Aiken
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Katherine Yelick
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. École Polytechnique, STIX, 91128, Palaiseau cedex, France

    Radhia Cousot

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Liblit, B., Aiken, A., Yelick, K. (2003). Type Systems for Distributed Data Sharing. In: Cousot, R. (eds) Static Analysis. SAS 2003. Lecture Notes in Computer Science, vol 2694. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44898-5_15

Download citation

  • DOI: https://doi.org/10.1007/3-540-44898-5_15

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-40325-8

  • Online ISBN: 978-3-540-44898-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation