Analytical review on a theme of master's work. Description of own results

Theme urgency

Digital systems are widely used as basic elements of computer technologies, automatics, robotics, manufacturing, transport. Creation of very large-scale integration circuits (VLSI), building of systems-on-chip (SoC), development of field-programmable gate arrays (FPGAs) and complex programmable logic devices (CPLDs) changed the basis of implementation digital systems and proposed increased requirements to the process of their design, which has led to the widespread using of computer-aided design (CAD) tools and hardware description languages (HDLs). All this should raise quality of the resultant product, promote in realization of multifold analysis and testing. Besides, new base-oriented methods of combinational and sequential synthesis of logical circuits were created, the greatest effectiveness from which can be reached in the case of application automation and joint combined using with already known algorithms.

Model of Moore finite state machine (FSM, offered by E. Moore in 1956 and named in his honor), as synchronous sequential circuit, is the part of numerous digital systems and is used in construction of control devices. High complexity of integrated circuits (which is increasing, according to the G. Moore's law) and theoretical basis of automatic calculations make possible the implementation of comprehensive algorithms of processing information. However direct realization of algorithms can lead to inefficient using of crystal's resources and extension of project's cost.

The number of methods of Moore FSM's hardware optimization is known: minimization of the amount of states (state reduction) and their specific encoding (state assignment), using features of target basis and algorithm of functioning, multilevel logic circuit's implementation. Mentioned methods are quite effective, but for getting the most economic FSM's implementation they have to be used jointly.

Master's work is dedicated to the actual scientific task of development a unified approach to the synthesis of Moore FSM, which is directing on hardware amount reduction in resultant device and is including algorithmic, combinatory and circuitry optimizing techniques. FPGAs by Xilinx, which combine functionality, programmability and availability to consumers, are used as the target basis. CAD Xilinx ISE, Verilog HDL and Java SE are applied as tools of the research.

Goal and tasks of the research

Development of an approach to the unification of synthesis Moore FSM, directing on hardware amount reduction in FPGA is the goal of research.

Main tasks of the research:

1. Analysis methods of minimization amount of states in completely and incompletely specified Moore FSM.
2. Estimation ways of hardware amount reduction with the help of encoding states of Moore FSM.
3. Search and detection characteristics of existing construction methods of logic circuits of Moore FSM and estimation possibilities of their use on FPGA.
4. Association of functionally different optimization directions of Moore FSM hardware amount into the unified approach to synthesis and formation recommendations for it's use.
5. Design of alternative variants of basic stages of unified Moore FSM synthesis process and estimate of it's efficiency.

Research object: Moore FSM synthesis.

Research subject: association of hardware amount reduction methods at Moore FSM implementation on FPGA.

An approach to the unification of synthesis of Moore FSM on FPGA

An approach to the unification of synthesis of Moore FSM on FPGA is offered in article [1]. It joints several possibilities of optimization and is directed on FPGA (fig. 1). Entity of an approach consists in sequential application of algorithmic, combinatory and circuitry stages and using FPGA-oriented tools: CAD and HDLs.

Figure 1 – An approach to the unification of synthesis of Moore FSM

On the first step of algorithmic stage of synthesis, arbitrary Moore FSM specification is led to a uniform type – state transition table. Necessity of leading to a uniform type is caused by possibility of specification Moore FSM with the help of different representation forms, such as: graph schemes of algorithm, state diagrams, ASM-diagrams (ASM – Algorithmic State Machine) [2-4]. Second step of algorithmic stage consists of minimization of the state transition table. Algorithms of Brzozowski, ARNES, SMAS, CHESMIN, SLIM, HSM2, STAMINA, OPTIMIST, BICA, ISM can be used for this [3, 5-16].

Combinatory stage is directed on effective encoding of minimized transition table's states and, also, on receiving of hardware-minimum functions of the next state and, at necessity, of output functions of FSM. Considerable influence of states encoding method on parameters of resultant logical circuit caused development of various approaches, directed on decreasing of power expenses, high-speed performance, minimization of hardware amount. The last one of these approaches can be used on combinatory stage of synthesis with the help of application, adaptation and modification of MUSTANG, MUSE, FEL-Code, JEDI, NOVA, Two-Hot Encoding, DISA, one-hot and positional-binary states encoding algorithms [17-37].

Circuitry stage of synthesis process assumes using Moore FSM logical circuit's construction methods, directing on reduction of hardware amount of target chip. Trivial and multilevel implementations, structures with transformation of objects codes, circuits on counters can be carried to these methods [37]. Modern digital design is oriented on using HDLs (basically, VHDL and Verilog), because of what the second step of circuitry stage is development of HDL program, which describes Moore FSM and is suitable for processing of appropriate CAD and immersion into the chip.

The described unified synthesis process can be successfully implemented automatically and assume only user's administrative functions: describing of Moore FSM and choosing algorithms and structures, which should be used. Moreover, presented approach can be applied to the number of other modern basis (CPLD, ASIC) and define the general direction of optimizing works at synthesis of logic sequential circuits.

Five Verilog-programs, describing given Moore FSM [38] (fig. 2) in various ways, were designed for an estimation of unified synthesis process application to the exact example:

Figure 2 – State diagram of Moore FSM
(animation: 10 frames, 5 cycles of repeating, 160 kilobytes)
(x_i – input signals, y_i – bites of state code, z_i – output signals)

1. Implementation of not minimized Moore FSM with the help of XST (Xilinx Synthesis Technology) analyzer [39] (experiment 1).
2. Implementation of minimized Moore FSM with the help of XST (Xilinx Synthesis Technology) analyzer (experiment 2).
3. Implementation of minimized Moore FSM on two–level circuit [40] with positional-binary states encoding. Use of ROM with asynchronous reading [39] (experiment 3).
4. Implementation of minimized Moore FSM on two–level circuit with positional-binary states encoding. Use of ROM with synchronous reading [39] and an additional signal of synchronization (experiment 4).
5. Implementation of minimized Moore FSM on two–level circuit with positional-binary states encoding. Use of ROM with synchronous reading and back front of the main signal of synchronization (experiment 5).

All researches were held with the help of CAD Xilinx ISE 13.1 for the family of FPGA Xilinx Spartan-3, namely for the chip XC3S200. Results for cumulative hardware amount for five variants of implementation are graphically shown on fig. 3.

Figure 3 – Results of experiments

If the goal of optimization is amount of LUT-cells, the best result has been received at use of two–level implementation of minimized Moore FSM with synchronous ROM and two signals of synchronization (experiment 4). In comparison with experiment 1, number of slices has decreased in 3 times, number of flip-flops – in 1,5 times, number of LUT-cells – in 2,5 times. However in this case has increased the total of circuit's outputs, number of synchronization signals and one RAM (Random Access Memory) module has been involved.

In the process of abstract writing the master's work hasn't been finished yet. Date of finish: December, 2011. The full thesis of master's work and materials according to the theme may be received from the author or his scientific advisor after the pointed date.

References

1. Ковалев С.А. Подход к унификации процесса синтеза МПА Мура для FPGA / С.А. Ковалев, И.Я. Зеленёва, Е.Р. Татолов // Материалы Двенадцатого международного научно-практического семинара «Практика и перспективы развития партнерства в сфере высшей школы». – Донецк-Таганрог, 2011. – Том 2. – С. 45-48.
2. Mano M. Digital design / M. Mano. – Prentice Hall, 2003. – 516 pp.
3. Nelson V. Digital logic circuit analysis and design / V. Nelson, H. Nagle, J. Irwin, B. Carroll. – Prentice Hall, 1995. – 842 pp.
4. Barkalov A.A. Synthesis of operational and control automata / A.A. Barkalov, L.A. Titarenko. – Donetsk: DonNTU, TechPark DonNTU UNITECH, 2009. – 256 pp.
5. Avedillo M.J. New approach to the state reduction in incompletely specified sequential machines / M.J. Avedillo, J.M. Quintana, J.L. Huertas // Proceedings of IEEE International Symposium on Circuits and Systems. – New Orleans, 1990. – pp. 440-443.
6. Avedillo M.J. SMAS: a program for the concurrent state reduction and state assignment of finite state machines / M.J. Avedillo, J.M. Quintana, J.L. Huertas // Proceedings of IEEE International Symposium on Circuits and Systems. – 1991. – vol. 3. – pp. 1781-1784.
7. Champarnaud J.-M. Split and minimizing: Brzozowski's algorithm / J.-M. Champarnaud, A. Khorsi, T. Paranthoen // Prague Stringology Conference. – Prague, 2002. – pp. 96-104.
8. Goren S. CHESMIN: a heuristic for state reduction in incompletely specified finite state machines / S. Goren, F. Ferguson // Proceedings of the Conference on Design, Automation and Test in Europe. – 2002. – pp. 248-254.
9. Higuchi H. A fast state reduction algorithm for incompletely specified finite state machines / H. Higuchi, Y. Matsunaga // 33rd Annual Conference of Design Automation. – Las Vegas, 1996. – pp. 463-466.
10. Hu H. HSM2: a new heuristic state minimization algorithm for finite state machine / H. Hu, H.-X. Xue, J.-N. Bian // Journal of Computer Science and Technology. – 2004. – № 19 (5). – pp. 729-733.
11. Rho J.-K. Exact and heuristic algorithms for the minimization of incompletely specified state machines / J.-K. Rho, G. Hachtel, F. Somenzi, R. Jacoby // IEEE Transactions on Computer-Aided Design. – 1994. – vol. 13. – pp. 167-177.
12. Xu Y. Describing an n log n algorithm for minimizing states in deterministic finite automaton [Электронный ресурс]. – Режим доступа: http://www.cs.sun.ac.za/rw711/documentation/hopcroft2.pdf.
13. Fuhrer R.M. OPTIMIST: state minimization for optimal 2-level logic implementation / R.M. Fuhrer, S.M. Nowick // Proceedings of International Conference of Computer-Aided Design. – 1997. – pp. 308-315.
14. Pena J.M. A new algorithm for exact reduction of incompletely specified finite state machines / J.M. Pena, A.L. Oliveira // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. – 1999. – vol. 18 (11). – pp. 1619-1632.
15. Kam T. A fully implicit algorithm for exact state minimization / T. Kam, T. Villa, R. Brayton, A. Sangiovanni-Vincentelli // Proceedings of the Design Automation Conference. – 1994. – pp. 684-690.
16. Almeida M. On the performance of automata minimization algorithms / M. Almeida, N. Moreira, R. Reis // Technical Report Series: DCC-2007-03. – 2007. – 12 pp.
17. Slusarczyk A. State assignment techniques – short review [Электронный ресурс]. – Режим доступа: http://web.cecs.pdx.edu/~mperkows/nov17/051.slusarczyk-state-assignment-review.pdf.
18. De Micheli G. KISS: a program for optimal state assignment of finite state machines / G. De Micheli, R. Brayton, A. Sangiovanni-Vincentelli // Proceedings of IEEE International Conference of Computer-Aided Design. – Santa Clara, 1984. – pp. 209-211.
19. De Micheli G. Optimal state assignment for finite state machines / G. De Micheli, R. Brayton, A. Sangiovanni-Vincentelli // IEEE Transactions on Computer-Aided Design. – 1985. – pp. 269-285.
20. De Micheli G. Optimal encoding of control logic / G. De Micheli // Proceedings of the International Conference on Circuits and Computer Design. – 1984. – pp. 16-22.
21. El-Maleh A. Finite state machine state assignment for area and power minimization / A. El-Maleh, S.M. Sait, F.N. Khan // Proceedings of IEEE International Symposium on Circuits and Systems. – 2006. – pp. 5303-5306.
22. Devadas S. MUSTANG: state assignment of finite state machines targeting multilevel logic implementations / S. Devadas, H.-K. Ma, A.R. Newton, A. Sangiovanni-Vincentelli // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. – 1998. – vol. 7 (12). – pp. 1290-1300.
23. Du X. MUSE: a multilevel symbolic encoding algorithm for state assignment / X. Du, G. Hachtel, B. Lin, A.R. Newton // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. – 1991. – vol. 10 (1). – pp. 28-38.
24. Kubatova H. FEL-Code: FSM internal state encoding method / H. Kubatova, M. Becvar // Proceedings of 5th International Workshop on Boolean Problems. – Freiberg, 2002. – pp. 109-114.
25. Lin B. Synthesis of multiple level logic from symbolic high-level description languages / B. Lin, A.R. Newton // Proceedings of the International Conference on VLSI. – Munich, 1989. – pp. 187-196.
26. Villa T. NOVA: state assignment of finite-state machines for optimal two-level logic implementation / T. Villa, A. Sangiovanni-Vincentelli // IEEE Transactions on Computer-Aided Design. – 1990. – pp. 905-924.
27. Gupta, B.N.V.M. A state assignment scheme targeting performance and area / B.N.V.M. Gupta, H. Narayanan, M.P. Desai // Proceedings of 12th International Conference on VLSI Design. – 1999. – pp. 378-383.
28. Martinez M. A dynamic model for the state assignment problem / M. Martinez, M.J. Avedillo, J.M. Quintana, J.L. Huertas // Proceedings of Design, Automation and Test in Europe. – Paris, 1998. – pp. 835-839.
29. Golson S. One-hot state machine design for FPGAs / S. Golson // Proceedings of the 3rd PLD Design Conference. – Santa Clara, 1993. – pp. 1-6.
30. Almaini A. State assignment of finite state machines using a genetic algorithm / A. Almaini, J. Miller, P. Thomson, S. Billina // IEEE Proceedings on Computer and Digital Techniques. – 1995. – pp. 279-286.
31. Amaral J. Designing genetic algorithms for the state assignment problem / J. Amaral, K. Turner, J. Chosh // IEEE Transactions on Systems, Man, and Cybernetics. – 1995. – vol. 25. – pp. 659-694.
32. Chyzy M. Evolutionary algorithm for state assignment of finite state machines / M. Chyzy, W. Kosinski // Artificial Intelligence Methods. – Gliwice, 2003. – pp. 51-52.
33. Nedjah N. Evolutionary synthesis of synchronous finite state machines / N. Nedjah, L.M. Mourelle // Evolvable Machines. – Berlin, 2004. – pp. 103-128.
34. Chattopadhyay S. Area conscious state assignment with flip-flop and output polarity selection for finite state machine synthesis – a genetic algorithm approach / S. Chattopadhyay // The Computer Journal. – 2005. – vol. 48 (4). – pp. 443-450.
35. Hasteer G. Parallel algorithms for state assignment of finite state machines. Master's thesis. – University of Illinois, 1996. – 58 pp.
36. Bader D.A. A parallel state assignment algorithm for finite state machines / D.A. Bader, K. Madduri // Proceedings of IEEE Conference on High-Performance Computing. – Bangalore, 2004. – pp. 297-308.
37. Баркалов А.А. Синтез микропрограммных автоматов на заказных и программируемых СБИС / А.А. Баркалов, Л.А. Титаренко. – Донецк: ДонНТУ, Технопарк ДонНТУ УНИТЕХ, 2009. – 336 с.
38. Уилкинсон Б. Основы проектирования цифровых схем / Б. Уилкинсон. – М.: Издательский дом «Вильямс», 2004. – 320 с.
39. XST User Guide for Virtex-4, Virtex-5, Spartan-3, and Newer CPLD Devices [Электронный ресурс]. – Режим доступа: http://www.xilinx.com/support/documentation/sw_manuals/xilinx13_1/xst.pdf.
40. Баркалов А.А. Синтез устройств управления на программируемых логических устройствах / А.А. Баркалов. – Донецк: ДонНТУ, 2002. – 262 с.

© Tatolov E., 2011
© Donetsk national technical university, 2011