Mapping Task-Graphs on Distributed ECU Networks: Efficient Algorithms for Feasibility and Optimality

This mapping problem has to be solved in many application scenarios. In the automotive industry, for example, the implementation of car functions involves distributed task sets running on multiple electronic control units (ECU) with bus-based inter-task communication, a problem we consider in this paper. Our approach is based on mixed integer linear programming (MILP). MILP is concerned with optimizing a linear function subject to a set of linear constraints where some variables are required to be integer. The current state-of-the art method to solve integer programs is the branch-and-cut (B&C) algorithm and several industrial strength solvers are available. We describe a MILP-model for the mapping problem. Handling this model over to a general MILP-solver does not yield satisfactory results in terms of running time. To make the model more efficient we use the above ingredients: we incorporate a primal heuristic, strengthen the model with further inequalities and generate on-demand cutting planes, which violate the current fractional solution. These routines drastically speed up the solution time