Period-based load partitioning and assignment for large real-time applications

We propose a new approach to the problem of workload partitioning and assig nment for very large distributed real-time systems, in which software compo nents are typically organized hierarchically, and hardware components poten tially span several shared and/or dedicated links. Existing approaches for load partitioning and assignment are based on either schedulability or comm unication. The first category attempts to construct a feasible schedule for various assignments and chooses the one that minimizes task lateness (or o ther similar criteria), while the second category partitions the workload h euristically in accordance with the amount of intertask communication. We p ropose, and argue for, a (new) third category based on task periods, which, among others, combines the ability of handling heterogeneity with excellen t scalability. Our algorithm is a recursive invocation of two stages: clust ering and assignment. The clustering stage partitions tasks and processors into clusters. The assignment stage maps task clusters to processor cluster s. A later scheduling stage will compute a feasible schedule, if any, when the size of processor clusters reduces to one at the bottom of the recursio n tree. We introduce a new clustering heuristic and evaluate elements of th e period-based approach using simulations to verify its suitability for lar ge real-time applications. Also presented is an example application drawn f rom the field of command and control that has the potential to benefit sign ificantly from the proposed approach.