Estimating Shortest Circuit Path Length Complexity

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.

Authors:

• Azam Beg
• P. W. Chandana Prasad
• S.M.N.A Senenayake

Keywords:

• Monte Carlo circuit simulation data
• binary decision diagrams
• neural network modeling
• shortest path length estimation

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.