US7146590B1ExpiredUtility
Congestion estimation for programmable logic devices
Est. expiryAug 27, 2024(expired)· nominal 20-yr term from priority
Inventors:Kamal Chaudhary
G06F 30/394
66
PatentIndex Score
10
Cited by
2
References
25
Claims
Abstract
A method of estimating congestion for a programmable logic device can include calculating a number of fan-in paths for each resource in the programmable logic device and calculating a number of fan-out paths for each resource in the programmable logic device. For each resource of the programmable logic device, a number of paths having different path characteristics can be determined and a probability can be assigned thereto. One or more measures of congestion can be computed according to the determining step.
Claims
exact text as granted — not AI-modified1. A method of estimating congestion for a programmable logic device comprising the steps:
calculating a number of fan-in paths for each routing resource in the programmable logic device;
calculating a number of fan-out paths for each routing resource in the programmable logic device;
for each routing resource of the programmable logic device, determining a number of paths having different path characteristics and assigning a probability thereto; and
computing at least one measure of congestion according to said determining step.
2. The method of claim 1 , said step of calculating a number of fan-in paths comprising sorting the routing resources from a source to a load in a forward pass.
3. The method of claim 2 , wherein said step of calculating a number of fan-in paths is performed according to
faninpaths
c
(
i
,
k
)
=
∑
j
∈
fanin
of
i
faninpaths
c
(
j
,
k
-
1
)
.
4. The method of claim 1 , said step of calculating a number of fan-out paths comprising sorting the routing resources from a load to a source in a backward pass.
5. The method of claim 4 , wherein said step of calculating a number of fan-out paths is performed according to
fanoutpaths
c
(
i
,
k
)
=
∑
j
∈
fanout
of
i
fanoutpaths
c
(
j
,
k
-
1
)
.
6. The method of claim 1 , wherein the path characteristics are selected from a group consisting of a number of programmable interconnect points and path delay.
7. The method of claim 6 , wherein said step of determining a number of paths is performed according to
#
paths
c
(
i
,
k
)
=
∑
j
=
0
k
#
faninpaths
c
(
i
,
k
-
j
)
×
#
fanoutpaths
c
(
i
,
j
)
.
8. The method of claim 1 , said step of computing at least one measure of congestion comprising calculating the at least one measure of congestion for at least one routing resource.
9. The method of claim 8 , wherein a measure of congestion is calculated for each routing resource of the programmable logic device, said method further comprising summing the measures of congestion for the routing resources to determine an overall measure of congestion for the programmable logic device.
10. A computer automated system for estimating congestion for a programmable logic device, said computer automated system comprising:
means for calculating a number of fan-in paths for each routing resource in the programmable logic device;
means for calculating a number of fan-out paths for each routing resource in the programmable logic device;
means for determining a number of paths having different path characteristics and assigning a probability thereto for each routing resource of the programmable logic device; and
means for computing at least one measure of congestion according to operation of said means for determining.
11. The computer automated system of claim 10 , said means for calculating a number of fan-in paths comprising means for sorting the routing resources from a source to a load in a forward pass.
12. The computer automated system of claim 11 , wherein said means for calculating a number of fan-in paths operates according to
faninpaths
c
(
i
,
k
)
=
∑
j
∈
fanin
of
i
faninpaths
c
(
j
,
k
-
1
)
.
13. The computer automated system of claim 10 , said means for calculating a number of fan-out paths comprising means for sorting the routing resources from a load to a source in a backward pass.
14. The computer automated system of claim 13 , wherein said means for calculating a number of fan-out paths operates according to
fanoutpaths
c
(
i
,
k
)
=
∑
j
∈
fanout
of
i
fanoutpaths
c
(
j
,
k
-
1
)
.
15. The computer automated system of claim 10 , wherein the path characteristics are selected from a group consisting of a number of programmable interconnect points and path delay.
16. The computer automated system of claim 15 , wherein said means for determining a number of paths is performed according to
#
paths
c
(
i
,
k
)
=
∑
j
=
0
k
#
faninpaths
c
(
i
,
k
-
j
)
×
#
fanoutpaths
c
(
i
,
j
)
.
17. A machine readable storage, having stored thereon a computer program having a plurality of code sections executable by a machine for causing the machine to perform steps of:
calculating a number of fan-in paths for each routing resource in a programmable logic device;
calculating a number of fan-out paths for each routing resource in the programmable logic device;
for each routing resource of the programmable logic device, determining a number of paths having different path characteristics and assigning a probability thereto; and
computing at least one measure of congestion according to said determining step.
18. The machine readable storage of claim 17 , said step of calculating a number of fan-in paths comprising sorting the routing resources from a source to a load in a forward pass.
19. The machine readable storage of claim 18 , wherein said step of calculating a number of fan-in paths is performed according to
faninpaths
c
(
i
,
k
)
=
∑
j
∈
fanin
of
i
faninpaths
c
(
j
,
k
-
1
)
.
20. The machine readable storage of claim 17 , said step of calculating a number of fan-out paths comprising sorting the routing resources from a load to a source in a backward pass.
21. The machine readable storage of claim 20 , wherein said step of calculating a number of fan-out paths is performed according to
fanoutpaths
c
(
i
,
k
)
=
∑
j
∈
fanout
of
i
fanoutpaths
c
(
j
,
k
-
1
)
.
22. The machine readable storage of claim 17 , wherein the path characteristics are selected from a group consisting of a number of programmable interconnect points and path delay.
23. The machine readable storage of claim 22 , wherein said step of determining a number of paths is performed according to
#
paths
c
(
i
,
k
)
=
∑
j
=
0
k
#
faninpaths
c
(
i
,
k
-
j
)
×
#
fanoutpaths
c
(
i
,
j
)
.
24. The machine readable storage of claim 17 , said step of computing at least one measure of congestion comprising calculating the at least one measure of congestion for at least one routing resource.
25. The machine readable storage of claim 24 , wherein a measure of congestion is calculated for each routing resource of the programmable logic device, said method further comprising summing the measures of congestion for the routing resources to determine an overall measure of congestion for the programmable logic device.Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.