Search

Introduction. A digital system is a collection of combinational and sequential blocks. Sequential blocks can be divided into library and non-standard classes. The first class includes, for example, counters or shift registers. To implement the circuits of such blocks, standard CAD programs are used. And for the second class, which is the control unit (CU), there are no standard library solutions. This explains the relevance of methods for synthesis and optimization of circuits of non-standard sequential blocks, such as CU. When synthesizing a finite state machine (FSM) circuit, a number of optimization problems arise that are aimed at improving CU characteristics. Methods for solving these problems depend on elemental base characteristics. This paper discusses the implementation of the FSM circuit on a FPGA (field-programmable logic array) basis. The main FPGA blocks that are used for FSM circuit implementation are LUT (look-up table) elements and EMB (embedded memory blocks) elements. Therefore, to solve optimization problems while developing an FSM circuit, it is necessary to reduce the number of these elements. The purpose of the article. This work presents an approach to lower hardware costs in the FSM Mile technique, which uses FPGA for implementation. The method is based on the extended coding of micro-operation sets, in which the set code also includes the transition state code. The state code is partial since it is determined for a set of states upon transition, from which this set is formed. To implement part of the FSM circuit, the built-in memory block EMB is used. If EMB capabilities are not enough to implement the circuit, then part of the circuit is implemented on LUT elements. It is proposed to implement part of the output signals (micro-operations) on EMB. An example of the synthesis of an FSM circuit using the proposed method is given. Results. To study the effectiveness of the proposed method, a comparison was made between the control unit of the known structure (U5) and the control unit obtained using the proposed method (U7). In this case, standard benchmarks from a well-known library were used. Research has shown that U7 can reduce the number of LUTs by 28 % of all benchmarks, and U5 only by 9 %. It is important to note that when implementing the entire 64 % standard MPA circuit, one EMB block is sufficient. Conclusions. The proposed method allows for a reduction in hardware costs (the number of LUT elements). The article shows the conditions for applying the proposed method. Results of experiments examining the effectiveness of the suggested approach to automata implementation with Virtex-7 family chips and the Vivado industrial package are given

A method is proposed for reducing chip area occupied by logic circuits of FPGA-based Mealy finite state machines (FSMs). The proposed method aims at optimization of FSM circuits implemented with look-up table (LUT) elements of FPGA chip. The proposed method combines positive features of such state assignment methods as extended (ESCs) and composite (CSCs) state codes. The method is based on finding a partition of the set of internal states by classes of compatible states. To reduce LUT count, we propose a special kind of states codes named mixed state codes. These codes include two parts. The first part includes the maximum binary codes of states as elements of some partition class. The second part consists of the code of corresponding partition class. Unlike CSCs, the proposed approach allows obtaining partial state codes having different lengths. Unlike ESCs, all partial state codes consist of the same variables. Using mixed state codes allows obtaining LUT-based FSM circuits with exactly two levels of logic. The first level generates partial Boolean functions. The second level combines them into FSM outputs and input memory functions. If some conditions hold, then both levels consist of single-LUT circuits. Example of FSM synthesis based on mixed state codes is shown. The conducted experiments prove that the proposed approach allows reducing hardware compared with FSMs based on JEDI, one-hot state codes, CSCs and ESCs. On average, the proposed method reduces the value of LUT count by 6.21% compared to CSC-based FSMs and 22.21% compared to ESC-based counterparts. The advantages of the proposed approach grow with the growth of FSM complexness. An additional positive effect of the proposed method is a slight increase in the operating frequency.

Introduction. One of the most important blocks of almost any digital system is the control device (CU), since the characteristics of the CU largely determine the characteristics of the system as a whole. In the practice of engineering design, the behavior of the CU is often specified using the Mealy finite state machine (FSM) model. A feature of Mealy FSM is the dependence of systems of Boolean functions that define the circuit on FSM inputs and states. In this article, this feature is taken into account when optimizing the characteristics of FSM circuit in the basis of FPGA chips. When developing FSM circuits, it is necessary to optimize its characteristics, such as performance and hardware costs. FPGAs are one of the most common logic bases for implementing digital systems. FPGA components such as look-up table (LUT) elements, programmable flip-flops, embedded memory blocks (EMBs), and programmable interconnects are sufficient to implement the CU circuit. The purpose of the article. In this paper, we propose a method for reducing hardware costs in the Mealy FSM cirucit implemented in the FPGA basis. In this case, the problem of implementing a circuit in a mixed elemental basis is considered. A mixed basis is understood as the joint use of LUTs and EMBs. The situation is considered when the number of available EMBs is extremely limited, which is quite possible, since EMBs are widely used to implement various operating blocks of digital systems. The main disadvantage of LUTs is the small number of inputs. Modern digital systems can generate signals of logical conditions entering the CU, the number of which is tens of times greater than the number of LUT inputs. This discrepancy between the characteristics of the control algorithm and the number of inputs of the LUTs leads to multilevel CU circuits with an irregular structure of programmable interconnections. To optimize multilevel schemes, the method of replacing input variables is used with the joint use of LUTs and EMB blocks. Results. The analysis of the effectiveness of the proposed method was carried out using the libraries of standard benchmarks FSMs and the Vivado CAD platform. Studies have shown that the proposed method makes it possible to reduce the number of LUTs in the range from 100% to 82%. For 37% of automata, the method of replacing input variables can be applied only in conjunction with the separation of input variables. Conclusions. The proposed method makes it possible to reduce hardware costs (the number of LUTs and their interconnections), delay time, and power consumption. The article shows the conditions for applying the proposed method. The results of studies of the effectiveness of the proposed method for standard automata using chips of the Virtex-7 family and the Vivado industrial package are presented.

Replacement policies have an important role in the functioning of the cache memory of processor cores. The implementation of a successful policy allows us to increase the performance of the processor core and the computer system as a whole. Replacement policies are most often evaluated by the percentage of cache hits during the cycles of the processor bus when accessing the cache memory. The policies that focus on replacing the Least Recently Used (LRU) or Least Frequently Used (LFU) elements, whether instructions or data, are relevant for use. It should be noted that in the paging cache buffer, the above replacement policies can also be used to replace address information. The pseudo LRU (PLRU) policy introduces replacing based on approximate information about the age of the elements in the cache memory. The hardware implementation of any replacement policy algorithm is the circuit. This hardware part of the processor core has certain characteristics: the latency of the search process for a candidate element for replacement, the gate complexity, and the reliability. The characteristics of the PLRUt and PLRUm replacement policies are synthesized and investigated. Both are the varieties of the PLRU replacement policy, which is close to the LRU policy in terms of the percentage of cache hits. In the current study, the hardware implementation of these policies is evaluated, and the possibility of adaptation to each of the policies in the processor core according to a selected priority characteristic is analyzed. The dependency of the rise in the delay and gate complexity in the case of an increase in the associativity of the cache memory is shown. The advantage of the hardware implementation of the PLRUt algorithm in comparison with the PLRUm algorithm for higher values of associativity is shown.

Introduction. The control device is one of the most important blocks of any digital system. The main function of the control device is to coordinate the interaction of the remaining units of the system. Therefore, the characteristics of the control device circuit have a significant impact on the quality of the overall system. To represent the law of functioning of the control device, the models of the microprogrammed automaton (MPA) by Moore and Mealy are used. When synthesizing MPA circuits, it is necessary to solve a number of optimization problems: reducing hardware costs, increasing performance, minimizing power consumption, and jointly optimizing hardware-time characteristics. Methods for solving these problems largely depend on the elemental basis used. Currently, one of the main bases in which modern digital systems are implemented is the FPGA. The main blocks in the FPGA are configurable logic blocks, a programmable interconnect matrix, a timing tree, and programmable inputs and outputs. To implement MPA schemes, two types of configurable logic blocks can be used: tabular logic elements (TLE) and built-in memory blocks (VBP), which have the property of reconfiguration. However, VBPs are widely used to implement various operating blocks of digital systems. Therefore, the controller circuit designer can use a limited number of such memory blocks. Purpose of the article. The article deals with the issues of MPA synthesis when there are a limited number of "free" blocks of EBP. In this case, the microprogram automaton circuit is represented by a network consisting of VBP and TLE blocks. A method for the synthesis of a microprogram automaton with optimization of the number of TLEs is proposed when only one VBP can be used in the microprogram automaton circuit. The proposed method is based on the use of a built-in memory block that performs the replacement of input variables and the coding of the automaton outputs. Results. Studies of the effectiveness of the proposed method were carried out on standard machines. FPGAs of the Virtex-7 family from Xilinx were used as the elemental basis. To implement the proposed MPA, the Vivado package was used. The results of the research showed that the use of the VBP block made it possible to reduce the number of SLE blocks by an average of 14 % – 18 % compared to schemes consisting only of SLE. For the Virtex-7 family FPGA, the number of TLE inputs Io= 6 was sufficient for a single-level implementation of the output system. Conclusions. The effectiveness of the proposed method makes it possible to recommend it for use in the synthesis of microprogram automata under conditions of an extremely limited number of BVPs.

Methods for reducing power consumption in circuits of finite state machines (FSMs) are discussed in this review. The review outlines the main approaches to solving this problem that have been developed over the last 40 years. The main sources of power dissipation in CMOS circuits are shown; the static and dynamic components of this phenomenon are analyzed. The power consumption saving can be achieved by using coarse-grained methods common to all digital systems. These methods are based on voltage or/and clock frequency scaling. The review shows the main structural diagrams generated by the use of these methods when optimizing the power characteristics of FSM circuits. Also, there are various known fine-grained methods taking into account the specifics of both FSMs and logic elements used. Three groups of the fine-grained methods targeting FPGA-based FSM circuits are analyzed. These groups include clock gating, state assignment, and replacing look-up table (LUT) elements by embedded memory blocks (EMBs). The clock gating involves a separate or joint use of such approaches as the (1) decomposition of FSM inputs and (2) disabling FSM inputs. The aim of the power-saving state assignment is to reduce the switching activity of a resulting FSM circuit. The replacement of LUTs by EMBs allows a reduction in the power consumption due to a decrease in the number of FSM circuit elements and their interconnections. We hope that the review will help experts to use known methods and develop new ones for reducing power consumption. We think that a good knowledge and understanding of existing methods of reducing power consumption is a prerequisite for the development of new, more effective methods to solve this very important problem. Although the methods considered are mainly aimed at FPGA-based FSMs, they can be modified, if necessary, and used for the power consumption optimization of FSM circuits implemented with other logic elements.

Introduction. The control unit is one of the most important building blocks of any digital system. The main function of the control unit is to coordinate the interaction between all system blocks. Therefore, the characteristics of a control unit circuit have a significant impact on the quality of the system as a whole. To represent the law of functioning of a control unit, the models of the Moore and Mealy finite state machines (FSM) are used. When synthesizing circuits of FSMs, it is necessary to solve a number of optimization problems, such as the reducing hardware amount, increasing performance, minimizing power consumption, joint optimization of hardware-temporal characteristics. Methods for solving these problems largely depend on the used logical elements. Currently, FPGA microchips are one of the main platforms in which modern digital systems are implemented. The main blocks in the FPGA, which are used in the implementation of FSM circuits, are embedded memory blocks (EMBs), logical blocks LUT (look-up table) and a system of programmable interconnections. The best characteristics are possessed by FSM circuits implemented with EMBs. However, EMBs are widely used to implement various operational blocks of digital systems. Therefore, the designer of a control unit circuitry can use a rather limited number of EMBs. Purpose of the article. The article deals with the extreme case when there is only a single "free" EMB available. In this case, the FSM circuit is represented by a network consisting of this EMB and LUTs. There is proposed a method for the synthesis of an FSM with the optimization of the number of LUTs, when only one EMB block is available for implementing some part of the circuit. The proposed method is based on the using classes of pseudoequivalent states of Moore FSMs. The states are coded in such a way that the state code consists of the code of the class of pseudoequivalent states and the code of a collection of microoperations. Results. Studies of the effectiveness of the proposed method were carried out on standard FSMs. FPGAs of the Virtex-7 family from Xilinx were used as an implementation platform. The research results showed that the proposed method allows reducing the number of LUTs in FSM circuits by 12 % – 19 % in comparison with the known methods. In all cases, only a single EMB was used. Conclusions. The effectiveness of the proposed method allows us to recommend it for use in the synthesis of FSMs if there is of an extreme shortage of EMBs.

Practically, any digital system includes sequential blocks. This paper considers a case when LUT-based sequential blocks are represented by Mealy finite state machines (FSMs). The LUT count is one of the most important characteristics of an FSM circuit. In this paper, a method is proposed which aims at decreasing the LUT counts of FPGA-based Mealy FSMs with mixed encoding of the collections of outputs. To do it, a method of encoding of the fields of compatible states is proposed. The proposed approach leads to LUT-based Mealy FSM circuits having three levels of logic blocks. Each function for any logic level is represented by a circuit including a single LUT. There is given an example of FSM synthesis with the proposed method. The experiments are conducted using standard benchmark FSMs. The results of experiments show that the proposed approach produces LUT-based circuits with fewer LUTs than it is for circuits produced by other investigated methods (Auto and One-hot of Vivado, JEDI, the mixed encoding the collections of outputs). The LUT count is decreased by an average of 6.97 to 62.85 percent. These improvements are accompanied by a slight decrease in the maximum operating frequency. The frequency is decreased by up to 8.09%. The advantages of the proposed method increase as the number of FSM inputs and states increases.

This work proposes a method for hardware reduction in circuits of Mealy finite state machines (FSMs). The circuits are implemented as networks of interconnected look-up table (LUT) elements. The FSMs with twofold state assignment and encoding of output collections are discussed. The method is based on using two LUT-based cores to implement systems of partial Boolean functions. One of the cores uses only maximum binary codes, while the second core is based on the use of extended state codes. The hardware reduction is based on diminishing the number of transformed maximum binary codes. This leads to FPGA-based FSM circuits with three levels of logic blocks. Each logic block has a single level of LUTs. As a result, partial functions are represented by single-LUT circuits. The article shows a step-by-step procedure for the transition from the initial form of the FSM representation to its logical circuit (a network of programmable look-up table elements, flip-flops, and interconnects). The results of experiments conducted with standard benchmarks show that the proposed approach produces LUT-based FSM circuits with significantly better area characteristics than for circuits produced by such methods as Auto and One-Hot of Vivado, JEDI, and twofold state assignment. Compared to these methods, the number of LUTs is reduced from 9.44% to 69.98%. Additionally, the proposed method leads to the following phenomenon: the maximum operating frequency is slightly improved as compared with FSM circuits based on twofold state assignment (up to 0.6%). The negative effect of these improvements is an increase in power consumption. However, it is extremely insignificant (up to 1.56%). As the values of the FSM’s main characteristics grow, there is an increase in the gain from the application of the proposed method. The conditions for applying the proposed method are determined. A generalized architecture consisting of three blocks of partial functions and a method for synthesizing an FSM with this architecture are proposed. A method for selecting one of the seven architectures generated by the generalized architecture is proposed.

This study focuses on creating and investigating models that optimize load balancing in communication networks by managing routing and traffic limitations. The purpose is to use these models to optimize the network’s routing and traffic limitations while ensuring predictable quality of service levels, and adhering to traffic engineering requirements for routing and limiting traffic at the network edge. In order to achieve this aim, a mathematical optimization model was developed based on a chosen optimality criterion. Two modifications of the traffic engineering routing were created, including the linear limitation model (TER-LLM) and traffic engineering limitation (TER-TEL), each considering the main features of packet flow: intensity and priority. The proposed solutions were compared by analyzing various data inputs, including the ratio of flow parameters and the intensity with which packets will be limited at the border router. The study presents recommendations on the optimal use of the proposed solutions based on their respective features and advantages.

Almost any digital system includes sequential blocks which can be represented using a model of finite state machine (FSM). It is very important to improve such characteristics of FSM circuits as the number of logic elements, operating frequency and consumed energy. The paper proposes a novel design method targeting a decrease in the number of look-up table (LUT) elements in logic circuits of FPGA-based Moore FSMs. The method is based on using two sets of variables for encoding the collections of outputs. It results in a partition of the set of outputs by two blocks. The outputs from the first block depend on state variables, the outputs from the second block on additional variables. A method is proposed for splitting the set of outputs. The conditions for using the proposed method are given. An example of synthesis is shown. The results of experiments with standard benchmarks are discussed. The experiments outcomes show that the proposed approach allows diminishing the number of LUTs and consumed energy. Also, it leads to an increase in the operating frequency. The method targets rather complex FSMs when the number of state variables exceeds the number of LUT's inputs.

The main contribution of this paper is a novel design method reducing the number of look-up table (LUT) elements in the circuits of three-block Mealy finite-state machines (FSMs). The proposed method is based on using codes of collections of outputs (COs) for representing both FSM state variables and outputs. The interstate transitions are represented by output collections generated during two adjacent cycles of FSM operation. To avoid doubling the number of variables encoding of COs, two registers are used. The first register keeps a code of CO produced in the current cycle of operation; the code of a CO produced in the previous cycle is kept in the second register. There is given a synthesis example with applying the proposed method. The results of the research are shown. The research is conducted using the CAD tool Vivado by Xilinx. The experiments prove that the proposed approach allows reducing the hardware compared with such known methods as auto and one-hot of Vivado, and JEDI. Additionally, the proposed approach gives better results than a method based on the simultaneous replacement of inputs and encoding of COs. Compared to circuits of the three-block FSMs, the LUT counts are reduced by an average of 7.21% without significant reduction in the performance. Our approach loses in terms of power consumption (on average 9.62%) and power–time products (on average 10.44%). The gain in LUT counts and area–time products increases with the increase in the numbers of FSM states and inputs.

A method is proposed for optimizing circuits of sequential devices which are used in cyber-physical systems (CPSs) implemented using field programmable gate arrays (FPGAs). The optimizing hardware is a very important problem connected with implementing digital parts of CPSs. In this article, we discuss a case when Mealy finite state machines (FSMs) represent behaviour of sequential devices. The proposed method is aimed at optimization of FSM circuits implemented with look-up table (LUT) elements of FPGA chip. The method aims to reduce the LUT count of Mealy FSMs with extended state codes. The method is based on finding a partition of the set of internal states by classes of compatible states. To reduce LUT count, we propose a special kind of state codes named composite state codes. The composite codes include two parts. The first part includes the binary codes of states as elements of some partition class. The second part consists of the code of corresponding partition class. Using composite state codes allows us to obtain FPGA-based FSM circuits with exactly two levels of logic. If some conditions hold, then any FSM function from the first level is implemented by a single LUT. The second level is represented as a network of multiplexers. Each multiplexer generates either an FSM output or input memory function. An example of synthesis is shown. The experiments prove that the proposed approach allows us to reduce hardware compared with two methods from Vivado, JEDI-based FSMs, and extended state assignment. Depending on the complexity of an FSM, the LUT count is reduced on average from 15.46 to 68.59 percent. The advantages of the proposed approach grow with the growth of FSM complexness. An additional positive effect of the proposed method is a decrease in the latency time.

Very often, a digital system includes sequential blocks which can be represented using a model of the finite state machine (FSM). It is very important to improve such FSM characteristics as the number of used logic elements, operating frequency and consumed energy. The paper proposes a novel technology-dependant design method targeting LUT-based Mealy FSMs. It belongs to the group of structural decomposition methods. The method is based on encoding the product terms of Boolean functions representing the FSM circuit. To diminish the number of LUTs, a partition of the set of internal states is constructed. It leads to three-level logic circuits of Mealy FSMs. Each function from the first level requires only a single LUT to be implemented. The method of constructing the partition with the minimum amount of classes is proposed. There is given an example of FSM synthesis with the proposed method. The experiments with standard benchmarks were conducted. They show that the proposed method can improve such FSM characteristics as the number of used LUTs. This improvement is accompanied by a decrease in performance. A positive side effect of the proposed method is a reduction in power consumption compared with FSMs obtained with other design methods.

Very often, digital systems include sequential blocks which can be represented using a model of Mealy finite state machine (FSM). It is very important to improve such FSM characteristics as the number of used logic elements, operating frequency and power consumption. The paper proposes a novel design method optimizing LUT counts of LUT-based Mealy FSMs. The method is based on simultaneous use of such methods of structural decomposition as the replacement of FSM inputs and encoding of the collections of outputs. The proposed method results in three-level logic circuits of Mealy FSMs. These circuits have regular systems of interconnections. An example of FSM synthesis with the proposed method is given. The experiments with standard benchmarks were conducted. The results of experiments show that the proposed approach leads to reducing the LUT counts from 12% to 59% in average compared with known methods of synthesis of single-level FSMs. Furthermore, our approach provides better LUT counts as compared to methods of synthesis of two-level FSMs (from 9% to 20%). This gain is accompanied by a small loss of FSM performance.

A method is proposed targeting implementation of FPGA-based Mealy finite state machines. The main goal of the method is a reduction for the number of look-up table (LUT) elements and their levels in FSM logic circuits. To do it, it is necessary to eliminate the direct dependence of input memory functions and FSM output functions on FSM inputs and state variables. The method is based on encoding of the terms corresponding to rows of direct structure tables. In such an approach, only terms depend on FSM inputs and state variables. Other functions depend on variables representing terms. The method belongs to the group of the methods of structural decomposition. The set of terms is divided by classes such that each class corresponds to a single-level LUT-based circuit. An embedded memory block (EMB) generates codes of both classes and terms as elements of these classes. The mutual using LUTs and EMB allows diminishing chip area occupied by FSM circuit (as compared to its LUT-based counterpart). The simple sequential algorithm is proposed for finding the partition of the set of terms by a determined number of classes. The method is based on representation of an FSM by a state transition table. However, it can be used for any known form of FSM specification. The example of synthesis is shown. The efficiency of the proposed method was investigated using a library of standard benchmarks. We compared the proposed with some other known design methods. The investigations show that the proposed method gives better results than other discussed methods. It allows the obtaining of FSM circuits with three levels of logic and regular interconnections.