PaperlayerView exact revision on arXiv

Source-linked AI summary

Timing-Driven Logic Remapping with Local Physical Context

Zijian Jiang, Hongyang Pan, Cunqing Lan, Keren Zhu

arXiv:2610.01918v1cs.AR

TL;DR

Post-placement remapping must account for surrounding timing, fanout loads, and interconnect effects, while physical implementation can change how candidate mappings perform. PCR searches bounded windows with context-aware mapping and physical validation. It reports lower timing-violation magnitudes than the compared mapping and resynthesis methods under the stated postprocessing settings.

  • Problem

    Post-placement timing improvement may be constrained by an existing logic decomposition, while larger restructuring regions can disrupt placement and modeled rankings may differ from post-implementation timing.

    Source: §I · p. 1

  • Method

    PCR extracts bounded windows, jointly optimizes cut, phase, and cell choices using estimated interconnect delay, screens with an LP relaxation, and physically evaluates discrete candidates before acceptance.

    Source: §I · pp. 1–2

  • Results

    PCR reduces geometric-mean WNS/TNS violation magnitudes by 86.7%/95.2% versus PigMap3 under position-aware postprocessing, and by 48.6–49.2%/53.3–63.1% versus genetic and annealing under uniform postprocessing.

    Source: §I · p. 2

  • Takeaways & Limitations

    Accepted physical improvements update the design context used to guide subsequent local searches.

    Source: §I · p. 1, §V · p. 6

    The LP lower bound applies only to the specified candidate domain and current frozen RC model, and does not bound timing after routing or a subsequent model update.

    Source: 2) Delay model and relaxation · p. 4

Abstract

from arXiv · show

The timing behavior of a mapped circuit depends on both its logic implementation and the physical environment in which that implementation is realized. Revisiting mapping decisions after placement therefore requires a search procedure that accounts for surrounding timing constraints, fanout loads, and interconnect effects. We study local remapping in this setting and develop a framework that couples discrete mapping search with physical implementation feedback. Timing-critical regions are isolated through bounded windows whose interfaces retain the context of the surrounding circuit. Within each window, a mixed-integer formulation jointly selects logic cuts, signal polarities, and library cells under a delay model informed by estimated locations and interconnect parasitics. A continuous relaxation filters the search space before discrete optimization produces alternative implementations with similar modeled timing and different structural choices. These implementations are reconstructed and assessed through legalization, routing-based parasitic estimation, and timing analysis. Physically validated improvements are incorporated into the design, and the updated context guides subsequent searches. The framework provides a systematic way to revisit local logic implementations while accounting for their interaction with an existing placement.

I. INTRODUCTION

Post-placement logic restructuring can explore alternative Boolean decompositions, but its search must balance optimization scope with disruption to the established placement and validate modeled gains physically. PCR addresses this with context-aware local mapping and reports lower timing-violation magnitudes than the compared methods.

Motivation

  • Post-placement restructuring can replace suboptimal logic decompositions, but larger regions may disrupt placement and alter neighboring-gate loads, while modeled rankings may differ from post-implementation timing.Evaluating every alternative physically is costly, motivating selective candidate generation followed by physical validation.Source: §I · p. 1

Related work

  • Prior work connects logic optimization and physical design through placement-aware synthesis and mapping, while PCR focuses on local mapping guided by a placed design’s timing and load context.The cited approaches include PigMap3 and CPA-Remap.Source: §I · p. 1

Proposed framework

  • PCR guides bounded-window remapping with placed-design timing and load context plus estimated interconnect delay, then uses physical evaluation to decide candidate acceptance.Reference timing and external pin loads retain surrounding context; accepted candidates update the design and guide subsequent searches.Source: §I · p. 1
  • PCR jointly models cut, phase, and library-cell choices within bounded windows while preserving shared boundary signals and surrounding timing context.The formulation incorporates estimated interconnect delays.Source: §I · p. 1
  • PCR combines relaxation-bound screening and action-domain restriction with integer feasibility and timing optimization to produce sparse and structurally distinct mappings under a common modeled timing cap.The distinct candidates receive separate physical evaluation despite similar modeled timing.Source: §I · pp. 1–2

Experimental evaluation

  • PCR reduces geometric-mean WNS/TNS violation magnitudes by 86.7%/95.2% versus PigMap3 under position-aware postprocessing, and by 48.6–49.2%/53.3–63.1% versus genetic and annealing under uniform postprocessing.It outperforms PigMap3 in WNS on seven of nine cases and each resynthesis baseline on six of seven cases, with one tie.Source: §I · p. 2

II. PRELIMINARIES

The preliminaries connect technology mapping and timing closure to the paper’s use of relaxed mapping bounds and physical context. They position local logic replacement as complementary to post-placement sizing and buffering.

A. Logic Synthesis and Technology Mapping

  • Cut-based mapping selects compatible implementations to cover required outputs, often from a restricted set of priority cuts, and PCR optimizes legal cut, phase, and cell alternatives obtained with ABC.Technology-independent logic such as an And-Inverter Graph is mapped to library cells.Source: A. Logic Synthesis and Technology… · p. 2

B. Linear Programming Relaxation

  • An LP relaxation enlarges the feasible set and supplies a lower bound, which PCR uses to screen local mapping domains before generating integer candidates.Fractional solutions need not represent realizable mappings.Source: B. Linear Programming Relaxation · p. 2

C. Placement and Timing Closure

  • Static timing analysis combines cell models with placement- or routing-estimated parasitics; WNS measures the largest setup violation and TNS sums negative endpoint slacks.Setup slack is required time minus arrival time; negative slack indicates a violation.Source: C. Placement and Timing Closure · p. 2

D. Post-Placement Timing Optimization

  • Post-placement sizing and buffering adjust drive strengths and interconnect loads, while PCR complements these operations by replacing local logic with equivalent mappings.PCR uses estimated positions and interconnect delays for search and physical evaluation for acceptance.Source: D. Post-Placement Timing Optimization · p. 2

III. APPROACH

PCR iteratively extracts bounded timing-critical windows, formulates context-preserving mapping choices, and screens them before discrete optimization. Reconstructed candidates are physically evaluated before acceptance.

III. APPROACH

  • PCR repeats four stages—timing-driven window extraction, mapping formulation and LP screening, integer mapping and reconstruction, and physical evaluation with iterative update—until timing closes or the search budget is exhausted.Physical checks and global-routing-based timing evaluation precede acceptance.Source: §III · p. 2

A. Timing-Driven Window Extraction

  • Each bounded combinational window is rooted at the worst-slack data endpoint, subject to depth, instance-count, and boundary-input limits, while sequential and macro instances remain outside it.Interface nets, reference timing, external pin loads, and existing cell and boundary positions retain surrounding context; external fanouts remain boundary outputs.Source: A. Timing-Driven Window Extraction · p. 2

B. Mapping Formulation and LP Screening

  • The action graph represents legal cut–phase choices, fanin dependencies, and cell variants; compatible actions are selected jointly to satisfy required outputs.An action specifies a cut and phase implementation, while cell variants include available drive strengths; joint selection accounts for delay dependence on drive and fanout loads.Source: A. Timing-Driven Window Extraction · p. 2, B. Mapping Formulation and LP Screening · p. 2
  • Core constraints connect selected actions to demanded phases, require compatible cells for used gates, and account for boundary outputs serving internal and external loads.The formulation uses frozen RC coefficients and a common timing cap while generating sparse and diverse mappings.Source: B. Mapping Formulation and LP Screening · pp. 2–3
  • LP screening and integer optimization use a frozen delay model to generate sparse and diverse mappings; reconstructed candidates undergo legalization, global routing, and timing analysis before acceptance.The sparse mapping can refresh the model for one additional solve.Source: Figure 1 · p. 3

1) Candidate position and interconnect estimation:

PCR estimates candidate positions and internal interconnect costs before each solve. The estimates inform mapping scores while retaining fixed external timing and output context.

Candidate position and interconnect estimation

  • Candidate node positions move iteratively toward weighted centroids within a local region enclosing the window and interface positions, expanded by 2 µm and clipped to the core.Boundary sources stay fixed; external sinks receive greater weight, and coordinates predict connectivity costs rather than act as placement variables.Source: 1) Candidate position and interconnect… · p. 3
  • For each candidate driver, a Manhattan-length minimum spanning tree approximates the internal fanout net used to estimate wire capacitance and worst-sink Elmore delay.The estimate uses per-unit-length resistance and capacitance, edge length, and downstream sink and wire capacitance.Source: 1) Candidate position and interconnect… · p. 3
  • The first solve uses possible fanouts and maximum available input-pin capacitances; if it finds a sparse mapping, selected topology and cell loads can refresh estimates for at most one additional solve.Both solves share the search budget, while external output RC and downstream timing remain in the fixed reference context.Source: 1) Candidate position and interconnect… · p. 3

2) Delay model and relaxation:

The delay model minimizes target arrival using frozen RC estimates for fanout and boundary-input wires, then relaxes binary selections to screen the modeled search. Its certified bound applies only to the configured candidate domain and current frozen RC model.

2) Delay model and relaxation:

  • The proxy minimizes modeled target arrival using fanout-cell mean input capacitances and maximum boundary-source input-wire estimates for gates driven by window inputs.The input-wire estimate uses Manhattan length; it is zero otherwise.Source: 2) Delay model and relaxation · p. 3
  • Reference STA offsets calibrate local arrivals, external pin loads stay fixed, and each variant's RC correction is constant within a solve, preserving linearity.The model does not predict congestion, obstacle detours, or slew propagation.Source: 2) Delay model and relaxation · p. 4
  • Driver-selection products are encoded by four linear inequalities that are exact for binary variables, making the discrete proxy a mixed-integer linear model.The remaining binary domains are relaxed to [0, 1], with the product constraints retained.Source: 2) Delay model and relaxation · p. 4
  • A certified lower bound above τ + ϵcert, or proven threshold-relaxation infeasibility, rejects the modeled target; the bound covers only the configured domain and frozen RC model.It does not bound timing after routing or a later model update.Source: 2) Delay model and relaxation · p. 4

C. Integer Mapping and Reconstruction

Integer mapping selects gates and connections under the current frozen delay model, restricting actions using LP rankings before jointly choosing actions and compatible cells.

C. Integer Mapping and Reconstruction

  • The integer assignment jointly determines selected gates and their connections under the current frozen delay model.An assignment includes action and cell selections together with continuous timing variables.Source: C. Integer Mapping and Reconstruction · p. 4

1) Restrict the action domain:

  • At each node, the action restriction retains the two highest-ranked LP actions, or all actions when fewer than two are available.Compatible cell variants remain available after the action restriction.Source: 1) Restrict the action domain · p. 4
  • The MIP jointly selects actions and compatible cells subject to dependency and phase constraints, with infeasibility and optimality applying only to restricted domain F′.Source: 1) Restrict the action domain · p. 4

2) Establish feasibility and optimize timing:

The search first seeks a threshold-feasible assignment, then optimizes timing and selects alternatives within a narrow modeled-timing band, subject to its search budget.

2) Establish feasibility and optimize timing:

3) Select two representatives:

The method chooses two representatives at similar modeled timing: one sparse in non-default cell selections and another structurally different from it.

3) Select two representatives:

4) Reconstruct the netlists:

Reconstructed candidates preserve window interfaces and are checked before physical evaluation. Candidates that pass physical timing and cost criteria update the design and guide subsequent endpoint searches.

4) Reconstruct the netlists:

  • Candidates are reconstructed with preserved window interfaces and retained only when their mappings are compatible, realizable, and structurally or cell-distinct.The procedure also recomputes the original cell/load-model score for consistency checks; search uses the RC-augmented score.Source: 4) Reconstruct the netlists · p. 4
  • Table I covers nine completed position-aware pairs with PigMap3, while the reported timing aggregates use add-one smoothing and lower values are better.The ratio is G_method/G_PCR; values above one favor PCR, and timing uses a geometric mean while area and leakage use ordinary geometric means.Source: Table I · p. 5, 4) Reconstruct the netlists · p. 5
  • In Algorithm 1, ⊥ means a solve did not meet its completion criterion; a timeout does not establish infeasibility.For FindFeasible the criterion is feasibility; for optimization it is optimality within solver tolerances.Source: 4) Reconstruct the netlists · p. 5

D. Physical Evaluation and Iterative Update

  • Each candidate is applied to a separate copy of the placed design, then legalized, checked, globally routed, parasitic-estimated, and analyzed with STA under the same settings as the reference.Predicted coordinates inform only the delay model; physical locations are determined during placement and legalization.Source: D. Physical Evaluation and Iterative… · p. 5
  • A candidate is accepted only if WNS and TNS stay within tolerance, at least one improves, and composite cost decreases; accepted designs refresh context and restart search at the worst slack.Otherwise the previous design is retained, remaining representatives are tried, and then search advances to another endpoint; iteration ends at timing closure, the window limit, or the wall-time limit.Source: D. Physical Evaluation and Iterative… · p. 5

A. Experimental Setup

Experiments compare PCR with PigMap3 and OpenROAD resynthesis methods using shared checkpoints, libraries, constraints, and final evaluation settings. The comparisons use distinct physical flows, case sets, and bounded search budgets.

A. Experimental Setup

  • Experiments use ASAP7 libraries and OpenROAD, comparing PCR with PigMap3 and OpenROAD genetic-algorithm and simulated-annealing restructuring methods.The methods use the same initial checkpoint, libraries, timing constraints, and final evaluation settings for each design.Source: A. Experimental Setup · p. 5
  • The nine-case position-aware comparison is against PigMap3, while the seven-case uniform-flow comparison is against annealing and genetic; both report WNS, TNS, standard-cell area, and leakage power.Each table uses a common case set for its methods.Source: A. Experimental Setup · p. 5
  • Each run attempts at most 20 windows under depth-six, 60-instance, 40-boundary-input extraction limits and a time budget of max(1800, ⌈2t_ref + 600⌉) seconds.The endpoint pool is 256; resynthesis and physical-stage timeouts are 7200 and 14400 seconds, respectively, and search budgets are method-specific.Source: A. Experimental Setup · p. 5
  • The local acceptance rule limits WNS/TNS degradation to 0.001 ps and requires improvement exceeding 0.001 ps in at least one timing measure.The stated rule also requires a decrease exceeding 10^-6 in a quantity whose name is cut off in the supplied passage.Source: A. Experimental Setup · p. 5
  • The composite cost combines leakage, negative TNS magnitude, slew violation, and capacitance violation, expressed in µW, ns, ns, and fF, respectively.C = P_leak + 10|min(TNS, 0)| + 20V_slew + 20V_cap.Source: A. Experimental Setup · p. 5

B. Experimental Flow

  • The position-aware flow compares PCR and PigMap3 after detailed placement, setup timing repair, and final detailed placement; the uniform flow adds global placement before and after repair.Both flows reuse the same mapping output, and final checkpoints are evaluated after legalization and global-routing-based timing analysis.Source: B. Experimental Flow · pp. 5–6, Table II · p. 6
  • Timing aggregates use add-one smoothing, with geometric means over seven cases; area and leakage use ordinary geometric means, and values above one in the method-to-PCR ratio favor PCR.The uniform comparison applies to the common seven completed cases.Source: B. Experimental Flow · p. 6

C. Results Analysis

PCR reports lower timing-violation aggregates than PigMap3 in the position-aware flow and than annealing and genetic in the uniform flow. The tables use different case sets and physical flows, so their aggregates are not directly comparable.

C. Results Analysis

  • The tables use different completed case sets and physical flows, so their aggregate values are not directly comparable.Each table reports geometric means and ratios over its own completed cases.Source: C. Results Analysis · p. 6

1) Position-Aware Comparison with PigMap3:

  • Against PigMap3, PCR has better WNS on seven of nine cases, better TNS on eight, closes timing on aes_256 and hidden5, and has lower area on all nine.The aggregate timing advantage reflects both zero-violation cases and large PigMap3 violations on mempool_tile_wrap and hidden1; its magnitude depends on smoothing.Source: 1) Position-Aware Comparison with… · p. 6
  • Only MLCAD partition_m and partition_c accept remapping updates; partition_c improves WNS/TNS over PigMap3 by 37.90/34.95 ps after the complete flow, while partition_m has a 0.52% TNS-violation decrease but WNS worsens by 2.86 ps.The other seven cases retain their input mappings, so the overall advantage reflects complete-flow outcomes rather than isolated remapping gains.Source: 1) Position-Aware Comparison with… · p. 6

2) Uniform Comparison with Annealing and Genetic:

  • Across seven uniform-flow cases, PCR has the best WNS on all seven, including a tie on aes_256, and the best TNS on five, also including that tie.Area and leakage show design-dependent tradeoffs.Source: 2) Uniform Comparison with Annealing… · p. 6

V. CONCLUSION

  • PCR reduces geometric-mean WNS/TNS violation magnitudes by 86.7%/95.2% versus PigMap3 in the position-aware flow, and by 48.6–49.2%/53.3–63.1% versus genetic and annealing in the uniform flow.PCR has better WNS on seven of nine PigMap3 cases and beats each resynthesis baseline on six of seven cases, with one tie.Source: §V · p. 6
Loading 2610.01918v1…