Source-linked AI summary
FAPO: Fanout-Aware Post-Mapping Optimization for LUT-Based FPGAs
Xiaoyu Hao, Keren Zhu
TL;DR
Fanout bottlenecks can remain after FPGA LUT technology mapping, while replication can consume area and increase upstream loading. FAPO jointly refines sink assignments and LUT cuts under a final-area constraint, combining minimum-cut proposals with greedy refinement. Across three initial mappers, it reports up to 14.48% lower geometric-mean ATP with a 5% final-area allowance.
Problem
Logic depth alone does not capture LUT fanout loading, and replication to relieve heavily loaded LUTs consumes area and may increase upstream loading.
Source: §I · p. 1Method
FAPO jointly refines sink assignments and LUT cuts under a final-area constraint, evaluating compound changes by resulting live area and timing.
Source: §I · p. 1, A. Coupled refinement under a… · p. 2Results
Across three initial mappers, geometric-mean ATP fell by up to 14.48% with a 5% final-area allowance; VPR routed critical-path delay fell 7.04% relative to ABC if.
Source: §I · p. 1, B. Comparison with Initial Mappings · p. 4, §V · p. 4Takeaways & Limitations
Minimum-cut proposals provide smallest same-cut copy sets covering current critical paths and complement greedy refinement.
Source: §I · p. 1, B. Coordinated replication across… · p. 3
Abstract
from arXiv · showhide
Reducing logic depth during FPGA technology mapping does not necessarily eliminate fanout bottlenecks in the resulting LUT networks.Replicating heavily loaded LUTs can alleviate these bottlenecks, but the added copies consume area and may increase upstream loading. We propose FAPO, a mapper-independent post-mapping optimizer that jointly refines sink assignments and LUT cuts under a final-area constraint.Replication, cut switching, and recovery are evaluated by the resulting live LUT count.We derive a necessary all-critical-path condition for delay reduction and obtain minimum-copy proposals by minimum cut within a restricted same-cut family.These proposals complement greedy refinement, with mappings selected by full-network area and timing.Experiments on EPFL benchmarks with three initial mappers achieve geometric-mean reductions of up to 14.48% in fanout-aware area--timing product (ATP) with a 5% final-area allowance.VPR evaluation shows a 7.04% reduction in routed critical-path delay relative to ABC if.
I. INTRODUCTION
FAPO addresses fanout bottlenecks that logic-depth optimization can leave in LUT networks by coordinating sink assignments and LUT cuts under a final-area constraint. Its minimum-cut proposals complement greedy refinement, and experiments report lower ATP across three initial mappers.
I. INTRODUCTION
- Heavily shared LUTs can create fanout bottlenecks that logic-depth reduction alone does not resolve.Mapping methods can reduce structural depth, yet networks with the same number of logic levels may place different loads on their LUTs.Source: §I · p. 1
- FAPO refinement can complement different mapping flows without relying on their internal representations or search histories.Prior approaches broaden the mapping search space, but their resulting covers can still retain concentrated sink loads.Source: §I · p. 1
- FAPO coordinates sink assignments and LUT cuts under a final LUT budget, evaluating replication, cut switching, and recovery by final live LUT count.These coupled changes matter because replication can increase upstream fanin loads, while cut switching and cleanup or recovery can remove redundant instances.Source: §I · p. 1
- A necessary all-critical-path condition motivates minimum-copy proposals, which complement greedy compound refinement and are selected using remeasured area and timing.The proposals use minimum cut to find the smallest same-cut copy set that intersects every current critical path.Source: §I · p. 1
- Up to 14.48% lower geometric-mean ATP across three initial mappers, with a 5% final-area allowance.The VPR evaluation also reports a 7.04% reduction in routed critical-path delay relative to ABC if.Source: §I · p. 1
II. MAPPED-NETWORK OPTIMIZATION
FAPO imports a legal LUT mapping into a mapper-independent state and refines it subject to a final live-LUT area cap. Its search maintains feasible candidates and selects a mapping by area–timing product.
II. MAPPED-NETWORK OPTIMIZATION
- Each live LUT instance is represented by its logic root, selected K-feasible cut, and served sinks; copies of a root can serve disjoint sink sets with different cuts.Unreachable instances are removed, and the source network provides the reference function for equivalence checking.Source: A. State and final-area constraint · p. 1
- The final mapping must satisfy A(M) ≤ A0 + floor(βA0), with area counting live LUT instances after cleanup and recovery.The final-area constraint allows cleanup and recovery to offset replication costs.Source: A. State and final-area constraint · pp. 1–2
- FAPO refines the imported cover without access to the parent mapper’s internal subject graph or cut database.Algorithm 1 maintains an archive and frontier, optionally admits cut-derived candidates, then selects the minimum-ATP mapping from the seed and finalized archive.Source: A. State and final-area constraint · p. 2
B. Fanout-aware timing and objective
FAPO’s timing model incorporates both logic depth and fanout loading, then searches for low fanout-aware area–timing product while retaining feasible mappings.
B. Fanout-aware timing and objective
- Fanout counts the live LUT-input arcs and primary-output sinks driven by a LUT.Source: B. Fanout-aware timing and objective · p. 2
- The maximum output-driver arrival defines Tα(M), and the mapping-level timing model captures both logic depth and fanout loading.Source: B. Fanout-aware timing and objective · p. 2
- The search targets fanout-aware ATP while retaining nondominated area–timing pairs and requiring acyclicity, K-feasibility, and functional equivalence within the area cap.The original seed remains a protected candidate.Source: B. Fanout-aware timing and objective · p. 2
A. Coupled refinement under a final-area bound
FAPO evaluates replication, cut changes, and recovery together because each operation can alter both live area and timing. Final-area accounting and full-network remeasurement determine whether compound changes are useful.
A. Coupled refinement under a final-area bound
- Replication partitions sinks to reduce a LUT’s output load but adds load to shared fanins, while cut switching can change dependencies and make other instances unreachable.Copy recovery can merge compatible same-root realizations by redirecting their sinks, so each operation’s area and timing effects depend on accompanying transformations.Source: A. Coupled refinement under a… · p. 2
- FAPO charges each compound transformation by the live LUT count after cleanup and recovery, allowing recovered area to offset replication.Source: A. Coupled refinement under a… · p. 2
- Full-network evaluation captures upstream loads and critical-path changes when assessing compound transformations against the final-area bound.The search can spend area where replication improves timing and recover it through compatible cut changes and copy merges.Source: A. Coupled refinement under a… · p. 2
B. Coordinated replication across critical paths
FAPO identifies copy actions that intersect every current critical path, using minimum cut to find the smallest covering set within a restricted same-cut family. It then repartitions sinks and remeasures the network because changed loads can expose new bottlenecks.
B. Coordinated replication across critical paths
- Strict delay reduction requires affecting every current critical path, including tied maximum-weight paths in the critical DAG.The timing recurrence is a node-weighted longest-path problem, with input weights based on fanout and LUT weights adding one logic-delay unit.Source: B. Coordinated replication across… · pp. 2–3
- A same-cut action partitions an eligible LUT’s sinks between the original and one copy with identical root, cut, and fanins.Each action adds one LUT before recovery.Source: B. Coordinated replication across… · p. 3
- Minimum cut finds the smallest set of eligible same-cut copy actions that intersects every current critical path, when a feasible cover exists.A shared vertex can cover several reconvergent paths with one copy; the cut identifies replication sites rather than removing LUTs.Source: B. Coordinated replication across… · p. 3
- Added fanin loads can expose new bottlenecks, so CutBundle remeasures timing and rebuilds the critical DAG after accepted copy sets.Coverage alone does not ensure delay reduction; bounded rounds preserve feasibility and nonincreasing delay.Source: B. Coordinated replication across… · p. 3
C. Combining greedy refinement and cut proposals
FAPO combines greedy compound refinement with minimum-cut proposals that coordinate replication across the complete critical DAG. It retains feasible area–delay tradeoffs and selects a mapping using final area and timing.
C. Combining greedy refinement and cut proposals
- Greedy refinement couples sink assignment, cut switching, and recovery, while minimum cut proposes a smallest covering set in the restricted same-cut family.The two branches address complementary choices.Source: C. Combining greedy refinement and cut… · p. 3
- When α > 0, β > 0, and proposals are available, one minimum-ATP mapping from a bounded Pareto sample supplies the base for CutBundle.Only the greedy branch advances the frontier; each sweep contributes at most one cut proposal, potentially containing multiple copy actions.Source: C. Combining greedy refinement and cut… · p. 3
- Final area recovery precedes minimum-ATP selection from retained mappings and the protected seed, reflecting realized timing benefit and final LUT cost.A cut proposal enters the archive only if it is legal, area-feasible, and strictly reduces delay relative to its base.Source: C. Combining greedy refinement and cut… · p. 3
IV. EXPERIMENTAL EVALUATION
The experiments used EPFL benchmarks and three initial mapping flows. Placement and routing evaluated mappings with VPR on a 40-nm FPGA architecture.
IV. EXPERIMENTAL EVALUATION
- The workstation used for experiments had 128 GB of memory and a 64-core, 128-thread AMD Ryzen Threadripper PRO 7985WX processor.Source: A. Experiment Setup · p. 4
- Experiments used the EPFL benchmark suite, with ABC if, ACD-remap, and AGDMap-D providing initial mappings and baselines.The FAPO framework was implemented in C++.Source: A. Experiment Setup · p. 4
- VPR from VTR 9.0 performed placement and routing using a 40-nm FPGA architecture.Experiments ran on a workstation with a 64-core, 128-thread AMD Ryzen Threadripper PRO 7985WX and 128 GB of memory.Source: A. Experiment Setup · p. 4
B. Comparison with Initial Mappings
Across three initial mappers, FAPO reduced geometric-mean ATP under a 5% final-area allowance, with no circuit-level ATP regression. Ablation and allowance-sensitivity results assess the cut proposals and the effect of available area.
B. Comparison with Initial Mappings
- ATP decreased by 14.48% for ACD-remap, 12.02% for ABC if, and 12.04% for AGDMap-D, with no circuit-level ATP regression.LUT-count increases stayed within the 5% allowance for every circuit.Source: B. Comparison with Initial Mappings · p. 4
C. Search-Strategy Ablation
- FAPO achieved the lowest development-circuit ATP ratio, 0.8553, versus 0.8607 for greedy-only and 0.8757 for minimum-cut-only.Against matched greedy-only search, FAPO/control ATP ratios were 0.9940 overall, a 0.60% additional gain; all strict improvements selected cut-derived mappings.Source: C. Search-Strategy Ablation · p. 4
D. Effect of the Final-Area Allowance
- At 5% allowance, ATP reduction reached 14.48% for ACD-remap, while additional area brought diminishing gains.The allowance sweep selected minimum ATP independently at each setting; Figure 2 plots geometric-mean ATP ratios to the corresponding initial mappers, with lower values better.Source: D. Effect of the Final-Area Allowance · p. 4, Figure 2 · p. 4
E. Post-Route Evaluation
FAPO-refined mappings reduce fanout-aware ATP across three initial mappers and improve routed critical-path delay against ABC if. VPR results show these timing gains with only modest packed-CLB and wirelength ratios.
E. Post-Route Evaluation
- 7.04% lower critical-path delay was measured on EPFL benchmarks after VPR placement and routing, relative to ABC if.Reductions reached 17.84% for i2c, 15.60% for router, and 15.55% for dec; packed CLB and wirelength ratios were 1.0080 and 1.0151.Source: E. Post-Route Evaluation · p. 4
V. CONCLUSION
- Up to 14.48% lower geometric-mean ATP was achieved across three initial mappers with a 5% final-area allowance.VPR evaluation also showed a 7.04% reduction in routed critical-path delay relative to ABC if.Source: §V · p. 4
- FAPO jointly refines sink assignments and LUT cuts, using an all-critical-path condition to guide minimum-copy proposals alongside greedy refinement.It evaluates replication and recovery by final live area and timing.Source: §V · p. 4