Presentation
Delay-Constrained Area Optimisation Using SAT-Based Local Improvement
DescriptionThis paper presents a new approach for minimising Boolean circuits subject to delay constraints.
The proposed approach extends the efficient but purely area-based Boolean circuit minimiser eSLIM.
The eSLIM minimiser reduces circuits by iteratively computing optimal replacements for small subcircuits on the fly.
We extend the SAT encoding used, for synthesising these replacements, to take account for delay.
While the additional constraints on delay restrict the set of possible candidates for the replacement, we can still harness the flexibility of making use of Boolean relations and multi-output circuits.
We implemented the proposed method as part of the industrial-strength tool ABC.
Surprisingly, in an experimental evaluation our implementation showed only a rather small deterioration in terms of area improvement, but substantial improvements in terms of delay compared to the purely area-based eSLIM approach on different benchmark sets.
The proposed approach extends the efficient but purely area-based Boolean circuit minimiser eSLIM.
The eSLIM minimiser reduces circuits by iteratively computing optimal replacements for small subcircuits on the fly.
We extend the SAT encoding used, for synthesising these replacements, to take account for delay.
While the additional constraints on delay restrict the set of possible candidates for the replacement, we can still harness the flexibility of making use of Boolean relations and multi-output circuits.
We implemented the proposed method as part of the industrial-strength tool ABC.
Surprisingly, in an experimental evaluation our implementation showed only a rather small deterioration in terms of area improvement, but substantial improvements in terms of delay compared to the purely area-based eSLIM approach on different benchmark sets.
Event Type
Research Manuscript
TimeTuesday, July 284:10pm - 4:23pm PDT
LocationMtg Room 201B