# US 2025/0165760 A1 · Neural network on-chip mapping method and apparatus based on tabu search algorithm

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2025/0165760 A1
- Document ID: US20250165760A1
- Status: Published application
- Kind: A1
- Application number: 18/288,819
- Filed: 2023-07-31
- Published: 2025-05-22
- Earliest claimed: 2022-09-09
- Assignees: Zhejiang Lab; Zhejiang University
- Applicants: Zhejiang Lab; Zhejiang University
- Inventors: Yukun HE; De MA; Ying LI; Shichun SUN; Ming ZHANG; Xiaofei JIN; Guoquan ZHU; Fangchao YANG; Pan LV; Shuiguang DENG; Gang PAN
- Web page: https://patentgrep.com/patent/US20250165760A1

## CPC

- G06N 3/063: using electronic means
- G06N 3/049: Temporal neural networks, e.g. delay elements, oscillating neurons or pulsed inputs
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

A neural network on-chip mapping method and apparatus based on a tabu search algorithm are provided. The method includes: constructing a tabu search table and using a heuristic-based iterative search process to select local computing cores of a network-on-chip as candidates, establishing an integer programming model and solving an optimal solution, continuously reducing an objective cost function of a mapping solution by loop iteration, and finally obtaining an approximately optimal deployment scheme.

## Claims

### Claim 1

A neural network on-chip mapping method based on a tabu search algorithm, comprising following steps:
step 1, acquiring a topological structure and parameter information of a spiking neural network to be deployed and constraint information of computing cores of a target machine network-on-chip;
step 2, converting the spiking neural network into a directed acyclic graph (DAG), and determining neuron sequences to be assigned according to topological sorting in the DAG;
step 3, from a pre-specified initial computing core in the network-on-chip, sequentially assigning the neuron sequences in clusters, and mapping and placing, by using a nearest neighbor algorithm, the neuron sequences one by one on the computing cores of the network-on-chip to construct an initial solution of mapping;
step 4, defining and initializing a tabu search table and a timer, calculating cost functions of all computing cores, and selecting candidate computing cores according to the cost functions, to construct a candidate set;
step 5, establishing an integer programming model for a selected and constructed candidate set and calculating an optimal solution, and swapping a core position of each neuron group according to the optimal solution, to complete local search optimization; and
step 6, iterating the timer, checking and updating the tabu search table, iteratively repeating step 4 to step 6 until an upper limit of iteration is reached, and finally outputting mapping results from the neuron groups to the computing cores, to complete the mapping.

### Claim 2 (depends on 1)

The neural network on-chip mapping method based on the tabu search algorithm of claim 1, wherein, at step 1, the spiking neural network comprises synapses and connection structures with neuron groups as nodes, each of the neuron groups comprises a plurality of neurons, the topological structure is a graph data structure represented by nodes and edges or a network structure comprising size and shape information, and at the same time, the topological structure is configured to provide behavioral parameters of the neurons and connection parameters in synaptic connections; and
each of the computing cores is a hardware unit comprising a memory and a computing unit, and the acquiring the constraint information of the computing cores of the target machine network-on-chip comprises: acquiring sizes of memories of the computing cores, two-dimensional spatial position coordinates on the network-on-chip, and a connection between the computing cores.

### Claim 3 (depends on 2)

The neural network on-chip mapping method based on the tabu search algorithm of claim 2, wherein step 2 further comprises:
converting a computing graph represented by neuron groups as nodes and synaptic connections as edges, and constructing a complete directed acyclic graph according to a model input node of the spiking neural network as a source, a model output node as a target, and directions of the synaptic connections as directed edges, which is called a network DAG;
then determining an order of the neuron groups for the DAG by using a topological sorting method, wherein the topological sorting method comprises: counting all node in-degrees in the DAG and maintaining a priority queue sorted in ascending order of the node in-degrees, popping a node in the priority queue, sequentially deleting the edges in the DAG with this node as output, updating in-degrees of the remaining nodes in the priority queue, and repeating the steps until the priority queue is empty; and
finally, marking an order in which nodes of the neuron group are popped from the priority queue as topological sorting corresponding to the nodes of the neuron group, wherein numbers of the topological sorting are topological numbers of all neurons in the neuron group.

### Claim 4 (depends on 3)

The neural network on-chip mapping method based on the tabu search algorithm of claim 3, wherein step 3 further comprises: starting assignment from the pre-specified initial computing core according to acquired two-dimensional grid information of the network-on-chip, wherein, when not specified, the computing core at an upper left corner of a two-dimensional grid in the two-dimensional grid information is used as the initial computing core; and
sequentially assigning the neuron sequences in clusters to the computing nodes according to the topological numbers, counting a quantity of synaptic connections between a current neuron group and a neuron group assigned by the network-on-chip, sequentially trying to use all available unassigned computing core resources of the network-on-chip to calculate local cost functions, respectively, and selecting, by using the nearest neighbor algorithm, the computing core of the network-on-chip with a minimum cost as a target core next assigned;
wherein, prior to assignment of all neurons in one neuron group, since all neurons have a same topological number, node in-degrees of all the neurons are counted, and assignment is performed sequentially in descending order of the node in-degrees of the neurons until a memory of a current computing core is full or all the neurons of the neuron group are assigned; when remaining neurons are still unassigned, the remaining neurons are classified into a new neuron group and assigned; and after all neurons are assigned, a corresponding relationship between the topological numbers of the neurons and the computing cores is returned as the constructed initial solution of mapping; and
at the same time, all the neurons in each computing core reconstitute a new neuron group, and a new DAG with the neuron group as a node is generated, which is called a physical DAG.

### Claim 5 (depends on 4)

The neural network on-chip mapping method based on the tabu search algorithm of claim 4, wherein step 4 further comprises:
step 4.1, setting that a total of N neuron groups are mapped and placed in step 3 and a total of G available assigned network-on-chip computing cores, wherein N≤G, and both N and G are positive integers;
step 4.2, initializing a one-dimensional tabu search table denoted as T with a length of N, with initial values of 0, and initializing a tabu time window constant denoted as t with a typical value that is an integer within an interval [5, 10] and a timer denoted as t with an initial value of 0; and
for an i-th neuron group, i∈N, defining a tabu time denoted as T[i] in the tabu search table, which indicates that when a current time t, i.e., a current optimization round satisfies a relationship: t<T[i], the neuron group is not allowed to be selected into the candidate set, and only when the time t satisfies a relationship: t≥T[i], the neuron group is selected into the candidate set, and when the i-th neuron group is selected into the candidate set at the moment t, the time of the neuron group in the tabu search table is updated to t+τ; and
step 4.3, calculating a cost function between the neuron groups in the physical DAG and a global cost function of the network-on-chip, and searching for the candidate set by using a selection method based on undirected graph breadth-first search algorithm or a selection method based on a global cost function and a Prim minimum spanning tree algorithm.

### Claim 6 (depends on 5)

The neural network on-chip mapping method based on the tabu search algorithm of claim 5, wherein at step 4.3,
the calculating the cost function between the neuron groups in the physical DAG is calculating communication density of spike packets between two neuron groups, which further comprises: randomly selecting a sampled subset from an input dataset used by a neural network and inputting the data of the sampled subset to the neural network, and counting the number of spike packets sent from a neuron group in to a neuron group jn, wherein a count value of the number of spike packets is the corresponding communication density, and NCM(in, jn) represents communication density between the neuron group in and the neuron group jn;
the calculating the global cost function of the network-on-chip is calculating an overall cost of communication of spikes on the network-on-chip, which further comprises: assuming that numbers of the computing cores where the neuron group in and the neuron group jn are located are ig and jg, respectively, wherein the overall cost is a product of a communication distance and communication density, that is,
C(in, ig, jn, jg)=GCM(ig, jg)×NCM(in, jn), where GCM(ig, jg) represents Manhattan distance between the computing core ig and the computing core jg;
the selection method based on undirected graph breadth-first search algorithm further comprises: transforming the physical DAG into an undirected graph, randomly selecting a neuron group to build an initial candidate set, traversing, by using a breadth-first search algorithm, the undirected graph with the neuron group as a starting point, and sequentially adding visited neuron groups not within a tabu range to the candidate set until a required number of neuron groups is reached in the candidate set; and
the selection method based on the global cost function and the Prim minimum spanning tree algorithm further comprises: transforming the physical DAG into an undirected graph, randomly selecting a neuron group to build an initial candidate set, calculating and sorting, in the undirected graph with the neuron group as an endpoint, global costs of all neuron groups connected thereto, selecting a neuron group with a maximum global cost and adding the selected neuron group to the candidate set, investigating all edges accessible to all current neuron groups in the candidate set, searching for a neuron group of which the edges are not in the candidate set, has the maximum global cost, and is not within a range of the tabu search table, adding the searched neuron group to the candidate set again, and repeating the search process until a required number of neuron groups is reached in the candidate set.

### Claim 7 (depends on 6)

The neural network on-chip mapping method based on the tabu search algorithm of claim 6, wherein the establishing the integer programming model at step 5 further comprises:
setting that the candidate set comprises K neuron groups, wherein numbers of the computing cores where a neuron group in and a neuron group jn are located are ig and jg, respectively; setting that a variable xin,ig of 0-1 is an existence state of the neuron group in on the computing core ig, when xin,ig is 1, it indicates that the neuron group in is mapped on the computing core ig, and when xin,ig is 0, it indicates that the neuron group in is not mapped on the computing core ig; and establishing the integer programming model, wherein an expression of the integer programming model is:
minimize:
∑
i
n
⁢
i
g
,
j
n
,
j
g
∈
K
x
i
n
,
i
g
⁢
x
j
n
,
j
g
⁢
C
⁡
(
i
n
,
i
g
,
j
n
,
j
g
)
+
∑
i
n
⁢
i
g
∈
K
,
j
n
,
j
g
∈
N
⁢
\
⁢
K
x
i
n
,
i
g
⁢
C
⁡
(
i
n
,
i
g
,
j
n
,
j
g
)
subject to:
∑
i
n
∈
K
x
i
n
,
i
g
=
1
⁢
for
⁢
all
⁢
i
g
⁢
in
⁢
K
⁢
∑
i
g
∈
K
x
i
n
,
i
g
=
1
⁢
for
⁢
all
⁢
i
n
⁢
in
⁢
K
⁢
x
i
n
,
i
g
∈
{
0
,
1
}
⁢
for
⁢
all
⁢
i
n
,
i
g
⁢
in
⁢
K
wherein an objective function comprises two parts, Σinig,jn,jg∈Kxin,igxjn,jgC(in, ig, jn, jg) is a total communication cost between the K neuron groups and the computing cores where the K neuron groups are located, Σinig∈K,jn,jg∈N\Kxin,igC(in, ig, jn, jg) is a total communication cost between the K neuron groups and other neuron groups not in the candidate set, and positions of the computing cores to which the neuron groups not in the candidate set are mapped are all fixed, so only xin,ig is retained; and
wherein a constraint condition Σin∈Kxin,ig=1 for all ig in K requires that, for each computing core, only one neuron group is deployed thereon; and a constraint condition Σig∈Kxin,ig=1 for all in in K requires that each neuron group is deployed on only one computing core.

### Claim 8 (depends on 7)

The neural network on-chip mapping method based on the tabu search algorithm of claim 7, wherein the integer programming model is a mixed integer nonlinear programming model, an optimal solution xin,ig is obtained by using an extended cutting plane method, and the neuron groups in, ig satisfying a relationship: xin,ig=1 are found to obtain swapped positions of the computer cores of all K neuron groups.

### Claim 9 (depends on 1)

A neural network on-chip mapping apparatus based on a tabu search algorithm, comprising one or more processors configured to implement the neural network on-chip mapping method based on the tabu search algorithm of claim 1.

### Claim 10 (depends on 1)

A computer-readable storage medium, wherein a program is stored on the computer-readable storage medium, and when the program is executed by a processor, the neural network on-chip mapping method based on the tabu search algorithm of claim 1 is implemented.

### Claim 11 (depends on 9)

The neural network on-chip mapping apparatus based on the tabu search algorithm of claim 9, wherein, at step 1, the spiking neural network comprises synapses and connection structures with neuron groups as nodes, each of the neuron groups comprises a plurality of neurons, the topological structure is a graph data structure represented by nodes and edges or a network structure comprising size and shape information, and at the same time, the topological structure is configured to provide behavioral parameters of the neurons and connection parameters in synaptic connections; and
each of the computing cores is a hardware unit comprising a memory and a computing unit, and the acquiring the constraint information of the computing cores of the target machine network-on-chip comprises: acquiring sizes of memories of the computing cores, two-dimensional spatial position coordinates on the network-on-chip, and a connection between the computing cores.

### Claim 12 (depends on 11)

The neural network on-chip mapping apparatus based on the tabu search algorithm of claim 11, wherein step 2 further comprises:
converting a computing graph represented by neuron groups as nodes and synaptic connections as edges, and constructing a complete directed acyclic graph according to a model input node of the spiking neural network as a source, a model output node as a target, and directions of the synaptic connections as directed edges, which is called a network DAG;
then determining an order of the neuron groups for the DAG by using a topological sorting method, wherein the topological sorting method comprises: counting all node in-degrees in the DAG and maintaining a priority queue sorted in ascending order of the node in-degrees, popping a node in the priority queue, sequentially deleting the edges in the DAG with this node as output, updating in-degrees of the remaining nodes in the priority queue, and repeating the steps until the priority queue is empty; and
finally, marking an order in which nodes of the neuron group are popped from the priority queue as topological sorting corresponding to the nodes of the neuron group, wherein numbers of the topological sorting are topological numbers of all neurons in the neuron group.

### Claim 13 (depends on 12)

The neural network on-chip mapping apparatus based on the tabu search algorithm of claim 12, wherein step 3 further comprises: starting assignment from the pre-specified initial computing core according to acquired two-dimensional grid information of the network-on-chip, wherein, when not specified, the computing core at an upper left corner of a two-dimensional grid in the two-dimensional grid information is used as the initial computing core; and
sequentially assigning the neuron sequences in clusters to the computing nodes according to the topological numbers, counting a quantity of synaptic connections between a current neuron group and a neuron group assigned by the network-on-chip, sequentially trying to use all available unassigned computing core resources of the network-on-chip to calculate local cost functions, respectively, and selecting, by using the nearest neighbor algorithm, the computing core of the network-on-chip with a minimum cost as a target core next assigned;
wherein, prior to assignment of all neurons in one neuron group, since all neurons have a same topological number, node in-degrees of all the neurons are counted, and assignment is performed sequentially in descending order of the node in-degrees of the neurons until a memory of a current computing core is full or all the neurons of the neuron group are assigned; when remaining neurons are still unassigned, the remaining neurons are classified into a new neuron group and assigned; and after all neurons are assigned, a corresponding relationship between the topological numbers of the neurons and the computing cores is returned as the constructed initial solution of mapping; and
at the same time, all the neurons in each computing core reconstitute a new neuron group, and a new DAG with the neuron group as a node is generated, which is called a physical DAG.

### Claim 14 (depends on 13)

The neural network on-chip mapping apparatus based on the tabu search algorithm of claim 13, wherein step 4 further comprises:
step 4.1, setting that a total of N neuron groups are mapped and placed in step 3 and a total of G available assigned network-on-chip computing cores, wherein N≤G, and both N and G are positive integers;
step 4.2, initializing a one-dimensional tabu search table denoted as T with a length of N, with initial values of 0, and initializing a tabu time window constant denoted as t with a typical value that is an integer within an interval [5, 10] and a timer denoted as t with an initial value of 0; and
for an i-th neuron group, i∈N, defining a tabu time denoted as T[i] in the tabu search table, which indicates that when a current time t, i.e., a current optimization round satisfies a relationship: t<T[i], the neuron group is not allowed to be selected into the candidate set, and only when the time t satisfies a relationship: t≥T[i], the neuron group is selected into the candidate set, and when the i-th neuron group is selected into the candidate set at the moment t, the time of the neuron group in the tabu search table is updated to t+τ; and
step 4.3, calculating a cost function between the neuron groups in the physical DAG and a global cost function of the network-on-chip, and searching for the candidate set by using a selection method based on undirected graph breadth-first search algorithm or a selection method based on a global cost function and a Prim minimum spanning tree algorithm.

### Claim 15 (depends on 14)

The neural network on-chip mapping apparatus based on the tabu search algorithm of claim 14, wherein at step 4.3,
the calculating the cost function between the neuron groups in the physical DAG is calculating communication density of spike packets between two neuron groups, which further comprises: randomly selecting a sampled subset from an input dataset used by a neural network and inputting the data of the sampled subset to the neural network, and counting the number of spike packets sent from a neuron group in to a neuron group jn, wherein a count value of the number of spike packets is the corresponding communication density, and NCM(in, jn) represents communication density between the neuron group in and the neuron group jn;
the calculating the global cost function of the network-on-chip is calculating an overall cost of communication of spikes on the network-on-chip, which further comprises: assuming that numbers of the computing cores where the neuron group in and the neuron group jn are located are ig and jg, respectively, wherein the overall cost is a product of a communication distance and communication density, that is,
C(in, ig, jn, jg)=GCM(ig, jg)×NCM(in, jn), where GCM(ig, jg) represents Manhattan distance between the computing core ig and the computing core jg;
the selection method based on undirected graph breadth-first search algorithm further comprises: transforming the physical DAG into an undirected graph, randomly selecting a neuron group to build an initial candidate set, traversing, by using a breadth-first search algorithm, the undirected graph with the neuron group as a starting point, and sequentially adding visited neuron groups not within a tabu range to the candidate set until a required number of neuron groups is reached in the candidate set; and
the selection method based on the global cost function and the Prim minimum spanning tree algorithm further comprises: transforming the physical DAG into an undirected graph, randomly selecting a neuron group to build an initial candidate set, calculating and sorting, in the undirected graph with the neuron group as an endpoint, global costs of all neuron groups connected thereto, selecting a neuron group with a maximum global cost and adding the selected neuron group to the candidate set, investigating all edges accessible to all current neuron groups in the candidate set, searching for a neuron group of which the edges are not in the candidate set, has the maximum global cost, and is not within a range of the tabu search table, adding the searched neuron group to the candidate set again, and repeating the search process until a required number of neuron groups is reached in the candidate set.

### Claim 16 (depends on 15)

The neural network on-chip mapping apparatus based on the tabu search algorithm of claim 15, wherein the establishing the integer programming model at step 5 further comprises:
setting that the candidate set comprises K neuron groups, wherein numbers of the computing cores where a neuron group in and a neuron group jn are located are ig and jg, respectively; setting that a variable xin,ig of 0-1 is an existence state of the neuron group in on the computing core ig, when xin,ig is 1, it indicates that the neuron group in is mapped on the computing core ig, and when xin,ig is 0, it indicates that the neuron group in is not mapped on the computing core ig; and establishing the integer programming model, wherein an expression of the integer programming model is:
minimize:
∑
i
n
⁢
i
g
,
j
n
,
j
g
∈
K
x
i
n
,
i
g
⁢
x
j
n
,
j
g
⁢
C
⁡
(
i
n
,
i
g
,
j
n
,
j
g
)
+
∑
i
n
⁢
i
g
∈
K
,
j
n
,
j
g
∈
N
⁢
\
⁢
K
x
i
n
,
i
g
⁢
C
⁡
(
i
n
,
i
g
,
j
n
,
j
g
)
subject to:
∑
i
n
∈
K
x
i
n
,
i
g
=
1
⁢
for
⁢
all
⁢
i
g
⁢
in
⁢
K
⁢
∑
i
g
∈
K
x
i
n
,
i
g
=
1
⁢
for
⁢
all
⁢
i
n
⁢
in
⁢
K
⁢
x
i
n
,
i
g
∈
{
0
,
1
}
⁢
for
⁢
all
⁢
i
n
,
i
g
⁢
in
⁢
K
wherein an objective function comprises two parts, Σinig,jn,jg∈Kxin,igxjn,jgC(in, ig, jn, jg) is a total communication cost between the K neuron groups and the computing cores where the K neuron groups are located, Σinig∈K,jn,jg∈N\Kxin,igC(in, ig, jn, jg) is a total communication cost between the K neuron groups and other neuron groups not in the candidate set, and positions of the computing cores to which the neuron groups not in the candidate set are mapped are all fixed, so only xin,ig is retained; and
wherein a constraint condition Σin∈Kxin,ig=1 for all ig in K requires that, for each computing core, only one neuron group is deployed thereon; and a constraint condition Σig∈Kxin,ig=1 for all in in K requires that each neuron group is deployed on only one computing core.

### Claim 17 (depends on 16)

The neural network on-chip mapping apparatus based on the tabu search algorithm of claim 16, wherein the integer programming model is a mixed integer nonlinear programming model, an optimal solution xin,ig is obtained by using an extended cutting plane method, and the neuron groups in, ig satisfying a relationship: xin,ig=1 are found to obtain swapped positions of the computer cores of all K neuron groups.

### Claim 18 (depends on 10)

The computer-readable storage medium of claim 10, wherein, at step 1, the spiking neural network comprises synapses and connection structures with neuron groups as nodes, each of the neuron groups comprises a plurality of neurons, the topological structure is a graph data structure represented by nodes and edges or a network structure comprising size and shape information, and at the same time, the topological structure is configured to provide behavioral parameters of the neurons and connection parameters in synaptic connections; and
each of the computing cores is a hardware unit comprising a memory and a computing unit, and the acquiring the constraint information of the computing cores of the target machine network-on-chip comprises: acquiring sizes of memories of the computing cores, two-dimensional spatial position coordinates on the network-on-chip, and a connection between the computing cores.

### Claim 19 (depends on 18)

The computer-readable storage medium of claim 18, wherein step 2 further comprises:
converting a computing graph represented by neuron groups as nodes and synaptic connections as edges, and constructing a complete directed acyclic graph according to a model input node of the spiking neural network as a source, a model output node as a target, and directions of the synaptic connections as directed edges, which is called a network DAG;
then determining an order of the neuron groups for the DAG by using a topological sorting method, wherein the topological sorting method comprises: counting all node in-degrees in the DAG and maintaining a priority queue sorted in ascending order of the node in-degrees, popping a node in the priority queue, sequentially deleting the edges in the DAG with this node as output, updating in-degrees of the remaining nodes in the priority queue, and repeating the steps until the priority queue is empty; and
finally, marking an order in which nodes of the neuron group are popped from the priority queue as topological sorting corresponding to the nodes of the neuron group, wherein numbers of the topological sorting are topological numbers of all neurons in the neuron group.

### Claim 20 (depends on 19)

The neural network on-chip mapping apparatus based on the tabu search algorithm of claim 19, wherein step 3 further comprises: starting assignment from the pre-specified initial computing core according to acquired two-dimensional grid information of the network-on-chip, wherein, when not specified, the computing core at an upper left corner of a two-dimensional grid in the two-dimensional grid information is used as the initial computing core; and
sequentially assigning the neuron sequences in clusters to the computing nodes according to the topological numbers, counting a quantity of synaptic connections between a current neuron group and a neuron group assigned by the network-on-chip, sequentially trying to use all available unassigned computing core resources of the network-on-chip to calculate local cost functions, respectively, and selecting, by using the nearest neighbor algorithm, the computing core of the network-on-chip with a minimum cost as a target core next assigned;
wherein, prior to assignment of all neurons in one neuron group, since all neurons have a same topological number, node in-degrees of all the neurons are counted, and assignment is performed sequentially in descending order of the node in-degrees of the neurons until a memory of a current computing core is full or all the neurons of the neuron group are assigned; when remaining neurons are still unassigned, the remaining neurons are classified into a new neuron group and assigned; and after all neurons are assigned, a corresponding relationship between the topological numbers of the neurons and the computing cores is returned as the constructed initial solution of mapping; and
at the same time, all the neurons in each computing core reconstitute a new neuron group, and a new DAG with the neuron group as a node is generated, which is called a physical DAG.
