Methods of using ant colony optimization to pack designs into programmable logic devices

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.

1. A method of packing a design into a programmable logic device (PLD), the method comprising:
 defining an augmented graph and a probabilistic equation for the design, the augmented graph comprising a plurality of nodes and a plurality of edges each coupled between two of the nodes, wherein each node corresponds to a sub-circuit within the design, each edge corresponds to an interconnection between the sub-circuits corresponding to the two nodes coupled to the edge, and the nodes have a topological order; 
 assigning an initial pheromone value to each edge in the augmented graph; 
 applying M packing agents to a node occurring first in the topological order, wherein M is an integer; 
 generating M packing implementations of the design by, for each of the M packing agents, touring the nodes in the topological order and selecting for each node at least one edge coupled to one or more preceding nodes in the topographical order; 
 scoring each of the M packing implementations and identifying a top-scoring packing implementation from the M packing implementations; 
 updating the pheromone values for at least some of the edges in the augmented graph based on the top-scoring packing implementation; and 
 returning, when criteria are met, the top-scoring packing implementation, 
 wherein defining the augmented graph and the probabilistic equation for the design comprises:
 defining each node in the augmented graph to correspond to one lookup table (LUT) in the PLD; 
 defining a first plurality of edges in the augmented graph to designate the two LUTs corresponding to the nodes coupled to each of the first plurality of edges being merged into a single slice in the PLD; and 
 defining a second plurality of edges in the augmented graph to designate the two LUTs corresponding to the nodes coupled to each of the second plurality of edges being placed in two different slices in the PLD. 
 
 
   
   
     2. The method of  claim 1 , further comprising:
 repeating, when the criteria are not met, the steps of applying, generating, scoring, and updating. 
 
   
   
     3. The method of  claim 1 , wherein updating the pheromone values for at least some of the edges in the augmented graph comprises increasing the pheromone value for each edge included in the top-scoring packing implementation, and decreasing the pheromone value for any edge not included in the top-scoring packing implementation. 
   
   
     4. The method of  claim 1 , wherein the probabilistic equation and the scoring are based on timing constraints for the design. 
   
   
     5. The method of  claim 1 , wherein the probabilistic equation and the scoring are based on area constraints for the design. 
   
   
     6. A method of packing a design into a programmable logic device (PLD), the method comprising:
 defining an augmented graph and a probabilistic equation for the design, the augmented graph comprising a plurality of nodes and a plurality of edges each coupled between two of the nodes, wherein each node corresponds to a sub-circuit within the design, each edge corresponds to an interconnection between the sub-circuits corresponding to the two nodes coupled to the edge, and the nodes have a topological order; 
 assigning an initial pheromone value to each edge in the augmented graph; 
 applying M packing agents to a node occurring first in the topological order, wherein M is an integer; 
 generating M packing implementations of the design by, for each of the M packing agents, touring the nodes in the topological order and selecting for each node at least one edge coupled to one or more preceding nodes in the topographical order; 
 scoring each of the M packing implementations and identifying a top-scoring packing implementation from the M packing implementations; 
 updating the pheromone values for at least some of the edges in the augmented graph based on the top-scoring packing implementation; and 
 returning, when criteria are met, the top-scoring packing implementation, 
 wherein defining the augmented graph and the probabilistic equation for the design comprises:
 defining each node in the augmented graph to correspond to one lookup table (LUT) in the PLD; 
 defining a first plurality of edges in the augmented graph to designate the two LUTs corresponding to the nodes coupled to each of the first plurality of edges being merged into a single logic block in the PLD; and 
 defining a second plurality of edges in the augmented graph to designate the two LUTs corresponding to the nodes coupled to each of the second plurality of edges being placed in two different logic blocks in the PLD. 
 
 
   
   
     7. The method of  claim 6 , further comprising:
 repeating, when the criteria are not met, the steps of applying, generating, scoring, and updating. 
 
   
   
     8. The method of  claim 6 , wherein updating the pheromone values for at least some of the edges in the augmented graph comprises increasing the pheromone value for each edge included in the top-scoring packing implementation, and decreasing the pheromone value for any edge not included in the top-scoring packing implementation. 
   
   
     9. The method of  claim 6 , wherein the probabilistic equation and the scoring are based on timing constraints for the design. 
   
   
     10. The method of  claim 6 , wherein the probabilistic equation and the scoring are based on area constraints for the design. 
   
   
     11. A method of packing a design into a programmable logic device (PLD), the method comprising:
 defining an augmented graph and a probabilistic equation for the design, the augmented graph comprising a plurality of nodes and a plurality of edges each coupled between two of the nodes, wherein each node corresponds to a sub-circuit within the design, each edge corresponds to an interconnection between the sub-circuits corresponding to the two nodes coupled to the edge, and the nodes have a topological order; 
 assigning an initial pheromone value to each edge in the augmented graph; 
 applying M packing agents to a node occurring first in the topological order, wherein M is an integer; 
 generating M packing implementations of the design by, for each of the M packing agents, touring the nodes in the topological order and selecting for each node at least one edge coupled to one or more preceding nodes in the topographical order; 
 scoring each of the M packing implementations and identifying a top-scoring packing implementation from the M packing implementations; 
 updating the pheromone values for at least some of the edges in the augmented graph based on the top-scoring packing implementation; and 
 returning, when criteria are met, the top-scoring packing implementation, 
 wherein defining the augmented graph and the probabilistic equation for the design comprises:
 defining each node in the augmented graph to correspond to one slice in the PLD, each slice including a plurality of lookup tables (LUTs); 
 defining a first plurality of edges in the augmented graph to designate the two slices corresponding to the nodes coupled to each edge being merged into a single logic block in the PLD; and 
 defining a second plurality of edges in the augmented graph to designate the two slices corresponding to the nodes coupled to each edge being placed in two different logic blocks in the PLD. 
 
 
   
   
     12. The method of  claim 11 , further comprising:
 repeating, when the criteria are not met, the steps of applying, generating, scoring, and updating. 
 
   
   
     13. The method of  claim 11 , wherein updating the pheromone values for at least some of the edges in the augmented graph comprises increasing the pheromone value for each edge included in the top-scoring packing implementation, and decreasing the pheromone value for any edge not included in the top-scoring packing implementation. 
   
   
     14. The method of  claim 11 , wherein the probabilistic equation and the scoring are based on timing constraints for the design. 
   
   
     15. The method of  claim 11 , wherein the probabilistic equation and the scoring are based on area constraints for the design.