US 2026/0212104 A1 · FPGA-ORIENTED DSP PLACEMENT OPTIMIZATION METHOD FOR CNN ACCELERATORS

Abstract

An FPGA-oriented DSP placement optimization method for CNN accelerators includes the following steps: S1. DSP path information extraction: converting a designed netlist into a graph representation, and carrying out data-path DSP node identification and data-path DSP graph building; and S2. datapath-driven DSP placement: distributing data-path DSP nodes to specific positions on an FPGA according to an extracted data-path DSP graph. According to the invention, automated extraction and building of data-path DSP graphs are carried out by means of graph neural network (GCN)-based DSP node classification and min-cost flow (MCF) model optimization algorithms, and compact placement and cascade constraint optimization are used in combination, thereby greatly improving the timing performance and computing efficiency of the placement and also significantly improving the clock frequency and throughput. Therefore, the method provides a universal and efficient FPGA placement solution for multiple CNN accelerator architectures.

An field programmable gate array (FPGA)-oriented digital signal processing unit (DSP) placement optimization method for convolutional neural network (CNN) accelerators, comprising the following steps:

S1:
DSP path information extraction:
converting a design netlist into a graph representation, and carrying out datapath DSP node identification and datapath DSP graph building;
and
S2:
datapath-driven DSP placement:
allocating datapath DSP nodes to specific positions on an FPGA according to an extracted datapath DSP graph;
wherein
step S2 comprises:
S201:
transforming a datapath DSP node placement problem into a constrained optimization problem and modeling the datapath DSP placement problem:
setting that the datapath DSP graph comprises N datapath DSP nodes to be placed, mapping each datapath DSP node vi, i∈{1,2 . . . ,N}, to one of M DSP positions in the FPGA;
setting the coordinates of DSP position j as (px,j,py,j), j∈{1,2 . . . ,M};
introducing a binary decision variable xi, where j represents an allocation relationship:
x
i
,
j
=
{
1
,
if
⁢
datapath
⁢
DSP
⁢
node
⁢
i
⁢
is
⁢
assigned
⁢
to
⁢
DSP
⁢
position
⁢
j
0
,
datapath
⁢
DSP
⁢
node
⁢
i
⁢
is
⁢
not
⁢
assigned
⁢
to
⁢
DSP
⁢
position
⁢
j
giving basic hard constraints that must be met by a datapath DSP node placement:
single position constraint:
each datapath DSP node must be assigned to one position;
position uniqueness constraint:
each position can only be allocated with at most one datapath DSP node;
S202:
introducing cascade constraints for the datapath DSP nodes so that the datapath DSP nodes can be arranged in cascade form in the placement, in order to maintain compactness and directionality of a data link:
wherein datapath DSP nodes cascaded on the DSP graph must be arranged in adjacent positions in the same column;
a cascading relationship between multiple datapath DSP nodes is decomposed into cascading relationships between multiple DSP pairs;
the cascading relationship between DSP nodes in each pair is a cascade pair;
let C be a set of all cascade pairs, each cascade pair in the set C is denoted as (cp, cs), cp and cs represent predecessor and successor nodes respectively, the following constraint needs to be satisfied:
cp and cs are adjacent in placement to ensure continuity and efficiency of signaling;
that is, the following constraint needs to be satisfied:
x
cp
,
j
=
x
cs
,
j
+
1
,
∀
(
c
p
,
c
s
)
∈
C
where xcp,j represents a binary decision variable of predecessor cp at DSP position j, and xcs, j+1 represents a binary decision variable of successor cs at DSP position j+1;
S203:
incorporating a cascade constraint and a datapath constraint into an overall optimization goal and transforming the constraints into soft constraints so as to build a model in a unified manner because in DSP placement, the cascade constraint needs to be met, and further optimization is also required for the characteristics of datapaths to improve placement compactness and timing performance:
wherein an overall mathematical model combines the directionality and placement compactness of datapaths and is expressed as follows:
min
x
i
,
j
∑
e
⁢
□ε
(
x
e
p
-
x
e
s
)
T
⁢
(
p
x
⁢
p
x
T
+
p
y
⁢
p
y
T
)
⁢
(
x
e
p
-
x
e
s
)
+
λ
⁢
∑
e
D
⁢
□
⁢
ε
D
(
cos
⁢
θ
e
D
⁢
p
-
cos
⁢
θ
e
D
⁢
s
)
+
η
⁢
∑
(
c
p
,
c
s
)
⁢
□
⁢
C
∑
j
=
1
M
-
1
(
x
c
p
,
j
-
x
c
s
,
j
+
1
)
2
,
s
.
t
.
∑
j
=
1
M
⁢
x
i
,
j
=
1
,
∑
i
=
1
N
⁢
x
i
,
j
≤
1
,
x
i
,
j
∈
{
0
,
1
}
;
(
1
)
where ε represents an edge set of any datapath DSP nodes and other component nodes respectively connected to the datapath DSP nodes in a directed graph after netlist conversion, e is an edge in ε, and εD represents an edge set in the datapath DSP graph, and eD is an edge in εD;
ep and es represent the predecessor node and successor node of edge e respectively, xep and xes represent assignment variables of the predecessor node and successor node respectively and are both vectors of length S;
S represents the number of placement positions of all components on the FPGA;
if ep is assigned to position p, then in xep, element p is 1 and the remaining elements are 0;
if es is assigned to position q, then in xes the element p is 1 and the remaining elements are 0, where p=1, 2, . . . , S;
q=1, 2, . . . , S, and p is not equal to q;
px is a vector composed of the x coordinates of the placement positions of all components on the FPGA;
py is a vector composed of the y coordinates of the placement positions of all components on the FPGA;
since the number of placement positions is S, the lengths of px and py are both S;
the superscript T represents transposition, and
(
p
x
⁢
p
x
T
+
p
y
⁢
p
y
T
)
constitutes a distance matrix;
xep-xes represents a difference vector between vectors xep and xes;
in the difference vector, one element is 1, one element is −1, and other elements are 0;
the positions of element “1” and element “−1” represent the positions of the predecessor and successor nodes;
θeDp represents an angle between a line from the predecessor node eDp of edge eD to an ARM core in the FPGA and a horizontal line;
θeDs represents an angle between a line from the successor node eDs of edge eD to the ARM core in the FPGA and the horizontal line;
wherein the ARM core is located in the lower left corner of the FPGA by default;
λ is a super parameter, and η is a penalty factor;
hard constraints directly limit the legitimacy of placement variable xi,j to ensure that the resource allocation of DSP nodes on the FPGA meets basic rules:
single position constraint:
each datapath DSP node i must and can only be assigned to one position j, that is:
∑
j
=
1
M
x
i
,
j
=
1
,
∀
i
∈
{
1
,
2
,
…
,
N
}
this constraint ensures that each datapath DSP node does not occupy multiple positions repeatedly;
resource restriction constraint:
each position j can only accommodate at most one datapath DSP node;
the resource restriction constraint is expressed as:
∑
i
=
1
N
x
i
,
j
≤
1
,
∀
j
∈
{
1
,
2
,
…
,
M
}
this constraint ensures reasonable use of limited resources on the FPGA and avoids resource conflicts;
variable legitimacy constraint:
xi,j is a binary variable, indicating whether a datapath DSP node i is assigned to a position j;
that is:
x
i
,
j
∈
{
0
,
1
}
,
∀
i
∈
{
1
,
2
,
…
,
N
}
,
∀
j
∈
{
1
,
2
,
…
,
M
}
S204:
three penalty terms in an objective function together constituting soft constraints, wherein these constraints achieve flexible placement adjustments based on weight parameters of the optimization process:
distance constraint for a datapath DSP node and other components connected to the node:
∑
e
⁢
□ε
(
x
e
p
-
x
e
s
)
T
⁢
(
p
x
⁢
p
x
T
+
p
y
⁢
p
y
T
)
⁢
(
x
e
p
-
x
e
s
)
this term represents the sum of the squares of distances between a DSP node in a path and other component nodes connected to the node, with an optimization goal being to minimize the length of the datapath to reduce wiring delay and wiring complexity;
datapath directionality constraint:
λ
⁢
∑
e
D
⁢
□
⁢
ε
D
(
cos
⁢
θ
e
D
⁢
p
-
cos
⁢
θ
e
D
⁢
s
)
this term is measured by the difference in direction cosine value, with an optimization goal being to maintain the directionality of the datapath and avoid path detours;
λ is used to adjust the intensity of the directionality optimization;
cascade constraint:
η
⁢
∑
(
c
p
,
c
s
)
⁢
□
⁢
C
∑
j
=
1
M
-
1
(
x
c
p
,
j
-
x
c
s
,
j
+
1
)
2
,
where C is a set of all cascade pairs, xcp,j represents a binary decision variable of predecessor node cp at DSP position j, and xcs, j+1 represents a binary decision variable of successor node cs at DSP position j+1;
this term ensures the close arrangement of cascaded DSP nodes in physical positions, and the weight parameter η controls the priority of cascade constraints in the overall optimization;
and
S205:
solving the built mathematical model of the optimization problem.

504 more elements

Fpga-oriented dsp placement optimization method for cnn accelerators

Life of this patent

Fpga-oriented dsp placement optimization method for cnn accelerators

Life of this patent

Abstract

Claims7