Post-placement residual overlap removal method for core-based PLD programming process

A post-placement residual overlap removal method for use in a core-based programmable logic device (PLD) programming process wherein the PLD is programmed to implement a logic operation, the PLD including a plurality of configurable logic blocks (CLBs) arranged in rows aligned in a horizontal direction and columns aligned in a vertical direction, the logic operation being defined by a plurality of cores, each core including a group of interrelated logic portions, wherein the logic portions of each core are assigned to a selected group of the plurality of CLBs during a placement portion of the PLD programming process to produce an original placement solution, the method comprising the steps of:

• defining a positional relationship between the cores using a horizontal constraint graph and a vertical constraint graph, the horizontal constraint graph including a plurality of horizontal paths determined by a horizontal positional relationship of the cores assigned to each row of CLBs, and the vertical constraint graph including a plurality of vertical paths determined by a vertical positional relationship of the cores assigned to each column of CLBs;
• determining the feasibility of the horizontal constraint graph and the vertical constraint graph by identifying critical paths in which the number of logic portions assigned to a row of CLBs or a column of CLBs is greater than the number of CLBs in the row of CLBs or the column of CLBs;
• if one of the horizontal constraint graph and the vertical constraint graph is infeasible, revising the infeasible constraint graph by reassigning the logic portions of a selected core such that the number of logic portions assigned to the CLBs of the critical path are reduced;
• repeating the steps of determining the feasibility and revising an infeasible constraint graph until both the horizontal constraint graph and the vertical constraint graph are feasible;
• and
• allocating slack along the paths of the horizontal and vertical constraint paths such that a revised placement solution is produced that is as close to the original placement solution as possible.