Computing Per-Process Summary Side-Effect Information (250KB)

By Tor Jeremiassen and Susan J. Eggers

ABSTRACT

This paper presents a static algorithm, based on standard iterative data-flow techniques, for computing per-process memory references to shared data in coarse-grained parallel programs. The algorithm constructs control flow graphs for families of processes by recognizing predicates used in control statements whose values are invariant relative to any one process, but vary across processes. It is used in conjunction with interprocedural flow-insensitive side-effect analysis techniques to identify data objects accessed by each process. Dynamically allocated objects and descriptors for sections of arrays are incorporated into the general framework.

The motivation for the work was to reduce coherency overhead in shared memory multiprocessors. However, the algorithm can also be applied to local/global memory allocation decisions in distributed systems. 

@inproceedings{JeEg92:Workshop,
    author="T.E. Jeremiassen and S.J. Eggers",
    title="Computing Per-Process Summary Side-Effect Information",
    booktitle="Fifth Workshop on Languages and Compilers for Parallelism",
    Editor = {U. Banerjee and D. Gelernter and A. Nicolau and D. Padua},
    month = "August",
    year="1992"
}
pardo@cs.washington.edu