A Hierarchical Framework for Design Space Exploration and Optimization of TTP-Based Distributed Embedded Systems

Time-triggered protocol (TTP) is a time-division multiple access (TDMA)-based bus protocol designed for use in safety-critical avionics and automotive distributed embedded systems. Design space exploration (DSE) for TTP-based distributed embedded system involves searching through a vast design space of possible task-to-CPU mappings, task/message schedules and bus access configurations to achieve certain design objectives. In this paper, we present an efficient two-level hierarchical DSE framework for TTP-based distributed embedded systems, with the objective of minimizing the total bus utilization while meeting an end-to-end deadline constraint. Logic-based Benders decomposition (LBBD) is used to divide the problem into a master problem of mapping tasks to CPU nodes to minimize the total bus utilization, solved with a satisfiability modulo theories (SMT) solver, and a subproblem of finding a feasible solution of bus access configuration and task/message schedule under an end-to-end deadline constraint for a given task-to-CPU mapping, solved with a constraint programming (CP) solver. Performance evaluation results show that our approach is scalable to problems with realistic size.