Optimal SAT-based scheduler for time-triggered networks-on-a-chip

Many embedded systems are deployed with multi-core platforms where processor cores are interconnected by networks-on-a-chip. Time-triggered networks-on-a-chip are ideal for safety-critical systems due to the inherent fault isolation and temporal predictability. However, a communication schedule is required that determines for each message the points in time for the injection of messages at the network interface as well as conflict-free paths through the network-on-a-chip. The schedule ensures that at a given point in time only one flit traverses the physical link between two router ports, thereby avoiding the need for dynamic arbitration and improving temporal predictability. This paper introduces an optimal scheduler based on a Boolean SAT solver for a time-triggered network-on-a-chip. By adopting this solver technique from the area of Electronic Design Automation (EDA) we have observed a significant reduction of the computation time for optimal schedules in several example scenarios. The evaluation was performed by comparing the SAT-based scheduler with an optimal scheduler using Mixed Integer Linear Programming (MILP). Due to the low computational time, we expect that the scheduling algorithm can replace heuristics in many applications.