Variability inspired implementation selection problem

ABSTRACT

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 V/sub th/, 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. 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 co-optimal solution at each stage. A case study of leakage optimization using dual V/sub th/ is presented where we show the effectiveness of a probabilistic approach considering V/sub th/ variability over a traditional deterministic one.

REFERENCES

• 1: Azadeh Davoodi , Ankur Srivastava, Voltage scheduling under unpredictabilities: a risk management paradigm, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871581]
• 2: Anirudh Devgan , Chandramouli Kashyap, Block-based Static Timing Analysis with Uncertainty, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.607, November 09-13, 2003 [doi>10.1109/ICCAD.2003.41]
• 3: Ankur Srivastava , Majid Sarrafzadeh, Predictability: definition, ananlysis and optimization, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.118-121, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774589]
• 4: Chandu Visweswariah, Death, taxes and failing chips, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775921]
• 5: [5] A. Srivastava E. Kursun and M. Sarrafzadeh. "Predictability Driven Binding: Methodologies and Tradeoffs". In Journal of Circuits, Systems and Computers, Special Issue on Low Power IC Designs, 2002.
• 6: [6] L.P.P.P. van Ginneken. "Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay". In Proc. of International Symposium on Circuits and Systems, pages 865-868, December 1990.
• 7: Shekhar Borkar , Tanay Karnik , Siva Narendra , Jim Tschanz , Ali Keshavarzi , Vivek De, Parameter variations and impact on circuits and microarchitecture, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775920]
• 8: [8] S. Mutah, T. Douseki, Y. Matsuya, T. Aoki, S. Shigematsu and J. Yamada. "I-V Power Supply High-speed Digital Circuit Technology with Multi Threshold Voltage CMOS". In Processings of IEEE Journal of Solid-State Circuits, pages 847-853, August 1995.
• 9: Sani R. Nassif, Modeling and forecasting of manufacturing variations (embedded tutorial), Proceedings of the 2001 conference on Asia South Pacific design automation, p.145-150, January 2001, Yokohama, Japan [doi>10.1145/370155.370308]
• 10: [10] T. Kuroda. "A 0.9 v 150 MHz 10MW 4mm² 2-d discrete cosine transform core processor with variable threshold voltage scheme". In Proc. of IEEE Journal of Solid-State Circuits, pages 1770-1779, Novemebr 1996.