Recent Changes - Search:

PmWiki

pmwiki.org

edit SideBar

WhatUseIsDynamicCompilationForParallelism

General

Assumption is that dynamic compilation is 'better' for any form of parallelisation because

  • System can adapt to physical resources available and parallelise when appropriate.
  • System can monitor effects of parallelisation and modify strategy if necessary.

[ jsinger - In the same way that concurrent garbage collection obviates the need to "stop the world" when GC occurs, dynamic compilation on parallel architectures can happen concurrently with execution of user code. This should decrease start-up overhead, increase system throughput ... -jsinger ]

This can (hopefully!) be expanded in the context of particular approaches.

To Support Non-Speculative Parallelisation

Over the years considerable work has been done on extracting parallelism from sequential programs. Most of this work has concentrated on loop constructs, and the usefulness of the parallelism extracted depends to a large degree on achieving low costs for managing the threads and their interactions. Schemes have been invented (e.g. SLAM) in which the compiler-generated code for a loop was capable of being executed in parallel on several processors but may actually only get executed on one, depending on the loading of the system. Although efforts were made to minimise the extra cost incurred by compiling in this way, dynamic compilation allows the compiler to generate parallel code when this is known to be useful, and to generate sequential code when parallel resources are not available. It is also possible to know, for example, the computed bounds of the loop to avoid parallelising loops which would be too small to justify the overheads incurred. What is more an adaptive compiler enables this decision to be remade, so that subsequent executions are not bound by the decisions made just ahead of the first. [CCK]

To Support Speculation

An important issue in the exploitation of speculative parallelism is the choice of 'speculation points' within a serial program. In theory any branch could be a speculation point but only some will be profitable.

[ jsinger - The situation is actually more general than this. A speculation can be characterized by two arbitrary program points, p0 and p1, where there is a control flow path from p0 to p1. To speculate on ( p0,p1) when control reaches p0, the speculative thread commences execution from p1, and the non-speculative thread continues execution from p0. The speculation may be committed when the non-speculative thread reaches p1. This subsumes loop-level and method-level TLS, not so sure about lock-level TLS ??? -jsinger ]

To Support 'Conventional' TLS

To Support TCC

Better than what?

If we are going to assert that dynamic compilation is better, we need to decide what we are comparing against. Current state of the art analysis for TLS seems to be profile-guided compilation. (I like to call this quasi-dynamic compilation :-) Heuristics are used to determine speculation points. Whaley and Kozyrakis had a recent ICPP paper on this topic. [ -jsinger ]

Edit - History - Print - Recent Changes - Search
Page last modified on December 05, 2005, at 02:56 PM