Article

Type systems for distributed data sharing

Authors:

Katherine YelickAuthors Info & Claims

SAS'03: Proceedings of the 10th international conference on Static analysis

Pages 273 - 294

Published: 11 June 2003 Publication History

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.

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.

Digital Library

[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.

Digital Library

[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.

[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.

Digital Library

[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.

Digital Library

[6]

B. Blanchet. Escape analysis for object oriented languages. Application to Java. In OOPSLA {27}, pages 20-34.

Digital Library

[7]

J. Bogda and U. Hölzle. Removing unnecessary synchronization in Java. In OOPSLA {27}, pages 35-46.

Digital Library

[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.

[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.

Digital Library

[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.

Digital Library

[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.

[12]

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

Digital Library

[13]

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

Digital Library

[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.

Digital Library

[15]

J. Foster. cqual. Available at 〈http://bane.cs.berkeley.edu/cqual〉, Nov. 2001.

[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.

Digital Library

[17]

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

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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〉.

Digital Library

[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〉.

Digital Library

[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.

Digital Library

[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.

[26]

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

[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.

[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.

Digital Library

[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.

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[34]

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

[35]

J. Whaley and M. Rinard. Compositional pointer and escape analysis for Java programs. In OOPSLA {27}, pages 187-206.

Digital Library

[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.

Digital Library

[37]

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

Digital Library

Cited By

Phothilimthana PJelvis TShah RTotla NChasins SBodik R(2014)ChlorophyllACM SIGPLAN Notices10.1145/2666356.259433949:6(396-407)Online publication date: 9-Jun-2014
https://dl.acm.org/doi/10.1145/2666356.2594339
Phothilimthana PJelvis TShah RTotla NChasins SBodik RO'Boyle MPingali K(2014)ChlorophyllProceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2594291.2594339(396-407)Online publication date: 9-Jun-2014
https://dl.acm.org/doi/10.1145/2594291.2594339
El-Zawawy M(2012)Abstraction analysis and certified flow and context sensitive points-to relation for distributed programsProceedings of the 12th international conference on Computational Science and Its Applications - Volume Part IV10.1007/978-3-642-31128-4_7(83-99)Online publication date: 18-Jun-2012
https://dl.acm.org/doi/10.1007/978-3-642-31128-4_7
Show More Cited By

Recommendations

Polymorphic type inference and abstract data types
Polymorphic type inference and abstract data types

Many statically typed programming languages provide an abstract data type construct, such as the module in Modula-2. However, in most of these languages, implementations of abstract data types are not first-class values. Thus, they cannot be assigned to ...
Metadata based management and sharing of distributed biomedical data

Biomedical research data sharing is becoming increasingly important for researchers to reuse experiments, pool expertise and validate approaches. However, there are many hurdles for data sharing, including the unwillingness to share, lack of flexible ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SAS'03: Proceedings of the 10th international conference on Static analysis

June 2003

504 pages

ISBN:3540403256

Editor:
Radhia Cousot
École Polytechnique, STIX, Palaiseau cedex, France

Sponsors

ACM: Association for Computing Machinery

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 11 June 2003

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Phothilimthana PJelvis TShah RTotla NChasins SBodik R(2014)ChlorophyllACM SIGPLAN Notices10.1145/2666356.259433949:6(396-407)Online publication date: 9-Jun-2014
https://dl.acm.org/doi/10.1145/2666356.2594339
Phothilimthana PJelvis TShah RTotla NChasins SBodik RO'Boyle MPingali K(2014)ChlorophyllProceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2594291.2594339(396-407)Online publication date: 9-Jun-2014
https://dl.acm.org/doi/10.1145/2594291.2594339
El-Zawawy M(2012)Abstraction analysis and certified flow and context sensitive points-to relation for distributed programsProceedings of the 12th international conference on Computational Science and Its Applications - Volume Part IV10.1007/978-3-642-31128-4_7(83-99)Online publication date: 18-Jun-2012
https://dl.acm.org/doi/10.1007/978-3-642-31128-4_7
Marino DSingh AMillstein TMusuvathi MNarayanasamy S(2010)DRFXACM SIGPLAN Notices10.1145/1809028.180663645:6(351-362)Online publication date: 5-Jun-2010
https://dl.acm.org/doi/10.1145/1809028.1806636
Marino DSingh AMillstein TMusuvathi MNarayanasamy SZorn BAiken A(2010)DRFXProceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/1806596.1806636(351-362)Online publication date: 5-Jun-2010
https://dl.acm.org/doi/10.1145/1806596.1806636
Ahn WQi SNicolaides MTorrellas JLee JFang XMidkiff SWong DAlbonesi DMartonosi MAugust DMartínez J(2009)BulkCompilerProceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture10.1145/1669112.1669131(133-144)Online publication date: 12-Dec-2009
https://dl.acm.org/doi/10.1145/1669112.1669131
Larsen PKarlsson SMadsen J(2009)Identifying Inter-task Communication in Shared Memory Programming ModelsProceedings of the 5th International Workshop on OpenMP: Evolving OpenMP in an Age of Extreme Parallelism10.1007/978-3-642-02303-3_14(168-182)Online publication date: 22-May-2009
https://dl.acm.org/doi/10.1007/978-3-642-02303-3_14
Kamil AYelick K(2007)Hierarchical pointer analysis for distributed programsProceedings of the 14th international conference on Static Analysis10.5555/2391451.2391471(281-297)Online publication date: 22-Aug-2007
https://dl.acm.org/doi/10.5555/2391451.2391471
Sura ZFang XWong CMidkiff SLee JPadua DPingali KYelick KGrimshaw A(2005)Compiler techniques for high performance sequentially consistent java programsProceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming10.1145/1065944.1065947(2-13)Online publication date: 15-Jun-2005
https://dl.acm.org/doi/10.1145/1065944.1065947
Kamil ASu JYelick KKramer W(2005)Making Sequential Consistency Practical in TitaniumProceedings of the 2005 ACM/IEEE conference on Supercomputing10.1109/SC.2005.43Online publication date: 12-Nov-2005
https://dl.acm.org/doi/10.1109/SC.2005.43

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

Media

Figures

Other

Tables

View Table of Contents