Algorytm kodowania stanów wewnętrznych automatu skończonego ze zmienną długością kodu do minimalizacji mocy

• Autorzy: Salauyou V. , Grześ T.

Warianty tytułu

EN

Finite State Machine State Assignment Algorithm with Variable Code Length for Power Minimization

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono dwie heurystyczne metody kodowania stanów wewnętrznych automatów skończonych, których celem jest zminimalizowanie poboru energii: ze stałą i ze zmienną długością kodu. Drugie podejście charakteryzuje się małym kosztem obliczeniowym. Badania eksperymentalne wykazują znaczące zmniejszenie poboru energii w przypadku pierwszej metody w porównaniu z algorytmem NOVA średnio o 39%. Druga metoda w porównaniu z pierwszą pozwala na zmniejszenie poboru energii nawet o 34%.

EN

This paper presents two heuristic methods of encoding the internal states of finite state machine to minimize the power consumption: a fixed and a variable code length. The second approach has low computational cost. Experimental researches show a significant reduction in energy consumption in the first method, compared to the algorithm NOVA average of 39%. The second method compared to the first allows you to reduce power consumption by up to 34%.

Słowa kluczowe

PL

minimalizacja mocy strat przesyłowych; automat skończony; kodowanie stanów

EN

power minimisation; finite state machine; state assignment

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2013
• Tom: R. 89, nr 11
• Strony: 101--104
• Opis fizyczny: Bibliogr. 13 poz., tab.

Twórcy

autor

Salauyou V.

• Politechnika Białostocka, Wydział Informatyki

autor

Grześ T.

• Politechnika Białostocka, Wydział Informatyki

Bibliografia

• [1] Benini L., De Micheli G.: State Assignment for Low Power Dissipation. IEEE Journal on Solid-state Circuits, Vol. 30, No. 3 (1995), pp. 259-268.
• [2] Chattopadhyay S.: Low Power State Assignment and Flipflop Selection for Finite State Machine Synthesis – a Genetic Algorithmic Approach. IEE Proceedings – Computers and Digital Techniques, Volume: 148, Issue: 45, 2001, pp. 147-151.
• [3] Salauyou V., Grzes T.: FSM State Assignment Methods for Low-power Design. Proceedings of 6th International Conference on Computer Information Systems and Industrial Management Applications: CISIM’2007, Ełk, June 28-30, IEEE Computer Society, Los Alamitos 2007, pp. 345-348.
• [4] Shiue W.-T.: Novel State Minimization and State Assignment in Finite State Machine Design for Low-power Portable Devices. Integration, the VLSI Journal, Volume 38, Issue 4 (April 2005), pp. 549-570.
• [5] Xia Y., Ye X., Wang L., Tao W., Almaini A.: A Uniform Framework of Low Power FSM Partition Approach. International Conference on Communications, Circuits and Systems Proceedings, Guilin, 25-28 June 2006, Volume 4, p. 2642-2647.
• [6] Tiwari A. Tomko K.A.: Saving Power by Mapping Finite-state Machines into Embedded Memory Blocks in FPGAs. Proceedings of Design, Automation and Test in Europe Conference and Exhibition, 16-20 Feb. 2004, Vol. 2, pp. 916-921.
• [7] Grzes T., Salauyou V., Bulatava I.: Algorithms of coding the internal states of finite-state machine focused on the reduced power consumption. Radioelectronics and Communications Systems, 2010, V. 53, No. 5, pp. 265-273.
• [8] Grzes T., Salauyou V., Bulatava I.: Power estimation methods in digital circuit design. Optoelectronics, Instrumentation and Data Processing, 2009, V. 45, No. 6, pp. 576-583.
• [9] Tsui C.-Y., Monteiro J., Devadas S., Despain A.M., Lin B.: Power Estimation Methods for Sequential Logic Circuits. IEEE Transactions on VLSI Systems, Vol. 3, No. 3 (1995), pp. 404-416.
• [10] Villa T., Vincentelli A.S.: NOVA: State Assignment of Finite State Machines for Optimal Two-level Logic Implementation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume 9, Issue 9, Sep 1990, pp. 905-924.
• [11] Lin B., Newton A. R.: Synthesis of Multiple Level Logic from Symbolic High-Level Description Languages. Proceedings of the IFIP Conference on VLSI, Munich, West Germany, August 1989, pp. 187-196.
• [12] Sentovich E.M., Singh K.J., Lavagno L., et al.: SIS: A system for sequentional circuit synthesis. Memorandum № UCB/ERL M92/41, Electronics Research Laboratory, Department of Electrical Engineering and Computer Science, University of California, Berkley, May 1992. http:www.eesc.berkeley.edu/Pubs./TechRpts/1992/ERL-92-41.pdf
• [13] Yang S.: Logic synthesis and optimization benchmarks user guide. Version 3.0. Technical Report. North Carolina. Microelectronics Center of North Carolina, 1991.