Some conditions under which hierarchical verification is O(N)

摘要: Before manufacturing, each chip design must be inspected for possible errors. For example, rule checking is used to check adherence the physical manufacturing rules, and static timing analysis verify that has adequate performance. Although modern designs are invariably specified hierarchically, verification algorithms can treat this hierarchy in different ways. The most straightforward way a hierarchical expand (or flatten) hierarchy, then do test. Since involve at least sorting data, such O(N log N), where N size of flattened hierarchy. Alternatively, tool try use rather than flattening it. One form involves verifying cell, generating model (also called an abstract) all interactions between cells by using their abstracts. Under some conditions, may more efficient verifying. In particular, if abstract O(n/sup a/) cell containing n primitives, time generate b/), complete levels O(N), provided ab<1.