5
Application Mapping on
Network-on-Chip
5.1 Introduction
In chapters 2, 3, and 4, we have seen how to design a router fabric following a specific topology (such as mesh, mesh-of-tree, and butterfly fat
tree). However, a complete network-on-chip (NoC) system consists of the
router fabric and the intellectual property (IP) cores. The router network
is utilized to facilitate communication between these cores. Looking at the
NoC design problem from a system perspective, the whole process starts
with the specification of the system. The specification is refined into a set
of interactive tasks that accomplish the system functionality. For example,
Figure 5.1 shows a task-level decomposition of a video object plane decoder
(VOPD) application. It consists of several tasks, such as down sampler and
run length decoder. The tasks need to communicate between themselves at
the rates specified as edge labels. A label represents the required bandwidth between the tasks in megabytes per second. The corresponding
graph-based representation is shown in Figure 5.2a. The router-based communication backbone is utilized for these communications. Assuming that
each task is realized by an IP core, it is desirable that the cores corresponding to two highly communicating tasks be placed close to each other. If
only one core is attached to a router, such cores should be attached to two
neighboring routers, whereas cores having little bandwidth requirement
between them can be placed relatively far apart, without affecting the system performance significantly. Once the communication infrastructure of
a NoC is finalized, a major challenge in the overall system design is to
associate the IP cores implementing tasks of an application with the routers. This problem of application mapping has a very significant role to play in
determining the performance of the overall system, as it directly influences
the communication time, the required link bandwidth, and the admissible
delay in the routers. For example, Figure 5.2b shows a possible mapping of
the application shown in Figure 5.2a onto a mesh topology. The mapping
problem is NP-hard (Pop and Kumar 2004). In this chapter, we will look
119