← Back
Home › Systems › Hardware and datacenter

physical-verification

Hardware and datacenter | physical-verification — signoff physical verification: design-rule check, layout-versus-schematic, parasitic extraction, power-grid IR drop and electromigration on full-chip hierarchical layouts

Siemens Calibre, Synopsys IC Validator / StarRC, Cadence Pegasus / Quantus, KLayout (open)

SystemTechniques · 14Primitives · 19 physical-verification Hierarchical instance databasegeometry · medium: Cell definitions with placed instances and transforms, expanded lazily for region queries over huge layoutsPolygon clippinggeometry · medium: Polygon intersection/union/difference (Weiler-Atherton, Martinez) for spatial predicatesGraph isomorphism matchinggraphs · medium: Canonical labelling and subgraph isomorphism matching (e.g. layout-versus-schematic) by partition refinementGraph partitioninggraphs · medium: Split a graph into k balanced parts with few edges between them; multilevel coarsen-partition-refine (METIS, KaHIP) for quality, streaming heuristics (LDG, Fennel) for one-pass scale.›Design rule check edge querieshardware-os · medium: Edge-based width/space/enclosure checks on layout polygons with hierarchical scanline queriesIr drop analysishardware-os · medium: Solve power-grid resistive networks for static and dynamic voltage drop under current mapsGmresnumerics · medium: GMRES with restarts: Arnoldi, Givens rotations, for nonsymmetric sparse systemsQuadtree octreegeometry · low: Adaptive spatial subdivision trees for queries and level of detail; loose and linear variantsInterval treedata-structures · low: Index of ranges that answers "which intervals overlap this point or range?" in O(log n + k); static sorted-array form is the compact, cache-friendly choice.›R-treegeometry · low: A balanced tree of nested bounding boxes that indexes rectangles and points, answering window and nearest-neighbour queries by pruning whole subtrees.›BFS and DFSgraphs · low: The two basic graph traversals; BFS gives hop distances and levels, DFS gives discovery/finish order for cycles, components and topological order.›Union-findgraphs · low: Disjoint-set forest with union by size and path compression; merges sets and answers same-set queries in effectively constant time.›Electromigration checkhardware-os · low: Check wire current density against EM limits per layer, width and temperatureRc network reductionhardware-os · low: Reduce parasitic RC networks to few-pole models (Elmore, AWE, PRIMA) preserving delayd-ary heapdata-structures · low: Array heap with d children per node (d = 4 typical): half the binary heap's depth, siblings in one cache line, faster priority queues.›Exact geometric predicatesgeometry · low: Robust orient and incircle tests with adaptive-precision floats (Shewchuk) or exact arithmeticPoint in polygongeometry · low: Ray-casting/winding tests and indexed polygon lookup for reverse geocodingPRNGs (PCG, xoshiro)numerics · low: Small, fast, statistically strong non-cryptographic generators: PCG32 and xoshiro256**, with seeding, parallel streams and unbiased ranges.›Sparse matrices (CSR)numerics · low: Compressed sparse row stores only nonzeros as row pointers, column indices and values; SpMV streams them once, so it is memory-bandwidth bound.›Newton root findingnumerics · low: Linearize at the guess and jump to the tangent root; quadratic convergence near a simple root, made robust by brackets (1D) or line search.›Stiff solvers (implicit, BDF)numerics · low: Implicit steps solve a small nonlinear system so fast decaying modes stay stable at any step size; BDF methods are the stiff-ODE workhorse.›LU and Cholesky factorizationnumerics · low: Factor A = PLU (any square matrix, partial pivoting) or A = LLᵀ (SPD) once in O(n³), then solve each right-hand side in O(n²).›Space filling curvesgeometry · low: Z-order/Morton (geohash) and Hilbert curves mapping multi-dimensional points to sortable keys+ 7 more techniques+ 3 more primitives

Similar systems

Share the most building blocks with this one.

computational-lithography 17 %