Cloning ADT modules to increase parallelism: rationale and techniques

This paper presents efficient techniques for identifying opportunities to increase parallelism when the asynchronous remote procedure call model of parallel execution is applied to programs constructed from abstract data type (ADT) modules. Frequently, an ADT module is needed simultaneously by multiple clients, thus causing contention. To decrease queueing delays to execute module operations, cloning of modules is often useful. The main contribution of this work is a heuristic to efficiently determine, for each module used in a program, an upper bound on the number of clones of that module that can be used concurrently. The results include transformation rules for conditionals, so that the clone analysis algorithm avoids considering an exponential number of paths through the program. Additionally, a technique is presented to determine the number of clones required each time a loop is unrolled. Furthermore, analysis is given to consider the effects of intermodule dependence relationships on the sharing of clones