CN113986812B - CHNN-based network-on-light-sheet mapping method and device - Google Patents
CHNN-based network-on-light-sheet mapping method and device Download PDFInfo
- Publication number
- CN113986812B CN113986812B CN202111046022.8A CN202111046022A CN113986812B CN 113986812 B CN113986812 B CN 113986812B CN 202111046022 A CN202111046022 A CN 202111046022A CN 113986812 B CN113986812 B CN 113986812B
- Authority
- CN
- China
- Prior art keywords
- mapping
- chnn
- elements
- network
- prokaryotic
- 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.)
- Active
Links
- 238000013507 mapping Methods 0.000 title claims abstract description 192
- 238000000034 method Methods 0.000 title claims abstract description 42
- 239000011159 matrix material Substances 0.000 claims description 58
- 230000003287 optical effect Effects 0.000 claims description 9
- 238000012545 processing Methods 0.000 claims description 9
- 238000004364 calculation method Methods 0.000 claims description 7
- 238000004891 communication Methods 0.000 claims description 7
- 238000013528 artificial neural network Methods 0.000 description 8
- 238000005516 engineering process Methods 0.000 description 7
- 238000010586 diagram Methods 0.000 description 5
- 210000002569 neuron Anatomy 0.000 description 3
- 230000005540 biological transmission Effects 0.000 description 2
- 238000013461 design Methods 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 238000011160 research Methods 0.000 description 2
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000007423 decrease Effects 0.000 description 1
- 238000012804 iterative process Methods 0.000 description 1
- 239000002184 metal Substances 0.000 description 1
- 230000008054 signal transmission Effects 0.000 description 1
- 239000002356 single layer Substances 0.000 description 1
- 238000006467 substitution reaction Methods 0.000 description 1
- 238000012546 transfer Methods 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F15/00—Digital computers in general; Data processing equipment in general
- G06F15/76—Architectures of general purpose stored program computers
- G06F15/78—Architectures of general purpose stored program computers comprising a single central processing unit
- G06F15/7807—System on chip, i.e. computer system on a single chip; System in package, i.e. computer system on one or more chips in a single package
- G06F15/7825—Globally asynchronous, locally synchronous, e.g. network on chip
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/10—Complex mathematical operations
- G06F17/11—Complex mathematical operations for solving equations, e.g. nonlinear equations, general mathematical optimization problems
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computer Hardware Design (AREA)
- General Engineering & Computer Science (AREA)
- Mathematical Physics (AREA)
- Pure & Applied Mathematics (AREA)
- Data Mining & Analysis (AREA)
- Mathematical Optimization (AREA)
- Mathematical Analysis (AREA)
- Computational Mathematics (AREA)
- Operations Research (AREA)
- Algebra (AREA)
- Databases & Information Systems (AREA)
- Software Systems (AREA)
- Computing Systems (AREA)
- Microelectronics & Electronic Packaging (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The invention discloses a CHNN-based network-on-light-sheet mapping method and a device, wherein the method comprises the following steps: s1: establishing a mapping problem model to convert the mapping problem to be solved into a dynamic process of the CHNN; s2: constructing a CHNN dynamic equation according to the mapping problem model; s3: initializing CHNN; s4: updating the CHNN state according to the CHNN dynamic equation to obtain an effective mapping scheme; s5: resetting the initial state of the CHNN, executing the step S4, repeating the steps for a plurality of times to obtain a plurality of effective mapping schemes, and selecting an optimal mapping scheme from the plurality of effective mapping schemes according to the objective function. The network-on-light-sheet mapping method solves the problems of high computational complexity and long time of the existing mapping algorithm, improves the running speed of the algorithm and ensures the stability of the algorithm.
Description
Technical Field
The invention belongs to the technical field of network-on-chip, and particularly relates to a CHNN-based network-on-chip mapping method and device.
Background
The network on chip is a new communication method of the system on chip, and is an essential component of the multi-core technology. The network-on-chip method brings a brand new communication method on chip, which is obviously superior to the performance of the traditional bus system. Conventional network-on-chip (soc) mainly uses electrical signals to transfer signals, called on-chip (on-chip) networks, also called electrical on-chip (on-chip) networks, however, the performance and efficiency are limited by the metal lines in the chip. With the progress of communication technology and photonics technology, a novel interconnection technology for multiprocessor chips, namely network-on-chip technology, is proposed.
Currently, network-on-chip research is mainly based on two aspects of bus technology and network structure technology, wherein the position of an IP core in a network structure greatly influences network performance. The mapping in the network on the optical sheet is to correspond the IP cores to the virtual core picture elements in the core picture one by one, and meanwhile, the related mapping requirements are met. Therefore, how to reasonably distribute many virtual core map elements in the network-on-chip structure to meet the requirement of optical interconnection in future high-performance computing is a current urgent problem to be solved. The existing mapping algorithm mainly comprises a heuristic algorithm, a linear programming algorithm and the like.
However, the existing mapping method has high computational complexity and long time, so that the running speed of the network is slow and unstable. In addition, the state of the neural network can change along with time, and the existing algorithm lacks effective iteration stop conditions, so that errors in the running process of the algorithm influence the accuracy of the result.
Disclosure of Invention
In order to solve the problems in the prior art, the invention provides a CHNN-based network-on-chip mapping method and device. The technical problems to be solved by the invention are realized by the following technical scheme:
in one aspect, the present invention provides a method for mapping a network on a chip based on CHNN, including:
S1: establishing a mapping problem model to convert the mapping problem to be solved into a dynamic process of the CHNN;
S2: constructing a CHNN dynamic equation according to the mapping problem model;
S3: initializing CHNN;
s4: updating the CHNN state according to the CHNN dynamic equation to obtain an effective mapping scheme;
S5: resetting the initial state of the CHNN, executing the step S4, repeating the steps for a plurality of times to obtain a plurality of effective mapping schemes, and selecting an optimal mapping scheme from the plurality of effective mapping schemes according to the objective function.
In one embodiment of the present invention, step S1 includes:
Mapping a plurality of prokaryotic map elements into network elements in a topology; the mapped network elements and the prokaryotic graph elements are in one-to-one correspondence and have the same communication relationship;
representing the mapping result in a mode of a replacement matrix so as to convert the mapping problem to be solved into a dynamic process of CHNN; wherein the permutation matrix needs to satisfy a preset rule.
In one embodiment of the present invention, the preset rule includes:
first rule: only one element in each row of elements of the permutation matrix is 1, and the other elements are 0;
a second rule: only one element in each column of elements of the permutation matrix is 1, and the other elements are 0;
Third rule: the sum of all elements in the permutation matrix is equal to the number of elements before mapping.
In one embodiment of the present invention, step S2 includes:
Converting the preset rule into a constraint term equation by adopting binary decision variable definition;
Constructing an objective function according to the mapping algorithm objective;
combining the objective function and the constraint term equation to obtain an energy function of the CHNN;
and obtaining a CHNN dynamic equation according to the energy function.
In one embodiment of the invention, the objective function is expressed as:
max(i，x)V(i,j)V(x，y)Wastage(j,y)
Wherein, the elements i and x represent elements in the prokaryotic graph, and j and y represent elements in the network; (i, x) represents a connection relationship between elements in the prokaryotic map, wherein when the element i and the element x are connected, (i, x) is 1, and when the element i and the element x are not connected, (i, x) is 0; matrix V represents the state output matrix after iteration, after binary judgment is carried out on the state output matrix, a mapping scheme is represented, V (i, j) represents the corresponding relation before and after element mapping, when element i in the prokaryotic graph is mapped to element j in the network, V (i, j) is 1, otherwise, V (i, j) is 0; v (x, y) also represents the correspondence between before and after element mapping, when element x in the prokaryotic map is mapped to element y in the network, V (x, y) is 1, otherwise, is 0; wastage (j, y) represents losses between network elements.
In one embodiment of the invention, the CHNN dynamic equation is expressed as:
Wherein E represents an energy function, A, B, C, D are all scaling parameters of CHNN; n represents the number of elements; elements i and x represent elements in the prokaryotic graph, and j and y represent elements in the network; v (x) represents the correspondence between before and after mapping, and is obtained by performing binary decision processing on the state output matrix V after iteration.
In one embodiment of the present invention, step 3 comprises:
performing assignment initialization on the input voltage, iteration times and weights of the CHNN;
calculating the loss between any two elements of the network;
the initial state of the CHNN is set.
In one embodiment of the present invention, step S4 includes:
updating the input and output of the dynamic equation and calculating an energy function until the iteration ending condition is met; wherein, the iteration end condition is: the current iteration times are between a preset minimum value and a preset maximum value, and the energy function reaches a minimum value;
Performing binarization processing on the output matrix meeting the iteration ending condition to obtain a mapping scheme;
and judging the effectiveness of the mapping scheme to obtain an effective mapping scheme.
In one embodiment of the present invention, in step S5, selecting an optimal mapping scheme from the plurality of valid mapping schemes according to an objective function includes:
Solving the maximum loss of all effective mapping schemes according to an objective function;
and selecting a mapping scheme corresponding to one loss with the minimum maximum loss as an optimal mapping scheme.
On the other hand, the invention also provides a CHNN-based optical network-on-chip mapping device, which comprises:
The model building module is used for building a mapping problem model so as to convert the mapping problem to be solved into a dynamic process of the CHNN;
the calculation module is used for constructing a CHNN dynamic equation according to the mapping problem model;
The initialization module is used for initializing the CHNN;
The iteration updating module is used for updating the CHNN state according to the CHNN dynamic equation so as to obtain an effective mapping scheme;
And the preferential module is used for selecting an optimal mapping scheme from the plurality of effective mapping schemes according to the objective function.
The invention has the beneficial effects that:
1. The invention applies the CHNN algorithm to solve the mapping problem of the network on the optical sheet, converts the mapping problem to be solved into a dynamic process of the CHNN by establishing a mapping problem model, then establishes a CHNN dynamic equation, initializes the network, finally obtains an effective mapping scheme by iteratively updating the state of the CHNN network, and selects an optimal mapping scheme from a plurality of obtained effective mapping schemes according to an objective function by solving for many times, thereby solving the problems of high calculation complexity and long time of the existing mapping algorithm, improving the operation speed of the algorithm and guaranteeing the stability of the algorithm;
2. According to the invention, the limit of the iteration times and the change of the energy function value are used together as the judging conditions for ending the iteration, when the corresponding conditions are met, the iteration solution mapping scheme is ended, when the corresponding conditions are not met all the time, the iteration times are exceeded, the CHNN is automatically initialized to solve again, so that the solved effectiveness and accuracy are greatly increased, and the CHNN has good fault tolerance.
The present invention will be described in further detail with reference to the accompanying drawings and examples.
Drawings
FIG. 1 is a schematic diagram of a CHNN-based on-chip network mapping method according to an embodiment of the present invention;
FIG. 2 is a flow chart of a complete CHNN initialization and iteration process provided in an embodiment of the invention;
Fig. 3 is a schematic structural diagram of a CHNN-based on-chip network mapping device according to an embodiment of the present invention.
Detailed Description
In order to further illustrate the technical means and effects adopted by the present invention to achieve the preset purpose, the present invention provides a method and apparatus for mapping a network on a chip based on CHNN according to the present invention, which is described in further detail below with reference to the accompanying drawings and the detailed description, but the embodiments of the present invention are not limited thereto. The mapping algorithm target can be adjusted according to the actual situation, namely the overall design thought of the mapping algorithm is similar, and the objective function can be adjusted correspondingly according to the actual situation.
The foregoing and other features, aspects, and advantages of the present invention will become more apparent from the following detailed description of the preferred embodiments when taken in conjunction with the accompanying drawings. The technical means and effects adopted by the present invention to achieve the intended purpose can be more deeply and specifically understood through the description of the specific embodiments, however, the attached drawings are provided for reference and description only, and are not intended to limit the technical scheme of the present invention.
It should be noted that in this document relational terms such as first and second, and the like are used solely to distinguish one entity or action from another entity or action without necessarily requiring or implying any actual such relationship or order between such entities or actions. Moreover, the terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that an article or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed. Without further limitation, an element defined by the phrase "comprising one … …" does not exclude the presence of other like elements in an article or device comprising the element.
Example 1
Referring to fig. 1, fig. 1 is a schematic diagram of a network-on-chip mapping method based on CHNN according to an embodiment of the invention, which includes:
S1: and establishing a mapping problem model to convert the mapping problem to be solved into a dynamic process of the CHNN.
Specifically, mapping in the network on optical sheet is to make the IP cores correspond to the virtual core picture elements in the core picture one by one, and meanwhile, the related mapping requirements are met.
In the embodiment, the hopfield neural network (Hopfield neural network, HNN) is used as a single-layer fully-connected feedback neural network, and has the advantages of a more complete theoretical system, an intelligent algorithm, a higher running speed and the like. The input samples can be classified into Discrete (DHNN) and Continuous (CHNN) types according to the process. Based on the processing object of the invention, a Continuous Hopfield Neural Network (CHNN) is selected for algorithm design.
Specifically, step S1 includes:
s11: mapping a plurality of prokaryotic map elements into network elements in a topology; the mapped network elements and the prokaryotic graph elements are in one-to-one correspondence, and have the same communication relationship.
Specifically, when the number of prokaryotic elements is N, there may be N ≡ -! A mapping scheme. For example, taking the number of the prokaryotic map elements as 4 as an example, assuming that the prokaryotic map elements comprise four elements of 1,2, 3 and 4, the network element comprises A, B, C, D four elements, and the four elements of 1,2, 3 and 4 are mapped to A, B, C, D positions respectively, there are 24 mapping schemes.
S12: representing the mapping result in a mode of a replacement matrix so as to convert the mapping problem to be solved into a dynamic process of CHNN; wherein the permutation matrix needs to satisfy a preset rule.
Specifically, in this embodiment, the mapping result is expressed in the form of a permutation matrix, and then the rule of the permutation matrix needs to be satisfied. For the final mapping scheme of any one prokaryotic element, the final mapping scheme can be generally expressed by an N-dimensional vector, i.e. N neurons are needed, and then the mapping problem of N elements needs n×n neurons to be implemented. For example, in the mapping problem of 5 prokaryotic map elements, prokaryotic map element 1 is mapped to network element 3, and the corresponding vector is V (1:) =00100.
Further, the preset rules that the permutation matrix needs to satisfy include the following three:
first rule: only one element in each row of elements of the permutation matrix is 1, and the other elements are 0;
a second rule: only one element in each column of elements of the permutation matrix is 1, and the other elements are 0;
Third rule: the sum of all elements in the permutation matrix is equal to the number of elements before mapping.
S2: and constructing a CHNN dynamic equation according to the mapping problem model.
In this embodiment, step S2 includes:
S21: and converting the preset rule into a constraint term equation by adopting binary decision variable definition.
First, the first rule, that is, that one and only one element of each row of elements of the permutation matrix is 1 and the other elements are 0, is converted into the following formula:
Namely: for any one i Where i represents a prokaryotic graph element and j represents a network element. The matrix V represents the state output matrix after iteration, namely the mapping result, and binary judgment is carried out on the state output matrix after iteration, so that the final mapping scheme is represented. V (i, j) is 1 when the i element in the prokaryotic map maps to the j element in the network, otherwise it is 0.
Then, the first rule, that is, that only one element in each column of elements of the permutation matrix is 1 and the other elements are 0, is converted into the following formula:
I.e. for any one j
Finally, the third rule, that is, the sum of all elements in the permutation matrix is equal to the number of elements before mapping, is converted into the following formula:
The three formulas together form a constraint term in the energy equation, so that the binary mapping result is a satisfactory replacement matrix.
S22: and constructing an objective function according to the mapping algorithm target.
In this embodiment, the mapping algorithm aims to perform signal transmission on the elements mapped in the network according to the element relationship in the kernel graph, and solve the maximum loss generated in the transmission process of the elements with the connected relationship in each effective mapping scheme. And solving for multiple times, comparing the maximum loss obtained by the multiple effective mapping schemes, and finding out the one with the minimum maximum loss in all schemes. The objective function may find the one loss value that is the largest in the transmission path loss in one mapping.
Specifically, the objective function built according to the mapping algorithm objective can be expressed as:
max(i，x)V(i，j)V(x，y)Wastage(j，y)
Wherein, the elements i and x represent elements in the prokaryotic graph, and j and y represent elements in the network; (i, x) represents a connection relationship between elements in the prokaryotic map, wherein when the element i and the element x are connected, (i, x) is 1, and when the element i and the element x are not connected, (i, x) is 0; matrix V represents the state output matrix after iteration, namely the mapping result, and binary judgment is carried out on the state output matrix after iteration is finished, so that a final mapping scheme is obtained; v (i, j) represents the correspondence between before and after element mapping, when element i in the prokaryotic graph is mapped to element j in the network, V (i, j) is 1, otherwise, is 0; v (x, y) also represents the correspondence between before and after element mapping, when element x in the prokaryotic map is mapped to element y in the network, V (x, y) is 1, otherwise, is 0; wastage (j, y) represents losses between network elements.
S23: and combining the objective function and the constraint term equation to obtain the energy function of the CHNN.
In this embodiment, the objective function is constructed by combining the constructed objective function and the constraint term equation obtained in step S21, so that the objective function corresponds to the energy function, and the specific expression of the energy function is:
Wherein A, B, C, D are penalty parameters of CHNN; i. x is a prokaryotic picture element, and x and y are network elements; the matrix V represents the state output matrix after iteration, i.e. the mapping result, and V (x) after binary decision can obviously reflect the correspondence relation between the elements before and after mapping.
In this embodiment, the first three terms in the energy function expression are constraint terms of the problem, the latter term being the target term to be optimized. When the CHNN runs, the energy function value continuously decreases along with the increase of the iteration times, and when the energy function value changes little compared with the last time, the network tends to be stable.
S24: and obtaining a CHNN dynamic equation according to the energy function.
Specifically, according to the energy equation obtained in step S23, the dynamic equation of the CHNN corresponding to the mapping problem can be deduced as follows:
s3: and (5) carrying out initialization processing on the CHNN.
First, the network parameters such as the input voltage, the iteration times, the weight and the like of the CHNN are assigned and initialized.
Specifically, the CHNN is sensitive to the energy function of the network and the coefficient of the dynamic equation in the iterative process, and the determination of the network parameter value has a direct influence on the convergence performance of the neural network, so that the reasonable selection of the parameter value is very important for solving the problem. Because of less research on the aspect of network mapping of CHNN on optical sheets at present, assignment initialization can be mainly performed by researchers on the basis of early experience summarization when network parameters are initialized.
Referring to fig. 2, fig. 2 is a flowchart of a complete CHNN initialization and iteration process provided by an embodiment of the invention.
First, assignment initialization is performed on the input voltage, iteration number, weight, and the like of the CHNN.
Then, the loss between any two elements of the network is calculated.
Specifically, after parameter initialization assignment is performed on the CHNN, loss parameters L Moff、LMon and L wc of the network can be obtained, and loss between any two elements of the network is calculated according to the loss parameters for later recall during iteration.
When the loss calculation is performed, the path problem needs to be considered; the paths are different and the losses are different.
Finally, the initial state of the CHNN is set.
Specifically, the present embodiment may initialize the input of the network as:
Wherein U 0 is the input voltage of the network, U is the input state matrix, n is the number of the elements of the prokaryotic diagram, delta xy is the added random term, and the following conditions are satisfied:
δxy∈(-1，1)。
S4: and updating the CHNN state according to the CHNN dynamic equation to obtain an effective mapping scheme.
S41: and updating the input and output of the dynamic equation and calculating the energy function until the iteration ending condition is met.
Specifically, please continue to refer to fig. 2.
First, the increment of the input state may be calculated using the CHNN dynamic equation.
Then, the input state of the next moment of CHNN is updated by using a first-order Euler method, and the update formula is as follows:
Wherein U (t) is the input state matrix at the previous moment, U (t+1) is the input state matrix at the next moment, Delta t is the iteration step size, which is the increment of the input state.
Next, the output state of the CHNN at the next time is updated by using the sigmoid function, and the update formula is as follows:
wherein V is an output state matrix, namely a mapping result, reflecting the mapping relation between the kernel graph element i and the network element j; u is the input state matrix and U 0 is the input voltage of the network.
Further, after updating the state of the dynamic equation, the energy function of the current CHNN is calculated according to the updated output, and the calculation formula refers to the energy function expression in step S23.
And finally, using the limit of the iteration times and the change of the energy function value as the judging condition for ending the iteration, and ending the iteration solution mapping scheme when the corresponding condition is met.
Since the energy function is continuously reduced as the number of iterations increases, the neuron state of the network gradually tends to the equilibrium point, and the energy function reaches a minimum when the network is running steady. Therefore, the present embodiment uses the limit of the number of iterations and the change of the energy function value together as the criterion for the end of the iteration.
Specifically, the conditions for judging the end of the iteration are: the current iteration number is between a preset minimum value and a preset maximum value, and the energy function reaches a minimum value.
If the iteration ending condition is not met, stopping iteration when the current iteration number exceeds the preset maximum iteration number, and automatically reinitializing the CHNN initial state matrix to solve again. And if the current iteration number does not exceed the maximum iteration number or the current network energy function does not meet the requirement, namely, if the current network energy function does not reach the minimum value, repeating the iteration operation.
If the iteration end condition is satisfied, the iteration is terminated.
For example, a minimum iteration number of 1000 and a maximum iteration number of 6000 may be set, and the upper limit of the energy function variation value is set to 10+ (-8). Each solution to the mapping scheme requires at least 1000 iterations, so that the energy function value is continuously reduced, and the network tends to be in a stable state as much as possible. Each iteration needs to calculate an energy function value, and the energy function value is compared with the energy function value obtained in the previous iteration to save the change value. When the number of iterations i is greater than or equal to 1000 and less than 6000, the variation of the energy function values of the (i-10) th and (i-9) th times is less than 10 (-8), and the variation of the energy function values of the (i-1) th and (i-1) th times is also less than 10 (-8), the network is basically stable, and the iteration ends by continuously comparing the variation of the two intervals to eliminate errors caused by local minima of the energy function as much as possible. When the discrimination condition i is more than 6000 and still is still not established, the initial state matrix is automatically adjusted to be solved in a iterated mode.
According to the invention, the limit of the iteration times and the change of the energy function value are used together as the judging conditions for ending the iteration, when the corresponding conditions are met, the iteration solution mapping scheme is ended, when the corresponding conditions are not met all the time, the iteration times are exceeded, the CHNN is automatically initialized to solve again, so that the solved effectiveness and accuracy are greatly increased, and the CHNN has good fault tolerance.
S42: and performing binarization processing on the output matrix meeting the iteration ending condition to obtain a mapping scheme.
Because the output matrix cannot be completely taken to 0 at the non-mapping position and taken to 1 at the mapping position as approximate values, when the iteration end condition is met, binarization processing is needed to be carried out on the output matrix V (namely the mapping result) at the moment so as to obtain a standard and complete mapping scheme.
S43: and judging the effectiveness of the mapping scheme to obtain an effective mapping scheme.
Specifically, the embodiment judges the validity of the mapping scheme according to the constraint term equation of the permutation matrix, if the binarized output matrix meets the constraint term equation, the mapping scheme is valid, otherwise, the mapping scheme is invalid, and the mapping scheme is re-solved.
S5: resetting the initial state of the CHNN, executing the step S4, repeating the steps for a plurality of times to obtain a plurality of effective mapping schemes, and selecting an optimal mapping scheme from the plurality of effective mapping schemes according to the objective function.
Because of the non-robustness of the CHNN, the result of each solution is not necessarily a globally optimal solution, and a suboptimal solution and an effective solution close to the optimal solution may occur, so that the solution needs to be performed multiple times, and the globally optimal solution is selected.
Specifically, the initial state of the setting CHNN in step S3 may be referred to, and then step S4 is performed. Through multiple solutions, multiple effective mapping schemes can be obtained, and finally, the maximum loss of all the effective mapping schemes is solved according to an objective function.
Comparing the maximum loss of each mapping scheme in the obtained multiple effective mapping schemes, and selecting the mapping scheme corresponding to the minimum loss in the maximum loss as the optimal mapping scheme.
In this embodiment, iterative computation is performed according to a network update formula to obtain an effective mapping scheme, the maximum loss in a plurality of effective mapping schemes obtained by multiple solutions is calculated and compared, and a mapping scheme corresponding to the minimum value is selected from the maximum loss, so as to obtain the optimal mapping scheme.
According to the embodiment, a CHNN algorithm is applied to solve the mapping problem of the network on the optical sheet, the mapping problem to be solved is converted into a dynamic process of the CHNN by establishing a mapping problem model, then a CHNN dynamic equation is established, the network is initialized, finally an effective mapping scheme is obtained by iteratively updating the state of the CHNN network, and an optimal mapping scheme is selected from a plurality of obtained effective mapping schemes according to an objective function through multiple solutions, so that the problems of high calculation complexity and long time of the existing mapping algorithm are solved, the operation speed of the algorithm is improved, and meanwhile the stability of the algorithm is ensured;
Example two
On the basis of the first embodiment, the present embodiment provides a CHNN-based on-chip network mapping device. Referring to fig. 3, fig. 3 is a schematic structural diagram of a CHNN-based on-chip network mapping device according to an embodiment of the present invention, which includes:
The model building module 1 is used for building a mapping problem model so as to convert a mapping problem to be solved into a dynamic process of the CHNN;
the calculation module 2 is used for constructing a CHNN dynamic equation according to the mapping problem model;
an initialization module 3, configured to perform an initialization process on the CHNN;
The iteration updating module 4 is used for updating the CHNN state according to the CHNN dynamic equation so as to obtain an effective mapping scheme;
and the preferential module 5 is used for selecting an optimal mapping scheme from the plurality of effective mapping schemes according to the objective function.
The optical network-on-chip mapping device provided in this embodiment may implement the mapping method provided in the first embodiment, and detailed processes are not described herein.
The invention solves the network-on-light-sheet problem by adopting the CHNN mapping algorithm, and the provided CHNN mapping algorithm is stable and feasible in solving the network-on-light-sheet mapping problem. The adopted neural network has good fault tolerance, the state of the neural network can change along with the change of time, and the limit of iteration times and the change of energy function values are used together as the judging condition for ending the iteration, so that the solved effectiveness and accuracy are greatly improved.
The foregoing is a further detailed description of the invention in connection with the preferred embodiments, and it is not intended that the invention be limited to the specific embodiments described. It will be apparent to those skilled in the art that several simple deductions or substitutions may be made without departing from the spirit of the invention, and these should be considered to be within the scope of the invention.
Claims (6)
1. The optical network-on-chip mapping method based on CHNN is characterized by comprising the following steps of:
s1: establishing a mapping problem model to convert the mapping problem to be solved into a dynamic process of the CHNN, which specifically comprises the following steps:
Mapping a plurality of prokaryotic map elements into network elements in a topology; the mapped network elements and the prokaryotic graph elements are in one-to-one correspondence and have the same communication relationship;
Representing the mapping result in a mode of a replacement matrix so as to convert the mapping problem to be solved into a dynamic process of CHNN; wherein the permutation matrix is required to meet a preset rule;
s2: the CHNN dynamic equation is constructed according to the mapping problem model, and the method specifically comprises the following steps:
Converting the preset rule into a constraint term equation by adopting binary decision variable definition;
Constructing an objective function according to the mapping algorithm objective; the objective function is expressed as:
max(i,x)V(i,j)V(x,y)Wastage(j,y)
Wherein, the elements i and x represent elements in the prokaryotic graph, and j and y represent elements in the network; (i, x) represents a connection relationship between elements in the prokaryotic map, wherein when the element i and the element x are connected, (i, x) is 1, and when the element i and the element x are not connected, (i, x) is 0; matrix V represents the state output matrix after iteration, after binary judgment is carried out on the state output matrix, a mapping scheme is represented, V (i, j) represents the corresponding relation before and after element mapping, when element i in the prokaryotic graph is mapped to element j in the network, V (i, j) is 1, otherwise, V (i, j) is 0; v (x, y) also represents the correspondence between before and after element mapping, when element x in the prokaryotic map is mapped to element y in the network, V (x, y) Is that 1, is 0 ; Wastage (j, y) otherwise, represents the loss between network elements;
combining the objective function and the constraint term equation to obtain an energy function of the CHNN;
Obtaining a CHNN dynamic equation according to the energy function; the CHNN dynamic equation is expressed as:
Wherein E represents an energy function, A, B, C, D are all scaling parameters of CHNN; n represents the number of elements; elements i and x represent elements in the prokaryotic graph, and j and y represent elements in the network; v (x) represents the corresponding relation before and after mapping, and is obtained by performing binary judgment processing on the state output matrix V after iteration;
S3: initializing CHNN;
s4: updating the CHNN state according to the CHNN dynamic equation to obtain an effective mapping scheme;
S5: resetting the initial state of the CHNN, executing the step S4, repeating the steps for a plurality of times to obtain a plurality of effective mapping schemes, and selecting an optimal mapping scheme from the plurality of effective mapping schemes according to the objective function.
2. The CHNN-based on-chip network-on-chip mapping method according to claim 1, wherein the preset rules comprise:
first rule: only one element in each row of elements of the permutation matrix is 1, and the other elements are 0;
a second rule: only one element in each column of elements of the permutation matrix is 1, and the other elements are 0;
Third rule: the sum of all elements in the permutation matrix is equal to the number of elements before mapping.
3. The CHNN-based on-chip network-on-chip mapping method according to claim 1, wherein step 3 comprises:
performing assignment initialization on the input voltage, iteration times and weights of the CHNN;
calculating the loss between any two elements of the network;
the initial state of the CHNN is set.
4. The CHNN-based on-chip network-on-chip mapping method according to claim 1, wherein step S4 comprises:
updating the input and output of the dynamic equation and calculating an energy function until the iteration ending condition is met; wherein, the iteration end condition is: the current iteration times are between a preset minimum value and a preset maximum value, and the energy function reaches a minimum value;
Performing binarization processing on the output matrix meeting the iteration ending condition to obtain a mapping scheme;
and judging the effectiveness of the mapping scheme to obtain an effective mapping scheme.
5. The CHNN-based on-chip network-on-chip mapping method according to claim 1, wherein in step S5, selecting an optimal mapping scheme from the plurality of valid mapping schemes according to an objective function comprises:
Solving the maximum loss of all effective mapping schemes according to an objective function;
and selecting a mapping scheme corresponding to one loss with the minimum maximum loss as an optimal mapping scheme.
6. A CHNN-based network-on-chip mapping apparatus, comprising:
the model building module (1) is used for building a mapping problem model so as to convert a mapping problem to be solved into a dynamic process of the CHNN;
a calculation module (2) for constructing a CHNN dynamic equation according to the mapping problem model;
the initialization module (3) is used for initializing the CHNN;
The iteration updating module (4) is used for updating the CHNN state according to the CHNN dynamic equation so as to obtain an effective mapping scheme;
a preferential module (5) for selecting an optimal mapping scheme from a plurality of effective mapping schemes according to an objective function;
Wherein, the model building module (1) is specifically used for:
Mapping a plurality of prokaryotic map elements into network elements in a topology; the mapped network elements and the prokaryotic graph elements are in one-to-one correspondence and have the same communication relationship;
Representing the mapping result in a mode of a replacement matrix so as to convert the mapping problem to be solved into a dynamic process of CHNN; wherein the permutation matrix is required to meet a preset rule;
The computing module (2) is specifically configured to:
Converting the preset rule into a constraint term equation by adopting binary decision variable definition;
Constructing an objective function according to the mapping algorithm objective; the objective function is expressed as:
max(i,x)V(i,j)V(x,y)Wastage(j,y)
Wherein, the elements i and x represent elements in the prokaryotic graph, and j and y represent elements in the network; (i, x) represents a connection relationship between elements in the prokaryotic map, wherein when the element i and the element x are connected, (i, x) is 1, and when the element i and the element x are not connected, (i, x) is 0; matrix V represents the state output matrix after iteration, after binary judgment is carried out on the state output matrix, a mapping scheme is represented, V (i, j) represents the corresponding relation before and after element mapping, when element i in the prokaryotic graph is mapped to element j in the network, V (i, j) is 1, otherwise, V (i, j) is 0; v (x, y) also represents the correspondence between before and after element mapping, when element x in the prokaryotic map is mapped to element y in the network, V (x, y) is 1, Whether or not is 0 ; Wastage (j, y) represents the loss between network elements;
combining the objective function and the constraint term equation to obtain an energy function of the CHNN;
Obtaining a CHNN dynamic equation according to the energy function; the CHNN dynamic equation is expressed as:
Wherein E represents an energy function, A, B, C, D are all scaling parameters of CHNN; n represents the number of elements; elements i and x represent elements in the prokaryotic graph, and j and y represent elements in the network; v (x) represents the correspondence between before and after mapping, and is obtained by performing binary decision processing on the state output matrix V after iteration.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202111046022.8A CN113986812B (en) | 2021-09-07 | 2021-09-07 | CHNN-based network-on-light-sheet mapping method and device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202111046022.8A CN113986812B (en) | 2021-09-07 | 2021-09-07 | CHNN-based network-on-light-sheet mapping method and device |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN113986812A CN113986812A (en) | 2022-01-28 |
| CN113986812B true CN113986812B (en) | 2024-07-12 |
Family
ID=79735453
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202111046022.8A Active CN113986812B (en) | 2021-09-07 | 2021-09-07 | CHNN-based network-on-light-sheet mapping method and device |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN113986812B (en) |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7003109B2 (en) * | 2001-04-19 | 2006-02-21 | City University Of Hong Kong | Compact crypto-engine for random number and stream cipher generation |
| CN104021420B (en) * | 2014-05-23 | 2017-07-04 | 电子科技大学 | Programmable discrete hopfield network circuit |
| US9842082B2 (en) * | 2015-02-27 | 2017-12-12 | Intel Corporation | Dynamically updating logical identifiers of cores of a processor |
| US9948460B2 (en) * | 2015-08-28 | 2018-04-17 | City University Of Hong Kong | Multivariate cryptography based on clipped hopfield neural network |
| CN108173760B (en) * | 2017-12-22 | 2020-11-20 | 北京工业大学 | Network-on-chip mapping method based on improved simulated annealing algorithm |
| CN111752891B (en) * | 2020-06-05 | 2022-06-03 | 西安电子科技大学 | IP core mapping method for optical network on chip |
| CN112054869B (en) * | 2020-08-05 | 2021-07-23 | 西安电子科技大学 | Wavelength allocation method based on continuous Hopfield neural network |
-
2021
- 2021-09-07 CN CN202111046022.8A patent/CN113986812B/en active Active
Non-Patent Citations (1)
| Title |
|---|
| A Loss-aware Continuous Hopfield Neural NetWork(CHNN)-based Maping Algorithm in Optical Nwework-on-Chip(NnoC);Yuxiang Niu et al;《2022 20th International Conference on Optical Communicaations and Networks（ICOCN）》;20221004;全文 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN113986812A (en) | 2022-01-28 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US20220083868A1 (en) | Neural network training method and apparatus, and electronic device | |
| CN109840154B (en) | Task dependency-based computing migration method in mobile cloud environment | |
| CN107017640B (en) | A kind of optimal load flow calculation method of electric system, apparatus and system | |
| CN113489654B (en) | Routing method, device, electronic equipment and storage medium | |
| CN110531996B (en) | Particle swarm optimization-based computing task unloading method in multi-micro cloud environment | |
| CN111158912A (en) | Task unloading decision method based on deep learning in cloud and mist collaborative computing environment | |
| CN112330021A (en) | Network coordination control method of distributed optical storage system | |
| CN116156563A (en) | Heterogeneous task and resource end edge collaborative scheduling method based on digital twin | |
| CN111798037B (en) | Data-driven optimal power flow calculation method based on stacked extreme learning machine framework | |
| CN110471621A (en) | A kind of edge towards real time data processing application under isomery peripheral surroundings cooperates with storage method | |
| CN115686846B (en) | Container cluster online deployment method integrating graph neural network and reinforcement learning in edge calculation | |
| CN113986812B (en) | CHNN-based network-on-light-sheet mapping method and device | |
| CN112101728A (en) | Energy optimization distribution method for mobile edge computing system | |
| CN111931924A (en) | Memristor neural network chip architecture compensation method based on online migration training | |
| CN115659792A (en) | Multi-period multi-scene SCUC decoupling method, system, equipment and storage medium | |
| CN112561050A (en) | Neural network model training method and device | |
| CN111488208B (en) | Bian Yun collaborative computing node scheduling optimization method based on variable-step-size bat algorithm | |
| CN108965016B (en) | Mapping method and device of virtual network | |
| CN116702598A (en) | Training method, device, equipment and storage medium for building achievement prediction model | |
| CN113296953B (en) | Distributed computing architecture, method and device of cloud side heterogeneous edge computing network | |
| WO2019200548A1 (en) | Network model compiler and related product | |
| CN110417020B (en) | Load flow calculation method and system for comprehensive energy system for processing non-smooth constraint | |
| CN114662658A (en) | On-chip optical network hot spot prediction method based on LSTM neural network | |
| CN114745386A (en) | Neural network segmentation and unloading method under multi-user edge intelligent scene | |
| CN114327853A (en) | Low-cost user association and computation migration method facing complex tasks in cloud-side hybrid system |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |