123
Application Mapping on Network-on-Chip
where hopcount(a, b) is the number of hops between the topology nodes a and
b, assuming that all routers take the same number of clock cycles to pass a
packet from an input port to an output port.
Otherwise, the hopcount metric needs to be replaced by the number of
router cycles involved. For a deterministic shortest path routing, hopcount
corresponds to the minimum number of hops between the constituent nodes.
Since the communication cost is very much dependent on the mapping solution, the overall mapping problem is to optimize the communication cost,
ensuring that the bandwidth constraints of all individual links are satisfied.
The communication cost affects the performance of the overall system and
its energy consumption, as both of these factors are directly proportional to
the total hopcount. The application mapping problem is to determine the map
function of an application to be mapped onto a given topology graph such
that the overall communication cost T is minimized.
Several strategies have been proposed to solve the mapping problem. The
techniques may broadly be classified belonging to one or more of the following categories:
• Exact mapping strategies, such as integer linear programming (ILP)
• Constructive heuristics with/without iterative improvement
• Evolutionary techniques, such as genetic algorithms (GAs), ant colony optimization (ACO), and particle swarm optimization (PSO)
Some proposed techniques from each of the categories will be discussed in
Sections 5.3 through 5.6.
5.3 ILP Formulation
ILP is an exact technique to solve optimization problems. It attempts to
assign values to the unknowns (and thus constructs a solution) satisfying a
set of constraints and optimizing the given objective function. However, as
the problem size grows, it takes exponential time to arrive at the optimum
result. Due to its exact nature, ILP is often used to judge the quality of other
nonexact approaches (such as heuristics and meta-search techniques). Often
approximations are introduced into the ILP formulation to arrive at fast heuristic techniques. In the following, we will discuss about an ILP formulation
of the application mapping problem. We have used the following variables to
express the constraints and the objective function.
• U: The set of routers {u 1 , u 2 ,…} of the topology graph
• C: The set of cores {c 1 , c 2 ,…} of the application
Application Mapping on Network-on-Chip
where hopcount(a, b) is the number of hops between the topology nodes a and
b, assuming that all routers take the same number of clock cycles to pass a
packet from an input port to an output port.
Otherwise, the hopcount metric needs to be replaced by the number of
router cycles involved. For a deterministic shortest path routing, hopcount
corresponds to the minimum number of hops between the constituent nodes.
Since the communication cost is very much dependent on the mapping solution, the overall mapping problem is to optimize the communication cost,
ensuring that the bandwidth constraints of all individual links are satisfied.
The communication cost affects the performance of the overall system and
its energy consumption, as both of these factors are directly proportional to
the total hopcount. The application mapping problem is to determine the map
function of an application to be mapped onto a given topology graph such
that the overall communication cost T is minimized.
Several strategies have been proposed to solve the mapping problem. The
techniques may broadly be classified belonging to one or more of the following categories:
• Exact mapping strategies, such as integer linear programming (ILP)
• Constructive heuristics with/without iterative improvement
• Evolutionary techniques, such as genetic algorithms (GAs), ant colony optimization (ACO), and particle swarm optimization (PSO)
Some proposed techniques from each of the categories will be discussed in
Sections 5.3 through 5.6.
5.3 ILP Formulation
ILP is an exact technique to solve optimization problems. It attempts to
assign values to the unknowns (and thus constructs a solution) satisfying a
set of constraints and optimizing the given objective function. However, as
the problem size grows, it takes exponential time to arrive at the optimum
result. Due to its exact nature, ILP is often used to judge the quality of other
nonexact approaches (such as heuristics and meta-search techniques). Often
approximations are introduced into the ILP formulation to arrive at fast heuristic techniques. In the following, we will discuss about an ILP formulation
of the application mapping problem. We have used the following variables to
express the constraints and the objective function.
• U: The set of routers {u 1 , u 2 ,…} of the topology graph
• C: The set of cores {c 1 , c 2 ,…} of the application