Fine-grained post placement voltage assignment considering level shifter overhead

Multi-Vdd techniques enable application of lower supply voltage levels on cells with timing slacks. New voltage assignment, placement and voltage island partitioning methods are needed for better utilization of this technology. Our experiments show that in order to have an effective post placement voltage island generation we need to directly consider the energy consumption overhead of the level shifters. We first model the level shifter aware post placement voltage assignment as a 0-1 quadratic programming problem and show that it can be solved in linear time using a 0.879-approximation algorithm. Also, for rectangular voltage island generation we propose an exact modified algorithm as well as a heuristic algorithm both involving the overhead of the level shifters in their cost functions. While the modified algorithm results in better power saving the heuristic algorithm runs with lower time complexity with marginal loss in the quality.