US2024143883A1PendingUtilityA1
Layout method and application of scalable multi-die network-on-chip fpga architecture
Est. expiryOct 14, 2042(~16.2 yrs left)· nominal 20-yr term from priority
G06F 30/347G06F 30/31Y02D10/00G06F 30/392G06F 30/34
50
PatentIndex Score
0
Cited by
0
References
0
Claims
Abstract
A layout method for a scalable multi-die network-on-chip FPGA architecture is provided. An application of the aforementioned layout method for the scalable multi-die network-on-chip FPGA architecture is further provided. A scalable multi-die FPGA architecture based on network-on-chip and a corresponding hierarchical recursive layout algorithm are provided, aiming to directly map a register transfer level dataflow design generated by existing high-level synthesis onto the provided interconnection architecture. The layout method can exploit the potential for hierarchical topology and make more efficient use of dedicated interconnection resources, such as cross-die nets, network-on-chips, and high-speed transceivers.
Claims
exact text as granted — not AI-modifiedWhat is claimed is:
1 . A layout method for a scalable multi-die network-on-chip field-programmable gate array (FPGA) architecture, wherein when a structure parameter is (), the FPGA architecture is a single die; when the structure parameter is (m), m is a positive integer, the FPGA architecture is that m single crystal dies are connected to one NoC router via an NoC, and the NoC router is referred to as a central router of the FPGA architecture; when the structure parameters are (m 1 , m 2 ), m 1 and m 2 are positive integers, and the FPGA architecture is that central routers of the m 2 (m 7) structure are connected to one NoC router via an NoC, and the NoC router is referred to as a central router of the FPGA architecture; when the structure parameter is (m 1 , . . . , m n ), m, . . . , m n are positive integers, the FPGA architecture is that central routers of m n (m 1 , . . . , m n−1 ) structures are connected to one NoC router via an NoC, the NoC router is referred to as a central router of the FPGA architecture, and the (m 1 , . . . , m n−1 ) structures are referred to as a secondary substructure;
a layout of the FPGA architecture comprises an integer linear programming problem and a hierarchical recursive layout algorithm based on the integer linear programming problem, wherein: the integer linear programming problem comprises the following steps: step 1: taking the FPGA architecture model as a graph G FPGA , G FPGA =(T m l , {tilde over (B)}, a(T * 0 )),{tilde over ( )}wherein T m l is an architecture topology, is a link bandwidth of each layer of NoC, and a(T * 0 ) is resource capacity of each die; and taking a dataflow design as graph G design , G design =(V, E, a(V), S(E), D(E), w(E)) , wherein V is a dataflow module, E is a dataflow queue, a(V) is an area of the dataflow module, S(E) is a start point of the dataflow queue, D(E) is an end point of the dataflow queue, and w(E) is a bitwidth of the dataflow queue; step 2: taking φ:V→T * 0 as a target layout, T * 0 represents a set of all dies, and an objective function dominated by a vertex is as follows:
arg
min
φ
:
V
→
T
*
0
∑
e
∈
E
w
(
e
)
d
m
(
φ
(
S
(
e
)
)
,
φ
(
D
(
e
)
)
)
wherein w(e) represents a dataflow queue bitwidth, d m (⋅, ⋅) represents a distance metric, S(e) represents a source module of the dataflow queue, φ(S(e)) represents a die corresponding to the source module of the dataflow queue, D(e) represents a drain module of the dataflow queue, and φ(D(e)) represents a die corresponding to the drain module of the dataflow queue;
step 3: encoding a linearized vertex space using a one-hot code, accordingly a linearized linear transformation φ of Φ, so that there is a linearized objective function as the objective function of the integer linear programming problem, as shown in the following formula:
arg
min
Φ
∑
e
∈
E
w
T
e
·
d
m
(
Φ
Se
,
Φ
De
)
wherein W T e represents a linear form of the dataflow queue bitwidth, Se represents a linear form of a queue source module, ΦSe represents a linear form of a die corresponding to the queue source module, De represents a linear form of a queue drain module, and ΦDe represents a linear form of a die corresponding to the queue drain module;
step 4: laying out each dataflow module on exactly 1 die, formalizing same as a constraint as shown in the following formula:
∑
x
∈
T
*
0
Φ
xv
=
1
,
∀
v
∈
V
wherein x represents a target die, v represents a dataflow module to be laid out, and Φ xv represents a layout decision variable which is 1 if the dataflow module x is allocated to a die v, otherwise 0;
step 5: making a total resource of the dataflow module on the same die not exceed a total resource of the die; and formalizing same as a constraint represented by the following formula:
∑
v
∈
V
a
(
v
)
Φ
xv
≤
a
(
x
)
,
∀
v
∈
V
,
∀
x
∈
T
*
0
wherein a(v) represents resource occupation of the dataflow module V, and a(x) represents resource capacity of the die x; and
step 6: providing, by a user, a manual layout, and formalizing same as a constraint as shown in the following formula:
Φ v =φ M ( v ), ∀ v ϵ V M
wherein φ M (v) represents a manual allocation of a die corresponding to a dataflow module by the user, and V M represents a dataflow module for manually allocating a die by a design user;
the hierarchical recursive layout algorithm comprises the following steps:
step a: summarizing layout results of the dataflow module on the substructure of the FPGA topology T m l as V m,x n , as shown in the following two formulae:
V m,x n =V m,() l V ( n=l )
V m∂,x n {v ϵ V m,∂x n+1 |φ m,∂x n+1 ( v )= T m∂, x n } ( n≠l )
wherein V m,() l represents a top substructure, V m,x n represents an n level substructure of which a structure parameter is m and a position is x, m∂ represents a tuple m excluding a tail item, and ∂x represents a tuple x excluding a first item;
step b: defining a recursive layout operator ϕ:
ϕ( T m,x n , v ) ϕ(φ m,x n ( v ), v )
= . . . ϕ( T y 0 , v ), ∃ T y 0 ϵ T * 0 , ∀v ϵ V
wherein ϕ(T m,x n , v) represents a recursive layout of a module v calculated from the n level substructure, φ m,x n (v) represents a secondary layout of the module V on the n level substructure, and T y 0 represents a crystal die with position y; with φ(v) Φ(φ m,x n (v), v) , ∀v ϵ V, a solution of an original layout problem to φ is decomposed into a solution of a layout φ m,x n :V m,x n →T m,x n on the substructure;
step c: representing the objective function on the substructure instead using edge dominance as shown in the following formula:
arg
min
Φ
m
,
x
n
∑
e
∈
E
m
,
x
n
w
T
e
·
d
T
Ξ
e
wherein Φ m,x n represents a layout to be solved on the n substructure of which the structure parameter is m and the position is x , E m,x n represents a dataflow queue allocated to the n substructure of structure parameter m and position x, d represents a distance metric of the network-on-chip link, and Ξe represents the network-on-chip link corresponding to the dataflow queue on the n substructure; and
step d: establishing a constraint based on the following conditions when performing a layout:
a dataflow module is allocated to a secondary substructure on the substructure;
a dataflow queue is allocated to exactly one link of a current substructure central router and a secondary substructure central router on the substructure;
the allocation of the dataflow module is consistent with the allocation of the dataflow queue;
for a resource estimation of an i substructure, a congestion factor p i is introduced as a modification of Σ vϵV a(v)Φ xv ≤a(x), ∀v ϵ V, ∀x ϵ T * 0 , as shown in the following formula:
∑
v
∈
V
m
,
x
n
a
(
v
)
(
Φ
m
,
x
n
)
xv
≤
ρ
n
a
(
x
)
,
∀
x
∈
T
m
,
x
′
n
∀
a
∈
A
wherein A represents a resource type;
a dataflow module bit-width allocated to the link shall not exceed the link bandwidth;
the layout on the substructure coincides with the user's manual layout.
2 . The layout method for the scalable multi-die network-on-chip FPGA architecture according to claim 1 , wherein when the structure parameter is (), the FPGA architecture is represented by the following formula:
T
m
,
X
n
=
T
(
)
,
X
0
=
△
T
X
0
=
∑
i
=
1
n
∏
j
=
1
i
-
1
m
j
x
i
wherein x T m,x n represents the n substructure of which the structure parameter is m and the position is X, T (),X 0 represents a 0 substructure of which the structure parameter is () and the position is X, T X 0 represents a die of which the position is X, m j represents an item j of a total structure parameter, and x i represents an item i of a tuple X.
3 . The layout method for the scalable multi-die network-on-chip FPGA architecture according to claim 1 , wherein when the structure parameter is (m 1 , . . . , m n ), the FPGA architecture is represented by the following formula:
T m,X n {T m∂,(x,X) n−1 |0 ≤x<m n−1 , i ϵ + } wherein T m∂,(x,X) n−1 represents an n−1 substructure of which the structure parameter is m∂ and the position (x, X)), and x represents a relative position of the n−1 substructure in the current n substructure.
4 . A design method of a multi-die FPGA, comprising: using the layout method for the scalable multi-die network-on-chip FPGA architecture according to claim 1 to improve a scalability of the FPGA architecture and facilitate a scalable implementation of a matched electronic design automation (EDA) tool.Join the waitlist — get patent alerts
Track US2024143883A1 — get alerts on status changes and closely related new filings.
We store only your email — no account needed. See our privacy policy.