264
Network-on-Chip
9.2 ASNoC Synthesis Problem
The overall ASNoC synthesis problem can be stated as follows:
Given the following:
• A directed communication graph G(V,E), where each v i ∊ V denotes
an intellectual property (IP) core of the design, and each directed
edge e k = (v i , v j ) ∊ E denotes a communication trace from v i to v j . For
every v i ∊ V, the height and width of the core are denoted by H i and
W i , respectively
• For every e k ∊ E, ω(e k ) denotes the bandwidth requirement and σ(e k )
denotes the latency constraint in hops for the edge
• A router architecture with η number of I/O ports per router, peak
bandwidth Ω per port, two quantities Ψ i and Ψ o denoting the power
consumed per megabytes per second of traffic flowing through the
router in input and output directions, respectively
• A physical link power model denoted by Ψ l per megabytes per second per millimeter
• Two constants H and W denoting the height and width constraints
on the overall system-level floorplan dimension
• Two ratios γ min and γ max denoting the lower and upper bounds on the
aspect ratio of the layout, respectively
Let R denote the set of routers in the synthesized architecture, E r is the set of
links between two routers, and E v be the set of local links connecting cores
to the routers. The objective of the NoC synthesis problem is to generate a
system-level floorplan and a network topology T(R, V, E r , E v ) such that
• For every e k ∊ E, there exists a route p in T that satisfies ω(e k ) and
σ(e k ).
• The bandwidth constraints on the ports and routers are satisfied.
• The bounding box of the floorplan satisfies H and W.
• The aspect ratio of the floorplan lies between γ min and γ max .
• The total system-level communication cost/power for communication is minimized.
The floorplanning subproblem is a variant of quadratic assignment problem (Garey and Johnson 1979), while the interconnection network generation
problem is an instance of Steiner forest problem (Ravi et al. 2001). Both these
problems are NP-hard. As a result, many exact and heuristic methods have
been developed to solve the problem. The overall problem may be solved
as an integrated problem in which the floorplan and router network are
Network-on-Chip
9.2 ASNoC Synthesis Problem
The overall ASNoC synthesis problem can be stated as follows:
Given the following:
• A directed communication graph G(V,E), where each v i ∊ V denotes
an intellectual property (IP) core of the design, and each directed
edge e k = (v i , v j ) ∊ E denotes a communication trace from v i to v j . For
every v i ∊ V, the height and width of the core are denoted by H i and
W i , respectively
• For every e k ∊ E, ω(e k ) denotes the bandwidth requirement and σ(e k )
denotes the latency constraint in hops for the edge
• A router architecture with η number of I/O ports per router, peak
bandwidth Ω per port, two quantities Ψ i and Ψ o denoting the power
consumed per megabytes per second of traffic flowing through the
router in input and output directions, respectively
• A physical link power model denoted by Ψ l per megabytes per second per millimeter
• Two constants H and W denoting the height and width constraints
on the overall system-level floorplan dimension
• Two ratios γ min and γ max denoting the lower and upper bounds on the
aspect ratio of the layout, respectively
Let R denote the set of routers in the synthesized architecture, E r is the set of
links between two routers, and E v be the set of local links connecting cores
to the routers. The objective of the NoC synthesis problem is to generate a
system-level floorplan and a network topology T(R, V, E r , E v ) such that
• For every e k ∊ E, there exists a route p in T that satisfies ω(e k ) and
σ(e k ).
• The bandwidth constraints on the ports and routers are satisfied.
• The bounding box of the floorplan satisfies H and W.
• The aspect ratio of the floorplan lies between γ min and γ max .
• The total system-level communication cost/power for communication is minimized.
The floorplanning subproblem is a variant of quadratic assignment problem (Garey and Johnson 1979), while the interconnection network generation
problem is an instance of Steiner forest problem (Ravi et al. 2001). Both these
problems are NP-hard. As a result, many exact and heuristic methods have
been developed to solve the problem. The overall problem may be solved
as an integrated problem in which the floorplan and router network are