299
Reconfigurable Network-on-Chip Design
10.3.5.2 Mapping of CCG
The CCG is now mapped onto the mesh topology. The cost of a mapping
solution is computed by determining the total communication cost of the
CCG. The communication cost corresponding to a pair of cores in CCG is
computed as the product of the bandwidth requirement between the cores
and the number of hops between the corresponding routers. Each router can
have at most two cores connected to it. The communication cost between two
such cores connected to the same router is taken as zero, as no router cycle is
spent in the process.
For achieving this mapping, first an integer linear programming (ILP) formulation of the problem has been done. This produces optimal results, but
could give solutions for small graphs only. Next, a particle swarm optimization (PSO) has been performed for obtaining mapping of larger CCGs.
10.3.5.3 Configuration Generation
The mapping stage attaches cores to routers taking a global view of the set of
applications. The next task is to fine-tune the mapping for each application
separately, and thus generate the corresponding configuration program for
the application. As it can be noted in Figure 10.2, excepting the boundary
routers, each core can be attached to any of the four routers surrounding it,
by applying suitable controls to the multiplexers. Thus, it leads to a restricted
version of the mapping problem that can be solved in the global mapping
stage considering the CCG. The problem can be solved using the following
three different strategies:
• ILP
• PSO
• An iterative improvement algorithm
The ILP and PSO formulations are similar to that in the previous phase,
whereas the iterative approach is a new one. In Section 10.3.6, the ILP formulation to solve the mapping problem is presented. This can be used to
get solution to both the CCG mapping and local configuration generation.
Section 10.3.7 presents the PSO-based approach that may also be used to
solve both global and local mapping. Section 10.3.8 presents the iterative
approach for local mapping.
10.3.6 iLP-Based Approach
This section presents an ILP formulation for the problem of mapping and
reconfiguration onto the proposed reconfigurable NoC architecture. First,
formulation has been given for mapping problem, which has next been
extended for reconfiguration.
Reconfigurable Network-on-Chip Design
10.3.5.2 Mapping of CCG
The CCG is now mapped onto the mesh topology. The cost of a mapping
solution is computed by determining the total communication cost of the
CCG. The communication cost corresponding to a pair of cores in CCG is
computed as the product of the bandwidth requirement between the cores
and the number of hops between the corresponding routers. Each router can
have at most two cores connected to it. The communication cost between two
such cores connected to the same router is taken as zero, as no router cycle is
spent in the process.
For achieving this mapping, first an integer linear programming (ILP) formulation of the problem has been done. This produces optimal results, but
could give solutions for small graphs only. Next, a particle swarm optimization (PSO) has been performed for obtaining mapping of larger CCGs.
10.3.5.3 Configuration Generation
The mapping stage attaches cores to routers taking a global view of the set of
applications. The next task is to fine-tune the mapping for each application
separately, and thus generate the corresponding configuration program for
the application. As it can be noted in Figure 10.2, excepting the boundary
routers, each core can be attached to any of the four routers surrounding it,
by applying suitable controls to the multiplexers. Thus, it leads to a restricted
version of the mapping problem that can be solved in the global mapping
stage considering the CCG. The problem can be solved using the following
three different strategies:
• ILP
• PSO
• An iterative improvement algorithm
The ILP and PSO formulations are similar to that in the previous phase,
whereas the iterative approach is a new one. In Section 10.3.6, the ILP formulation to solve the mapping problem is presented. This can be used to
get solution to both the CCG mapping and local configuration generation.
Section 10.3.7 presents the PSO-based approach that may also be used to
solve both global and local mapping. Section 10.3.8 presents the iterative
approach for local mapping.
10.3.6 iLP-Based Approach
This section presents an ILP formulation for the problem of mapping and
reconfiguration onto the proposed reconfigurable NoC architecture. First,
formulation has been given for mapping problem, which has next been
extended for reconfiguration.