Slew constrained minimum cost buffering

Abstract

A buffer insertion technique addresses slew constraints while minimizing buffer cost. The method builds initial solutions for the sinks, each having an associated cost, slew and capacitance. As a solution propagates toward a source, wire capacitance and wire slew are added to the solution. When a buffer is selected for possible insertion, the slew of the solution is set to zero while the cost of the solution is incremented based on the selected buffer and the capacitance is set to an intrinsic capacitance of the buffer. The solutions of two intersecting wire branches are merged by adding branch capacitances and costs, and selecting the highest branch slew. The solution sets are updated by disregarding solutions which have a slew component greater than a slew constraint, and any solution that is dominated by another solution is eliminated. The solution having the smallest cost is selected as the final solution.

1. A method of providing a buffer tree for a net of an integrated circuit design, comprising:
 building an initial solution set for the buffer tree from initial solutions for sinks of the net wherein solutions have associated cost, slew and capacitance components; 
 generating sets of candidate solutions for wire branches of the net which originate at the sinks and extend toward a source of the net wherein the candidate solutions have associated cost, slew and capacitance components derived by selectively inserting at least one buffer along a given wire branch,
 setting the slew component of a candidate solution for the given wire branch to zero, 
 incrementing the cost component of the candidate solution based on the inserted buffer, 
 setting the capacitance component of the candidate solution to an intrinsic capacitance of the inserted buffer, 
 increasing the capacitance component of the candidate solution by adding a wire capacitance of any new wire section connected between the source and the inserted buffer, and 
 increasing the slew component of the candidate solution by adding a wire slew of the new wire section; merging candidate solutions for two wire branches by summing the capacitance component of the two wire branches, summing the cost components of the two wire branches, and selecting a maximum slew component from the two wire branches; 
 
 updating the candidate solution sets by disregarding any candidate solutions whose slew component is greater than a slew constraint; and 
 selecting a final solution which has a smallest cost component from updated candidate solution sets. 
 
   
   
     2. The method of  claim 1  wherein:
 the buffers are selected from a buffer library having different buffer types; and 
 the candidate solutions are generated for more than one buffer type in the library. 
 
   
   
     3. The method of  claim 1  wherein said updating includes eliminating any candidate solution whose associated cost, slew and capacitance components are dominated by the associated cost, slew and capacitance components of another candidate solution. 
   
   
     4. The method of  claim 1  wherein said generating includes merging solutions of two intersecting wire branches by adding branch capacitance and cost components, and selecting a highest branch slew component.