Frequent Statement and De-reference Elimination for Distributed Programs

摘要

This paper introduces a new approach for the analysis of frequent statement and de-reference elimination for distributed programs run on parallel machines equipped with hierarchical memories. The address space of the language studied in the paper is globally partitioned. This language allows programmers to define data layout and threads which can write to and read from other thread memories. Simply structured type systems are the tools of the techniques presented in this paper which presents three type systems. The first type system defines for program points of a given distributed program sets of calculated {ready) statements and memory accesses. The second type system uses an enriched version of types of the first type system and determines which of the specified statements and memory accesses are used later in the program. The third type system uses the information gather so far to eliminate unnecessary statement computations and memory accesses (the analysis of frequent statement and de-reference elimination). Two advantages of our work over related work are the following. The hierarchical style of concurrent parallel computers is similar to the memory model used in this paper. In our approach, each analysis result is assigned a type derivation (serves as a correctness proof).