Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-03-06
2001-03-06
Teska, Kevin J. (Department: 2768)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06199192
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to assigning signal routes in a programmable logic device, and more particularly to assigning signal routes via an interconnect multiplexer in a programmable logic device.
BACKGROUND OF THE INVENTION
Programmable logic devices (PLDs) typically make use of one or more interconnect arrays that are programmed via an array of memory cells (e.g., EPROM, EEPROM Flash EPROM or Flash EEPROM cells) to make the various interconnections within the PLD that are specific to a desired design. Because advances in the art allow regular increases in the complexity of PLDs, the size of the programmable interconnect array must also be increased to achieve the desired PLD complexity.
Unfortunately, a problem exists in assigning signals to routes or paths provided by the programmable interconnect array in the PLD. U.S. Pat. No. 5,563,528, entitled, Multiplexer for Programmable Logic Device, to Diba et al., illustrates an example of a programmable interconnect array for which routing signals may be difficult. Specifically, an interconnect-multiplexer (XMUX) is used to direct signals to a plurality of function blocks in a PLD. The XMUX has multiple input resources, each of which is connectable to at least three output resources. Therefore, the problem is one of assigning the multiple signals that are required for various ones of the function blocks to the available input and output resources of the XMUX. A successful assignment requires that all the signals be assigned to paths provided by the XMUX, such that the functional blocks will receive the required signals.
A prior method for assigning signals to XMUX paths does so on a function block by function block basis. The method first orders function blocks by the number of input signals required by the function block. The function block requiring the most input signals is processed first. That is, signals required by this function block are assigned to XMUX paths first. Since the signals associated with the last function block to be processed will be the most difficult to assign to XMUX paths, it is desirable to save the function block needing the fewest signals until last.
If all of the signals required by one function block could not be assigned to paths of the XMUX, then a version of the Hungarian algorithm is applied to signals required by the function block such that signals are reassigned to different XMUX paths. The Hungarian algorithm is described in “Applied and Algorithmic Graph Theory” by Chartrand and Oellermann, McGraw Hill. If the Hungarian algorithm fails to assign all signals to paths of the XMUX for the function block, then the assignment process has failed. It will be appreciated that even though there may be a combination of assignments of signals to XMUX paths that results in all signals being assigned, present methods are not sophisticated enough to redo signal assignments between function blocks.
Therefore, while prior methods sometimes function effectively to assign signals to input/output resources of an interconnect array, they sometimes are unable to assign all signals, even though such a solution exists. A method that addresses the aforementioned problems is therefore desirable.
SUMMARY OF THE INVENTION
In a first embodiment of the invention, a method is provided for assigning signals required by function blocks of a programmable logic device to interconnect multiplexer input resources and assigning the interconnect multiplexer input resources to interconnect multiplexer output resources. The method comprises 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 fanout and that is not assigned to a path, determining the cost of each path not in use; (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.
An apparatus for assigning signals required by function blocks of a programmable logic device to interconnect multiplexer input resources and assigning the interconnect multiplexer input resources to interconnect multiplexer output resources is provided in another embodiment of the invention. The apparatus comprises: 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 and that is not assigned to a path, means for determining the cost of each path not in use; 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.
In another embodiment, a computer readable medium is provided that comprises instructions for causing a computer to assign signals required by function blocks of a programmable logic device to interconnect multiplexer input resources and assign the interconnect multiplexer input resources to interconnect multiplexer output resources. The instructions cause 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 fanout and not assigned to a path, determining the cost of each path not in use; (c) selecting a path having the least cost; (d) assigning the signal path selected; and (e) repeating steps (b)-(d) until all the signals have been assigned
The above summary of the present invention is not intended to describe each embodiment of the present invention. The figures and detailed description that follow provide additional example embodiments and aspects of the present invention.
REFERENCES:
patent: 5128871 (1992-07-01), Schmitz
patent: 5563528 (1996-10-01), Diba et al.
patent: 5648912 (1997-07-01), Narayanan et al.
patent: 5734592 (1998-03-01), Cox et al.
Diestel, R., “Graph Theory”, Springer-Verlag, New York, May 1997, pp. 4-6 May 1997.
Kelsen, P., “Fast Parallel Matching in Expander Graphs”, Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 293-299 Jul. 1993.
Balas, E., Miller, D., Pekny, J., and Toth, P., “A Parallel Shortest Augmenting Path Algorithm for the Assignment Problem”, Journal of the Association for Computing Machinery, vol. 38, No. 4, pp. Oct. 1991, 985-1004.
Gabow, H.N., and Tarjan, R.E., “Faster Scaling Algorithms for General Graph-Matching Problems”, Journal of the Association for Computing Machinery, vol. 38, No. 4, Oct. 1991, pp. 815-853.
Galil, Z., “Efficient Algorithms for Finding Maximum Matching in Graphs”, Computing Surveys, vol. 18, No. 1, Mar. 1986, pp. 23-38.
Osiakwan, C.N.K., and Akl, S.G., “A Perfect Speedup Parallel Algorithm for the Assignment Problem on Complete Weighted Bipartite Graphs”, International Conference on Databases, Parallel Architectures and Their Applications, Mar. 1990, pp. 293-301.
Demjanenko, M. and Upadhyaya, S.J., “Yield Enhancement of Field Programmable Logic Arrays by Inherent Component Redundancy”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 8, No. 8, Aug. 1990, pp. 876-884.
Yeung, K.L. and Yum, T.-S.P., “A Wavelength Concentrator for WDMA Networks”, IEEE Global Telecommunications Conference, Dec. 1993, pp. 144-148 vol. 1.
Efrat, A. and Itai, A., “Improvements on Bottleneck Matching and Related Problems Using Geometry”, Proceedings of the 12th Annual Symposium on Computational Geometry, May 1996, pp. 301-310.
Gary Chartrand and Ortrud R. Oellermann, “Applied and AlgorithmicGraphTheory”,Copyright1993by McGraw-Hill, Inc.; Chapter 6, pp. 161-177.
S. Brown et al., “Field-Programmable Gate Arrays”, Copyright 1992 by Kluwer Academic Publishers, pp. 132-145.
Marquez Jose M.
Xue Hua
Maunu LeRoy D.
Siek Vuthe
Teska Kevin J.
Wallace T. Lester
Xilinix, Inc.
LandOfFree
Method and apparatus for assigning signal routes via an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for assigning signal routes via an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for assigning signal routes via an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2483865