Commenced in January 2007
Paper Count: 30172
Estimating Shortest Circuit Path Length Complexity
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.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1077870Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1017
 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.
 S. B. Akers, "Binary Decision Diagram", IEEE Trans. Computers, Vol. 27, pp. 509-516, 1978.
 R. E. Bryant, "Graph-Based Algorithm for BF Manipulation", IEEE Trans. Computers, Vol. 35,, pp. 677-691, 1986.
 C. Scholl, R. Drechsler, and B. Becker, "Functional simulation using binary decision diagrams", Proc. Inter. Conf. of CAD, pp. 8-12, 1997.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 R. Rudell, "Dynamic Variable Ordering for Ordered Binary Decision Diagrams", Proc. of the Intl. Conf. on Computer Aided Design (ICCAD), pp. 42-47, 1993.
 F. Somenzi, "Efficient manipulation of decision diagrams", Inter. Journal on. Software Tools for Technology. Transfer, (STTT), Vol. 3, pp. 171-181, 2001.
 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.
 A. Jain, M. Narayan, and A. Sangiovanni Vincentelli, "Formal Verification of combinational Circuits", Proc. of Intl Conf. on VLSI Design, pp. 218-225, 1997.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 "BrainMaker - User-s Guide and Reference Manual," 7th ed., California Scientific Software Press, 1998.
 F. Somenzi, "CUDD: CU Decision Diagram Package," ftp://vlsi.colorado.edu/ pub/, 2003.
 S., Yang, "Logic synthesis and optimization benchmarks user guide version 3.0," Technical report, Microelectronic Center of North Carolina, Research Triangle Park, NC, 1991.