US6199192B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for assigning signal routes via an interconnect-multiplexer in a PLD
Assignee: Xilinx Inc
•
Filing: 1998-03-06
•
Granted: 2001-03-06
•
Expires: 2018-03-06
Abstract
Abstract A system and method for routing signals to function blocks of a programmable logic device (PLD) via an interconnect multiplexer (XMUX). All available paths from an interconnect multiplexer input resource to an interconnect multiplexer output resource are first identified. Signals are assigned to XMUX paths in order of number of fanouts to function blocks. The signal required by the most function blocks is assigned first. The costs of the XMUX paths relative to the signal to be assigned are determined, and the signal is assigned to the path having the least cost. The process is repeated until all the signals are assigned. A recovery method uses augmenting paths to assign signals if all the signals could not be assigned using least cost paths assignment.
Inventors
- 👤 Jose M. Marquez
- 👤 Hua Xue
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 22:14
CPC Classifications
H; H03; H03K; H03K19/00; H03K19/02; H03K19/173; H03K19/177; H03K19/17736; G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
164 words
A method for assigning signals required by function blocks of a programmable integrated circuit to interconnect multiplexer input resources and assigning the interconnect multiplexer input resources to interconnect multiplexer output resources, comprising the steps of: (a) identifying all available paths from an interconnect multiplexer input resource to an interconnect multiplexer output resource; (b) determining a signal that has a greatest number of function blocks that require the signal and that is not assigned to a path, and determining a cost of each path not having an assigned signal, wherein the cost of a path for one of the function blocks that requires the signal is a function of a number of other output resources that are available for other input resources that are mapped to the output resource of the path for the one function block: (c) selecting a path having the least cost; (d) assigning the signal to the path selected; and (e) repeating steps (b)-(d) until all the signals have been assigned.
Claim 2
Independent Claim
164 words
A method for assigning signals required by function blocks of a programmable integrated circuit to interconnect multiplexer input resources and assigning the interconnect multiplexer input resources to interconnect multiplexer output resources, comprising the steps of: (a) identifying all available paths from an interconnect multiplexer input resource to an interconnect multiplexer output resource; (b) determining a signal that has a greatest number of function blocks that require the signal and that is not assigned to a path, and determining a cost of each path not having an assigned signal, wherein the cost of a path for one of the function blocks that requires the signal is a function of a number of other output resources that are available for other input resources that are mapped to the output resource of the path for the one function block: (c) selecting a path having the least cost; (d) assigning the signal to the path selected; and (e) repeating steps (b)-(d) until all the signals have been assigned.
Claim 3
Dependent Claim
23 words
The method of claim 1 , further comprising the step of sorting the signals by numbers of function blocks which require the signals.
Claim 4
Dependent Claim
40 words
The method of claim 2 , further comprising the steps of: removing from consideration for assignment alternative paths for input resource of the path selected; and removing from consideration for assignment conflicting paths for output resource of the path selected.
Claim 5
Dependent Claim
79 words
The method of claim 1 , wherein for n inputs, x 1 , x 2 , . . . , x n , mapped to an output resource, y, the cost of the path for the one function block is a function of: ∑ j = 1 j = n 1 total alternative outputs for x j in one function block .
Claim 6
Dependent Claim
52 words
The method of claim 1 , wherein the cost of a path for the one function block is a function of a number of output resources that are available for the other input resources that are mapped to the output resource of the path for other function blocks that require the signal.
Claim 7
Dependent Claim
87 words
The method of claim 5 , wherein for n inputs x 1 , x 2 , . . . , x n , mapped to an output resource y, the cost of the path for the one function block is a function of: ∑ j = 1 j = n 1 total outputs for x j in other function blocks that require the signal .
Claim 8
Dependent Claim
197 words
The method of claim 1 , further comprising the steps of: (f) selecting an unassigned input resource to create a tree-type data structure having as a root the unassigned input resource; (g) adding to the tree output resources that are connectable to the unassigned input resource; (h) adding below a lowest level of the tree, input resources that are assigned to the output resources; (i) adding below a lowest level of the tree, output resources that are connectable to corresponding input resources; (j) if an output resource at a lowest level of the tree is not assigned to an input resource, then in an augmenting path that begins with the unassigned input resource at the root and ends at the output resource at the lowest level of the tree, reassigning input resources to neighboring output resources to create an alternating path of input resources assigned to output resources, assigning an unassigned signal to one of the input resources assigned to output resources in the alternating path, and reassigning signals of the augmenting path to inputs assigned to output resources in the alternating path; (k) repeating steps (f)-(j) until all the signals are assigned to interconnect multiplexer paths.
Claim 9
Dependent Claim
48 words
The method of claim 7 , further comprising the step of repeating steps (h)-(i) until either there are no remaining input resources and output resources to add to the tree or an output resource at a lowest level of the tree is not assigned to an input resource.
Claim 10
Dependent Claim
50 words
The method of claim 8 , further comprising the step of: indicating a failure if there are no remaining input resources and output resources to add to the tree and there is no output resource at a lowest level of the tree that is not assigned to an input resource.
Claim 11
Independent Claim
212 words
A method for assigning signals required by function blocks of a programmable circuit to interconnect multiplexer input resources assigning the interconnect multiplexer input resources to interconnect multiplexer output resources, comprising the steps of: (a) identifying all available paths from an interconnect multiplexer input resource to an interconnect multiplexer output resource; (b) sorting the signals by numbers of function blocks which require the signals, the sorting involving determining a signal that has a greatest number of function blocks that require the signal and that is not assigned to a path, and determining a cost of each path not having an assigned signal, wherein the cost of a path for one function block is a function of a number of output resources that are available for the other input resources that are mapped to the output resource of the path for other function blocks that require the signal; (c) selecting a path having the least cost the selecting involving: 1) removing from consideration for signal assignment alternative paths for the input resource of the path selected, and 2) removing from consideration for signal assignment conflicting paths for the output resource of the path selected: (d) assigning the signal to the path selected; and (e) repeating steps (b)-(d) until all the signals have been assigned.
Claim 12
Independent Claim
212 words
A method for assigning signals required by function blocks of a programmable circuit to interconnect multiplexer input resources assigning the interconnect multiplexer input resources to interconnect multiplexer output resources, comprising the steps of: (a) identifying all available paths from an interconnect multiplexer input resource to an interconnect multiplexer output resource; (b) sorting the signals by numbers of function blocks which require the signals, the sorting involving determining a signal that has a greatest number of function blocks that require the signal and that is not assigned to a path, and determining a cost of each path not having an assigned signal, wherein the cost of a path for one function block is a function of a number of output resources that are available for the other input resources that are mapped to the output resource of the path for other function blocks that require the signal; (c) selecting a path having the least cost the selecting involving: 1) removing from consideration for signal assignment alternative paths for the input resource of the path selected, and 2) removing from consideration for signal assignment conflicting paths for the output resource of the path selected: (d) assigning the signal to the path selected; and (e) repeating steps (b)-(d) until all the signals have been assigned.
Claim 13
Dependent Claim
95 words
The method of claim 10 , wherein for an input resource i and an output resource o, where n inputs, x 1 , x 2 , . . . , x n , are mapped to o, the cost of the path for the one function block is a function of: ∑ j = 1 j = n 1 total outputs for x j in other function blocks that require the signal .
Claim 14
Independent Claim
173 words
An apparatus for assigning signals required by function blocks of a programmable integrated circuit to interconnect multiplexer input resources and assigning the interconnect multiplexer input resources to interconnect multiplexer output resources, comprising: means for identifying all available paths from an interconnect multiplexer input resource to an interconnect multiplexer output resource; for a signal that has a greatest fanout to function blocks and that is not assigned to a path, means for determining a cost of each path not in use, wherein the cost of a path for one of the function blocks that requires the signal is a function of a number of other output resources that are available for other input resources that are mapped to the output resource of the one path for the one function means for selecting a path having the least cost; means for assigning the signal to the path selected; and means for repeating determination of the cost of each path, selection of a path, and assignment of a signal until all the signals have been assigned.
Claim 15
Independent Claim
173 words
An apparatus for assigning signals required by function blocks of a programmable integrated circuit to interconnect multiplexer input resources and assigning the interconnect multiplexer input resources to interconnect multiplexer output resources, comprising: means for identifying all available paths from an interconnect multiplexer input resource to an interconnect multiplexer output resource; for a signal that has a greatest fanout to function blocks and that is not assigned to a path, means for determining a cost of each path not in use, wherein the cost of a path for one of the function blocks that requires the signal is a function of a number of other output resources that are available for other input resources that are mapped to the output resource of the one path for the one function means for selecting a path having the least cost; means for assigning the signal to the path selected; and means for repeating determination of the cost of each path, selection of a path, and assignment of a signal until all the signals have been assigned.
Claim 16
Dependent Claim
22 words
The apparatus of claim 12 , further comprising means for sorting the signals by numbers of function blocks which require the signals.
Claim 17
Dependent Claim
41 words
The apparatus of claim 13 , further comprising: means for removing from consideration for assignment alternative paths for input resource of the path selected; and means for removing from consideration for assignment conflicting paths for output resource of the path selected.
Claim 18
Dependent Claim
79 words
The apparatus of claim 13 , wherein for n inputs, x 1 , x 2 , . . . , x n , mapped to an output resource, y, the cost of the path for the one function block is a function of: ∑ j = 1 j = n 1 total alternative outputs for x j in one function block .
Claim 19
Dependent Claim
52 words
The apparatus of claim 13 , wherein the cost of a path for the one function block is a function of a number of output resources that are available for the other input resources that are mapped to the output resource of the path for other function blocks that require the signal.
Claim 20
Dependent Claim
86 words
The apparatus of claim 16 , wherein for n inputs, x 1 , x 2 , . . . , x n mapped to an output resource, y, the cost of the path for the one function block is a function of: ∑ j = 1 j = n 1 total outputs for x j in other function blocks that require the signal .
Claim 21
Dependent Claim
250 words
The apparatus of claim 12 , further comprising: means for selecting an unassigned input resource to create a tree-type data structure having as a root the unassigned input resource; means for adding to the tree output resources that are connectable to the unassigned input resource; means for adding below a lowest level of the tree, input resources that are assigned to the output resources; means for adding below a lowest level of the tree, output resources that are connectable to corresponding input resources; means for reassigning input resources to neighboring output resources to create an alternating path of input resources assigned to output resources in an augmenting path that begins with the unassigned input resource at the root and ends at the output resource at the lowest level of the tree, if an output resource at a lowest level of the tree is not assigned to an input resource; means for assigning an unassigned signal to one of the input resources assigned to output resources in the alternating path, if an output resource at a lowest level of the tree is not assigned to an input resource; means for reassigning signals of the augmenting path to inputs assigned to output resources in the alternating path, if an output resource at a lowest level of the tree is not assigned to an input resource; and means for repeating selection of unassigned inputs, construction of trees having alternating paths, and reassigning signals until all the signals are assigned to interconnect multiplexer paths.
Claim 22
Independent Claim
176 words
An apparatus for assigning signals required by function blocks of a programmable integrated circuit to interconnect multiplexer input resources and assigning the interconnect multiplexer input resources, to interconnect multiplexer output resources, comprising: means for identifying all available paths from an interconnect multiplexer input resource to an interconnect multiplexer output resource; for a signal that has a greatest fanout to function blocks and that is not assigned to a path, means for determining a cost of each path not in use, wherein the cost of a path for one of the function blocks that requires the signal is a function of a number of output resources that are available for the other input resources that are mapped to the output resource of the path for other function blocks that require the signal; means for selecting a path having the least cost; means for assigning the signal to the path selected; and means for repeating determination of the cost of each path, selection of a path, and assignment of a signal until all the signals have been assigned.
Claim 23
Independent Claim
176 words
An apparatus for assigning signals required by function blocks of a programmable integrated circuit to interconnect multiplexer input resources and assigning the interconnect multiplexer input resources, to interconnect multiplexer output resources, comprising: means for identifying all available paths from an interconnect multiplexer input resource to an interconnect multiplexer output resource; for a signal that has a greatest fanout to function blocks and that is not assigned to a path, means for determining a cost of each path not in use, wherein the cost of a path for one of the function blocks that requires the signal is a function of a number of output resources that are available for the other input resources that are mapped to the output resource of the path for other function blocks that require the signal; means for selecting a path having the least cost; means for assigning the signal to the path selected; and means for repeating determination of the cost of each path, selection of a path, and assignment of a signal until all the signals have been assigned.
Claim 24
Dependent Claim
87 words
The apparatus of claim 19 , wherein for n inputs, x 1 , x 2 , . . . , x n , an output resource, y, mapped to the cost of the path for the one function block is a function of: ∑ j = 1 j = n 1 total outputs for x j in other function blocks that require the signal .
Claim 25
Dependent Claim
177 words
A computer readable medium comprising instructions for causing a computer to assign signals required by function blocks of a programmable integrated circuit to interconnect multiplexer input resources and assign the interconnect multiplexer input resources to interconnect multiplexer output resources, the instructions for causing the computer to perform the steps of: (a) identifying all available paths from an interconnect multiplexer input resource to an interconnect multiplexer output resource; (b) for a signal that has a greatest number of function blocks that require the signal and that is not assigned to a path, determining a cost of each path not having an assigned signal, wherein the cost of a path for one of the function blocks is a function of a number of other output resources that are available for other input resources, the other input resources being mapped to the output resource of the path for the one function block; (c) selecting a path having the least cost; (d) assigning the signal to the path selected; and (e) repeating steps (b)-(d) until all the signals have been assigned.
Claim 26
Dependent Claim
177 words
A computer readable medium comprising instructions for causing a computer to assign signals required by function blocks of a programmable integrated circuit to interconnect multiplexer input resources and assign the interconnect multiplexer input resources to interconnect multiplexer output resources, the instructions for causing the computer to perform the steps of: (a) identifying all available paths from an interconnect multiplexer input resource to an interconnect multiplexer output resource; (b) for a signal that has a greatest number of function blocks that require the signal and that is not assigned to a path, determining a cost of each path not having an assigned signal, wherein the cost of a path for one of the function blocks is a function of a number of other output resources that are available for other input resources, the other input resources being mapped to the output resource of the path for the one function block; (c) selecting a path having the least cost; (d) assigning the signal to the path selected; and (e) repeating steps (b)-(d) until all the signals have been assigned.
Claim 27
Independent Claim
200 words
A method for assigning a plurality of signals to paths within the programmable logic device, the programmable logic device including an interconnect multiplexer and a plurality of function blocks, each of the paths being a path from an interconnect multiplexer input to an interconnect multiplexer output, the method comprising the steps of: (a) viewing all function blocks of the programmable logic device and determining a signal of the plurality of signals that has a greatest number of function blocks that require the signal and that is not assigned to a path; (b) for the signal determined in (a), determining a cost of each path that the signal can be routed on but that does not have an assigned signal, wherein the cost of a path for one of the function blocks is a function of a number of other output resources that are available for other input resources, the other input resources being mapped to the output resource of the path for the one function block; (c) selecting the path in (b) having the least cost; (d) assigning the signal to the path selected in (c); and (e) repeating steps (a)-(d) until all the plurality of signals have been assigned.
Claim 28
Independent Claim
200 words
A method for assigning a plurality of signals to paths within the programmable logic device, the programmable logic device including an interconnect multiplexer and a plurality of function blocks, each of the paths being a path from an interconnect multiplexer input to an interconnect multiplexer output, the method comprising the steps of: (a) viewing all function blocks of the programmable logic device and determining a signal of the plurality of signals that has a greatest number of function blocks that require the signal and that is not assigned to a path; (b) for the signal determined in (a), determining a cost of each path that the signal can be routed on but that does not have an assigned signal, wherein the cost of a path for one of the function blocks is a function of a number of other output resources that are available for other input resources, the other input resources being mapped to the output resource of the path for the one function block; (c) selecting the path in (b) having the least cost; (d) assigning the signal to the path selected in (c); and (e) repeating steps (a)-(d) until all the plurality of signals have been assigned.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-03-05 | 2004-09-04 | 2005-03-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-03-05 | 2008-09-04 | 2009-03-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-03-05 | 2012-09-04 | 2013-03-06 | $7700.00 | Window Closed / Lapsed |