Variability Inspired Implementation Selection Problem

Given a Directed Acyclic Graph and different possible implementations for each node, the Implementation Selection Problem(ISP) selects the appropriate implementation for each node such that a given global design objective is optimized. ISP is a generic formulation that is explicitly or implicitly solved in several design automation problems like leakage optimization using dual Vth , gate sizing, etc. An implementation of a node results in an associated delay and perhaps cost for the node. In the presence of different sources of uncertainty and fabrication variability, fixed estimates of delays and costs of a node are extremely erroneous. In this paper we investigate a probabilistic approach to solve ISP by considering Probability Density Functions for delays and costs of a node. We propose a dynamic-programming based approach in a probabilistic sense and introduce effective pruning criteria when dealing with probability distributions for identifying cooptimal solution at each stage. A case study of leakage optimization using dual Vth is presented where we show the effectiveness of a probabilistic approach considering Vth variability over a traditional deterministic one