Channel trees: Reducing latency by sharing time slots in time-multiplexed networks on chip

Networks on Chip (NoC) have emerged as the design paradigm for scalable System on Chip communication infrastructure. A growing number of applications, often with firm (FRT) or soft real-time (SRT) requirements, are integrated on the same chip. To provide time-related guarantees, NoC resources are reserved, e.g. by non-work-conserving time-division multiplexing (TDM). Traditionally, reservations are made on a per-communication-channel basis, thus providing FRT guarantees to individual channels. For SRT applications, this strategy is overly restrictive, as slack bandwidth is not used to improve performance. In this paper we introduce the concept of channel trees, where time slots are reserved for sets of communication channels. By employing work-conserving arbitration within a tree, we exploit the inherent single-threaded behaviour of the resource at the root of the tree, resulting in a drastic reduction in both average-case latency and TDM-table size. We show how channel trees enable us to halve the latter in a car entertainment SoC, and reduce the average latency by as much as much as 52% in a mobile phone SoC. By applying channel trees to an H264 decoder SoC, we increase processor utilisation by 25%. Copyright 2007 ACM.