Use of concurrency enhancement in off-line schedule construction

To improve the performance of programs composed of abstract data types (ADTs), a parallel execution model is used to exploit concurrency at the method level. Typically, an ADT instance is used to manage more than one variable, and there may be contention for getting access to the ADT instance if multiple variables need to be accessed concurrently. To resolve the contention, the ADT instance is cloned, and the copies are placed in different processors so that the multiple copies can be used concurrently. To exploit automatically the concurrency available via ADT instance cloning, we analyze program dependence relations. Not only control and data dependence but also instance dependence is analyzed to reveal dependence relations among method calls and to determine the clonability of each ADT instance. The focus of this paper is the use of our ADT cloning techniques to help ease the task of off-line scheduling in hard-real-time systems. Cloning and ARPCs are applied repeatedly to increase concurrency within processes missing deadlines, thus reducing their execution times