Accounting for non-linear dependence using function driven component analysis

ABSTRACT

Majority of practical multivariate statistical analyses and optimizations model interdependence among random variables in terms of the linear correlation among them. Though linear correlation is simple to use and evaluate, in several cases non-linear dependence between random variables may be too strong to ignore. In this paper, We propose polynomial correlation coefficients as simple measure of multi-variable non-linear dependence and show that need for modeling non-linear dependence strongly depends on the end function that is to be evaluated from the random variables. Then, we calculate the errors in estimation which result from assuming independence of components generated by linear de-correlation techniques such as PCA and ICA. The experimental result shows that the error predicted by our method is within 1% error compared to the real simulation. In order to deal with non-linear dependence, we further develop a target function driven component analysis algorithm (FCA) to minimize the error caused by ignoring high order dependence and apply such technique to statistical leakage power analysis and SRAM cell noise margin variation analysis. Experimental results show that the proposed FCA method is more accurate compared to the traditional PCA or ICA.

REFERENCES

• 1: Anand Ramalingam , Gi-Joon Nam , Ashish Kumar Singh , Michael Orshansky , Sani R. Nassif , David Z. Pan, An accurate sparse matrix based framework for statistical static timing analysis, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233547]
• 2: C. Visweswariah , K. Ravindran , K. Kalafala , S. G. Walker , S. Narayan, First-order incremental block-based statistical timing analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996663]
• 3: Y. Lin, M. Hutton, and L. He, "Placement and timing for fpgas considering variations," in Proc. Intl. Conf. Field-Programmable Logic and its Application, August 2006.
• 4: L. Cheng, J. Xiong, and L. He, "FPGA performance optimization via chipwise placement considering process variations," in Proc. Intl. Conf. Field-Programmable Logic and its Application, August 2006.
• 5: Sarvesh Bhardwaj , Praveen Ghanta , Sarma Vrudhula, A framework for statistical timing analysis using non-linear delay and slew models, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233546]
• 6: Lerong Cheng , Jinjun Xiong , Lei He, Non-linear statistical static timing analysis for non-Gaussian variation sources, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278541]
• 7: Jaskirat Singh , Sachin Sapatnekar, Statistical timing analysis with correlated non-gaussian parameters using independent component analysis, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1146953]
• 8: Lerong Cheng , Jinjun Xiong , Lei He, Non-Gaussian statistical timing analysis using second-order polynomial fitting, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
• 9: Lerong Cheng , Yan Lin , Lei He, Trace-based framework for concurrent development of process and FPGA architecture considering process variation and reliability, Proceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays, February 24-26, 2008, Monterey, California, USA [doi>10.1145/1344671.1344696]
• 10: Li Tan , Yuanda Cao , Minghua Yang , Qiaoyan He, Modeling Objects with Local Descriptors of Biologically Motivated Selective Attention, Proceedings of the 2008 Fourth International Conference on Natural Computation, p.75-79, October 18-20, 2008 [doi>10.1109/ICNC.2008.649]
• 11: Ho-Yan Wong , Lerong Cheng , Yan Lin , Lei He, FPGA device and architecture evaluation considering process variations, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.19-24, November 06-10, 2005, San Jose, CA
• 12: Yan Lin , Lei He, Interactive presentation: Statistical dual-Vdd assignment for FPGA interconnect power reduction, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 13: Jinjun Xiong , Vladimir Zolotov , Lei He, Robust extraction of spatial correlation, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123011]
• 14: Roger B. Nelsen, An Introduction to Copulas (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 15: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 16: A. Azzalini, "Nonlinear principal component analysis using autoassociative neural networks," AICHE Journal, 1991.
• 17: C. Jutten, "Advances in blind source separation (bss) and independent component analysis (ica) for nonlinear mixtures," International Journal of Neural Systems, Apr 2000.
• 18: 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]
• 19: International Technology Roadmap for Semiconductor in http://public.itrs.net/, 2005.
• 20: International Technology Roadmap for Semiconductor, "A user's guide to MASTAR4," in http://www.itrs.net/models.html, 2005.
• 21: T. Skotnicki, "Heading for decananometer CMOS - Is navigation among icebergs still a viable strategy?," in Solid-State Device Research Conference, pp. 19--33, September 2000.
• 22: H. Shen, S. Jegelka, and A. Gretton, "Fast kernel ICA using an approximate newton method," in 11th International Conference on Artificial Intelligence and Statistic, 2007.
• 23: R. E. Blahut, Algebraic Codes for Data Transmission. Cambridge University Press, 2002.
• 24: A. Azzalini, "The skew-normal distribution and related multivariate families," Scandinavian Journal of Statistics, vol. 32, pp. 159--188, Jun 2005.