Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
2005-04-05
2005-04-05
Harvey, Jack B. (Department: 2143)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C709S239000, C709S240000, C709S241000, C709S242000, C709S243000, C709S244000, 37
Reexamination Certificate
active
06877040
ABSTRACT:
A method and apparatus for determining routing feasibility of a plurality of nets. Each net has an associated set of one or more routing solutions, wherein each solution specifies one or more routing resources consumed by the net. A liveness Boolean function is generated having variables that represent respective net/solution pairs. If there exists a set of values for the variables such that at least one of the variables for each net is logically true, then the liveness function is true. An exclusivity function is generated using the variables that represent the net/solution pairs. If there exists at least one set of values for the variables such that no resource is used is by more than a predetermined number of nets, then the exclusivity function is true. The nets are routable using the provided solutions if there is one set of values for the variables such that both the liveness and exclusivity functions are true.
REFERENCES:
patent: 6038392 (2000-03-01), Ashar et al.
patent: 6292916 (2001-09-01), Abramovici et al.
patent: 6308299 (2001-10-01), Burch et al.
patent: 6415430 (2002-07-01), Ashar et al.
patent: 6442732 (2002-08-01), Abramovici et al.
patent: 6473884 (2002-10-01), Ganai et al.
R. Glenn Wood and Rob A. Rutenbar IEEE Transaction on (VLSI) systems, vol. 6, No2, Jun. 1998.*
Hung et al. [On segmented Channel Routability, IEEE 2002].*
Kao et al. [A Routability and Performance Driven ehnology Mapping Igorithm for LUT Based FPGA Designs, IEEE 1999].*
J. P. M. Silva and K. A. Sakallah, “GRASP—A New Search Algorithm for Satisfiability”, The University of Michigan, Computer Science and Engineering Division, Ann Arbor, Michigan CSE-TR-292-96, Apr. 10, 1996, pp. 79-87.
C. Y. Lee, “An Algorithm for Path Connections and its Applications,” IRE Transactions on Electronic Computers, vol. EC=10, 1961, pp. 346-365.
L. McMurchie and C. Ebeling, “PathFinder: A Negotiation-Based Performance-Driven Router for FPGAs,” Proc. ACM/SIGDA Int. Symposium on Field Programmable Gate Arrays, 1995, pp. 111-117.
Carl Ebeling et al., “Placement and Routing Tools for the Triptych FPGA,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 3, No. 4, Dec. 1995 pp. 473-482.
G.J. Nam et al., “Resource-Based FPGA Routability Checking Via Boolean Satisfiability,” available from Xilinx, Inc. 2100 Logic Drive, San Jose, CA 95124.
G.J. Nam et al., “Satisfiability-based FPGA Detailed Routing,” Proceedings of the International Conference on VLSI, Jan. 1999 India.
G.J. Nam et al., “Satisfiability-Based Layout Revisited: Detailed Routing of Complex FPGAs Via Search-Based Boolean SAT,” Proceedings ACM International Symposium on FPGAs, Feb. 1999.
R. Glenn Wood and Rob A. Rutenbar, “FPGA Routing and Routability Estimation Via Boolean Satisfiability,” Proceedings ACM International Symposium on FPGAs, Feb. 1997.
Anderson Jason H.
Jayaraman Rajeev
Kalman Sandor S.
Nag Sudip K.
Nam Gi-Joon
Harvey Jack B.
Kianersi Mitra
Liu Justin
Maunu LeRoy D.
Xilinx , Inc.
LandOfFree
Method and apparatus for testing routability 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 testing routability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for testing routability will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3417319