Program dependence analysis for concurrency exploitation in programs composed of abstract data type modules

In object-based design and implementation, application programs are constructed by layering reusable abstract data type (ADT) module instances. An ADT instance is often used to manage more than one data object. There is contention for getting access to the instance if the multiple data objects need to be accessed concurrently. To resolve the contention, the ADT instance is replicated and the copies are placed in different processors so that each of the multiple clients can use the clones to concurrently access different data objects. To exploit the concurrency automatically, program dependence relations are analyzed. In this paper, the program dependence graph (PDG), which was previously used to describe data and control dependence relations among statements, is extended to include instance dependence relations. Several theorems are proved with respect to the instance dependence properties of the new PDG graph. A technique is presented for determining the upper bound on the number of clones of each module instance that can be used concurrently. The technique employs dependence analysis techniques at the statement, method, and instance levels of granularities