Distribution of Workload in IMA Systems by Solving a Modified Multiple Knapsack Problem

In this paper, we address the problem of workload distribution in Integrated Modular Avionics (IMA) systems. IMA system is a real-time computer system consisting of computing modules connected by a communications network. Each module has a multicore central processor unit (CPU). Workload for an IMA system is a set of periodic computational tasks grouped into partitions. Tasks from different partitions communicate by message passing. During workload distribution, each partition is assigned to a single CPU core of some module. Message passing between partitions assigned to cores of different modules creates network load. To guarantee system scalability, the network load must be minimized, while keeping all core loads within specified limits. We represent the workload distribution problem as a modified multiple knapsack problem and propose a branch and bound algorithm for solving this problem, along with a specific scheme of upper estimate calculation and an optimization which improves the algorithm performance. Results of experimental evaluation of the algorithm are also presented. The proposed algorithm is implemented in a tool system accepted for operation by one of the leading Russian aircraft design companies.