More Web Proxy on the site http://driver.im/

Article

GALLOP: Genetic Algorithm based Low Power FSM Synthesis by Simultaneous Partitioning and State Assignment

Authors:

Ganesh Venkataraman,

Sudhakar M. Reddy,

Irith PomeranzAuthors Info & Claims

VLSID '03: Proceedings of the 16th International Conference on VLSI Design

Page 533

Published: 04 January 2003 Publication History

Abstract

Partitioning has been shown to be an effectivemethod for synthesis of low power finite state machines.In this approach, an FSM is partitioned into two ormore coupled sub-machines such that most of the timeonly one of the sub-machines is active. In this paper,we present a GA based approach for simultaneous partitioning and state assignment of finite state machineswith power reduction as the objective. Experimental results obtained compare favorably with previous works onFSM partitioning, low power state assignment as wellas using GA for partitioning alone.

References

[1]

K. Keutzer and P. Vanbekbergen, "The Impact of CAD on the design of low power digital circuits", Dig. of Papers, IEEE Symp., pp. 42-45, 1994.

[2]

T. Villa and A. Sangiovinni-Vincentilli, "NOVA: State Assignment of finite state machines for optimal two-level logic implementation", IEEE Trans. on CAD, pp.905-924, Sept 1990.

Digital Library

[3]

S. Devadas, H-K. T. Ma, A. R. Newton, and Sangiovinni Vincentilli, "MUSTANG: State Assignment of finite state machines targeting multi-level implementations", IEEE Trans. on CAD, pp.1290-1300, Dec. 1988.

Digital Library

[4]

Chi-Ying Tsui, Massoud Pedram and Alvin Despain, "Low-Power State Assignment Targeting Two and Multilevel Implementations", IEEE Trans. on CAD, pp. 1281-1291, Dec. 1998.

Digital Library

[5]

S. Chattopadhyay, "Low power state assignment and flipflop selection for finite state machine synthesis -a genetic algorithmic approach", IEE Proceedings, pp. 147-151, July-Sept. 2001.

[6]

Jose C. Monteiro and Arlindo L. Oliveira, "FSM decomposition by direct circuit manipulation applied to low power design", ASP-DAC 2000, pp:351-358.

Digital Library

[7]

Luca Benini, Giovanni De Micheli and Frederik Vermulen, "Finite State Machine Partitioning for Low Power", ISCAS 98, pp:5-8.

[8]

Wai-Kwong Lee and Chi-Ying Tsui, "Finite State Machine Partitioning for Low Power", ISCAS 99, pp: 306-309.

[9]

Sue-Hing Chow, Yi-Cheng Ho and Tingting Hwang, "Low Power Realization of Finite State Machines-A Decomposition Approach", ACM Trans. on Design Automation of Electronic Systems, pp. 315-340, July 1996.

Digital Library

[10]

Luca Benini and Giovanni De Micheli, "Automatic Synthesis of Low-Power Gated-Clock Finite-State Machines", IEEE Trans. on CAD, pp. 630-643, June 1996.

Digital Library

[11]

D. Goldberg, "Genetic Algorithms in search, optimization and machine learning", Addison-Welsey, 1989.

Digital Library

[12]

Pinaki Mazumder and Elizabeth M. Rudnick, "Genetic Algorithms in VLSI Design, Layout and Test Automation", Prentice Hall PTR, 1999.

Digital Library

[13]

Shanq-Jang Ruan, Rung-Ji Shang, Feipei Lai and Kun-Lin Tsai, "A Bipolar-Codec Architecture to reduce Power in Pipelined Circuits", IEEE Trans. on CAD, pp:343-348, Feb 2001.

Digital Library

[14]

A. E. A. Almaini, J. F. Miller, P. Thomson and S. Billina, "State Assignment of finite state machines using a genetic algorithm", Computers and Digital Techniques, IEE Proceedings, pp. 279-286, July 1995.

[15]

E. Sentovich, K. Singh, et. al. "SIS: a system for sequential circuit synthesis", Tech. Rep. M92/41, Electronic Research Laboratory, College of Engineering, University of California, Berkeley, 1992.

Cited By

Choudhury PPradhan S(2012)Power modeling of power gated FSM and its low power realization by simultaneous partitioning and state encoding using genetic algorithmProceedings of the 16th international conference on Progress in VLSI Design and Test10.1007/978-3-642-31494-0_3(19-29)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31494-0_3
Nath Pradhan STilak Kumar MChattopadhyay S(2011)Low power finite state machine synthesis using power-gatingIntegration, the VLSI Journal10.1016/j.vlsi.2011.03.00344:3(175-184)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1016/j.vlsi.2011.03.003
Cao COelmann B(2008)Low-power state encoding for partitioned FSMs with mixed synchronous/asynchronous state memoryIntegration, the VLSI Journal10.1016/j.vlsi.2007.02.00241:1(123-134)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1016/j.vlsi.2007.02.002

Index Terms

GALLOP: Genetic Algorithm based Low Power FSM Synthesis by Simultaneous Partitioning and State Assignment
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction
2. Hardware
  1. Integrated circuits
  2. Very large scale integration design

Recommendations

Power modeling of power gated FSM and its low power realization by simultaneous partitioning and state encoding using genetic algorithm
VDAT'12: Proceedings of the 16th international conference on Progress in VLSI Design and Test

Partitioning is an effective method for synthesis of low power finite state machines (FSM). To make the partitioning more effective power gating can be applied to turn OFF the inactive sub-machine. During transition from the states of one sub-machine to ...
Low-power state encoding for partitioned FSMs with mixed synchronous/asynchronous state memory

Partitioned finite state machine (FSM) architectures in general enable low-power implementations and it has been shown that for these architectures, state memory based on both synchronous and asynchronous storage elements gives lower power consumption ...
Canonical finite state machines for distributed systems

There has been much interest in testing from finite state machines (FSMs) as a result of their suitability for modelling or specifying state-based systems. Where there are multiple ports/interfaces a multi-port FSM is used and in testing, a tester is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

VLSID '03: Proceedings of the 16th International Conference on VLSI Design

January 2003

ISBN:0769518680

Copyright © Copyright (c) 2003 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 04 January 2003

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Choudhury PPradhan S(2012)Power modeling of power gated FSM and its low power realization by simultaneous partitioning and state encoding using genetic algorithmProceedings of the 16th international conference on Progress in VLSI Design and Test10.1007/978-3-642-31494-0_3(19-29)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31494-0_3
Nath Pradhan STilak Kumar MChattopadhyay S(2011)Low power finite state machine synthesis using power-gatingIntegration, the VLSI Journal10.1016/j.vlsi.2011.03.00344:3(175-184)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1016/j.vlsi.2011.03.003
Cao COelmann B(2008)Low-power state encoding for partitioned FSMs with mixed synchronous/asynchronous state memoryIntegration, the VLSI Journal10.1016/j.vlsi.2007.02.00241:1(123-134)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1016/j.vlsi.2007.02.002

View Options

View options

Media

Figures

Other

Tables

View Table of Contents