Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2007-04-24
2007-04-24
Garbowski, Leigh M. (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
10643772
ABSTRACT:
A method and a device for performing placement of a plurality of elements for circuit design. A potential location is assigned to each element and a placement engine is assigned to each potential location. Pairing operations are performed, in parallel, between placement engines to determine whether to perform exchange of the elements associated with the engines. Exchange determination is based both on a cost function and on randomness considerations. Also self-placement is allowed, where the placement engines are implemented on the same hardware system on which the elements are to be placed.
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: 5796625 (1998-08-01), Scepanovic et al.
patent: 5815403 (1998-09-01), Jones et al.
patent: 6080204 (2000-06-01), Mendel
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: 2003/0174723 (2003-09-01), DeHon et al.
patent: 2005/0063373 (2005-03-01), DeHon et al.
patent: 98/35294 (1998-08-01), None
Alfke, P., “Efficient Shift Registers, LFSR Counters, and Long Psuedo-Random Sequence Generators,”Xilinx Application Note, KAPP 052, INTERNET: <http://www.xilinx.com/xapp/xapp203.pdf> pp. 1-6 (Jul. 7, 1996).
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 Acadmeic Publishers, pp. 50-61 (1999).
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,” presentedat 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, pp. 43-50 (2003).
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).
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).
DeHon, A., et al., “Hardware-Assisted Fast Routing,”IEEE Symposium on Field-Programmable Custom Computing Machines, Napa Valley, California, INTERNET: <http:www.cs.caltech.edu/research/ic/abstracts/fastroute—feem2002.html> pp. 1-11 (Apr. 22-24, 2002).
Goto, S., An Efficient Algorithm for the Two-Dimensional Placement Problem in Electrical Circuit Design,IEEE Transactions on Circuits and Systems, vol. CAS-28, No. 1, pp. 12-18 (Jan. 1981).
Haldar, M., et al., “Parallel Algorithms for PPGA Placement,”Proceedings of the Tenth Great Lakes Symposium on VLSI, INTERNET: <http://doi.acm.org/10.1145/330855.330988> pp. 86-94 (2000).
Huang, R., et al., “Stochastic, Spatial Routing for Hypergraphs, Trees, and Meshes,”Eleventh ACM International Symposium on Field-Programmable Gate Arrays, INTERNET:<http://www.cs.caltech.edu/research/ic/abstracts/fastroute—fpga2003.html> 12 pages total (Feb. 23-25, 2003).
Kirkpatrick, S., et al., “Optimization by Stimulated Annealing,”Science, vol. 220, No. 4598, pp. 671-680 (May 13, 1983).
Kravitz, S.A. et al., “Multiprocessor-Based Placement by Stimulated Annealing,”presented at the Twenty-Third IEEE Design Automation Conference, Las Vegas, Nevada INTERNET: <http://doi.acm.org/10.1145/318013.318104> pp. 567-573 (1986).
Mulpuri, C., et al., “Runtime and Quality Tradeoffs in FPGA Placement and Routing,”Proceedings of the Ninth International Symposium on Field-Programmable Gate Arrays, INTERNET:<http://www.ee.washington.edu/faculty/hauck/publications/RuntimeTradeoffs.pdf> pp. 29-36 (Feb. 11-13, 2001).
Sankar, Y., et al., “Trading Quality for Compile Time: Ultra-Fast Placement for FPGAs,”Proceedings of the 1999 ACM/SIGDA Seventh International Symposium on Field Programmable Gate Arrays, INTERNET:<http://www.eecg.toronto.edu/˜jayar/pubs/sankar/fpga99sankar.pdf> pp. 157-166 (1999).
Schnorr, C.P., et al., “An Optimal Sorting Algorithm For Mesh Connected Computers,”presented at the Eighteenth Annual ACM Symposium on Theory of Computing, Berkeley, CA, INTERNET: <http://doi.acm.org/10.1145/359461.359481> pp. 255-270 (1986).
Shahookar, K., et al., “VSLI Cell Placement Techniques,”ACM Computing Surveys(CSUR), vol. 23, No. 2, pp. 143-220 (Jun. 1991).
Spira, P., et al., “Hardware Acceleration of Gate Array Layout,”presented at the 22nd ACM/IEEE Design Automation Conference, Las Vegas, Nevada, INTERNET: <http://doi.acm.org/10.1145/317825.317913> pp. 359-366 (1985).
Tessier, R., “Fast Placement Approaches for FPGAs,”ACM Transactions on Design Automation of Electronic Systems(TODAES), vol. 7, No. 2 pp. 284-305, (Apr. 2002).
Thompson, C.D., et al., “Sorting on a Mesh-Connected Parallel Computer,”Communications of the ACM, vol. 20, No. 4, pp. 263-271 (Apr. 1977).
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).
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).
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).
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).
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 Interconnection 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, Mult
DeHon Andre
Wrighton Michael
California Institute of Technology
Garbowski Leigh M.
LandOfFree
Element placement method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Element placement method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Element placement method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3757848