Call for Paper - May 2023 Edition
IJCA solicits original research papers for the May 2023 Edition. Last date of manuscript submission is April 20, 2023. Read More

ILP-based Computer-aided Testing and Optimization of Embedded Core

International Journal of Computer Applications
© 2010 by IJCA Journal
Number 8 - Article 7
Year of Publication: 2010
G. Rohini
S. Salivahanan

G Rohini and S Salivahanan. Article: ILP-based Computer-aided Testing and Optimization of Embedded Core. International Journal of Computer Applications 11(8):33–36, December 2010. Published By Foundation of Computer Science. BibTeX

	author = {G. Rohini and S. Salivahanan},
	title = {Article: ILP-based Computer-aided Testing and Optimization of Embedded Core},
	journal = {International Journal of Computer Applications},
	year = {2010},
	volume = {11},
	number = {8},
	pages = {33--36},
	month = {December},
	note = {Published By Foundation of Computer Science}


The power consumption of a digital circuit can be reduced by decomposing it into sub circuits which can be turned off when inactive. Power can also be reduced by careful state encoding. Clock-gating techniques have been shown to be very effective in the reduction of the switching activity in sequential logic circuits. Modeling a given circuit as a finite-state machine, we formulate its decomposition into submachines as an integer linear programming (ILP) problem. A simple, but powerful state encoding method is used for the submachines to further reduce power consumption. The strategy consists in partitioning the original circuit into two structural sub circuits so that each sub circuit can be successively tested by the Computer Aided Testing (CAT) environment. In partitioning the circuit and planning the test session, the switching activity in time interval (i.e. the average power) power consumption are minimize. To minimize the average switching activity, we search for a small cluster of states with high stationary state probability and use it to create the small sub-FSM.


  • E. Macii, M. Pedram, and F. Somenzi, “High-Level Power Modeling, Estimation, and Optimization”, IEEE Trans. on CAD, vol. 17, 1998, pp. 1061-1079.
  • M. Pedram, “Power Minimization in IC Design: Principles and Application”, ACM TODAES, vol. 1, 1996, pp. 3-56.
  • K. Roy and S. Prasad Circuit Activity Based Logic Synthesis for Low Power Reliable Operations. IEEE Transactions on VLSI Systems, 1(4):503–513, December 1993.
  • J. Monteiro, S. Devadas, and A. Ghosh. Retiming Sequential Circuits for Low Power. In Proceedings of the International Conference on Computer-Aided Design, pages 398–402, November 1993.
  • L. Benini, G. De Micheli, and F. Vermulen, “Finite State Machine Partitioning for Low Power”, Proc. International Symposium on Circuits and Systems, 1998, pp. 5-8.
  • S. H. Chow, Y. C. Ho, T. Hwang and C. L. Liu, “Low Power Realization of Finite State Machines-A Decomposition Approach”, ACM TODAES, vol. 1, 1996, pp. 315-340.
  • J. C. Monterio and A. L. Oliveria, “Finite State Machine Decomposition for Low Power”, Proc. Design Automation Conference, 1998, pp. 758-763.
  • J. C.. Monterio and A. L. Oliveria, “FSM Decomposition by Direct Circuit Manipulation Applied to Low Power Design”, Proc. Asia South Pacific Design Automation Conference, 2000, pp. 351-358.
  • E. Olson and S. Kang, “Low-Power State Assignment for Finite State Machines”, Proc. International Symposium on Low Power Design, 1994, pp. 63-68.
  • C. Y. Tsui, M. Pedram, and A. Despain, “Low-Power State Assignment Targeting Two and Multilevel Implementations”, ZEEE Trans. on CAD, vol. 17, 1998, pp. 1281-1291.
  • H. R. Lewis and C. H. Papadimitriou, “Elements of the Theory of Computation”, Englewood Cliffs, NJ: Prentice-Hall, 1981.
  • E. Hwang, F. Vahid, and Y.-C. Hsu, “FSMD functional partitioning for low power”, 1999.
  • Nainesh Agarwal and Nikitas Dimopoulos,“FSMD Partitioning for Low Power using ILP”, IEEE Computer Society Annual Symposium on VLSI, 2008