Characterization of intermodule communications and heuristic task allocation for distributed real-time systems (imc, interprocessor communication, precedence relation, parallel processing, module assignment)
Lance Min-Tsung Lan · 1985
Distributed processing has the potential for providing lower cost, better response time, and higher availability than centralized processing. In a distributed real-time system, a fixed set of application program modules reside permanently on a set of computers (or, processors). Module executions are invoked by a stream of external stimuli (arrivals). A key work in the design of distributed real-time systems is task allocation (module assignment)--assigning the program modules onto the set of computers such that the processing of each stimulus (event) can be finished within a prescribed time limit. The three important parameters in task allocation are intermodule communication (IMC), accumulative execution time (AET) of each module, and precedence relations (PR) among program modules. IMC is the communication between program modules through shared files. When a module on a computer writes to or reads from a shared file on another computer, IMC results in IPC (interprocessor communication), an overhead to the processor load. Therefore, a task-allocation algorithm should try to minimize IPC by assigning a pair of heavily communicating modules to the same computer. On the other hand, AET always contributes to processor load; its contribution is independent of task allocation. Constructing a simulator to measure the IMC and AET is time-consuming. A model is therefore developed to estimate these values, based on the control-and-data-flow graph and branching probability. Estimated results for a space-defense application match closely with the measured values obtained from a simulator of this application. A program module can not be enabled before all its predecessor(s) finish execution; this relation is called the precedence relation (PR). Analytical results indicate that the size ratio of two consecutive modules plays an important role in task allocation. Generally if the execution time of the second module is much larger than the first one, then assigning these 2 modules to a same computer is beneficial to response time. Given J modules and S computers, there are S('j) module assignments. It is not feasible to enumerate through all these assignments to find the optimal assignment when S and J are large. A heuristic algorithm is proposed to find sub-optimal assignments, based on the concept of minimum bottleneck, using IMC and AET data and PR rules. Simulation results indicate that the algorithm generates good assignments.