CN102065019A - IP (Internet Protocol) core fast mapping method for network on chip based on region division - Google Patents
IP (Internet Protocol) core fast mapping method for network on chip based on region division Download PDFInfo
- Publication number
- CN102065019A CN102065019A CN2011100245965A CN201110024596A CN102065019A CN 102065019 A CN102065019 A CN 102065019A CN 2011100245965 A CN2011100245965 A CN 2011100245965A CN 201110024596 A CN201110024596 A CN 201110024596A CN 102065019 A CN102065019 A CN 102065019A
- Authority
- CN
- China
- Prior art keywords
- kernel
- network
- topology
- area
- communication
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000013507 mapping Methods 0.000 title claims abstract description 84
- 238000000034 method Methods 0.000 title claims abstract description 26
- 238000004891 communication Methods 0.000 claims abstract description 73
- 238000005265 energy consumption Methods 0.000 claims abstract description 35
- 230000008878 coupling Effects 0.000 claims description 13
- 238000010168 coupling process Methods 0.000 claims description 13
- 238000005859 coupling reaction Methods 0.000 claims description 13
- 238000012163 sequencing technique Methods 0.000 claims description 2
- 238000005457 optimization Methods 0.000 abstract description 6
- 238000004364 calculation method Methods 0.000 abstract description 4
- 238000004422 calculation algorithm Methods 0.000 description 20
- 230000002068 genetic effect Effects 0.000 description 14
- 238000002474 experimental method Methods 0.000 description 6
- 238000004088 simulation Methods 0.000 description 6
- 238000013461 design Methods 0.000 description 5
- 238000010586 diagram Methods 0.000 description 5
- 238000013459 approach Methods 0.000 description 3
- 238000005516 engineering process Methods 0.000 description 3
- 238000012545 processing Methods 0.000 description 3
- 235000003140 Panax quinquefolius Nutrition 0.000 description 2
- 240000005373 Panax quinquefolius Species 0.000 description 2
- 238000012217 deletion Methods 0.000 description 2
- 230000037430 deletion Effects 0.000 description 2
- 239000012467 final product Substances 0.000 description 2
- 239000011159 matrix material Substances 0.000 description 2
- 230000008569 process Effects 0.000 description 2
- 238000011160 research Methods 0.000 description 2
- 238000013528 artificial neural network Methods 0.000 description 1
- 230000008901 benefit Effects 0.000 description 1
- 230000007812 deficiency Effects 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 230000003760 hair shine Effects 0.000 description 1
- 238000003064 k means clustering Methods 0.000 description 1
- 230000007246 mechanism Effects 0.000 description 1
- 230000006855 networking Effects 0.000 description 1
- 230000000630 rising effect Effects 0.000 description 1
- 238000010845 search algorithm Methods 0.000 description 1
- 239000004065 semiconductor Substances 0.000 description 1
- 238000002922 simulated annealing Methods 0.000 description 1
- 230000001360 synchronised effect Effects 0.000 description 1
- 238000005303 weighing Methods 0.000 description 1
- 238000013316 zoning Methods 0.000 description 1
Images
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
本发明公开了一种基于区域划分的片上网络快速IP核映射方法，主要解决IP核匹配到网络节点的性能优化问题。其实现步骤是：(1)根据通信核图中IP核数目生成最佳网络拓扑，若最佳拓扑中节点数多于IP核数则虚拟IP核以修正通信核图；(2)划分欲映射IP核对应的拓扑区域，并按拓扑划分结果对通信核图进行相应数目的IP核划分匹配；(3)通过位置能耗计算确定每个IP核在网络中的具体位置并标记；(4)按照每个IP核的标记映射到对应的网络节点，删除步骤(1)中虚拟的IP核，输出最终映射结果。本发明降低了运算复杂度，在保证全网通信低能耗的同时避免了网络中心的热点产生，提高了网络可靠性，可用于低能耗、流量均衡的大规模IP核快速映射。
The invention discloses an on-chip network fast IP core mapping method based on area division, which mainly solves the performance optimization problem of IP core matching to network nodes. The implementation steps are: (1) Generate the optimal network topology according to the number of IP cores in the communication core graph, if the number of nodes in the optimal topology is more than the number of IP cores, virtual IP cores are used to modify the communication core graph; (2) Divide the desired mapping The topological area corresponding to the IP core, and divide and match the corresponding number of IP cores on the communication core map according to the topological division results; (3) Determine the specific position of each IP core in the network through position energy consumption calculation and mark it; (4) According to the label of each IP core is mapped to the corresponding network node, the virtual IP core in step (1) is deleted, and the final mapping result is output. The invention reduces the computational complexity, avoids hotspots in the network center while ensuring low energy consumption of the entire network communication, improves network reliability, and can be used for fast mapping of large-scale IP cores with low energy consumption and balanced flow.
Description
Technical field
The invention belongs to networking technology area, relate to that IP kernel is applicable to that to the mapping of network node the quick IP kernel of extensive network-on-chip of low energy consumption, heat balance shines upon on system level chip design and the sheet.
Background technology
Along with reducing gradually and the further increase of level of integrated system of gate, calculating and memory cell size in the system, existing bus structures in time delay, handle up, power consumption, synchronously and aspect such as extensibility be faced with great challenge, embody a concentrated expression of: (1) multiplied unit poor efficiency.Increase along with integrated unit on the sheet, data processing amount also increases thereupon, and be difficult to support a pair of above node unit communication on a bus, link bandwidth on the shared bus has also determined inter-node traffic simultaneously, and these restrictions have just caused the difficulty and the low problem of utilance of a plurality of processing unit communications; (2) clock synchronization issue.Because the continuous development of semiconductor technology, the reducing gradually and the rising of clock frequency of processing unit area size, the time delay on the line is more and more serious to the synchronous influence of global clock on the sheet, finally makes existing bus structures can't use on sheet.For this reason, design a kind of brand-new architecture and just become the key point of studying with the interconnection that solves between numerous IP kernels, network-on-chip NoC arises at the historic moment thus.
The appearance of NoC has effectively solved above problems, it adopts worm channel to be exchanged for base switch system, clock synchronization mechanism with Global Asynchronous local synchronization GALS has well solved the difficult synchronously problem of global clock, and it changes the conventional bus structure by actual macro network topology or its peculiar novel topology, has greatly improved network energy consumption, time delay, handle up and performance such as extensibility.
The mapping optimization problem is one of key issue of network design, it is on the basis of design constraint such as given communication task figure, bandwidth and IP kernel bank, with each Task Distribution to suitable IP kernel and arrange the task execution sequence of each IP kernel and the position in the NoC topological structure.Therefore, the main task of mapping is assigned to IP kernel or task module on the network node exactly efficiently, makes various application be able to efficiently, successfully finish.Usually the leading indicator of weighing a mapping performance quality has energy consumption, time delay and bandwidth etc.
Yet, mapping problems belongs to the category of quadratic assignment problem, and it has been proved to be the NP-complete problem, its search yardstick is factorial with the search volume growth and increases progressively, it is quite complicated accurately finding the solution on a large scale in finite time and space, therefore often adopts heuritic approach to carry out near-optimal in current domestic and international research and finds the solution.Common heuritic approach has genetic algorithm, branch-bound algorithm, ant group algorithm, simulated annealing, tabu search algorithm and artificial neural network algorithm etc. in network-on-chip mapping optimization problem is found the solution, and these heuritic approaches are mostly when modeling or keep an optimization aim and other targets are converted into constraints and then obtain the single goal optimization problem, or a plurality of targets are weighted summation are converted into the single goal optimization problem and then find the solution.Though this type of algorithm is by separating that a large amount of iteration can comparatively be optimized, but this is cost often with the time complexity, be difficult to be applied among the IP kernel mapping fast on a large scale, and can not guarantee to obtain at short notice the mapping result of low energy consumption, more do not consider the fatal influence of the appearance of network center's focus to chip reliability.
Summary of the invention
The objective of the invention is to overcome above-mentioned the deficiencies in the prior art, at common mesh topology a kind of network-on-chip Fast IP core mapping method based on area dividing is proposed, to reduce the IP kernel mapping time of implementation, to reduce network energy consumption and equalizing network flow, improve network reliability.
The technical thought that realizes the object of the invention is: at first consider the dimensional characteristic of chip and generate regular as far as possible topological structure, if in the network topology that produces the node number more than the then virtual IP kernel of IP kernel number to revise communication nuclear figure; The network topology that parameter is given is carried out area dividing, after corresponding communication examined figure divide coupling according to the IP kernel that zoning result's node number carries out respective number, and make traffic minimum between the IP kernel of dividing; Carry out the particular location energy consumption calculation at last, and with the energy consumption lower position as current IP kernel mapping position.Make like this that source node that the traffic is big is adjacent as far as possible with destination node and be mapped to the fringe region of network, not only guaranteed the low energy consumption of TOCOM total communication but also avoided the generation of network center's focus.The specific implementation step is as follows:
(1) generates the optimum network topology according to IP kernel number N among the communication nuclear figure,, fabricate M-N IP kernel, and suppose that the traffic of they and other IP kernel is 0 if network node number M then revises communication nuclear figure more than the IP kernel number N in the topology that generates; Each IP kernel token variable flag of initialization and network topology parameter;
(2) IP kernel of same tag variable flag and correspondence thereof, the traffic are formed new communication nuclear figure, and according to the corresponding network topology zone of token variable flag searching, this topology area is divided and divide the result by this IP kernel that communication nuclear figure carries out respective number is divided coupling, traffic minimum between the feasible IP kernel of dividing, and this division of mark result;
(3) repeated execution of steps (2) is divided mark to topology area and communication nuclear figure, up to the IP kernel number of same tag variable flag smaller or equal to 2;
(4) determine particular location and the mark of each IP kernel in network, check the IP kernel number of same tag variable flag, if the IP kernel number of same tag variable flag is 2, then determine the topology area of IP kernel according to token variable flag, and calculate the communication energy consumption of current these 2 IP kernels diverse location in its corresponding topology area, with the position of minimal communications energy consumption final mapping position as current 2 IP kernels, at last according to this position to the further mark of IP kernel, different up to the token variable flag of all IP kernels;
(5) carry out the correspondence coupling of network node according to the token variable flag of each IP kernel, and delete M-N the IP kernel of fabricating in the step (1), export final mapping result.
The present invention compared with prior art has following advantage:
1) the present invention has greatly reduced the complexity of computing owing to adopt the IP kernel mapping method based on area dividing of iteration, and the time of implementation of mapping obviously reduces;
2) the present invention is owing to divide coupling according to the area dividing result to the IP kernel that communication nuclear figure carries out respective number, and traffic minimum between the feasible IP kernel of dividing, this just makes the little IP kernel of the traffic be mapped to network center, can avoid the generation of central area focus effectively, and then improve the reliability of network.
3) the present invention is because when determining each IP kernel particular location, and the position of minimal communications energy consumption as current IP kernel mapping position, and is mapped to the principle of adjacent position according to the big IP kernel of the traffic, guaranteed the low energy consumption of TOCOM total communication.
Simulation result shows that the present invention is the mapping from the IP kernel to the network node fast not only, and can guarantee the low energy consumption of TOCOM total communication, has avoided the generation of network center's zone focus, has improved network reliability.
Description of drawings
Fig. 1 is the communication nuclear figure of video object plane decoding VOPD;
Fig. 2 is a mapping flow chart of the present invention;
Fig. 3 is the 2 dimension optimum topology structural representations that generate with the present invention;
Fig. 4 generates the tree-shaped schematic diagram that optimum topology carries out area dividing to the present invention;
Fig. 5 is the tree-shaped schematic diagram that the present invention divides video object plane decoding carrying out IP kernel;
Fig. 6 is existing method and mapping result of the present invention contrast schematic diagram;
Fig. 7 is the flow distribution contrast schematic diagram of communication nuclear under different mappings of video object plane decoding.
Embodiment
Mapping process below in conjunction with 16 nuclear video object plane decoding VOPD communication nuclear figure, flow process is shone upon in the present invention to be elaborated, the present invention is numbered each IP kernel among the communication nuclear figure of video object plane decoding VOPD for convenience of description: IP1, IP2, IP16, number order does not influence the mapping position of IP kernel.The communication nuclear figure of video object plane decoding VOPD and each IP kernel numbering are as shown in Figure 1.Among Fig. 1, each IP kernel is with a figure vertex representation, and digitized representation the numbering of IP kernel on the summit, if having a limit between certain two summit, then represents to exist correspondence between these two IP kernels, and the limit weight is being represented the traffic of these two IP kernels.
With reference to Fig. 2, specific implementation step of the present invention is as follows:
1.1) determine the IP kernel number N according to the concrete communication nuclear figure that uses, and satisfying condition of N is:
Wherein
Be rounding of x downwards,
Be rounding up of x, D ∈ 1,2,3 ..., and n} is a topological dimension, n is the maximum topological dimension of network;
1.2) gather from D dimension topology according to the IP kernel number N:
In select the optimum network topology, make topological node count M and count N, and the node of selected topology is counted M and is counted N with IP kernel and equate as far as possible more than or equal to IP kernel, being mapped to 2D mesh topology with the communication nuclear figure of N IP kernel is example, if line number is row, columns is col, and then it satisfies condition
And make min{ (row * col)-N} and (row * col)-N 〉=0; Wherein
Be rounding of x downwards,
Be rounding up of x;
1.3) output is in step 1.2) and in the network topology selected as the network-on-chip topological structure of mapping.
2.1) in communication nuclear figure, increase M-N virtual IP kernel, and suppose that the traffic of they and other IP kernel is 0;
2.2) markers step 2.1) the middle M-N that increases a virtual IP kernel, so that the virtual IP kernel of deletion in the mapping in the end;
If topological parameter is given, then do not carry out optimum topology and generate, only need whether to judge number of network node more than the IP kernel number, otherwise, then communication nuclear figure is revised.
Fig. 1 shows the communication nuclear figure of 16 nuclear video object plane decoder VOPD, because requirement generation dimension is 2 mesh topological structure, then the IP kernel number 16 of VOPD satisfies condition:
Promptly 4 * 4≤16≤4 * 4, obvious 4 * 42D mesh has satisfied optimum, and then the optimum topology of Sheng Chenging is 4 * 4 2D mesh, as shown in Figure 3, because IP kernel number and number of network node are 16, then needn't revise the nuclear figure that communicates by letter; Wherein
Be rounding of x downwards,
Be rounding up of x;
Supposing to have the IP kernel number of the communication nuclear figure of certain application-specific is 13, and the topology that requires to generate is 2 dimensions, and then it satisfies condition:
Promptly 3 * 3≤13≤4 * 4, then topology should be from set { 3 * 3,3 * 4,3 * 5, choose among 4 * 4}, consider that constraints is that number of network node and IP kernel number equate as far as possible and the node number should be more than or equal to the IP kernel number, then the communication nuclear figure of 13 IP kernels should select the 2D mesh structure of topology 3 * 5, need this moment communication nuclear figure is revised: add virtual IP14 and IP15 nuclear, and setting them and other 13 IP kernel traffics are 0, virtual IP14 and IP15 gets final product in the deletion network node that finishes to be mapped.
In network-on-chip mapping design, because the internal structure of network nodes such as IP kernel and router is not the emphasis of its research, the topology of Sheng Chenging is generally the network topology based on node for this reason, and Fig. 3 is the best network-on-chip topological structure schematic diagram based on node that the present invention generates according to VOPD communication nuclear figure.
As seen from Figure 3, each node unit comprises IP kernel and router, and router comprises cross bar switch, routing table and buffer memory micro-structural, cross bar switch has five ports, wherein 4 ports connect respectively eastwards, the router of south, west, 4 directions in north, all the other ports link to each other with local IP kernel.For mark for simplicity, all available two-dimensional coordinate of each node unit is represented uniquely in the topological structure, then all nodes of the whole network can be used two-dimensional coordinate (1,1), (1,2) ..., (1,4), (2,1) ..., (4,4) expression.
Because communication nuclear figure is the VOPD of 16 IP kernels, it is labeled as IP1 respectively successively in this example, IP2 ..., IP16, the network topology of generation is a 4x42D mesh structure; The token variable flag of initial each IP kernel is identical, so the new traffic nuclear figure that these IP kernels are formed is original communication nuclear figure.
Step 5 is sought corresponding network topology zone according to token variable flag, and this topology area is divided.
5.1) each IP kernel token variable flag of initialization and corresponding network topology parameter thereof, and make current division number of times variable i :=1,
Flag=(flag wherein
(1), flag
(2)..., flag
(n)), flag
(i)Be expressed as this IP kernel the i time division mark value, i ∈ 1,2 ..., n}, n are the length of token variable flag;
5.2) select IP kernel according to token variable flag with same tag, and select corresponding network topology zone according to token variable flag;
5.3) judge the parity of current division number of times i, if i is an odd number, then topology area is divided by row, if can not divide by row topology area then divide by row; If i is even number, then topology area is divided by row, if can not divide by row topology area then divide by row;
Described topology area is pressed is listed as division, carries out according to following steps:
At first, determine the topology area that it is corresponding by token variable flag, topological line number is new_row, and columns is new_col;
Then, according to the parity difference of columns topology area is divided accordingly; If new_col is that odd number then is divided into topology area three the sub-flat topologys in left, middle and right, its topological parameter is followed successively by respectively
New_row * 1,
If new_col is that even number then is divided into a left side with topology area, right two sub-flat topologys, its topological parameter is followed successively by respectively
Expression rounds downwards x.
Described topology area is divided by row, carries out according to following steps:
At first, determine the topology area that it is corresponding by token variable flag, topological line number is new_row, and columns is new_col;
Then, according to the parity difference of line number topology area is divided accordingly; If new_row is that odd number then is divided into topology area, in, following three sub-flat topologys, its topological parameter is followed successively by respectively
1 * new_col,
If new_row is that even number then is divided into topology area, following two sub-flat topologys, its topological parameter is followed successively by respectively
Expression rounds downwards x.
Result according to example VOPD communication nuclear figure and step 4 describes step 5: because current division number of times 1 is odd number, then divide by row, this moment, corresponding topology area was a 4x42D mesh structure, because columns 4 is an even number, then flat topology was divided into left and right two sub-planes.Each sub-plane is
2D mesh topological structure;
6.1) input IP kernel collection V={IP to be divided
1..., IP
i..., IP
nAnd traffic requirement matrix W,
Be nuclear IP
iTo IP
jThe traffic, calculate diagonal matrix D (i, i)=d
i, wherein vectorial d
i=∑
jW (i, j);
6.2) calculate
Characteristic of correspondence number vector y;
6.3) characteristic vector y is sorted from small to large, and its corresponding IP kernel numbering of mark;
6.4) judge the characteristic among the vectorial y, if before being divided into A and C two classes and then getting | the IP kernel numbering of A| characteristic is classified as a class, afterwards | C| is classified as another kind of; If be divided into A, B and C three classes, before then getting | and A| IP kernel numbering is classified as a class, the back | and C| is classified as a class, all the other | and B| is classified as a class; Wherein | x| represents to gather element number among the x;
6.5) each IP kernel of IP of dividing is carried out matched indicia, the principle of coupling is that the topology area of the IP kernel correspondence that the traffic is big is adjacent as far as possible according to IP kernel position relation to each other, the sequencing of mark is undertaken by traffic size sequence.
Above-mentioned communication nuclear figure is divided and makes the method for traffic minimum that other several different methods can be arranged, as minimal cut set algorithm, k means clustering algorithm etc.
Continuation describes step 6 according to VOPD example and step 5 result: divide the result by the topological plane of step 5 and show, VOPD communication nuclear figure will be divided into A and two subclasses of C, and element number is in each subclass
By the matching result that calculates to the position energy consumption: IP1, IP2, IP3, IP4, IP5, IP6, IP7, IP16} match in the category-A, IP8, and IP9, IP10, IP11, IP12, IP13, IP14, IP15} match in the C class;
Continuation describes step 7 according to VOPD example and step 6 result: the IP kernel according to step 6 is divided the result, all IP kernels in the category-A are matched left sub-plane, all IP kernels in the C class are matched right sub-plane, then with the division token variable flag of all IP kernels in the category-A
(1)Be designated as-1, the division token variable flag of all IP kernels in the C class
(1)Be designated as 1; Because the IP kernel number of same tag variable flag is 8 greater than 2, then also needs to divide: then with { IP1, IP2 next time, IP3, IP4, IP5, IP6, IP7, IP16} and { IP8, IP9, IP10, IP11, IP12, IP13, IP14, IP15} forms new traffic nuclear figure respectively, and turns back to step 4 and continue to divide, up to the IP kernel number of same tag variable flag smaller or equal to 2.
Fig. 4 and Fig. 5 show the communicate by letter tree-shaped result of corresponding division of nuclear figure of the tree-shaped result of division on 4x42Dmesh topology plane and video object plane decoding VOPD respectively.
From the ground floor of Fig. 4 dendrogram as seen, all nodes are divided into two sub-planes by row among the optimum network topology 4x42Dmesh that the present invention generates in the 1st time is divided, and are respectively (1,1), (1,2), (2,1) ..., (4,2) and (1,3), (1,4), (2,3) ..., (4,4).
From Fig. 5 as seen, communication nuclear figure is divided into IP1 in the 1st time, IP2, and IP3, IP4, IP5, IP6, IP7, IP16 and IP8, IP9, IP10, IP11, IP12, IP13, IP14, two subclasses of IP15, and the mark component of all IP kernels is flag in the 1st subclass
(1)The mark component of all IP is flag in the=-1, the 2nd subclass
(1)=1, the token variable flag of each IP kernel is shown in Fig. 5 below.
8.1) selected initial IP kernel of communicating by letter and mapping in communication nuclear figure, if the IP kernel that has same tag vector f lag with initial IP kernel is arranged, then select a kind of mapping mode this IP kernel also to be mapped to the zone of its correspondence at random;
8.2) from communication nuclear figure, select and shone upon the current desire mapping IP kernel that IP kernel has correspondence: promptly consider not shine upon IP kernel earlier and shine upon IP kernel and whether have correspondence, consider not shine upon IP kernel again and the traffic size of having shone upon between IP kernel, never shine upon at last and select an IP kernel to shine upon IP kernel in the IP kernel at random as current desire;
8.3) select with current desire and shine upon the IP kernel that IP kernel has same tag vector f lag, and calculating has the communication energy consumption of these two IP kernels of same tag vector f lag at its corresponding region diverse location, with the final mapping position of the minimum position of locating of energy consumption as current IP kernel, the calculating of this communication energy consumption is according to the ComEnergy=∑
IPj ∈ Cw
IPi, IPj* e
Map (IPi), map (IPj)Carry out w
IPi, IPjExpression IP
iAnd P
jThe traffic,
Expression IP
iMapping position map (IP
i) and P
jMapping position map (P
j) communication cost,
E
LinkThe power consumption values of representation unit flow on the unit link, E
SwitchThe energy consumption of representation unit flow on cross bar switch is E
LinkAnd E
SwitchBe known given parameter, dis represents communication distance;
8.4) position that will finally shine upon respectively mark return step 8.2 to the label vector flag of each IP kernel), mapped up to all IP kernels.
Still be that example integrating step 7 results are elaborated to step 8: the token variable flag that supposes can be determined by step 7 each IP kernel with VOPD, and the IP kernel maximum number of same tag variable flag is 2 at this moment, then needs by the position energy consumption calculation to determine the final position of IP kernel;
At first, determining IP1 by the communication nuclear figure of VOPD is initial mapping IP kernel, reading the IP kernel that has same tag variable flag with it is IP2, and the topology area of determining IP1 and IP2 according to token variable flag is node (3,2) and (4,2), provide a kind of coupling this moment at random, corresponds to (3,2) as IP1, IP2 corresponds to (4,2) network node;
Secondly, calculating only has IP3 with the nuclear that IP1 communicates by letter with IP2, then IP3 is shone upon IP kernel as current desire; And calculating and IP3 same tag variable flag is arranged is IP4, the topology area of determining IP3 and IP4 according to token variable flag is a node (3,1) and (4,1), then calculate IP3 and be mapped to node (3,1), IP4 is mapped to node (4,1), and IP4 is mapped to node (3,1), IP3 is mapped to node (4,1) power consumption values under two kinds of different mappings, the little position IP4 of energy consumption is mapped to node (3,1), IP3 is mapped to node (4,1) by selecting, as the final mapping position of IP3 and IP4, and the difference mark is in the label vector flag of IP3 and IP4.
At last, seek and IP1, IP2, IP3, the IP kernel of IP4 communication has IP16 and IP5, according to the traffic big preferentially as current desire mapping IP kernel criterion, from IP16 and IP5, select IP5 as current desire mapping IP kernel, then seek the IP kernel with same tag, calculating location energy consumption again, so repeated calculation position energy consumption and mark are mapped up to all IP kernels.
Owing in step 2, VOPD communication nuclear figure is not added virtual IP kernel, so in final mapping result, need not to delete IP kernel,, determine its concrete mapping position in network according to the label vector flag of each IP kernel, export final mapping scheme and get final product; Final mapping result as shown in Figure 6.
S in Fig. 6
I, jBe illustrated on the topological plane node unit for (i, router j), wherein i ∈ 1,2,3,4}, j ∈ 1,2,3,4}.Except coupled neighbor router, also be connected with an IP kernel on each router, the IP kernel that links to each other with it is the IP kernel that is mapped on the topological node, is example with the mapping position of IP16 among Fig. 6, IP16 and router S
1,1Link to each other, represent that then IP16 is mapped on the network node (1,1).
The effect of the inventive method can further specify by following experiment simulation:
1. simulated environment and emulation content:
This example is at Pentium (R) Dual-Core CPU E6500@2.93GHz 2.93GHz, 1.96GB under the internal memory Windows XP system, use MATLAB7.6 software to finish the experiment simulation that genetic algorithm GA and the present invention are carried out energy consumption, running time and network traffic condition.
E in emulation experiment of the present invention
Link=0.7066 (nJ), E
Switch=0.9334 (nJ), dis adopt the manhattan distance, promptly dis (i, j)=| x
i-x
j|+| y
i-y
j|.
2. emulation experiment and result:
As seen from Figure 7, the focus that mapping result under the genetic algorithm has produced in the network center zone, and the network center's flow under mapping result of the present invention obtains efficient balance, and the node that flow is big is distributed in the fringe region of network, under this mapping result, the reliability of network is effectively improved.
Can obtain by the further calculated flow rate variance of the simulation result of Fig. 7 simultaneously, flow variance based on the mapping result of genetic algorithm is 208068.7, and the flow variance of the mapping result that the present invention produces only is 127705.6, as seen, flow variance of the present invention is significantly less than the mapping result flow variance based on genetic algorithm.The flow variance is being represented the balanced intensity of flow in the whole network, and the more little then flow of flow variance is balanced more.And the size of flow is determining the generation of heat in the network, and the heat on the bigger then node of the flow of certain node is higher, and node just easy more quilt is damaged.
Table 1 has write down the running time and the corresponding power consumption values in preceding 1,5,10,50 and 1000 generations respectively.
Table 1 genetic algorithm mapping method and the inventive method energy consumption and running time contrast table
As can be seen from Table 1 in identical running time, based on the mapping result power consumption values of genetic algorithm more than 14537.80mJ, and the mapping result power consumption values that the present invention obtains only is 9506.3mJ, and as seen, power consumption values of the present invention will be starkly lower than the power consumption values based on genetic algorithm.
Simultaneously, because what genetic algorithm was too early has been absorbed in locally optimal solution, so that locally optimal solution is exported as global optimum based on the mapping method of genetic algorithm, this has not only expended a large amount of operation times and the mapping power consumption values is not further optimized again, and the method that the present invention adopts has not only provided a kind of mapping scheme fast, and mapping result is having very big reducing than the mapping result that genetic algorithm produces aspect the energy consumption.
Claims (8)
1. the network-on-chip Fast IP core mapping method based on area dividing comprises the steps:
(1) generates the optimum network topology according to IP kernel number N among the communication nuclear figure,, fabricate M-N IP kernel, and suppose that the traffic of they and other IP kernel is 0 if network node number M then revises communication nuclear figure more than the IP kernel number N in the topology that generates; Each IP kernel token variable flag of initialization and network topology parameter;
(2) IP kernel of same tag variable flag and correspondence thereof, the traffic are formed new communication nuclear figure, and according to the corresponding network topology zone of token variable flag searching, this topology area is divided and divide the result by this IP kernel that communication nuclear figure carries out respective number is divided coupling, traffic minimum between the feasible IP kernel of dividing, and this division of mark result;
(3) repeated execution of steps (2) is divided mark to topology area and communication nuclear figure, up to the IP kernel number of same tag variable flag smaller or equal to 2;
(4) determine particular location and the mark of each IP kernel in network, check the IP kernel number of same tag variable flag, if the IP kernel number of same tag variable flag is 2, then determine the topology area of IP kernel according to token variable flag, and calculate the communication energy consumption of current these 2 IP kernels diverse location in its corresponding topology area, with the position of minimal communications energy consumption final mapping position as current 2 IP kernels, at last according to this position to the further mark of IP kernel, different up to the token variable flag of all IP kernels;
(5) carry out the correspondence coupling of network node according to the token variable flag of each IP kernel, and delete M-N the IP kernel of fabricating in the step (1), export final mapping result.
2. the network-on-chip Fast IP core mapping method based on area dividing according to claim 1, wherein step (1) is described generates the optimum network topology according to IP kernel number N among the communication nuclear figure, carries out according to following steps:
1a) determine the IP kernel number N, and satisfying condition of N is according to the concrete communication nuclear figure that uses:
Wherein
Be rounding of x downwards,
Be rounding up of x, D ∈ 1,2,3 ..., and n} is a topological dimension, n is the maximum topological dimension of network;
1b) gather from D dimension topology according to the IP kernel number N:
In select the optimum network topology, make topological node count M and count N, and make the node of selected topology count M to count N with IP kernel and equate as far as possible more than or equal to IP kernel;
1c) output is at step 1b) in the network topology parameter selected.
3. the network-on-chip Fast IP core mapping method based on area dividing according to claim 1, wherein step (1) is described generates the optimum network topology according to IP kernel number N among the communication nuclear figure, only be meant in the not given network topology of parameter, generate if topological parameter does not carry out optimum topology for rule.
4. the network-on-chip Fast IP core mapping method based on area dividing according to claim 1, wherein step (2) is described divides topology area and divides the result by this IP kernel that communication nuclear figure carries out respective number is divided coupling, carries out according to following steps:
2a) each IP kernel token variable flag of initialization and corresponding network topology parameter thereof, and make current division number of times variable i :=1,
Flag=(flag wherein
(1), flag
(2)..., flag
(n)), flag
(i)Be expressed as this IP kernel the i time division mark value, i ∈ 1,2 ..., n}, n are the length of token variable flag;
2b) select IP kernel, and select corresponding network topology zone according to token variable flag with same tag according to token variable flag;
2c) judge the parity of current division number of times i,, then topology area is divided by row, if can not divide by row topology area then divide by row if i is an odd number; If i is even number, then topology area is divided by row, if can not divide by row topology area then divide by row;
2d) utilize topology area to divide the result IP kernel that communication nuclear figure carries out respective number is divided coupling, and traffic minimum between the feasible IP kernel of dividing;
2e) the division result difference mark with each IP kernel arrives its corresponding mark component flag
(i)In, and make current division number of times i:=i+1, and return step 2b), wherein, the sequencing of mark is undertaken by traffic size sequence.
5. the network-on-chip Fast IP core mapping method based on area dividing according to claim 4, wherein step 2c) described topology area is divided by row, carry out according to following steps:
2c-a1) determine the topology area that it is corresponding by token variable flag, topological line number is new_row, and columns is new_col;
2c-a2) if new_col is that odd number then is divided into topology area three the sub-flat topologys in left, middle and right, its topological parameter is followed successively by respectively
New_row * 1,
If new_col is that even number then is divided into a left side with topology area, right two sub-flat topologys, its topological parameter is followed successively by respectively
Expression rounds downwards x.
6. the network-on-chip Fast IP core mapping method based on area dividing according to claim 4, wherein step 2c) described topology area is divided by row, carry out according to following steps:
2c-b.1) determine the topology area that it is corresponding by token variable flag, topological line number is new_row, columns is new_col;
2c-b.2) if new_row is that odd number then is divided into topology area, in, following three sub-flat topologys, its topological parameter is followed successively by respectively
1 * new_col,
If new_row is that even number then is divided into topology area, following two sub-flat topologys, its topological parameter is followed successively by respectively
Expression rounds downwards x.
7. the network-on-chip Fast IP core mapping method based on area dividing according to claim 4, step 2d wherein) the described IP kernel that communication nuclear figure is carried out respective number is divided coupling, according to IP kernel position relation to each other, mate according to the adjacent as far as possible principle of topology area of the big IP kernel correspondence of the traffic.
8. the network-on-chip Fast IP core mapping method based on area dividing according to claim 1, described definite particular location and the mark of each IP kernel in network of step (4), carry out according to following steps:
4a) the initial IP kernel and the mapping of selected communication in communication nuclear figure if the IP kernel that has same tag vector f lag with initial IP kernel is arranged, then selects a kind of mapping mode this IP kernel also to be mapped to the zone of its correspondence at random;
4b) from communication nuclear figure, select and shone upon the current desire mapping IP kernel that IP kernel has correspondence: promptly consider not shine upon IP kernel earlier and shine upon IP kernel and whether have correspondence, consider not shine upon IP kernel again and the traffic size of having shone upon between IP kernel, never shine upon at last and select an IP kernel to shine upon IP kernel in the IP kernel at random as current desire;
4c) select the IP kernel that has same tag vector f lag with current desire mapping IP kernel, and calculate and to have the communication energy consumption of these two IP kernels of same tag vector f lag at its corresponding region diverse location, with the position at the minimum place of energy consumption as the final mapping position of working as IP kernel;
Step 4b is returned to the label vector flag of each IP kernel in the position that 4d) will finally shine upon mark respectively), mapped up to all IP kernels.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201110024596A CN102065019B (en) | 2011-01-21 | 2011-01-21 | IP (Internet Protocol) core fast mapping method for network on chip based on region division |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201110024596A CN102065019B (en) | 2011-01-21 | 2011-01-21 | IP (Internet Protocol) core fast mapping method for network on chip based on region division |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN102065019A true CN102065019A (en) | 2011-05-18 |
| CN102065019B CN102065019B (en) | 2012-10-24 |
Family
ID=44000125
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201110024596A Expired - Fee Related CN102065019B (en) | 2011-01-21 | 2011-01-21 | IP (Internet Protocol) core fast mapping method for network on chip based on region division |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN102065019B (en) |
Cited By (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105183693A (en) * | 2015-05-26 | 2015-12-23 | 扬州大学 | Multicast transmission method based on three-dimensional network on chip |
| WO2017000551A1 (en) * | 2015-06-29 | 2017-01-05 | 中兴通讯股份有限公司 | Method and device for measuring traffic balance degree |
| CN106330702A (en) * | 2016-08-16 | 2017-01-11 | 清华大学 | Multi-stage Hybrid Routing System and Its Routing Method for Neuromorphic Computing |
| CN107169561A (en) * | 2017-05-09 | 2017-09-15 | 广西师范大学 | Towards the hybrid particle swarm impulsive neural networks mapping method of power consumption |
| CN109547263A (en) * | 2018-12-15 | 2019-03-29 | 华南理工大学 | Network-on-chip optimization method based on approximate calculation |
| CN109995679A (en) * | 2019-04-08 | 2019-07-09 | 上海海洋大学 | NoC system based on task-driven chip-level multi-heterogeneous communication cores |
| CN112183015A (en) * | 2020-11-04 | 2021-01-05 | 南京师范大学 | Chip layout planning method for deep neural network |
| CN113900917A (en) * | 2021-09-30 | 2022-01-07 | 上海商汤智能科技有限公司 | A performance determination method, device, computer equipment and storage medium |
| CN115168281A (en) * | 2022-09-09 | 2022-10-11 | 之江实验室 | A neural network on-chip mapping method and device based on tabu search algorithm |
| CN115277563A (en) * | 2022-06-07 | 2022-11-01 | 南京大学 | On-chip network approximate control system based on offline reinforcement learning |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101847168A (en) * | 2010-04-09 | 2010-09-29 | 西安电子科技大学 | Application-oriented network on chip generation method based on regular topology database |
-
2011
- 2011-01-21 CN CN201110024596A patent/CN102065019B/en not_active Expired - Fee Related
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101847168A (en) * | 2010-04-09 | 2010-09-29 | 西安电子科技大学 | Application-oriented network on chip generation method based on regular topology database |
Cited By (18)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105183693A (en) * | 2015-05-26 | 2015-12-23 | 扬州大学 | Multicast transmission method based on three-dimensional network on chip |
| CN105183693B (en) * | 2015-05-26 | 2019-06-14 | 扬州大学 | A Multicast Transmission Method Based on 3D Network-on-Chip |
| WO2017000551A1 (en) * | 2015-06-29 | 2017-01-05 | 中兴通讯股份有限公司 | Method and device for measuring traffic balance degree |
| CN106330743A (en) * | 2015-06-29 | 2017-01-11 | 中兴通讯股份有限公司 | Method and device for measuring flow balance degree |
| CN106330743B (en) * | 2015-06-29 | 2020-10-13 | 中兴通讯股份有限公司 | Method and device for measuring flow balance degree |
| CN106330702B (en) * | 2016-08-16 | 2019-09-20 | 清华大学 | Multi-stage Hybrid Routing System and Its Routing Method for Neuromorphic Computing |
| CN106330702A (en) * | 2016-08-16 | 2017-01-11 | 清华大学 | Multi-stage Hybrid Routing System and Its Routing Method for Neuromorphic Computing |
| CN107169561A (en) * | 2017-05-09 | 2017-09-15 | 广西师范大学 | Towards the hybrid particle swarm impulsive neural networks mapping method of power consumption |
| CN109547263A (en) * | 2018-12-15 | 2019-03-29 | 华南理工大学 | Network-on-chip optimization method based on approximate calculation |
| CN109547263B (en) * | 2018-12-15 | 2021-08-20 | 华南理工大学 | On-chip Network Optimization Method Based on Approximate Computation |
| CN109995679A (en) * | 2019-04-08 | 2019-07-09 | 上海海洋大学 | NoC system based on task-driven chip-level multi-heterogeneous communication cores |
| CN112183015A (en) * | 2020-11-04 | 2021-01-05 | 南京师范大学 | Chip layout planning method for deep neural network |
| CN112183015B (en) * | 2020-11-04 | 2024-04-19 | 南京师范大学 | Chip layout planning method for deep neural network |
| CN113900917A (en) * | 2021-09-30 | 2022-01-07 | 上海商汤智能科技有限公司 | A performance determination method, device, computer equipment and storage medium |
| CN113900917B (en) * | 2021-09-30 | 2025-05-27 | 上海商汤智能科技有限公司 | A performance determination method, device, computer equipment and storage medium |
| CN115277563A (en) * | 2022-06-07 | 2022-11-01 | 南京大学 | On-chip network approximate control system based on offline reinforcement learning |
| CN115277563B (en) * | 2022-06-07 | 2024-03-19 | 南京大学 | An on-chip network approximate control system based on offline reinforcement learning |
| CN115168281A (en) * | 2022-09-09 | 2022-10-11 | 之江实验室 | A neural network on-chip mapping method and device based on tabu search algorithm |
Also Published As
| Publication number | Publication date |
|---|---|
| CN102065019B (en) | 2012-10-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN102065019A (en) | IP (Internet Protocol) core fast mapping method for network on chip based on region division | |
| CN104050390B (en) | Mobile robot path planning method based on variable-dimension particle swarm membrane algorithm | |
| CN112181867B (en) | On-chip network memory controller layout method based on multi-target genetic algorithm | |
| CN115168281B (en) | Neural network on-chip mapping method and device based on tabu search algorithm | |
| Sahu et al. | Extending Kernighan–Lin partitioning heuristic for application mapping onto Network-on-Chip | |
| CN105515987A (en) | SDN framework based virtual optical network oriented mapping method | |
| CN112468401A (en) | Network-on-chip routing communication method for brain-like processor and network-on-chip | |
| CN102073700A (en) | Discovery method of complex network community | |
| Srinivasan et al. | ISIS: a genetic algorithm based technique for custom on-chip interconnection network synthesis | |
| Fan et al. | Dynamic virtual network embedding of mobile cloud system based on global resources in internet of vehicles | |
| CN103455612B (en) | Based on two-stage policy non-overlapped with overlapping network community detection method | |
| Shao et al. | Identifying influential nodes in complex networks based on Neighbours and edges | |
| Alharbe et al. | An improved ant colony algorithm for solving a virtual machine placement problem in a cloud computing environment | |
| CN107016459A (en) | A kind of point-to-point shortest path computational methods based on network community message | |
| CN110807931A (en) | Traffic network directed graph path model construction and solving method based on steering relation | |
| CN106875064A (en) | A kind of method for routing asked under specified point constraint based on genetic algorithm | |
| CN105488247A (en) | K-mean community structure mining method and apparatus | |
| Wang et al. | Community discovery algorithm of complex network attention model | |
| CN118690159A (en) | A short-term power load forecasting method and device based on multi-model fusion | |
| CN104573880B (en) | A kind of method for optimizing route for logistics distribution field | |
| CN109582457A (en) | Network-on-chip heterogeneous multi-core system task schedule and mapping | |
| CN117688992B (en) | Resource mapping method and device for neuron computer operating system | |
| Guo et al. | A novel cluster-head selection algorithm based on hybrid genetic optimization for wireless sensor networks | |
| Lu et al. | Research on optimization method of computer network service quality based on feature matching algorithm | |
| Niu et al. | A loss-aware growing ring self-organizing map (GRSOM)-based mapping algorithm in optical network-on-chip (ONoC) |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| C41 | Transfer of patent application or patent right or utility model | ||
| TR01 | Transfer of patent right |
Effective date of registration: 20160728 Address after: Xi'an City, Shaanxi province Taibai Road 710071 No. 2 Patentee after: Shaanxi Xi'an electronic large Assets Management Co.,Ltd. Address before: Xi'an City, Shaanxi province Taibai Road 710071 No. 2 Patentee before: Xidian University |
|
| C41 | Transfer of patent application or patent right or utility model | ||
| TR01 | Transfer of patent right |
Effective date of registration: 20161011 Address after: High tech Zone Industrial Park Shanglinyuan road 710075 No. 15 Shaanxi Xi'an Patentee after: Shaanxi optoelectronic integrated circuit pilot Technology Research Institute Co.,Ltd. Address before: Xi'an City, Shaanxi province Taibai Road 710071 No. 2 Patentee before: Shaanxi Xi'an electronic large Assets Management Co.,Ltd. |
|
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20121024 Termination date: 20220121 |
|
| CF01 | Termination of patent right due to non-payment of annual fee |