122
Network-on-Chip
Definition 5.2
The NoC topology graph is a directed graph P(U, F), with each vertex u i ∈ U
representing a node in the topology and the directed edge f i,j ∈ F representing
a direct communication between the vertices u i and u j . The weight of the edge
f i,j , denoted as bw i,j , represents the bandwidth available across the edge f i,j .
A mapping of the core graph G(C, E) onto the topology graph P(U, F) is
defined by the function, map: C → U, such that c i ∈ C, u j ∈ U, and map(c i ) = u j .
The function associates core c i to router u j . Mapping is defined only when
|C| ≤ |U|, assuming that at most a single core is associated with a router.
The quality of such a mapping is defined in terms of the total communication cost of the application under this mapping. The communication between
each pair of cores can be treated as flow of a single commodity, d k , where
k = 1, 2,…, |E|. The value of commodity d k , corresponding to the communication between cores c i and c j , is equal to comm i,j , the bandwidth requirement.
If c i is mapped to the router map(c i ) and c j is mapped to map(c j ), the set of all
commodities D = {d k } is defined as follows:
D = {d
k |
(
k ) = comm , for k = , 2,…, E and e i j ∈E}
value d
i j
,
1
| |
,
source d
k ) = map c and
(
k ) = map c
(
( )
i
j
The link between two individual routers u i and u j of the topology has a maximum bandwidth of bw i,j . The total commodity flowing through such a link
should not exceed this bandwidth. The quantity x
k
i , j indicating the value of
commodity d k flowing through the link (u i , u j ) is given by
⎧
k
⎪ value( d k ), if link ( u ,u )
∈
Path( source( d k ), de est( d k ))

x =

i
i, j
j
⎨

⎪ 0,
otherwise
⎩

where Path(a, b) indicates the deterministic routing path between the mesh
nodes a and b in the topology.
Satisfaction of bandwidth limitations of individual links must be ensured.
That is, all mapping solutions should satisfy the following relation:
∑
|E|
x
k
i , j ≤ bw i , j , ∀i, j ∈{1, 2 , |U |}
k=1
If all bandwidth constraints are satisfied, the communication cost of a mapping solution is given by
|E
∑
|
T =
value( d
k )× hopcount( source( d
k ), dest( d
k ))
k =1
dest d
( )