Introduction

Incremental design is a useful capability when implemented properly. Unfortunately, due to the naming schemes employed by logic synthesis tools, confusion arises over what in the design has actually changed. What is needed is an algorithm that deterministically creates names for generated logic elements, simplifying the task of correctly identifying what has changed at each cycle.

For the incremental design flow illustrated in Figure 1 to be most effective, minor changes should be made to the design at each incremental turn to allow the reuse of the place-and-route data generated during the previous design turn. The major benefit of this methodology is the generation of a predictable design output similar to the previous place-and-route run, plus the associated shortening of the runtime.

The key to deterministic name generation is to create designs during logic synthesis that have similar instance and/or object names to the previous designs where they are logically equivalent, and different instance and/or object names where the designs differ.

Figure 1.

Design Objects and Naming in Logic Synthesis

Design objects are libraries, cells, views, ports, nets,  pins , and instances. Among these, instance, port, net, and pin are part of the design as a result of logic synthesis. Generally, names for objects are either derived from the RTL design or generated by the synthesis process:

• Port names are obtained from the RTL design.
• User level hierarchy names are obtained from the RTL design.
• Nets connecting to ports generally inherit the same name as the port name.
• Sequential elements (flip-flops) of a state machine often inherit names from the RTL design.

Instances and nets representing generated logic are named by logic synthesis, based on conventions that can range from the simple to the complex:

• Instance names can be prefix with an index number “ix”, for example, ix10.
• Net names can be a prefix with “nx”, concatenated with an index number, for example, nx20.
• Sequential instances (flip-flops) may have a predefined prefix to highlight this nature, for example, reg_state(1).
• Instances of operators (adders, subtractors, counters, etc.) may have some specific prefix to highlight their function, for example, addsub_5_5_1.

Sequential-Index Name Generation

Embedded in any human-generated RTL design, the logical block, signal and port names reflect the hierarchy and data flow of the design. Traditionally, logic synthesis tools have used this structure for generating the names of  design elements.  This technique for naming is refer to as sequential index naming.
During logic synthesis, the tool generates the detailed logic of the design, creating names for each design object. A common method for automatic name generation is to start at an index, initialized to a specific value, then incrementing its value for each object name. For  example, (with the index counter initialized to 0):

• Instance names: ix0, ix1, ix2
• Net names: nx3, nx4, nx5
• Operator names: addsub_5_5_6, addsub_5_5_7

For hierarchical designs, the index can be reset at each hierarchal level to allow for better readability. However, not all synthesis tools necessarily reset the index at each hierarchical level but may opt to continue incrementing.

Problems with Sequential-Index Naming

During Place-and-Route Iterations

During design iterations, sequential-index name generation has two major shortfalls:

• An object with the same instance name as a previous run may in fact have different functionality.
• A deletion or addition of a signal instance results in a domino effect of instance renaming.

Figure 2.

In the example shown in Figure 2, the single instance of logic AND and OR  would have the design and port names as in the following:

• Input port: a, b;
• Output port: y;
• Nets: a, b, y
                                                       

If the design is revised through incremental changes, with the logic AND being replaced by loigc OR, then both objects would receive the same instance name. The place-and-route tool cannot then tell the different based on the instance names.

In the second example shown if Figure 3, the design has multiple instances naming ix1 to ixn, if a single instance is removed in the design revision, then the instances are renamed ix1 to ix(n-1). In the next phase of place and route, the tool may mistakenly trying to match the placement of instances ix1 to ix(n-1) even though there is no longer one-to-one match with the previous placement. Depending on how early in the naming sequence the instance is removed, the more placement footprints can differ (but have the same instance names).

Figure 3.

During Design Debug

Sequential-index naming also causes problems for the designer during debug. As object names change, tracing failing conditions and verifying fixes is complicated. An object identified for observation in one run, may change name in the next, forcing the designer to waste time to re-identify the proper instance or net. As the number of objects renamed increases, the more time that is needed to correctly re-identify those under investigation.  

Deterministic Name Generation

At the naming level, deterministic name generation is designed to achieve several objectives:

• Given the same design, the generated names of each object must be deterministic.
• The name of the objects must be differentiated according the their logical function.
• Given the same design with arbitrary arrangement of logical blocks, the generated name for the object must not change with each iteration cycle.

The essential requirement for a deterministic name generation algorithm is in the area of incremental design changes. Given two designs, the second being a minor modification of the first at the RTL level, and assuming the logic synthesis tool can generate a consistent logical representation of the design:
The resulting object names must remain the same for the unchanged portion of the design.
The changed portion of the design must be name differently.

Designing the Algorithm

The keys to generating deterministic names for a design are:

• Localizing the logic names within affected logic cone
• Using user-defined object names as the root name for each logic cone where feasible
• Using indexing within the logic cones to represent the design structure
• Imbedding logic function markers in the instance
• Encoding the generated names into shorter ones to reduce memory usage and improve processing speed.

Localizing the Logic Names within Affected Logic Cone.

A given design can be partitioned into logic cones as illustrated in Figure 4a. Starting from the output ports, the logic cone extends backwards until reaching the starting points such as registers and/or input ports. As the design objects within each logic cone is named based on a specified rule set, then the name structure of each cone is independent of the other. In the event of design changes between different design revisions, only the affected logic cone(s) and the resulting names change. Thus the unaffected logic cones maintain their same names from the previous revision.

Figure 4a.

Using User-Defined Object Names as Root Name

The maintaining of readability of the design is one of the most important goals of the algorithm since the object names from the original RTL always convey the functionality and data flow to the designer. To this end, a deterministic naming algorithm should select the user-defined object name as the root for instance names within each logic cone. This process ensures uniqueness and repeatability of the algorithm.

User-defined object names are generally:

• Port names
• Logic signals name from RTL sources
• Sequential element names
• Special operator objects such as adder, multiplier, etc.
   

Figure 4b.

Using Indexing within Logic Cones to Represent Design Structure

Within each logic cone, the index of instances and nets starts with the first initialized value, normally 1. For example, the instances in the first and second logic cones shown in Figure 4b are named as follows:

• Logic cone: Out1
  • Root-name: Out1
  • Instance names: Out1_1, Out1_2, Out1_3,…Out1_7
• Logic cone: Out2
  • Root-name: Out2
  • Instance names: Out2_1, Out2_2, Out2_3, . . ..Out2_6.

Imbedding Logic Function Markers in Instance Names

One more level of qualifier to the name is added to ensure the uniqueness by using the name of the logical function of the instance. For example,  ASIC designs are synthesized to cells with names representing their logic functions, such as AND2, AND3, NOR2, NOR3 etc. These names could then be used directly as the name sub-qualifier. For FPGAs, where designs are generally synthesized to LUTs, the real function for each instance must be used. Using the simplified illustration in figure 4, with the convention of a square representing an AND gate, and a circle representing an OR gate, the resulting instance names are:

• Out1_1_AND, Out1_2_AND, Out1_3_OR, Out1_4_OR, Out1_5_AND, Out1_6_AND, Out1_7_AND.
• Out2_1_OR, Out2_2_AND, Out2_3_AND, Out2_4_OR, Out2_5_OR, Out2_6_AND.

Encoding names for practicality

For the examples above, the object names are presented in full form. In practice, the object names are encoded to provide a compact representation to improve both memory usage and processing runtime. A deterministic naming algorithm should use the following rules when encoding synthesis-generated names:

• Hierarchical Prefix – if applicable
• Instance names – start with prefix ix
• Net names – start with prefix nx
• Encoded root name as first qualifier
• Separating character
• Encoded logic function and topological position for instance
• Topological position for net

Example of encoded instance names indicating that the two instances are located in the same logic cone, with identical logic function and are adjacent to each other:

• ix54453z30210
• ix54453z30211

Example of net names indicating that the two nets are located in the same logic cone and are adjacent to each other.:

• ix54453z2
• ix54453z3

There should be an option to prevent the synthesis tool to not encode the object names but keep it in long format for analysis purpose. And the other option is to generate both encoded and original name internally and provide utility mapping the related name on demand. 

Conclusion

Incremental design is an effective methodology for reducing design cycle time. However, the problem with incremental design today is the confusion introduced in the naming of objects during logic synthesis. This confusion results in downstream tools being unable to correctly identify which parts of the design have change, and can end up negating the time savings incremental design was to deliver.  Deterministic naming of design objects is a methodology that aids downstream tools to correctly identify which parts of the design have changed, helping to deliver the promise of incremental design.

References

[1] Brand, D. et al, Incremental Synthesis, Proceeding of the 1994 IEEE/ACM international conference on Computer-aided design.
[2] Gu, Zhenyu et al, Incremental Exploration of the Combined Physical and Behavioral Design Space, Proceeding of the 42th annual conference on Design automation.
[3] Coudert, Oliver et al, Incremental CAD, Proceeding of the 2000 IEEE/ACM international conference on Computer-aided design.
[4] Cong, Jason and Huang, Hui, Depth optimal incremental mapping for field programmable gate arrays, Proceeding of the 37th conference on Design automation.
[5] Shinsha. T. et al, Incremental logic synthesis through gate logic structure identification, Proceedings of the 23rd ACM/IEEE conference on Design automation.
[6] Singh, Deshanand P.  et al, Incremental Retiming for FPGA Physical Synthesis, Proceeding of the 42nd annual conference on Design Automation.

March 13, 2007

[back to top]