Accession Number:

ADA273565

Title:

Optimizing Parallelization

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1993-10-01

Pagination or Media Count:

16.0

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.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE