CoEvoP&R: Co-Evolving Placement Objectives with Routing Feedback via Large Language Models

Technical Summary: CoEvoP&R

Problem Statement
Modern analytical placers, such as DREAMPlace, rely on differentiable objective functions to guide global placement. These objectives typically combine intermediate surrogate metrics, such as smooth approximations of half-perimeter wirelength (HPWL) and cell-density penalties. However, a significant misalignment exists between these placement-stage surrogates and the final quality of the routed design, including timing metrics like Worst Negative Slack (WNS) and Total Negative Slack (TNS).

Prior attempts to bridge this gap fall into two categories, both with limitations:

1. Human-designed terms: Methods like Rectangular Uniform wire DensitY (RUDY) incorporate routing demand estimates but rely on expert approximations that often require retuning across different designs or technologies.
2. Learned black-box surrogates: Approaches like LaMPlace, GOALPlace, and RoutePlacer use learned predictors or differentiable routability surrogates. While effective, these "black-box" components are difficult to explain, debug, or deploy within existing analytical placement flows that require symbolic, differentiable objectives.

Methodology
CoEvoP&R (Co-Evolving Placement Objectives with Routing Feedback) addresses these limitations by introducing a Large Language Model (LLM)-based framework that automatically evolves readable, differentiable analytical placement objectives. The system operates as a closed-loop evolutionary process consisting of three primary stages:

1. Archive-Conditioned Proposal:
   At each generation, the system assembles a prompt for the LLM. This prompt includes:

   • A restricted objective interface defining the allowable syntax and components.
   • Baseline context and the parent objective from the previous generation.
   • An archive of prior candidates, including their behavioral metrics and failure lessons.
   • Measured feedback from placement, timing proxies, and routing tools.
     The LLM generates a candidate symbolic program (a Python-like script) that defines an initialization map, an update map for schedule variables, and a loss function.

2. Candidate Validation and Embedding:
   Proposed symbolic programs are not immediately executed. They undergo a validation process to ensure they are differentiable, bounded, and executable within the DREAMPlace framework. Validated candidates are embedded into the placer, where they replace the native objective function. The system ensures that the generated objectives remain compatible with gradient-based optimization.

3. Cost-Scaled Evaluation and Archive Update:
   To manage computational costs, CoEvoP&R employs a tiered evaluation strategy:

   • Tier A: Runs the analytical placer for all validated candidates, recording HPWL, overflow, and convergence traces.
   • Tier B: Applies a timing proxy to selected candidates to estimate WNS/TNS improvements.
   • Tier C: Schedules the actual router for a subset of high-potential candidates to measure post-route wirelength, congestion, and timing.

   The system uses a MAP-Elites archive to store successful candidates. Each candidate is mapped to a feature cell based on its complexity, mechanism family, and behavioral metrics (HPWL, overflow, timing). The archive is updated using Pareto dominance over the available metrics, preserving diversity across different behavioral niches. Negative memory stores failed candidates and their failure reasons to prevent the LLM from repeating invalid mechanisms in future prompts.

Key Contributions
The paper claims four novel contributions:

• LLM Objective Evolution: The first automated framework to evolve analytical placement objective functions integrated with real placement and routing tools, moving beyond static or human-designed terms.
• Automated Validation: A restricted interface ensures that LLM-generated objectives are differentiable, bounded, and executable within analytical placement flows like DREAMPlace.
• Routing-Aware Feedback: The search is guided by downstream routing and timing feedback, allowing the objective to adapt to actual routed quality rather than just placement-stage surrogates.
• Archive-Guided Iteration: The system maintains an archive of objectives paired with their measured feedback (placement, routing, timing, and failure data), using this history to condition future LLM prompts and guide the evolution toward diverse, high-performing solutions.

Experimental Results
The framework was evaluated on eight ChiPBench Nangate45 designs and eight ICCAD 2015 Superblue designs, using three random seeds.

• ChiPBench Nangate45: Compared to native DREAMPlace, CoEvoP&R achieved a 16.9% reduction in routed wirelength and a 36.7% reduction in congestion. It also improved timing by 0.70 ns in WNS and 912 ns in TNS. These results outperformed other automated search methods (e.g., EvoPlace, AutoDMP) and learned surrogates (LaMPlace) in terms of congestion and timing, while maintaining competitive wirelength.
• ICCAD 2015 Superblue: The framework reduced routed wirelength by 5.4% and congestion by 23.2% over the baseline.
• Generalization: A zero-shot transfer experiment (CoEvoP&R-T), where an objective evolved on Nangate45 was applied to Superblue and ASAP7 designs without re-evolution, showed positive gains, suggesting the evolved objectives capture generalizable design principles.
• Ablation Studies: Experiments confirmed that the archive-conditioned iteration and cost-scaled evaluation hierarchy are critical. Removing the archive or using only Tier-A (placement-only) evaluation significantly degraded performance.

Significance
The paper positions CoEvoP&R as a significant step toward making the interface between differentiable placement and downstream physical design flows inspectable and automated. By evolving readable, symbolic objectives rather than black-box models, the method offers a path to optimize Power, Performance, and Area (PPA) metrics without sacrificing the debuggability and integration capabilities required by industrial EDA flows. The authors suggest that this approach validates LLM-guided program evolution as a viable method for optimizing complex engineering objectives where the search space is constrained by physical laws and tool requirements.