Accession Number:

ADA440521

Title:

Automatic Parallelization: An Incremental, Optimistic, Practical Approach

Descriptive Note:

Doctoral thesis

Corporate Author:

DEFENSE ADVANCED RESEARCH PROJECTS AGENCY ARLINGTON VA

Personal Author(s):

Report Date:

1999-09-01

Pagination or Media Count:

102.0

Abstract:

The historic focus of Automatic Parallelization efforts has been limited in two ways. First, parallelization has generally been attempted only on codes which can be proven to be parallelizeable. Unfortunately, the requisite dependence analysis is undecidable, and todays applications demonstrate that this restriction is more than just theoretical. Second, parallel program generation has generally been geared to custom multi-processing hardware. Although a network of workstations NOW could in principle be harnessed to serve as a multiprocessing platform, the NOW has characteristics which are at odds with elective utilization. This thesis shows that by restricting our attention to the important domain of embarrassingly parallel applications, leveraging existing scalable and efficient network services, and carefully orchestrating a synergy between compile-time transformations and a small runtime system, we can achieve a parallelization that not only works in the face of inconclusive program analysis, but is also efficient for the NOW. We optimistically parallelize loops whose memory access behavior is unknown, relying on the runtime system to provide efficient detection and recovery in the case of an overly optimistic transformation. Unlike previous work in speculative parallelization, we provide a methodology which is not tied to the Fortran language, making it feasible as a generally useful approach. Our runtime system implements Two-Phase Idempotent Eager Scheduling TIES for efficient network execution, providing an Automatic Parallelization platform with performance scalability for the NOW.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE