Patent ID: 7284228

Claim:
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.