Concise analysis using implication algebras for task-local memory optimisation

Add to your list(s) Download to your calendar using vCal

• Leo White
• Tuesday 11 June 2013, 13:00-14:00
• FW22, Computer Laboratory, William Gates Building.

If you have a question about this talk, please contact Raoul-Gabriel Urma.

OpenMP is a pragma-based extension to C to support parallelism. The OpenMP standard recently added support for task-based parallelism but in a richer way than languages such as Cilk. Naive implementations give each task its own stack for task-local memory, which is very inefficient.

We detail a program analysis for OpenMP to enable tasks to share stacks without synchronisation—-either unconditionally or dependent on some cheap run-time condition which is very likely to hold in busy systems.

The analysis is based on a novel implication-algebra generalisation of logic programming which allows concise but easily readable encodings of the various constraints. The formalism enables us to show that the analysis has a unique solution and polynomial-time complexity.

We conclude with performance figures.

This talk is part of the Computer Laboratory Programming Research Group Seminar series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory Programming Research Group Seminar
• Department of Computer Science and Technology talks and seminars
• FW22, Computer Laboratory, William Gates Building
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.