Estimating Shortest Circuit Path Length Complexity

Authors: Azam Beg, P. W. Chandana Prasad, S.M.N.A Senenayake

Abstract:

When binary decision diagrams are formed from uniformly distributed Monte Carlo data for a large number of variables, the complexity of the decision diagrams exhibits a predictable relationship to the number of variables and minterms. In the present work, a neural network model has been used to analyze the pattern of shortest path length for larger number of Monte Carlo data points. The neural model shows a strong descriptive power for the ISCAS benchmark data with an RMS error of 0.102 for the shortest path length complexity. Therefore, the model can be considered as a method of predicting path length complexities; this is expected to lead to minimum time complexity of very large-scale integrated circuitries and related computer-aided design tools that use binary decision diagrams.

Keywords: Monte Carlo circuit simulation data, binary decision diagrams, neural network modeling, shortest path length estimation

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1077870

References:

[1] K. Priyank, "VLSI Logic Test, Validation and Verification, Properties & Applications of Binary Decision Diagrams", Lecture Notes, Department of Electrical and Computer Engineering University of Utah, Salt Lake City, UT 84112.
[2] S. B. Akers, "Binary Decision Diagram", IEEE Trans. Computers, Vol. 27, pp. 509-516, 1978.
[3] R. E. Bryant, "Graph-Based Algorithm for BF Manipulation", IEEE Trans. Computers, Vol. 35,, pp. 677-691, 1986.
[4] C. Scholl, R. Drechsler, and B. Becker, "Functional simulation using binary decision diagrams", Proc. Inter. Conf. of CAD, pp. 8-12, 1997.
[5] D. K. Pradhan, A. K. Singh, T. L Rajaprabhu, A. M. Jabir, "GASIM: A Fast Galois Filed Based Simulator for Functional Model", IEEE Proc. of HLDVT-05, pp. 135-142, 2005.
[6] S. Nagayama, and T. Sasao, "On the minimization of longest path length for decision diagrams", Proc Inter. Workshop on Logic and Synthesis (IWLS-2004),pp. 28-35, 2004.
[7] P.W. C. Prasad, M. Raseen, A. Assi, and S. M. N. A. Senanayake, "BDD Path Length Minimization based on Initial Variable Ordering", Journal of Computer Science, Science Publications, Vol. 1(4), pp. 521-529, 2005.
[8] Y. Liu, K. H. Wang, T. T. Hwang, and C. L. Liu, "Binary decision Diagrams with minimum expected path length", Proc. of DATE 01, pp. 708-712, 2001.
[9] R. Ebendt, S. Hoehne, W. Guenther, and R. Drechsler, "Minimization of the expected path length in BDDs based on local changes", Proc. of Asia and South Pacific Design Automation Conf. (ASP-DAC-2004), pp. 866- 871, 2004.
[10] R. Ebendt, and R. Drechsler, "On the Exact Minimization of Path- Related Objective Functions for BDDs", Proc. of Intl. Conf. on Very Large Scale integration (IFIP VLSI-SOC), pp. 525-530, 2005.
[11] N. Drechsler, M. Hilgemeier, G. Fey, and R. Drechsler, "Disjoint Sum of Product Minimization by Evolutionary Algorithms", Proc. of Applications of Evolutionary Computing, Evo.Workshops, pp. 198-207, 2004.
[12] S. Nagayama, A. Mishchenko, T. Sasao, and J.T. Butler, "Minimization of average path length in BDDs by variable reordering", Proc. of Inter. Workshop on Logic and Synthesis, pp: 207-213, 2003.
[13] M. Fujita, H. Fujisawa, and N. Kawato, "Evaluation and Improvements of Boolean Comparison Method Based on Binary Decision Diagrams", Proc. of Intl. Conf. on Computer Aided Design (ICCAD), pp. 2-5, 1988.
[14] S. Malik, A. Wang, R. Brayton, and A. Sangiovanni-Vincentelli, "Logic Verification Using Binary Decision Diagrams in a Logic Synthesis Environment", Proc. of the Intl. Conf. on Computer Aided Design (ICCAD), pp. 6-9, 1988.
[15] R. Rudell, "Dynamic Variable Ordering for Ordered Binary Decision Diagrams", Proc. of the Intl. Conf. on Computer Aided Design (ICCAD), pp. 42-47, 1993.
[16] F. Somenzi, "Efficient manipulation of decision diagrams", Inter. Journal on. Software Tools for Technology. Transfer, (STTT), Vol. 3, pp. 171-181, 2001.
[17] G. Fey, J. Shi and R. Drechsler, "BDD Circuit Optimization for Path Delay Fault-Testability", Proc. of EUROMICRO Symposium on Digital System Design, pp. 168-172, 2004.
[18] A. Jain, M. Narayan, and A. Sangiovanni Vincentelli, "Formal Verification of combinational Circuits", Proc. of Intl Conf. on VLSI Design, pp. 218-225, 1997.
[19] M. Lindgren, H. Hansson, and H. Thane, "Using Measurements to Derive the Worst-case Execution Time", Proc. of 7th Inter. Conf. on Real-Time Systems and Applications (RTCSA-00), pp. 15-22, 2000.
[20] V. Bertacco, S. Minato, P. Verplaetse, L. Benini, and G. De Micheli, "Decision Diagrams and Pass Transistor Logic Synthesis", Stanford University CSL Technical Report, No. CSL-TR-97-748, 1997.
[21] R. S. Shelar and S. S. Sapatnekar, "Recursive Bi-partitioning of BDD's for Performance Driven Synthesis of Pass Transistor Logic", Proc. of IEEE/ACM ICCAD, pp. 449-452, 2001.
[22] M. Nemani and F. N. Najm, "High-Level Power Estimation and the Area Complexity of BFs", Proc. of IEEE Inter. Symposium on Low Power Electronics and Design, pp. 329-334, 1996.
[23] N. Ramalingam, and S. Bhanja, "Causal Probabilistic Input Dependency Learning for Switching model in VLSI Circuits", Proc. of ACM Great Lakes Symposium on VLSI, pp. 112-115, 2005.
[24] P. E. Dunne, and W. van der Hoeke, "Representation and Complexity in Boolean Games", Proc. 9th European Conf. on Logics in Artificial Intelligence, LNCS 3229, Springer-Verlag, pp. 347-355, 2004. I. Parberry, Circuit Complexity and Neural Networks. MIT Press, 1994.
[25] L. Franco, M. Anthony, "On a generalization complexity measure for BFs", IEEE Conference on Neural Networks, Proc. of IEEE International Joint Conference on Neural Networks, pp. 973-978, 2004.
[26] L. Franco, "Role of function complexity and network size in the generalization ability of feedforward networks", Lecture Notes in Computer Science, v 3512, Computational Intelligence and Bioinspired Systems: 8th International Workshop on Artificial Neural Networks, IWANN 2005, Proceedings, pp. 1-8, 2005.
[27] P.W.C. Prasad, A. Assi, and A. Beg, "Predicting the Complexity of Digital Circuits Using Neural Networks", WSEAS Transaction on Circuits and Systems, Vol. 5(6), pp. 813-820, 2006.
[28] A. Beg, P. W. C. Prasad, and A. Beg, "Applicability of Feed-Forward and Recurrent Neural Networks to Boolean Function Complexity Modeling," Expert Systems With Applications (Elsevier), (in press) November 2008, Vol. 36, No. 1.
[29] A. K. Singh, A. Beg and P. W. C. Prasad, "Modeling the Path Length Delay (LPL) Projection," In Proc. International Conference for Engineering and ICT, ICEI 2007, Melaka, Malaysia, November 27-28, 2007, pp. X.
[30] P. W. C. Prasad and A. Beg, "A Methodology for Evaluation (APL) Time Approximation," In Proc. IEEE International Midwest Symposium on Circuits and Systems, MWSCAS/NEWCAS 2007, Montreal, Canada, August 5-8, 2007, pp. 776-778.
[31] A. Beg, P. W. C. Prasad, M. Arshad, and K. Hasnain, "Using Recurrent Neural Networks for Circuit Complexity Modeling", In Proc. IEEE INMIC Conference, Islamabad, Pakistan, December 23-24, 2006, pp. 194-197.
[32] P. W. C. Prasad, A. K. Singh, A. Beg, and A. Assi, "Modeling the XOR/XNOR Boolean Functions' Complexity using Neural Networks," In Proc. IEEE International Conference on Electronics, Circuits and Systems, ICECS 2006, Nice, France, December 10-13, 2006, pp. 1348- 1351.
[33] A. Beg and P. W. C. Prasad, "Data Processing for Effective Modeling of Circuit Behavior," In Proc. WSEAS International Conference on Evolutionary Computing EC-07, Vancouver, Canada, June 18-20, 2007, pp. 312-318.
[34] P. W. C. Prasad and A. Beg, "Data Processing for Effective Modeling of Circuit Behavior," Expert Systems with Applications, (in press) Vol. 38, No. 4.
[35] "BrainMaker - User-s Guide and Reference Manual," 7th ed., California Scientific Software Press, 1998.
[36] F. Somenzi, "CUDD: CU Decision Diagram Package," ftp://vlsi.colorado.edu/ pub/, 2003.
[37] S., Yang, "Logic synthesis and optimization benchmarks user guide version 3.0," Technical report, Microelectronic Center of North Carolina, Research Triangle Park, NC, 1991.