In Electronic Computer Aided Design (ECAD) software systems, an integrated circuit design specification and implementation data must be stored as a set of database records, and these records have some finite maximum size based on the virtual memory capacity of the computer on which the software is running. In addition, the execution time of the ECAD software normally increases with the size of the design. The data to represent a very large integrated circuit design may be too large to fit in a computer's memory, or the execution time required to design or simulate the entire design may be prohibitive. This is particularly true where the number of components (i.e. gates) and attendant connections within an integrated circuit are in the 10s or 100s of millions or more.
Hierarchical decomposition or “partitioning” is a technique which may be used to reduce the complexity of a large integrated circuit design specification so that the memory and/or execution time required to complete the design remains manageable. Instead of representing the design as a single flat database, the design is partitioned into pieces, often called “blocks”, which can be designed and verified independently. With a given single level of hierarchy, the design specification consists of a set of blocks and the top-level interconnections between those blocks. With multiple levels of hierarchy the blocks may themselves consist of smaller sub-blocks and their interconnections.
Hierarchical decomposition may also be used simply as an organizational tool by a design team as a method for partitioning a design project among several designers. However, this logical hierarchy created by the design team in the design specification does not need to be the same as the physical hierarchy used to partition the design for implementation. Often the logical hierarchy is much deeper than the physical hierarchy. A process of block flattening may be used to transform the logical hierarchy into an appropriate physical hierarchy.
A conventional hierarchical design project typically proceeds in two major steps: a top-down block planning step followed by a bottom-up verification step. If the blocks themselves are implemented during the top-down phase (i.e. each block is implemented before its children) the flow is referred to as a top-down flow. Conversely, if the blocks are implemented during the bottom-up phase (i.e. each block is implemented after all of its children have been completed) the flow is referred to as a bottom-up flow. The top-down and bottom-up flows each have their advantages and disadvantages. Without loss of generality, a top-down flow is used as an example in the remainder of this document. A bottom-up flow could be implemented using identical techniques.
FIG. 1 shows a typical top-down block planning and implementation flow. It begins with a partitioning of the design netlist to map the logical hierarchy into the physical hierarchy, defining the top-level block and the set of sub-blocks to be implemented (step 110). Each sub-block is then assigned a width and height value and a placement in the floorplan (step 115). Locations are then assigned to the pins on each sub-block, which represent the locations where nets cross the sub-block boundaries (step 120). This is followed by a time budgeting step indicating which portion of the clock cycle is allocated to the timing paths that cross the sub-block boundaries (step 135).
At this point in a top-down flow, after the top-level block has been planned, the process is prepared to implement the block. All leaf-cells (standard cells and macros) owned by the block are assigned a placement, and all nets owned by the block are routed (step 140). If any of the nets were routed over the sub-blocks (so-called “feedthrough nets”) these wires are pushed down into the sub-blocks that they overlap, and new pins are created on the sub-block where the wires cross the sub-block boundaries (step 145). Then, recursively implement the sub-blocks according to the same process (step 150). This involves recursively performing steps 110 to 170 while treating each sub-block as the top-level block.
For the above process to complete successfully the shapes, pin locations, and timing budgets assigned to each block (steps 115 through 135) must represent achievable constraints. Otherwise the system may not be able to complete the implementation of some blocks according to their specifications. In such a case the specifications may need to be refined and the top-down process may need to be repeated before a correct implementation can be realized. Such an iterative refinement is time-consuming and should be avoided. Thus, methods for achieving high-quality results in these steps are of critical importance.
When the recursive top-down planning and implementation step is complete the bottom-up verification process can commence. Proceeding from the lowest-level blocks toward the top-level, each block is independently analyzed for logical correctness, as well as its timing and electrical performance, and compared against its specification (step 155). After all sub-blocks of a block have been independently verified the block itself can be analyzed (step 170), under the assumption that the sub-blocks are correct.
To work on an individual module, a designer or software tool requires a representation of the environment in which that module must operate. This includes the physical shape of the space in which the module is placed, the location of its input and output pins, power and other important signal routing information, the operating conditions (temperature and voltage), the expected details of the process used to fabricate the module, and the timing characteristics of the interface between the module and its environment. The focus of this method is to provide a representation of the timing characteristics. The problem is complicated by the fact that this representation must be generated before other modules or the top-level netlist has been completed. The result is that the timing characteristics used for design must be an approximation of the timing characteristics of the final product.
This set of timing characteristics is called the “timing budget” of a module. Good timing budgets must have the following characteristics-Completeness, Balance, and Achievability.
Completeness describes the characteristics of a budget at the block boundary. A complete timing budget describes the entire relevant context of a module. It should include signal arrival time constraints for all input pins (including bidirectional pins) and signal required time constraints for all output pins (also including bidirectional pins). It should include descriptions of all clocks that are applied as inputs of the design, generated within the design, or used as a reference for the timing constraints applied at the module outputs. It should also include any other special constraints that must be satisfied inside the module, such as global limits on signal transition times (i.e. slew limits). When the timing budget for a module is incomplete, the module cannot be fully designed without its context and the final design is likely to contain errors associated with violated constraints that were omitted from the budget. This is the minimal requirement for a timing budget.
Next, for successful integration of the top-level design, a set of timing budgets must be balanced. Balance describes the relationship between a budget, the top-level timing, and other budgets in the design. Balanced timing budgets guarantee that if all modules' timing constraints are satisfied, the top-level timing constraints will also be satisfied. When timing budgets are unbalanced, designers are forced to rework the final design to resolve problems that appear during integration of the top level. This rework often occurs very late in the design process and may require drastic and painful changes. Failure to generate balanced timing budgets may be seen as a lack of design discipline that has delayed timing closure in design methodologies.
The requirements of completeness and balance make achievability the most challenging aspect of the time budgeting problem. Achievability relates to the relationship between a timing budget and the block to which it applies. The difficulty is to create budgets that are achievable while maintaining balance and completeness. To achieve rapid design closure, it is crucial for the designer or design tool to have the ability to meet the timing constraints that are specified for each module. When the timing budget for a module is unachievable, designers are forced into a difficult cycle of iterative implementation and renegotiation of budgets. Each iteration attempts to resolve the conflicts between the timing requirements of the top-level netlist and other modules in a design and the difficulties found in implementing the module being designed. The inability to measure achievability is the biggest problem faced by design teams today and is the largest contributor to the failure to achieve timing closure that is experienced in contemporary design methodologies.
There is a need to provide a timing budgeting solution that better conforms to the completeness, balance, and achievability necessary but that does so in a resource-utilization friendly manner.