Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2011-03-08
2011-03-08
Doan, Nghia M (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
07904848
ABSTRACT:
A system for mapping tasks of at least one application on processing units of a reconfigurable array, the system comprising a plurality of programmable processing units, each programmable processing unit having at least one connection node, the programmable processing units disposed on a layer permitting interconnection between connection nodes; and a mapping unit adapted to substantially simultaneously optimize placement of the tasks on the plurality of programmable processing units and routing of interconnections between the plurality of processing units, the mapping unit adapted to select one placement algorithm among a plurality of predetermined placement algorithms and to select one routing algorithm from a plurality of predetermined placement algorithms, the selection configured to prefer use of non-random algorithms.
REFERENCES:
patent: 5701441 (1997-12-01), Trimberger
patent: 7073158 (2006-07-01), McCubbrey
patent: 2003/0099014 (2003-05-01), Egner et al.
patent: 2005/0278665 (2005-12-01), Gentry et al.
Betz et al., “VPR: A New Packing, Placement and Routing Tool for FPGA Research”, Int. Workshop on Field-Programmable Logic and Applications, pp. 213-222, 1997.
Boese et al., “Best-So-Far vs. Where-You-Are: New Perspectives on Simulated Annealing for CAD”, Proceedings EURO-DAC, pp. 78-83, 1993.
Breuer, M.A., “A class of min-cut placement algorithms”, Proceedings of the 14thconference on Design automation. pp. 284-290, 1977.
Caldwell et al., “Can Recursive Bisection Alone Produce Routable Placements?” Proc. Design Automation Conference, pp. 1-6, 2000.
Clow, G.W., “A Global Routing Algorithm for General Cells”, Proceedings of the ACM IEEE 21stDesign Automation Conference, pp. 45-51, 1984.
Cohoon et al., “Genetic Placement”, Proc. IEEE Int. Conf. on CAD, vol. CAD-6, No. 6, pp. 956-964, 1987.
Dijkstra, E.W., “A Note on Two Problems in Connexion with Graphs”, Numerical Mathematics, vol. 1, pp. 269-271, 1959.
Ebeling et al., “Placement and Routing Tools for the Triptych FPGA”, IEEE Trans on VLSI Systems, vol. 3, No. 4, pp. 473-482, 1995.
Fiduccia et al., “A Linear-Time Heuristic for Improving Network Partitions”, 19thDesign Automation Conference, pp. 175-181, 1982.
Goldberg et al., “Alleles, Loci, and the Traveling Salesman Problem”, Proc. Int. Conf. on Genetic Algorithms and their Applications, pp. 154-159, 1985.
Goto, S., “An Efficient Algorithm for the Two-Dimensional Placement Problem in Electrical Circuit Layout”, IEEE Transactions on Circuits and Systems, vol. CAS-28, No. 1, pp. 12-18, 1981.
Hadlock, F.O., “A Shortest Path Algorithm for Grid Graphs”, Networks, John Wiley & Sons, 7, pp. 323-334, 1977.
Hanan et al., “Placement Techniques”, M.A. Breuer, Ed. Prentice-Hall Inc., Englewood Cliffs, New Jersey, pp. 213-282, 1972.
Hightower, D.W., “A Solution to Line-Routing Problems on the Continuous Plane”, Proceedings of the 6thDesign Automation Workshop, pp. 1-24, 1969.
Kannan et al., “Tightly Integrated Placement and Routing for FPGAs”, Proc. Of the Int. Workshop on Field-Programmable Logic and Applications, pp. 233-242, 2001.
Karro et al., “Gambit: A Tool for the Simultaneous Placement and Detailed Routing of Gate-Arrays”, 11thInternational Conference on Field Programmable Logic and Applications, pp. 243-253, 2001.
Kirkpatrick et al., “Optimization by Simulated Annealing”, Science, vol. 220, No. 4598, pp. 671-680, 1983.
Land et al., “An Automatic Method of Solving Discrete Programming Problems”, Econometrica, vol. 28, No. 3, pp. 497-520, 1960.
Lee, C.Y., “An Algorithm for Path Connections and Its Applications”, IRE Transactions on Electronic Computers, vol. EC=10, pp. 346-365, 1961.
Lysecky, et al., Dynamic FPGA routing for just-in-time FPGA compilation; DAC, Jun. 2004, San Diego, California.
McMurchie et al., “PathFinder: A Negotiation-Based Performance-Driven Router for FPGAs”, Proc. Of ACM Symp. Field-Programmable Gate Arrays, 1995.
Mei et al., “Exploiting loop-level parallelism on coarse-grained reconfigurable architectures using modulo scheduling”, IEE Proc.-Computer and Digital Techniques, vol. 150, No. 5, pp. 255-261, 2003.
Mikami et al., “A Computer Program for Optimal Routing of Printed Circuit Conductors”, Proceedings of the IFIP Congress, vol. 2, pp. 1475-1478, 1968.
Mo et al., “A Force-Directed Macro-Cell Placer”, Proc. ICCAD, pp. 404-407, 2000.
Nag et al., “Performance-Driven Simultaneous Placement and Routing for FPGA's”, IEEE Transactions on Computer-Aided Design and Integrated Circuits and Systems, vol. 17, No. 6, pp. 499-518, 1998.
Nilsson, N.J., Problem-Solving Methods in Artificial Intelligence, McGraw-Hill, Ch. 3, pp. 43-78, 1971.
Onodera et al., “Branch-and-Bound Placement for Building Block Layout”, 28thACM/IEEE Design Automation Conference, pp. 433-439, 1991.
Preas et al., “Automatic Placement: A Review of Current Techniques”, Proc. Design Automation Conference, pp. 622-629, 1986.
Rose et al., “Temperature Measurement and Equilibrium Dynamics of Simulated Annealing Placements”, IEEE Transactions on Computer-Aided Design, vol. 9, No. 3, pp. 253-259, 1990.
Saito et al., “Cluster Architecture for Reconfigurable Signal Processing Engine for Wireless Communication”, IEEE, pp. 353-359, 2005.
Sankar et al., “Trading Quality for Compile Time: Ultra-Fast Placement for FPGAs”, ACM international conference on FPGA, pp. 157-166, 1999.
Sechen et al., “The TimberWolf Placement and Routing Package”, IEEE Journal of Solid-State Circuits, vol. sc-20, No. 2, pp. 510-522, 1985.
Shahookar et al., “VLSI Cell Placement Techniques”, ACM Computing Surveys, vol. 23, No. 2, pp. 143-220, 1991.
Shannon, C. , “Presentation of a Maze-Solving Machine”, Trans of the 8thCybernetics Conf., Josiah Macy Jr. Foundation, New York, NY, pp. 173-180, 1952.
Soukup, J., “Fast Maze Router”, Annual ACM IEEE Design Automation Conference, Proceedings of the 15thDesign Automation Conference, 1978, Las Vegas, Nevada, US, DAC-78, pp. 100-102.
Sun et al., “Efficient and Effective Placement for Very Large Circuits”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 14, No. 3, pp. 349-359, 1995.
Swartz et al., “New Algorithms for the Placement and Routing of Macro Cells”, Proc. Int. Conf. on Computer-Aided Design, pp. 336-339, 1990.
Coene Paul
Fujisawa Hisanori
Doan Nghia M
Fujitsu Ltd.
IMEC
Knobbe Martens Olson & Bear LLP
LandOfFree
System and method for runtime placement and routing of a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for runtime placement and routing of a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for runtime placement and routing of a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2663746