KTS: a real-time mapping algorithm for NoC-based many-cores

Many-core architectures based on network-on-chip (NoC) are scalable and have the ability to meet the increasing performance requirements of complex concurrent applications (real-time video, communications, control, etc.). This paper addresses the mapping problem of hard real-time task sets on NoC-based many-core processors. Our main contribution is a novel static mapping scheme called K-level task splitting (KTS). If a task cannot be allocated on a given core of the NoC because of a too high processing utilization ratio, it gets replicated so that its jobs execute on more than one core without migrating. Synchronization between task replicas could then be ensured by assigning offsets and virtual deadlines to them. KTS’s advantage is that data migration is not required, thus involving no overheads due to migrations. The only requirement is that all core clocks be synchronized within the NoC. In this newly proposed algorithm, the schedulability of each task is determined based upon fundamental results relative to the feasibility analysis of asynchronous real-time task sets. The paper describes the principles of task splitting, our algorithm and its properties. We evaluate the efficiency of KTS, demonstrating that it is a good compromise between existing semi-partitioned schemes (with possible migrations) and fully partitioned approaches.