**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**31097

##### Estimating Shortest Circuit Path Length Complexity

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

**Abstract:**

**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.