Optimizing Parallelization
Abstract
To transform a sequential program into a concurrent program, a compiler typically divides the sequential program into a partially-ordered set of basic blocks, allowing unrelated blocks to execute concurrently. Blocks may execute concurrently only if there are no dependencies among them, and therefore a compiler can introduce concurrency only to the extent that it can guarantee the absence of dependencies. A limitation of this technique is that it is necessarily conservative: it may be difficult or impossible to prove the absence of dependencies even when no dependencies exist. This paper investigates optimistic parallelization, a complementary technique for parallelizing sequential code. Blocks with potential conflicts are allowed to execute in parallel, and conflicts are detected at run-time. When a conflict is detected, the conflicting blocks are rolled back and re-executed in sequential order. Optimistic parallelization can enhance concurrency when the compiler cannot prove the absence of dependence among independent blocks, and when dependencies occur, but are sufficiently rare. We show how conflict detection and roll-back can be accomplished efficiently through relatively simple changes to the caches and the cache-coherence protocol of a shared-memory multiprocessor. Parallelism, Optimistic, Transactions.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1993
- Accession Number
- ADA273565
Entities
People
- Greg Morrisett
- Maurice Herlihy
Organizations
- Carnegie Mellon University