Method and apparatus for testing routability

Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFUS-PAI-O-3417319

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.