A Max Weighted-Matching Based Non-Greedy Post-HLS Power Gating Technique with Comprehensive Power Modeling

In the era of high-speed nanoscale VLSI that inherently consumes high power, incorporating power management mechanisms is very critical in every stage of the VLSI design flow. In most VLSI design methodologies, power gating (PG) is an effective power-minimization technique typically applied after the high-level synthesis (HLS) stage. PG constructs power islands (PIs), where each PI is a cluster of similarly-idle functional units (FUs) of an HLS solution, and employs additional control logic to control sleep periods of FUs. Thereby, the leakage power of a power-driven HLS solution is further reduced by periodically shutting down unused/idle FUs in PIs. This work proposes a max weighted-matching based power gating technique (WM-PG) with the following novel aspects: (1) A much more comprehensive power model than in previous PG works with a detailed PI sleep controller, and an H-tree based sleep-signal routing to estimate its wirelength and thus dynamic power. (2) A non-greedy power-driven PI-formation process that has a lookahead component as well as the flexibility of migrating FUs between PIs to prevent getting stuck at a local minima. Our results show that for the media data flow graph (DFG) benchmark suite and a few large-size random DFGs, WM-PG has an average power reduction of 39.4% compared to the initial non-PG'ed HLS solution. Further, it achieves a total power reduction of up to 44.9% and an average of 34.5%, while also having an average total area reduction of 9.2% compared to a state-of-the-art near-optimal power-gating technique. The “worst average-case” complexity of WM-PG is O(n<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup>) and the empirical average-case complexity is O(n<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>), where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> is the number of FUs. It processes all 17 DFGs in only 24 seconds.