Task response time and module assignment for real-time distributed processing systems (loosely coupled, allocation, interprocessor communications, design methodology, replications)
Kin Kwong Leung · 1985
Task response time is an important system performance measure for real-time systems. An analytic model is introduced to estimate task response time for loosely coupled distributed processing systems with real-time applications. The model considers such factors as assignment of modules to computers, module precedence relationships, interprocessor communications, interconnection network delay and module scheduling policy. Simulation experiments are used to validate the model assumptions and to show the accuracy of the model. The analytic model is first employed to investigate the effects of module precedence relationships on response times. Our study reveals that the distributions of module execution times and the mean execution time ratio for a pair of consecutive modules are major factors for the effects. The task response time model is then used to study module assignment for distributed systems. Based on the model, a new local search algorithm for module assignment is developed. Firstly, each module is assumed to be allocated to a single computer. Task response time is the optimality criterion, and the analytic model becomes the objective function. Search strategies are established to search for better module assignments. Further, the algorithm is extended to handle module replications; that is, modules may be replicated on several computers. The design objective for replicated module assignment is to minimize task response time with the thread response time constraints. A new objective criterion which is the sum of task response time and possible penalty delay to account for the violations of thread response time constraints is introduced. With this objective function, not only module copies are optimally assigned to computers, the proper module multiplicities are also iteratively determined by the algorithm so as to achieve the objective. The algorithm is validated by applying to two distinct distributed systems for space defense applications. One system does not require module replications while the other does. The sub-optimal module assignments generated by the algorithm provide excellent response time performance on both systems since the analytic model has considered all major factors that affect task response time. Therefore, the algorithm can serve as a valuable tool for distributed systems design.