This paper analyzes the patterns of the Monte Carlo
data for a large number of variables and minterms, in order to
characterize the circuit path length behavior. We propose models
that are determined by training process of shortest path length
derived from a wide range of binary decision diagram (BDD)
simulations. The creation of the model was done use of feed forward
neural network (NN) modeling methodology. Experimental results
for ISCAS benchmark circuits show an RMS error of 0.102 for the
shortest path length complexity estimation predicted by the NN
model (NNM). Use of such a model can help reduce the time
complexity of very large scale integrated (VLSI) circuitries and
related computer-aided design (CAD) tools that use BDDs.
[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 Inter. 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 Intl.
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 Inter. 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 Inter. Conf. on Computer Aided Design
(ICCAD), pp. 6-9, 1988.
[15] R. Rudell, "Dynamic Variable Ordering for Ordered Binary Decision
Diagrams", Proc. of the Inter. Conf. on Computer Aided Design
(ICCAD), pp. 42-47, 1993.
[16] F. Somenzi, "Efficient manipulation of decision diagrams", Intl. 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 Inter. 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.
[25] I. Parberry, Circuit Complexity and Neural Networks. MIT Press, 1994.
[26] 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.
[27] 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.
[28] BrainMaker - User-s Guide and Reference Manual, 7th ed., California
Scientific Software Press, 1998.
[29] 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.
[30] F. Somenzi, "CUDD: CU Decision Diagram Package,"
ftp://vlsi.colorado.edu/ pub/., 2003.
[31] S., Yang, "Logic synthesis and optimization benchmarks user guide
version 3.0," Technical report, Microelectronic Centre of North
Caroline, Research Triangle Park, NC, 1991.
[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 Inter. 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 Intl.
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 Inter. 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 Inter. Conf. on Computer Aided Design
(ICCAD), pp. 6-9, 1988.
[15] R. Rudell, "Dynamic Variable Ordering for Ordered Binary Decision
Diagrams", Proc. of the Inter. Conf. on Computer Aided Design
(ICCAD), pp. 42-47, 1993.
[16] F. Somenzi, "Efficient manipulation of decision diagrams", Intl. 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 Inter. 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.
[25] I. Parberry, Circuit Complexity and Neural Networks. MIT Press, 1994.
[26] 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.
[27] 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.
[28] BrainMaker - User-s Guide and Reference Manual, 7th ed., California
Scientific Software Press, 1998.
[29] 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.
[30] F. Somenzi, "CUDD: CU Decision Diagram Package,"
ftp://vlsi.colorado.edu/ pub/., 2003.
[31] S., Yang, "Logic synthesis and optimization benchmarks user guide
version 3.0," Technical report, Microelectronic Centre of North
Caroline, Research Triangle Park, NC, 1991.
@article{"International Journal of Information, Control and Computer Sciences:56880", author = "Namal A. Senanayake and A. Beg and Withana C. Prasad", title = "Learning Monte Carlo Data for Circuit Path Length", abstract = "This paper analyzes the patterns of the Monte Carlo
data for a large number of variables and minterms, in order to
characterize the circuit path length behavior. We propose models
that are determined by training process of shortest path length
derived from a wide range of binary decision diagram (BDD)
simulations. The creation of the model was done use of feed forward
neural network (NN) modeling methodology. Experimental results
for ISCAS benchmark circuits show an RMS error of 0.102 for the
shortest path length complexity estimation predicted by the NN
model (NNM). Use of such a model can help reduce the time
complexity of very large scale integrated (VLSI) circuitries and
related computer-aided design (CAD) tools that use BDDs.", keywords = "Monte Carlo data, Binary decision diagrams, Neural
network modeling, Shortest path length estimation.", volume = "2", number = "3", pages = "799-5", }
