Reasoning about inherent parallelism in modern object-oriented languages

ABSTRACT

In the future, if we are to continue to expect improved application performance we will have to achieve it by exploiting course-grained hardware parallelism rather then simply relying on processor cycles getting faster. Programmers will, therefore, need to accept some of the burden of detecting and exploiting application level parallelism because automatic parallelization is still far from a reality. On the one hand we need to fundamentally reconsider how we express algorithms as the languages we currently use were never designed to make reasoning about parallelism easy. On the other hand, to be widely adopted, any new programming approach will need to be only incrementally different to current paradigms. This paper attempts to find that difficult balance. It extends modern object-oriented programming techniques with a new abstraction that allows either programmers or automatic parallelizing compilers to reason about inherent data parallelism.

REFERENCES

• 1: Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 2: Almeida, P. S. (1997) Balloon Types: Controlling Sharing of State in Data Types. ECOOP '97 - Object-Oriented Programming. Heidelberg, Berlin, Springer Berlin / Heidelberg.
• 3: Chandrasekhar Boyapati , Robert Lee , Martin Rinard, Ownership types for safe programming: preventing data races and deadlocks, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 4: John Boyland , James Noble , William Retert, Capabilities for Sharing: A Generalisation of Uniqueness and Read-Only, Proceedings of the 15th European Conference on Object-Oriented Programming, p.2-27, June 18-22, 2001
• 5: Dave Clarke , Sophia Drossopoulou, Ownership, encapsulation and the disjointness of type and effect, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 6: David G. Clarke , John M. Potter , James Noble, Ownership types for flexible alias protection, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.48-64, October 18-22, 1998, Vancouver, British Columbia, Canada
• 7: Cohen, A., Wu, P. & Padua, D. (2001) Pointer Analysis for Monotonic Container Traversals (CSRD TR-1586). Univeristy of Illinois at Urbana-Champaign.
• 8: Dongol, B. & Mooij, A. J. (2006) Progress in Deriving Concurrent Programs: Emphasizing the Role of Stable Guards. 8th International Conference on the Mathematics of Program Construction Kuressaare, Estonia, Springer Berlin / Heidelberg.
• 9: John Hogg, Islands: aliasing protection in object-oriented languages, Conference proceedings on Object-oriented programming systems, languages, and applications, p.271-285, October 06-11, 1991, Phoenix, Arizona, United States
• 10: Lhoták, O. & Hendren, L. (2006) Context-Sensitive Points-to Analysis: Is It Worth It? 15th International Conference on Compiler Construction. Vienna, Austria, Springer.
• 11: Yi Lu , John Potter, Protecting representation with effect encapsulation, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.359-371, January 11-13, 2006, Charleston, South Carolina, USA
• 12: Ana Milanova , Atanas Rountev , Barbara G. Ryder, Parameterized object sensitivity for points-to analysis for Java, ACM Transactions on Software Engineering and Methodology (TOSEM), v.14 n.1, p.1-41, January 2005 [doi>10.1145/1044834.1044835]
• 13: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 14: Noble, J., Vitek, J. & Potter, J. (1998) Flexible Alias Protection. IN JUL, E. (Ed.) Lecture Notes in Computer Science. Berlin, Hidleburg, New York, Springer Berlin / Hamburg.
• 15: Ravi Ponnusamy , Yuan-Shin Hwang , Raja Das , Joel Saltz , Alok Choudhary , Geoffrey Fox, Supporting irregular distributions in FORTRAN 90D/HPF compilers, University of Maryland at College Park, College Park, MD, 1994
• 16: Martin C. Rinard , Monica S. Lam, The design, implementation, and evaluation of Jade, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.3, p.483-545, May 1998 [doi>10.1145/291889.291893]
• 17: Rus, T. & Van Wyk, E. (1997) Model Checking as a Tool Used by Parallelizing Compilers. 2nd International Workshop on Formal Methods for Parallel Programming: Theory and Applications. Geneva, Switzerland.

INDEX TERMS

Keywords:
object-oriented, ownership types, parallelism, reasoning