INTRODUCTION
Traditional system on chip1 (SoC) technology (e.g., bus structure, the effective address space) seriously restricts the development of the chip. Therefore, researchers put forward a new integrated circuit structure Network-on-chip (NoC)2 in 2005. From SoC to NoC, energy consumption has gradually become the primary limiting factor for chip design, the key point of integrated circuit design has also been transformed from the functional requirements of the chip to power requirements.
Quantum Genetic Algorithm (QGA) was a kind of probability optimization method based on the principle of quantum computing, which was proposed by Han and Kim3. The QGA has obtained the good effect for solving combinatorial optimization problems. The QGA introduces quantum state vector into the genetic encoding, it makes full use of the quantum state superposition, parallelism and quantum entanglement character. The QGA is superior to general genetic algorithm in terms of convergence speed, global and stability. In recent years, QGA has been widely used in power system reactive power optimization4,5, economic operation6,7, the grid planning, distribution network reconfiguration, etc8-10.
In this study, it obtains the optimal solution based on hybrid quantum genetic algorithm for Network-on-chip low-power mapping. Traditional genetic algorithm has strong global search ability but its local search ability is poor. It easily falls into premature phenomenon and takes a long time to achieve the optimal solution. Therefore, it proposes a hybrid quantum genetic algorithm11,12 to offset the above disadvantages. It uses communication weight of task node to divide priorities and first maps task node with big communication traffic. Genetic algorithm will start with a better initial solution. It combines adaptive rotating angle adjustment strategy, quantum bit crossover mutation operation and group catastrophe idea to improve genetic algorithm. In each iteration calculation, it uses initial solution with a certain probability to guarantee the population diversity and avoid the optimization stagnate. At the same time, it adopts roulette, optimal neighborhood selection and evolution reversal operation to adjust the evolution direction and improve convergence speed of algorithm.
MATERIALS AND METHODS
Network-on-chip mapping: Net-on-chip indicates that NoC allocates task nodes or logic IP cores into appropriate resources nodes in Architecture Characteristic Graph13 (ACG) under the condition of given task, topology structure and bandwidth, which makes various applications efficiently and smoothly completed and consumes the least energy. Figure 1 shows that, Task Graph14 (TG) allocates task nodes into resource nodes after mapping algorithm processing. So, NoC mapping can be abstracted as the mapping between TG and NoC structure characteristics graph. The NoC mapping question belongs to NP problem. When the size of problem is larger, it is almost impossible to get accurate solution and time consuming is longer, feasible degree is very low. Therefore, it needs to adopt intelligence algorithm to find the best mapping result with its fast searching ability.
In order to make the study more representative, it adopts NoC 2D mesh topological structure. The 2D mesh structure rule has better symmetry and extensibility, supports multiple routing protocols, flow control technology, exchanging algorithm and its two-dimensional structure is easily mapped into the silicon surface, which is easy to implement. Currently, it is one of the used widely topology structures15.
Problems definition
Definition 1: Task graph TG(t,v) is an acyclic directed graph. In Fig. 1, vertex tj∈T denotes a task node. Directed arc denotes the communication relationship between task node ti and tj as The denotes the number of connecting with other task nodes except itself.
|
| Fig. 1: | Mapping flow chart |
The value in the arc between task node ti and tj is the communication traffic, written as
Definition 2: Architecture characteristic graph ACG(p, h) is a directed graph. In Fig. 1, vertex pi∈P denotes a resource node in 2D Mesh. Directed arc hi,j denotes the physical link between pi and pj. Its value is the Manhattan distance.
The task nodes and resource nodes are one-to-one relationship, in order to ensure the proper execution of the mapping results, resource nodes number of ACG must be greater than or equal to the task node in the TG. Namely:
Mapping function map() allocates task nodes in TG(t, v) into resource nodes of ACG(p, h):
The Eq. 4-7 shows that each task is completed by one resource node. Each resource node executes one task. After mapping, jump number will be determined among each task node.
Power model: Unit bits data transmission between adjacent node resources consumes energy Ebit:
where, are consumed energy in exchange structure, buffering and internal wiring respectively. The is consumed energy in physical link. Under the existing technological level, size of resource nodes in the NoC has reached nanometer level, energy consumption in exchange structure, buffering and internal wiring is far less than that in the physical link.
So Eq. 8 can be written as:
Therefore, energy consumption of unit bits data transforming from ti to tj is:
where, is switches from resource node ti to tj denoted by Manhattan distance. Assuming that NoC 2D Mesh is in a x-y coordinate axis, so Size of NoC 2D mesh is N·N. Total energy consumption of information interaction in NoC is:
where, is communication traffic from resource node ti to tj. It can see that when the power consumption model is simplified, the direct optimization way for reducing the energy loss is to reduce the sum of the Manhattan distance. More specifically, it reduces the the Manhattan distance with bigger communication weight between mapping resource nodes. After computing and comparing the power consumption under each mapping result, it can find the minimum energy consumption. As Eq. 13:
Low-power mapping based on hybrid quantum genetic algorithm: In this study, it proposes a hybrid quantum genetic algorithm (HQGA) based on quantum genetic algorithm and the general genetic algorithm theory, its basic idea is that it uses adaptive rotation angle adjustment strategy to adaptively adjust the algorithm search speed; through quantum crossover and mutation operators, it realizes the combination between common genetic algorithm and quantum genetic algorithm which is beneficial to keep relatively good gene fragments and improve the local search ability, it introduces catastrophe strategy, which is conducive to jumping out of local optimal algorithm and improving the global search ability. Then it codes the question parameters into chromosomes and reuses iterative manner to make crossover and mutation operation to exchange the coded information in the chromosome, which is gradually close to the best chromosomes, finally it produces chromosomes meeting the optimization goal. Genetic algorithm16-18 has a big search range, can approximate optimal solution area with a faster speed. It is an ideal heuristic algorithm to solve the NoC mapping. Genetic algorithm has strong global search ability and poor local search ability, it uses hybrid quantum genetic algorithm to improve the disadvantages of traditional genetic algorithm.
Process of hybrid quantum genetic algorithm:
| • |
Setting parameters of algorithm: Parameters are as in Table 1. Parameters setting has a great influence on the genetic algorithm, for example the mutation probability is bigger that can lead to the mean and optimal value of each generation fitting not well. And it cannot achieve the stable value |
| • |
Initializing code, generating task node communication matrix. It obtains task node number M in task graph makes decimal coding for each task node. It gives no-repeat 1-M values for task node, extracts communication traffic and generates M×M communication matrix |
| • |
Constructing better initial solution: In ACG(p,h) with the rule of NoC mesh structure, initial mapping of genetic algorithm is random allocation. The M task nodes have N2!(N2-M)! mapping results. When the task node number is larger, it is not possible to put all random map as the initial population generation into the calculation. Population size is too big, so evolution efficiency is very low. In order to reduce the number of iterations and achieve the optimum solution area, it builds a better initial solution set and reduces the time-consuming of generating optimal solution. The following is the process to calculate better initial solution |
| • |
Calculating each task node communication traffic . The high communication traffic is, the high task node priority is |
| • |
It selects the task node with highest priority as first node. Assuming that multiple task nodes communication traffic is consistent, it takes the larger average traffic task node as the first node as in Eq. 14. The Ai is bigger, then the priority is high. If more than two communication traffics are same, then the Ai is unchanged. Table 2 is the each node priority order according to the rule: |
| • |
The selection of initial mapping resource node has a great influence on following nodes mapping. So, it first puts node with high priority on the symmetry resource node of NoC 2D mesh to reduce the jump number of highest priority task node. Because NoC 2D mesh is symmetrical structure with several symmetric resource nodes. Transition number is 1, its neighborhood node are 2, 3 and 4. Because it is one-to-one correspondence relation, connecting task node of the highest priority task node is less than or equal to 4, it chooses the neighborhood resource nodes equal to connected task nodes as the mapping nodes. If connected task node number is greater than 4, then it selects the neighborhood resources node which has a big difference from the connected task nodes, it can save the node and link resources. When there are multiple optimal resource nodes, it randomly selects a node as a mapping point. Second it places the highest priority task node connecting mapping task nodes on the connected resource nodes, thereby it can reduce transition number between big communication traffic task node as Fig. 2. First it places 2-3 nodes with big communication weight, then the rest of task nodes randomly map to construct better initial solution |
| • |
Adaptive rotation angle adjustment strategy. Quantum revolving door adjustment operation is: |
| Table 1: |
Definition of parameters |
|
| Table 2: |
Priority computing |
|
| • |
where, (αi, βi)T andare the probability amplitude of i-th quantum bit revolving door before and after updating in chromosome.θi is revolving angle. The k is coefficient related to convergence speed. The k is bigger, algorithm will be precocity. Otherwise, speed of algorithm is very slow. Function s(αi, βi) will leads algorithm search towards to optimal solution. Its value is as Table 3. The +1 denotes that rotation angle moves along counterclockwise direction. The -1 denotes that rotation angle moves along clockwise direction |
| • |
Genetic operation: Based on the better initial solution, it gradually produces new chromosome through selection, crossover and mutation operation to construct new population group and reach at the optimal solution |
| Table 3: | Value of function s(αi, βi) |
|
|
It selects communication power consumption of mapping results as fitness. Communication power consumption is low, the greater fitness is. It uses roulette, the optimal neighbor strategy to make chromosome selection. It divides wheel into M parts, which ensures that the probability of each chromosome selected is same. Then it chooses the chromosome with big fitness to make up a new group and execute crossover and mutation operation. In that some individuals breed next generation faster, which destroys the population diversity and makes the genetic operations fall into premature convergence trap. So, initial solution chromosome randomly replace that in a selected group with a certain probability of random in each iteration to ensure the population diversity and avoid premature convergence phenomenon |
|
Quantum crossover operation: In quantum genetic algorithm, crossover operation object is a quantum bit rather than gene. It introduces crossover operation to ensure group integrity and greatly improve local search ability of algorithm. Quantum crossover method in this study uses single point crossover operation, it randomly selects two chromosomes and generates a crossover location and then it keeps the individual pieces before the crossover position, only exchanges quantum bits after crossover position. Crossover process is as shown in Fig. 3 |
|
Quantum mutation operation: Quantum mutation operation is to prevent algorithm premature and improve the local searching ability. It selects a chromosome with a certain probability, then it determines the mutation quantum bits in chromosome. Finally, it executes CNOT operation for the selected quantum bits as Fig. 4 |
|
| Fig. 2: | Node priority mapping |
|
| Fig. 3: |
Crossover operation process |
|
| Fig. 4: | Mutation operation process |
| Table 4: | Characteristic pattern attribute |
|
|
Quantum catastrophe idea: It indicates that it puts a great disturbance on population in evolution process, which makes it jump out of local optimal and begins to research. It can effectively prevent the algorithm falling into local optimum. If the best value of individual after successive generations does not change, it suggests that algorithm may fall into local optimum. Then it should adopt quantum catastrophe strategy |
RESULTS AND DISCUSSION
In order to verify the effectiveness of our hybrid quantum genetic algorithm (HQGA) used for low-power mapping in Network-on-chip, it makes some experiments. To reflect that HQGA is effective to all kinds of applications, this study uses the actual task communication diagram (including MPEG-4, VOPD, 263Enc and 263Dec) and random task communication diagram (G1, G2 generated by TGFF software) for testing as Table 4. The task node number, communication side and total communication are different in this six application graphs, which can fully reflect the merits and demerits of mapping algorithm. In order to guarantee the accuracy of experimental results and improve the representation of the experimental data, it makes 20 calculation with different mapping algorithms under the different mesh size, record every power consumption value. Finally, it takes average results of the 20 times calculations. Mesh size is 4×4, 5×5, 6×6.
|
| Fig. 5: |
MPEG-4 function value |
|
| Fig. 6: | G1 function value |
Table 5 compares the power consumption with HQGA, Genetic Algorithm (GA), Random Mapping (RM). From Table 5, it can know that power consumption with HQGA decreases by 1.27, 1.98 and 35.39%, respectively in 4×4 NoC mesh condition compared to GA and RM. When NoC mesh is 5×5 and 6×6, it falls by 2.96, 6.09 and 46.00% and 4.09, 7.24 and 50.58%, respectively. So, mapping result of HQGA is generally superior to GA and RM and far less than power consumption of random mapping. With the increase of mesh size, performance of HQGA is more obvious. The HQGA places the task node with large communication traffic in the mesh symmetric resource nodes from the optimal initial solution mapping, greatly reduces the probability of task node in adverse resource nodes, thus it reduces the communication power consumption of task graph.
In this study, it selects MPEG-4 and G1 to illustrate the effectiveness as Fig. 5 and 6. When the iteration of evolution is 0, average power consumption value of HQGA mapping results is less than GA and RM, which demonstrates the feasibility of above optimal initial solution. In addition, average power consumption of GA and RM is higher than HQGA in the same evolution iteration, which shows that convergence rate of HQGA is faster than GA and RM.
| Table 5: | Power consumption decrease proportion |
|
When the best value and average value of each generation are consistent and increase with the evolution iteration, there will be no obvious fluctuation, the algorithm optimization has reached optimal stable value. In Fig. 5, HQGA reaches a steady value at 20 generations, however, GA and RM are at 40 and 70, respectively. It is similar to Fig. 6. The HQGA has the minimum power consumption and the fewest evolution iteration, followed by GA, then is RM in Fig. 6. Average power consumption of GA and RM easily occur fluctuation. Its optimization direction is different easily falling into local solution. Initial solution in HQGA can execute genetic operation with a certain probability to ensure the diversity of the population. At the same time, HQGA uses reverse evolution, the optimal neighbor strategy to adjust evolutionary direction, accelerate convergence time, avoid excessive volatility in the process of algorithm.
At present, how does it effectively map task node into each resource node in NoC structure feature diagram under system constraints to reduce total communication power consumption, which is becoming a research hot issue in the field of NoC technology. Tosun et al.19 adopted integer linear programming strategy based on clustering to reduce integer linear programming space and decrease search time and then could obtain the best mapping. However, the clustering standard was uncertain. Wu et al.20 combined genetic and ant colony algorithm. The quick search ability of genetic algorithm was used to obtain the optimal initial solution and assign pheromone concentration distribution for ant colony path according to optimal order of optimization solutions, which could make full use of the positive feedback characteristics of ant colony algorithm to search the better solution of mapping. Zang and You21 adopted adaptive genetic algorithm and used the change of best fitness and the average fitness to adjust probability of crossover and mutation in each iteration, thus it accelerated the best mapping acquirement. Sahu et al.22 presented a discrete Particle Swarm Optimization (PSO) based strategy to map applications on both 2-D and 3-D mesh-connected Networks-on-chip. The basic PSO formulation had been augmented by (1) Running multiple PSOs and (2) Deterministically generating a part of the initial population for PSO. In general, the algorithms have reduced the NoC communication power consumption but the convergence speed and the optimization effect still can be optimized. Hence, this study puts forward a new Network-on-chip low-power mapping method based on hybrid quantum genetic algorithm. Finally, it conducts comparison experiments with GA and RM from best value and average value, the simulation results and the theoretical analysis show that this new method can effectively improve the accuracy of Network-on-chip mapping.
CONCLUSION
In this study, it proposes a hybrid quantum genetic algorithm to solve low-power mapping problem in Network-on-chip. The new method adopts communication weight of task node and structure characteristics of mapping platform to make priority compartment for task node. And according to the priority and its connections, it gets better initial mapping solutions set. Meanwhile, it combines adaptive rotating angle adjustment strategy, quantum bit crossover mutation operation and group catastrophe idea. It also adds roulette, optimal neighborhood selection and evolution reversal operation into genetic algorithm. What’s more, it chooses a initial solution with a certain probability in each iteration to prevent stagnation of algorithm. The experimental results show that the HQGA is obviously better than GA and RM. In the future, it need further to consider time complexity of algorithm and build up a more representative objective function.
SIGNIFICANCE STATEMENTS
| • |
This study puts forward a new Network-on-chip low-power mapping method based on hybrid quantum genetic algorithm |
| • |
This new method adopts communication weight of task node and structure characteristics of mapping platform to make priority compartment for task node |
| • |
According to the priority and its connections, it gets better initial mapping solutions set. In solving process, combining adaptive rotating angle adjustment strategy, quantum bit crossover mutation operation and group catastrophe idea, it proposes a new hybrid quantum genetic algorithm |
| • |
It adds roulette, optimal neighborhood selection and evolution reversal operation into genetic algorithm. What’s more, it chooses a initial solution with a certain probability in each iteration to prevent stagnation of algorithm |