Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2007-10-16
2007-10-16
Dinh, Paul (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
11184452
ABSTRACT:
Methods of packing a design into a programmable logic device (PLD) using ant colony optimization. An augmented graph is assigned to the design, e.g., nodes and edges are defined based on sub-circuits and interconnections in the design, and a topological order is assigned to the nodes. An equation is determined for probabilistic behavior of packing agents at each node, and an initial pheromone value is assigned to each edge. In each iteration, each of “M” packing agents makes a tour of the graph, with merging decisions being made at each node in a probabilistic manner determined by the equation and pheromone values. The M resulting packing implementations are scored, and the best packing implementation is used to change the pheromone values for the next iteration. The probabilistic equation and scoring can be based on timing, area, and/or power constraints, for example. The process is complete when predefined criteria are met.
REFERENCES:
patent: 5963050 (1999-10-01), Young et al.
patent: 6363517 (2002-03-01), Levi et al.
patent: 6363519 (2002-03-01), Levi et al.
patent: 6378122 (2002-04-01), Levi et al.
patent: 6430736 (2002-08-01), Levi et al.
patent: 6539532 (2003-03-01), Levi et al.
Sarif, Bambang; Modified Ant Colony Algorithm For Combinational Logic Circuits Design; 2003; All pages.
Scheuermann, B.; FPGA Implementation of Population-Based Ant Colony Optimization; 2004; All pages.
Marco Dorigo et al.; “Ant Colonies for the Traveling Salesman Problem”; published in BioSystems, 1997; available on the web at http://dsp.jpl.nasa.gov/members/payman/swarm/dorigo97-bs.pdf; pp. 1-10.
James Montgomery; “Towards a Systematic Problem Classification Scheme for Ant Colony Optimisation”; Aug. 30, 2002; available on the web at http://www.it bond.edu.au/publications/02TR/02-15.pdf; pp. 1-12.
Gang Wang et al.; “Application Partitioning on Programmable Platforms Using the Ant Colony Optimization”; IEEE.tex, v 1.7; Jan. 6, 2004; pp. 1-23.
Dorian Gaertner; “Natural Algorithms for Optimisation Problems: Final Year Project Report”; Jun. 20, 2004; available on the web at http://www.doc.ic.ac.uk/teaching/projects/Distinguished04/DorianGaertner.pdf; pp. 1-129.
Gang Wang et al.; “System Level Partitioning for Programmable Platforms Using the Ant Colony Optimization”; downloaded from http://www.athena.ece.ucsb.edu/˜gang/papers/iwls2004.pdf on July 11, 2005; pp. 1-8.
Xilinx, Inc.; “Constraints Guide”; V9.1l; Copyright 1995-2007; available from www.xilinx.com; pp. 88-89, 115-116, 120-123, 135-138, 209-211, 214-216, 221-240, 247-255, 270-271, 337-377, and 388-389.
Cartier Lois D.
Dinh Paul
Memula Suresh
Xilinx , Inc.
LandOfFree
Methods of using ant colony optimization to pack designs... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods of using ant colony optimization to pack designs..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods of using ant colony optimization to pack designs... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3901780