Electronic digital logic circuitry – Multifunctional or programmable – Array
Reexamination Certificate
2003-01-31
2008-03-11
Barnie, Rexford (Department: 2819)
Electronic digital logic circuitry
Multifunctional or programmable
Array
C326S037000, C326S038000, C326S039000, C326S047000, C716S030000
Reexamination Certificate
active
07342414
ABSTRACT:
A fast router and a fast hardware-assisted routing method are disclosed in a network having endpoints, switches and interconnect links. The switches are programmable to allow endpoints to be connected through a particular configuration of switches. The switches also comprise: propagation circuitry which allows a search signal to be propagated through the network; allocation circuitry to set the configuration of switches once a path has been found; and deallocation circuitry to clear a configuration of switches once no path has been found.
REFERENCES:
patent: 3654615 (1972-04-01), Freitag
patent: 5144563 (1992-09-01), Date et al.
patent: 5200908 (1993-04-01), Date et al.
patent: 5465218 (1995-11-01), Handa
patent: 5495419 (1996-02-01), Rostoker et al.
patent: 5638292 (1997-06-01), Ueda
patent: 5744979 (1998-04-01), Goetting
patent: 5796625 (1998-08-01), Scepanovic et al.
patent: 5815403 (1998-09-01), Jones et al.
patent: 5824570 (1998-10-01), Aoki et al.
patent: 5943486 (1999-08-01), Fukui et al.
patent: 6074428 (2000-06-01), Petler
patent: 6080204 (2000-06-01), Mendel
patent: 6150877 (2000-11-01), Morikawa
patent: 6155725 (2000-12-01), Scepanovic et al.
patent: 6243851 (2001-06-01), Hwang et al.
patent: 6292929 (2001-09-01), Scepanovic et al.
patent: 6323678 (2001-11-01), Azegami
patent: 6330707 (2001-12-01), Shinomiya et al.
patent: 6405299 (2002-06-01), Vorbach et al.
patent: 6683872 (2004-01-01), Saito et al.
patent: 6687893 (2004-02-01), Teig et al.
patent: 6961782 (2005-11-01), Denneau et al.
patent: 7010667 (2006-03-01), Vorbach et al.
patent: 7171635 (2007-01-01), Teig et al.
patent: 2003/0066043 (2003-04-01), Teig et al.
patent: 2004/0139413 (2004-07-01), DeHon et al.
patent: 2005/0035783 (2005-02-01), Wang
patent: 2005/0063373 (2005-03-01), DeHon et al.
patent: 2006/0087342 (2006-04-01), Ayodhyawasi et al.
patent: 2007/0067750 (2007-03-01), Amit et al.
patent: 98/35294 (1998-08-01), None
Chan, P.K., et al., “Acceleration of an FPGA Router,”Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, IEEE, pp. 175-181 (Apr. 1997).
Chan, P.K., et al., “New Parallelization and Convergence Results for NC: A Negotiation-Based FPGA Router,”Proceedings of the 2000 International Symposium on Field-Programmable Gate Arrays(FPGA '00),ACM/SIGDA, pp. 165-174 (Feb. 2000).
DeHon, A., “Entropy, Counting and Programmable Interconnect,”FPGA '96, ACM-SIGDA Fourth International Symposium on FPGAs, Monterrey CA, Fig. 2, (Feb. 11-13, 1996).
DeHon, A., “Rent's Rule Based Switching Requirements, System Level Interconnect Prediction,”SLIP 2001, pp. 197-204 (Mar. 31-Apr. 1, 2001).
Henry, D.S., et al., “Cyclic Segmented Parallel Prefix,”Ultrascalar Memo 1, Yale (Nov. 1998).
Iosupovici, A., “A Class of Array Architectures for Hardware Grid Routers,”IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. CAD-5, No. 2, pp. 245-255 (Apr. 1986).
Landman, B.S., et al., “On Pin Versus Block Relationship for Partitions of Logic Graphs,”IEEE Transactions on Computers, vol. C-20, No. 12, pp. 1469-1479 (1971), month n/a.
Leiserson, C.E., “Fat Trees: Universal Networks for Hardware-Efficient Supercomputing,”IEEE Transactions on Computers, vol. C-34, No. 10, pp. 892-901 (Oct. 1985).
McMurchie, L., et al., “PathFinder: A Negotiation-Based Performance-Driven Router for FPGAs,”Proceedings of the ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, ACM, pp. 111-117 (Feb. 1995).
Ryan, T., et al., “An ISMA Lee Router Accelerator,”IEEE Design and Test of Computers, pp. 38-45 (Oct. 1987).
Swartz, J.S., et al., “A Fast Routability-Driven Router for FPGAs,”Proceedings of the 1998 International Symposium on Field-Programmable Gate Arrays(FPGA '98), pp. 140-149 (Feb. 1998).
Tessier, R., “Negotiated A* Routing for FPGAs,”Proceedings of the 5th Canadian Workshop on Field Programmable Devices, (Jun. 1998).
Tsu, W., et al., “HSRA: High-Speed, Hierarchical Synchronous Reconfigurable Array,”Proceedings of the International Symposium on Field Programmable Gate Arrays, pp. 1-10 (Feb. 1999).
“SS7 Tutorial,”Performance Technologies, INTERNET: <http://www.pt.com/tutorials/ss7>, pp. 1-23 (Aug. 22, 2001).
Chong, F., et al., “METRO: A Router Architecture for High-Performance, Short-Haul Routing Networks,”Proceedings of the Annual International Symposium on Computer Architecture, Chicago, IEEE, vol. SYMP. 21, pp. 266-277 (Apr. 18-21, 1994).
Alfke, P., “Efficient Shift Registers, LFSR Counters, and Long Psuedo-Random Sequence Generators,”Xilinx Application Note, XAPP 052, INTERNET: <http://www.xilinx.com/xapp203.pdf> pp. 1-6 (Jul. 7, 1996).
Arora, S., et al., “On-Line Algorithms For Path Selection In a Nonblocking Network,”SIAM Journal on Computing, vol. 25, No. 3, pp. 1-25 (Jun. 1996).
Banerjee, P., et al., “A Parallel Simulated Annealing Algorithm for Standard Cell Placement on a Hypercube Computer,”IEEE International Conference on Computer-Aided Design, pp. 34-37 (1986).
Banerjee, P., et al., “Parallel Simulated Annealing Algorithms for Cell Placement on Hypercube Multiprocessors,”IEEE Transactions on Parallel and Distributed Systems, vol. 1, No. 1, pp. 91-106 (1990).
Banerjee, P.,Parallel Algorithms for VLSI Computer-Aided Design, Chapter 3, Englewood Cliffs, New Jersey: PTR Prentice Hall, pp. 118-171 (1994).
Betz, V., et al.,Architecture and CAD for Deep-Submicron FPGAs, Boston: Kluwer Academic Publishers, pp. 50-61 (1999), month n/a.
Bhatt, S.N., et al., “A Framework for Solving VLSI Graph Layout Problems,”Journal of Computer and System Sciences, vol. 28, pp. 300-345 (1984), month n/a.
Brelet, J., “An Overview of Multiple CAM Designs in Virtex Family Devices,”Xilinx Application Note, XAPP201, INTERNET: <http://www.xilinx.com/xapp/xapp260.pdf> pp. 1-6 (Sep. 23, 1999).
Brelet, J., et al., “Designing Flexible, Fast CAMs with Virtex Family FPGAs,”Xilinx Application Note, XAPP03, INTERNET: <http://www.xilinx.com/xapp/xapp203.pdf> pp. 1-17, (Sep. 23, 1999).
Caspi, E., et al., “Stream Computations Organized for Reconfigurable Execution (SCORE): Introduction and Tutorial,”presented at the Tenth International Conference on Field Programmable Logic and Applications, Villach, Austria, INTERNET: <http://www.cs.berkeley.edu/projects/brass/documents/score—tutorial.html> 31 pages total (Aug. 25, 2000).
Chan, Pak K., et al., “Parallel Placement for Field-Programmable Gate Arrays,”presented at the Eleventh ACM International Symposium on Field-Programmable Gate Arrays, Monterey, California, INTERNET: <http://www.doi.acm.org/10.1145/103724.103725> pp. 43-50 (2003), month n/a.
Chyan, Dah-Jun, et al., “A Placement Algorithm for Array Processors,”presented at the ACM/IEEE Design Automation Conference, Miami Beach, Florida, INTERNET: <http://portal.acm.org/citation.cfm?id=800661> pp. 182-188 (1983), month n/a.
Compton, K., et al., “Reconfigurable Computing: A Survey of Systems and Software,”ACM Computing Surveys(CSUR), vol. 34, No. 2, INTERNET: <http://doi.acm.org/10.1145/508352.50353> pp. 171-210 (Jun. 2002).
Dally, W.J., “Express Cubes: Improving the Performance ofk-aryn-cube Interconnection Networks,”IEEE Transactions on Computers, vol. 40, No. 9, pp. 1016-1023 (Sep. 1991).
DeHon, A., “Balancing Interconnect and Computation in a Reconfigurable Computing Array (or why you don't really want 100% LUT utilization),”Proceedings of the 1999 ACM/SGDA Seventh International Symposium on Field Programmable Gate Arrays, pp. 1-10 (Feb. 21-23, 1999).
DeHon, A., “Compact, Multilayer Layout for Butterfly Fat-Tree,”Proceedings of the Twelfth ACM Symposium on Parallel Algorithms and Architectures, 10 pages total (Jul. 2000)
DeHon Andre
Huang Randy
Wawrzynek John
Barnie Rexford
California Institute of Technology
Ladas & Parry LLP
The Regents of the University of California
White Dylan
LandOfFree
Fast router and hardware-assisted fast routing method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast router and hardware-assisted fast routing method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast router and hardware-assisted fast routing method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3968616