Larysa Titarenko

A new method of structural decomposition of FPGA-based Moore finite state machines (FSMs) is proposed, together with the resulting architecture of the FSM circuit. The main aim of the proposed method is to improve the spatial characteristics of FPGA-based Moore FSM circuits based on twofold state assignment (TSA). The main idea of this method is to divide the set of FSM outputs into two disjoint sets. Each set determines a block of the FSM circuit. For one block, the generated outputs depend on maximum binary state codes (MBCs). For the other block, the generated outputs are functions of partial state variables. These variables are necessary for creating partial state codes that determine partial input memory functions. Under certain conditions, the proposed method improves the spatial characteristics of FSM circuits. As in the case of TSA, each FSM state has two codes. The first is a maximum binary code with the minimum possible number of bits, while the second is a partial state code representing a state as an element of a class of compatible states. The method can be applied to improve the spatial characteristics of Moore FSMs based on look-up table (LUT) elements. To improve the characteristics of the resulting FSM circuits, classes of compatible states are used; this allows us to reduce the number of literals in sum-of-products representations of partial input memory functions. An example of synthesis is presented. The experiments are conducted using a known library of benchmark FSMs. For the fourteen FS-FSM benchmarks requiring decomposition, the proposed method reduces the LUT count by 7.57% compared with equivalent TSA-based Moore FSM circuits, while the propagation time increases by 5.06%.

Introduction. Digital systems are widely used in various areas of human activity. Typically, digital systems include a control unit (CU), which coordinates the interaction of all other system units. The characteristics of the CU significantly affect the overall system performance. When developing a CU, the designer strives to achieve a circuit with the following optimal characteristics: minimum hardware amount, maximum operating frequency, and minimum power consumption. These characteristics are interrelated. For example, reducing hardware amount leads to increased performance and reduced power consumption. Optimization methods for these characteristics depend on the specifics of the control algorithm and the element basis. Therefore, new optimization methods focused on changing the element basis are constantly needed. Purpose of the article. This paper proposes a method for optimizing the circuit of a composite microprogrammed control unit (CMCU) with code sharing. The method is aimed at the basis of FPGA (field-programmable logic array). The main idea of the article is to adapt twofold state encoding methods to the specifics of CMCUs. The method involves dividing the set of outputs of the CMCU's operator linear chains (OLCs) into classes. Each class corresponds to a single block of partial input memory functions. A chain code converter is used to generate partial output codes. This paper presents a method for optimizing the circuit for this converter. The proposed method results in a three-level microinstruction addressing circuit with a regular interconnection structure. A graph-scheme of algorithm (GSA) language was chosen to represent the control algorithm. This language was chosen due to its clarity and ease of explanation of the proposed method. Results. An algorithm for implementing a CMCU circuit using FPGA chip resources such as look-up table (LUT) elements and embedded memory blocks (EMBs) is developed. This paper presents a step-by-step algorithm for synthesizing a CMCU based on a given GSA and provides an example of synthesis of a CMCU using the proposed optimization method. Conclusions. The proposed method reduces the number of LUT elements in the CMCU addressing circuit. The method focuses on the structural decomposition of the microinstruction addressing circuit. Keywords: compositional microprogram control unit, OLC code sharing, LUT, EMB, synthesis.

A new architecture and design method are proposed for field-programmable gate array (FPGA)-based Moore finite state machines (FSMs). The proposed architecture includes a core based on functional decomposition, a core based on twofold state assignment (TSA), and a block for replacing FSM inputs (RI) in the TSA-based core. TSA belongs to the class of structural decomposition methods. The conditions under which the proposed method leads to FSM circuits with better spatial characteristics than their counterparts without RI are identified. This improvement is accompanied by a degradation of temporal characteristics. The method targets Moore FSM circuits implemented with look-up table (LUT) elements. The TSA-based core is based on classes of compatible states. To reduce the number of these classes, we use the replacement of FSM inputs by additional variables. The efficiency of the proposed method is evaluated using experiments based on a known library of benchmark FSMs. The experiments show that the trade-off between LUT count and propagation time depends on the FSM group. For the SD group (14 benchmarks), the LUT count is reduced by 13.28%, while the propagation time increases by 41.08%. For the FD group (6 benchmarks), the LUT count is reduced by 8.09%, while the propagation time increases by 2.88%. Over all 53 benchmark FSMs, the LUT count is reduced by 2.20%, while the propagation time increases by 18.77%.

In this paper, we propose a new synthesis method for LUT-based Moore finite state machines (FSMs) with twofold state assignment (TSA). The method introduces an additional core of partial input memory functions (IMFs), resulting in an architecture with two IMF cores. The first core is based on structural decomposition using additional partial state variables, whereas the second uses maximum binary state codes. Both cores are implemented as single-level circuits. We formulate the conditions under which the proposed method can be applied and show that it improves both the area and timing characteristics of the resulting FSM circuits. The method exploits pseudoequivalent state classes to reduce the number of literals in sum-of-products describing partial IMFs. The developed FSM architecture is organized into three logic stages. At the first stage, two dedicated blocks generate partial IMFs. At the next stage, these intermediate functions are merged and used to form the maximum binary state code. The final stage produces both the output signals and the partial state encoding. The proposed method is illustrated by a synthesis example and validated using standard benchmark FSMs. The obtained results indicate that the method is particularly suitable for larger and more complex Moore FSM implementations.

A new architecture of FPGA-based Moore finite state machine (FSM) is proposed, as well as the corresponding method of synthesis. The proposed architecture of FSM circuit includes two cores of partial Boolean functions. The first core is based on functional decomposition, the second core is based on structural decomposition. Under certain conditions, the proposed method improves both spatial and temporal characteristics of FSM circuits. The FSM states have two codes. The first of them is a maximum binary code (MBC) having minimum possible number of bits. The second code is a partial state code representing a state as the element of some class of compatibility. The method can be applied if Moore FSM circuits are implemented using look-up table (LUT) elements of field-programmable gate arrays. To improve characteristics of resulting FSM circuits, the classes of pseudoequivalent states are used. This allows diminishing the numbers of literals in sum-of-products representing partial input memory functions. The first core is multi-level. For the second core, all partial functions are generated by single-LUT circuits. These cores form the first level of FSM circuit. The LUTs of the second level generate bits of MBCs. These codes are used by the third circuit level for generating both FSM outputs and partial state codes. An example of synthesis is shown. The experiments are conducted using a known library of benchmark Moore FSMs. The experiments show that the proposed approach can be used for complex FSMs where the total number of FSM inputs and state variables is at least twice the number of inputs of the base LUT. The results of experiments show that the proposed method allows improving both the spatial and temporal characteristics for complex FSMs compared with their counterparts based on other known design methods.

Electrical, electronics, and communications engineering continue to play a central role in modern technological development, underpinning the digital infrastructure that enables computation, connectivity, sensing, and control across virtually all sectors

In this paper, a new method of structural decomposition is proposed. The method focuses on FPGA-based Moore finite state machines (FSMs). The method makes it possible to improve both spatial and temporal characteristics of the FSM circuits. Each internal state is represented by two codes. One of them is a partial state code representing a state as an element of some class of compatibility. The second code is represented by a concatenation of two codes: a code of output collection and a code of identifier. The method can be applied if FSM circuits are implemented using look-up table (LUT) elements of field-programmable gate arrays. The resulting FSM circuit includes three logic blocks. The first block generates partial Boolean functions representing partial output collections and identifiers. These functions depend on partial state codes. The partial codes are assigned in a way minimizing the number of arguments in partial functions. This allows generating all partial functions by single-LUT circuits. The second block generates codes of output collections and identifiers. The third block transforms them into FSM outputs and partial state codes. The paper includes an example of FSM synthesis by applying the proposed method. The experiments are conducted using standard benchmark FSMs. The experiments show that the proposed approach can be used for complex FSMs where the total number of FSM inputs and state variables are at least twice the number of inputs of the base LUT. The results of experiments show that the proposed method allows improving both the spatial and temporal characteristics for complex FSMs compared with their counterparts based on methods used by the Vivado tool.

The article introduces the Guarantee-Based Bandwidth Traffic Engineering Queue (GB(Bw)-TEQ) and Guarantee-Based Utilization Traffic Engineering Queue (GB(U)-TEQ) models for queue management on router interfaces. These models implement the principles of Traffic Engineering Queues and support both DiffServ and IntServ. Their novelty lies in the ability to provide guarantees either for the bandwidth allocated to a class queue or for its utilization coefficient. Such guarantees stabilize and control the average queue length, positively affecting key Quality of Service (QoS) indicators, particularly average delay and packet loss probability. The unreserved portion of the interface bandwidth is allocated among queues in proportion to their classes. Therefore, the higher-priority queues have lower utilization, while lower-priority queues operate with higher utilization, which is consistent with DiffServ principles. The models are formulated as a mixed-integer linear programming problem with an optimality criterion and a system of constraints. Computational experiments confirmed the operability and efficiency of GB(Bw)-TEQ and GB(U)-TEQ compared to the known analogue CB-TEQ model, which does not provide service-level guarantees. The results demonstrate that the proposed models achieve the stated guarantees and enable differentiated service without blocking the lowest-class queues. These solutions can be applied to automate queue management in IP/MPLS switches and routers as well as in software-defined networks.

Introduction. Digital systems consist of combinational and sequential blocks. The most important sequential blocks include control units. Control unit circuits are not typical library components of CAD systems. Due to it, the designing a control unit circuit is a more labor-intensive process than implementing systems with such common blocks as registers, counters, arithmetic and logic blocks. The purpose of the article. When implementing digital systems, problems arise in optimizing their characteristics. This paper considers the problem of reducing hardware costs in the circuits of compositional microprogram control units (CMCU). The resources of FPGA (field-programmable logic array) chips are used as an element basis. The method proposed in the article is based on the adaptation of algorithms for optimizing microprogram automata circuits to the features of CMCUs. The method is aimed at converting the addresses of some microinstructions into partial inputs. Under certain conditions, this approach can significantly simplify the block of microinstruction addressing. This approach can improve the characteristics of the CMCU circuit in comparison with other known methods. The language of graph-schemes of algorithms (GSA) is used to specify the algorithm for the CMCU operating. Results. The implementation of the CMCU circuit using such FPGA chip resources as look-up table (LUT) elements and embedded memory blocks (EMB) is considered. Optimization is achieved by using the EMB redundancy at the outputs. The proposed method allows improving such basic CMCU characteristics as the chip area occupied by the CMCU circuit, the maximum operating frequency, the total number of interconnections and the power consumption. The article presents a step-by-step algorithm for synthesizing the CMCU for a given GSA. Also, it provides an example of CMCU synthesis using the proposed method. At last, the conditions of the proposed method’s applicability are shown. Conclusions. The proposed method allows reducing the number of LUT elements in the CMCU addressing circuit. This minimization does not require any additional FPGA chip resources. Reducing the number of LUT elements is achieved by using the redundancy of the EMB block outputs. Keywords: CMCU, LUT, EMB, operator linear chains.

A new state assignment method focusing on Mealy finite state machines (FSMs) is proposed. The proposed codes are an alternative to composite state codes (CSCs). CSCs are represented as concatenations of group codes and partial state codes. Both group and partial state codes are maximum binary codes. We propose encoding groups using one-hot codes. The main goal of this method is improving the value of the FSM cycle time without a significant degradation of the spatial characteristics. The method can be applied if FSM circuits are implemented using the look-up table (LUT) elements of field-programmable gate arrays (FPGAs). The resulting FSM circuit includes three logic blocks. The first block generates partial input memory functions and FSM outputs depending on maximum binary state codes and one-hot group codes. The partial codes are assigned in a way minimizing the number of arguments in the partial functions. This allows for the generation of most partial functions by single-LUT circuits. The second block generates the final values of the input memory functions and FSM outputs. This block does not require group codes to generate functions, as in CSC-based FSMs. The third block transforms maximum binary group codes into their one-hot equivalents. The proposed approach allows for a reduction in the number of series-connected LUTs in comparison with CSC-based FSMs. Due to this reduction, the temporal characteristics of an FSM circuit are improved. This paper includes an example of FSM synthesis applying the proposed method. The experiments were conducted using standard benchmark FSMs. The results of the experiments show that the proposed method allowed for an improvement in the cycle time of an average of 8.81%. Moreover, in relation to CSC-based FSMs, the LUT counts decreased by an average of 4.00%.