Mapping Outputs and States Encoding Bits to Outputs Using Multiplexers in Finite State Machine Implementations

Citation: Senhadji-Navarro, R.; Garcia-Vargas, I. Mapping Outputs and States Encoding Bits to Outputs Using Multiplexers in Finite State Machine Implementations. Electronics 2023,12, 502. https://doi.org/ 10.3390/electronics12030502 Academic Editors: Alexander Barkalov, Larysa Titarenko, Dariusz Kania and Remigiusz Wi´sniewski Received: 14 December 2022 Revised: 12 January 2023 Accepted: 14 January 2023 Published: 18 January 2023 Copyright: © 2023 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ 4.0/). electronics Article Mapping Outputs and States Encoding Bits to Outputs Using Multiplexers in Finite State Machine Implementations Raouf Senhadji-Navarro *,† and Ignacio Garcia-Vargas † Department of Computer Architecture and Technology, University of Seville, 41012 Seville, Spain *Correspondence: [email protected] † These authors contributed equally to this work. Abstract: This paper proposes a new technique for implementing Finite State Machines (FSMs) in Field Programmable Gate Arrays (FPGAs). The proposed approach extends the called column compaction in two ways. First, it is applied to the state-encoding bits in addition to the outputs, allowing a reduction in the number of logic functions required both by the state transition function and by the output function. Second, the technique exploits the dedicated multiplexers usually included in FPGAs to increase the number of columns that can be compacted. Unlike conventional state-encoding techniques, the proposed approach reduces the number of logic functions instead of their complexity. An Integer Linear Programming (ILP) formulation that maximizes the number of compacted columns has been proposed. In order to evaluate the effectiveness of the proposed approach, experimental results using standard benchmarks are presented. In most cases, the proposed approach reduces the number of used Look-Up Tables (LUTs) with respect to the conventional FSM implementation. Keywords: finite state machine; column compaction; state encoding; dedicated multiplexer; synthesis; FPGA 1. Introduction Finite State Machines (FSMs) are probably the most widely used component in digital design. They allow one to model any sequential circuit, particularly control units. Optimizing FSM implementations in terms of area, speed or power consumption is essential to meet the design constraints demanded by applications. For this reason, the synthesis of FSMs has received the attention of researchers, designers and EDA tool developers for decades [ 1 – 4 ]. One of the most active fields has been the encoding of the FSM states to achieve optimal implementations of the state transition and output functions [5–20]. Other techniques are focused on the optimal assignment of don’t care outputs, which are very usual because the values of some outputs do not matter in some states. The technique called column compaction exploits these don’t cares to reduce the number of logic functions that must be implemented [ 21 – 25 ]. The aim of this technique is to assign values of zero or one to the don’t cares in order to achieve that two or more outputs are equal to each other, and so only one logic function must be implemented for each group of equivalent outputs. Our technique extends column compaction in two ways. First, it extends the concept of column compaction to the state-encoding bits. To the best knowledge of the authors’ knowledge, column compaction has never been applied to the state transition function. In addition to assign values to don’t cares to find equivalent outputs, our technique also encodes the states to achieve that some encoding bits are equal to some outputs. Therefore, it can be viewed as an extension of column compaction that is applied to the state transition function, in addition to the output function. This allows one to reduce the number of logic functions required to implement both functions. We will refer to the Electronics 2023,12, 502. https://doi.org/10.3390/electronics12030502 https://www.mdpi.com/journal/electronics Electronics 2023,12, 502 2 of 15 one-to-one correspondence between state-encoding bits and outputs as direct mapping of state-encoding bits. For analogy, column compaction will be referred to as direct mapping of outputs. Second, the proposed technique exploits the dedicated 2:1 multiplexers usually included in Field Programmable Gate Arrays (FPGAs), which allow one to combine the outputs of two Look-Up Tables (LUTs) [ 26 ]. In order to reduce the number of LUTs used, the technique searches pairs of outputs that can be combined by means of dedicated multiplexers to generate the next state-encoding bits or other outputs. Therefore, the proposed technique also extends the concept of compaction to that of mapping via multiplexers. Each multiplexer is controlled by a bit of the present state. Due to the fact that the state-encoding bits are control inputs of the multiplexers and outputs of some of them, state encoding has a great influence on the results that can be obtained. Unlike conventional state-encoding techniques, the proposed approach reduces the number of logic functions instead of their complexity. Our technique is based on an Integer Linear Programming (ILP) formulation, which allows a solver to find the optimal mapping (or suboptimal, when the execution time is limited). As a conclusion, the proposed technique uses three mechanisms to reduce the number of logic functions: direct mapping of outputs (i.e., column compaction), direct mapping of state-encoding bits and mapping via multiplexers, which are each modeled by a unique ILP formulation. Unlike the other two mechanisms, which are presented for the first time, column compaction is a classical technique. However, the novelty lies in the fact that it is based on a ILP formulation instead of heuristics [ 22 ], which allows one to obtain the optimal value, or in the worst case, to find a bound of the error corresponding to a non-optimal solution. The remainder of this article is organized as follows. In Section 2, brief background about FSMs and FPGA devices is presented. Section 3describes the fundamentals of the proposed technique and its architecture. Section 4presents the proposed ILP formulation. Section 5shows the obtained experimental results. Finally, conclusions are drawn in Section 6. 2. Background Let F= (S , t , o , S0) be a FSM, where S represents the set of states; t:S× { 0, 1 }r→S , the state transition function; o:S× { 0, 1 }r→ { 0, 1, −}m , the output function; and S0 , the reset state. The parameters r and m represent the numbers of inputs and outputs, respectively. The State Transition Diagram (STD) is commonly used to show the behavior of a FSM. Figure 1shows an example of FSM, whose STD is shown in Figure 1a. For a proper description of the proposed technique, it is more convenient to represent the FSM in the form of a State Transition Table (STT). As Figure 1b,c show, a STT is a table whose rows represent the transitions of the FSM as the 4-tuple (in , ps , ns , out) , where in represents the inputs; ps , the present state; ns , the next state; and out , the outputs. The symbol “–” represents a don’t care value. A symbolic STT shows the states as symbols (see Figure 1b), whereas a codified STT shows the states once they have been codified (see Figure 1c). FPGAs are semiconductor devices that are based around a matrix of Configurable Logic Blocks (CLBs) connected via programmable interconnects. In current Xilinx FPGA devices, each CLB is composed by two slices, and each one of them includes four LUTs. In addition, each slice includes three dedicated 2:1 multiplexers: two called F7 and one called F8. Each F7 combines the outputs of two LUTs whereas F8 combines the outputs of two F7s. Dedicated multiplexers can be used to create general-purpose functions of up to 13 inputs in 2 LUTs or 27 inputs in 4 LUTs (i.e., in one slice) [26]. Electronics 2023,12, 502 3 of 15 0/0 – 01 – 1/–1010 –/11–11 1/11011 0/01100 1/00111 0/1– – 01 S0 S1 S2 S3 Input Present Next Outputs state state X O1O2O3O4O5 0S0S00 – 0 1 – 1S0S1– 1 0 1 0 –S1S21 1 – 1 1 0S2S30 1 1 0 0 1S2S11 1 0 1 1 0S3S31 – – 0 1 1S3S00 0 1 1 1 (b) Input Present Next Outputs state state X P1P2N1N2O1O2O3O4O5 0 0 0 0 0 0 – 0 1 0 1 0 0 1 1 11 0 1 0 –1 1 0 1 1 1 – 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1 11 0 0 0 0 0 1 1 1 (a) (c) (d) Figure 1. Example of the mapping of state-encoding bits and outputs to outputs: ( a ) STD, ( b ) symbolic SST, (c) encoded STT and (d) implementation. 3. Mapping Outputs and States Encoding Bits to Outputs by Means of Multiplexers The aim of the proposed technique is to generate FSM outputs or the next stateencoding bits from FSM outputs without using extra LUTs. Both direct mapping and mapping via multiplexers are applied for this purpose. Mapping via multiplexers benefits from dedicated multiplexers, avoiding the use of extra LUTs. The advantage of direct mapping is that it allows one to reduce the number logic levels (i.e., to remove the logic levels corresponding to the dedicated multiplexers) and to improve the routing; therefore, this mapping can increase the speed. To sum up, including mapping via multiplexer allows one to find solutions with a more mapped signals. However, the proposed ILP formulation gives priority to direct mapping. By exploiting the usual strong relationship between the transition and output functions, the proposed technique codifies the states to achieve that the maximum number of signals (whether outputs or state-encoding bits) are mapped. In addition to encode the states, the proposed technique assigns values to the don’t care outputs to achieve its objective. There Electronics 2023,12, 502 4 of 15 is a key difference between the proposed technique and the conventional state-encoding approaches [ 5 – 20 ] that justifies its novelty. State-encoding algorithms assign a different code to each FSM state with the purpose of simplifying the complexity of the transition and output functions. On the other hand, the proposed approach reduces the number of logic functions instead of its complexity. Compared with the conventional state-encoding approaches, assigning don’t care outputs and codifying states in a non-optimal way in terms of function complexity can result in an increase in the number of LUTs required by each logic function. However, a reduction in the number of logic functions achieved by the proposed technique can compensate for such an increase, resulting in a lesser overall LUT count. Figure 2shows the general architecture to implement the FSMs obtained from the proposed technique. For simplicity, the signals generated from a single output (i.e., by applying direct mapping) have been excluded from the figure. The combinational block implements the logic corresponding to the unmapped bits of the next state and the unmapped outputs, so it partially implements the state transition and output functions. The mapped signals are generated from unmapped outputs by means of multiplexers controlled by a bit of the present state (which is not necessarily different from those of other multiplexers). The larger the number of mapped signals, the simpler the combinational block. This is due to the fact that the number of logic functions is reduced. Figure 2. General architecture for mapping state-encoding bits and outputs to outputs. Figure 1c shows the STT of the FSM example (Figure 1b) after applying a mapping of state-encoding bits and outputs to outputs. After codifying the states and assigning some don’t care outputs, the next state-encoding bit N2 can be mapped to outputs O1 and O2 by means of a multiplexer controlled by the present state-encoding bit P1 , which selects O1 if P1= 0 and O2 if P1= 1 (see Figure 1b,c). Note that Figure 1c shows in bold the don’t care outputs that have been assigned. Similarly, O5 can be mapped to O3 and O4 by means of a multiplexer controlled by P2 , which selects O3 if P2= 0 and O4 if P2= 1. This mapping allows one to reduce the number of logic functions that must be implemented in LUTs from seven to five (see Figure 1d). By supposing LUTs of four inputs, the implementation obtained by the proposed technique requires five LUTs, whereas the conventional FSM implementation requires seven LUTs, independently of the state encoding used. We define optimal mapping of outputs and state-encoding bits to outputs (OMOSEBO) as the problem of finding the mapping that maximizes the number of mapped signals (i.e., that minimizes the number of logic functions that are required to implement the output and state transition functions). Electronics 2023,12, 502 5 of 15 We have proposed an ILP formulation for this problem, which prioritizes direct mapping over mapping via multiplexers. Some constraints are imposed by the Xilinx FPGA architecture itself. As the output of each LUT is physically connected to a unique F7 multiplexer, routing the output of the LUT to a different multiplexer requires an additional LUT (called route-thru). F8 multiplexers present similar problems because the output of each F7 is physically connected to a unique F8 multiplexer. To prevent these situations, the ILP formulation must ensure that a FSM output cannot be used to generate more than one signal via multiplexer. However, although dedicated multiplexers F7 and F8 can be chained, allowing the multiplexing of up to four signals, we have limited our approach to a unique number of multiplexers to avoid increasing the complexity of the proposed ILP formulation. Therefore, the solver must exclude candidate solutions in which outputs mapped via multiplexers are inputs of other multiplexers. 4. Integer Linear Programming Formulation Let S={S1 , S2 , . . . , Se} be the set of states of a FSM. Let us suppose that Oi for i= 1, . . . , m represents each output of the FSM. Let us consider the tuple (T1 , T2 , . . . , Tq) , where Ti≡(Sj , Sk)∈S×S , and Sj and Sk represent the present and next state, respectively, of the transition corresponding to i -th row of the STT. Let us consider that Pi and Ni represent the i -th encoding bit of the present and the next state, respectively. Let us suppose that Oi j∈ { 0, 1, −} represents the value of the output Oj for the transition corresponding to the i-th row of the STT. The ILP formulation requires the following binary variables: •fi,j,k,r for all i , j , k , r , which is equal to one if and only if Ni can be generated from Oj and Ok via a multiplexer controlled by Pr so that Ni=Oj for all transitions in which Pr=0, and Ni=Okfor the remaining (Niis therefore mapped to Ojand Ok). •gi,j,k,r for all i , j , k , r , which is equal to one if and only if Oi can be generated from Oj and Ok via a multiplexer controlled by Pr so that Oi=Oj for all transitions in which Pr=0, and Oi=Okfor the remaining (Oiis therefore mapped to Ojand Ok). •hi,j for all i , j , which represents the value of the Oj for the transition corresponding to the i -th row of the STT. Note that hi,j must be equal to Oi j for all i , j such that Oi j∈ { 0, 1 } (i.e., Oi j is not a don’t care); however, the remainder values of hi,j will be determined by the solver. •ci,jfor all i,j, which represents the j-th bit of the encoding of Si. •di,j,k for all i , j , k such that j<k , which is equal to one if and only if i -th bit of the encoding of Sjand that of Skare different. Note that if fi,j,j,r= 1, then there exits a direct mapping of Ni to Oj (so the value of r is not relevant). Similarly, if gi,j,j,r=1, then there exists a direct mapping of Oito Oj. The objective of the OMOSEBO problem is to find a mapping of outputs and stateencoding bits that maximize the following tuple in lexicographical order: (∑ u,v,t,r fu,v,t,r+∑ {w,v,t,r|v6=t} gw,v,t,r+∑ {w,v,r|v>w} gw,v,v,r,∑ u,v,r fu,v,v,r+∑ {w,v,r|v>w} gw,v,v,r)(1) The first element allows one to maximize the number of mapped signals; the second one prioritizes the direct mapping over the mapping via multiplexer. The terms gw,v,v,r include only the cases in which v>w to avoid counting twice one output directly mapped to another (e.g., if gw,v,v,r= 1 and gv,w,w,r0= 1, then only Ov or Ow can be removed in the corresponding implementation). Encoding e states requires d=dlog2ee bits; therefore, z=d+m is the total number of signals (either outputs or state-encoding bits). As ∑u,v,t,rfu,v,t,r+∑{w,v,t,r|v6=t}gw,v,t,r+ ∑{w,v,r|v>w}gw,v,v,r represent the number of mapped signals, it is obvious that ∑u,v,t,rfu,v,t,r+ ∑{w,v,t,r|v6=t}gw,v,t,r+∑{w,v,r|v>w}gw,v,v,r<z . We use this property to define the weight α= 1 +1 z for the terms corresponding to direct mapping in order to model the multi- Electronics 2023,12, 502 6 of 15 objective function. The ILP formulation of the OMOSEBO problem can be expressed as follows: Maximize ∑ {u,v,t,r|v6=t} fu,v,t,r+α∑ u,v,r fu,v,v,r+∑ {w,v,t,r|v6=t} gw,v,t,r+α∑ {w,v,r|v>w} gw,v,v,r(2) subject to −fu,v,t,r+ci,r−hj,v+ck,u≥ −1∀u,v,t,r,Tj≡(Si,Sk)(3) fu,v,t,r−ci,r−hj,v+ck,u≤1∀u,v,t,r,Tj≡(Si,Sk)(4) −fu,v,t,r−ci,r−hj,t+ck,u≥ −2∀u,v,t,r,Tj≡(Si,Sk)(5) fu,v,t,r+ci,r−hj,t+ck,u≤2∀u,v,t,r,Tj≡(Si,Sk)(6) −gw,v,t,r+ci,r−hj,v+hi,j,w≥ −1∀w,v,t,r,Tj≡(Si,Sk)(7) gw,v,t,r−ci,r−hj,v+hi,j,w≤1∀w,v,t,r,Tj≡(Si,Sk)(8) −gw,v,t,r−ci,r−hj,t+hi,j,w≥ −2∀w,v,t,r,Tj≡(Si,Sk)(9) gw,v,t,r+ci,r−hj,t+hi,j,w≤2∀w,v,t,r,Tj≡(Si,Sk)(10) ∑ v,t,r fu,v,t,r≤1∀u(11) ∑ v,t,r gw,v,t,r≤1∀w(12) ∑ {u,t,r|t6=v} fu,v,t,r+∑ {u,t,r|t6=v} fu,t,v,r+∑ {w,t,r|t6=v} gw,v,t,r+∑ {w,t,r|t6=v} gw,t,v,r≤1∀vs. (13) gw,w,t,r=0∀w,t,r(14) gw,t,w,r=0∀w,t,r(15) (gw,v,t,r−1)m+∑ {v0,t0,r0|t06=v0} gv,v0,t0,r0≤0∀w,v,t6=v,r(16) (gw,t,v,r−1)m+∑ {v0,t0,r0|t06=v0} gv,v0,t0,r0≤0∀w,v,t6=v,r(17) (fu,v,t,r−1)m+∑ {v0,t0,r0|t06=v0} gv,v0,t0,r0≤0∀u,v,t6=v,r(18) (fu,t,v,r−1)m+∑ {v0,t0,r0|t06=v0} gv,v0,t0,r0≤0∀u,v,t6=v,r(19) (gw,v,v,r−1)z+∑ w0,v0,r0 gw0,w,v0,r0+gw0,v0,w,r0+∑ u,v0,r0 fu,w,v0,r0+fu,v0,w,r0≤0∀w,v,r(20) −di,j,k+cj,i+ck,i≥0∀i,j,k(21) di,j,k+cj,i+ck,i≤2∀i,j,k(22) ∑ i di,j,k≥1∀j,k(23) hi,j=Oi j∀i,j|Oi j∈ {0, 1}(24) Constraints (3)–(6) ensure that the mapping is coherent with the transition function. Constraints (3) and (4) are the result of the linearization of the following constraint: fu,v,t,r=1∧ci,r=0=⇒ck,u=hj,v∀u,v,t,r,Tj≡(Si,Sk)(25) For each transition Tj≡(Si , Sk) , if Pr= 0 (i.e., the r -th bit of the encoding of the present state, Si , is equal to 0), then the multiplexer connects Ov to Nu ; therefore, the u -th Electronics 2023,12, 502 7 of 15 bit of the coding of the next state, Sk , must be equal to the value of the output Ov . Similarly, for the cases in which Pr= 1, (5) and (6) are obtained from the following constraint: fu,v,t,r=1∧ci,r=1=⇒ck,u=hj,t∀u,v,t,r,Tj≡(Si,Sk)(26) Constraints (7)–(10) guarantee the coherence with the output function. Constraints (7) and (8) are obtained by the linearization of the following constraint: gw,v,t,r=1∧ci,r=0=⇒hj,w=hj,v∀w,v,t,r,Tj≡(Si,Sk)(27) If Pr= 0, then the multiplexer connects Ov to Ow ; therefore, they must be equal to each other. Similarly, for the cases in which Pr= 1, (9) and (10) are obtained from the following constraint: gw,v,t,r=1∧ci,r=1=⇒hj,w=hj,t∀w,v,t,r,Tj≡(Si,Sk)(28) Constraints (11) and (12) ensure that the state-encoding bits and the outputs, respectively, are not mapped more than once (see Figure 3a,b). Constraint (13) guarantees that any output cannot be used to generate more than one signal by means of a multiplexer, whether a state-encoding bit or an output (see Figure 3c). Constraints (14) and (15) prevent that an output is mapped to itself (see Figure 3d). Constraints (16) and (17) are the results of the linearization of the constraints gw,v,t,r=1=⇒∑ v0,t06=v0,r0 gv,v0,t0,r0=0∀w,v,t6=v,r(29) and gw,t,v,r=1=⇒∑ v0,t06=v0,r0 gv,v0,t0,r0=0∀w,v,t6=v,r(30) respectively. They prevent that an output generated from others via a multiplexer is used to map an output using a multiplexer (see Figure 4a). Similarly, (18) and (19) are obtained by linearization of the constraints fu,v,t,r=1=⇒∑ v0,t06=v0,r0 gv,v0,t0,r0=0∀u,v,t6=v,r(31) and fu,t,v,r=1=⇒∑ v0,t06=v0,r0 gv,v0,t0,r0=0∀u,v,t6=v,r(32) respectively. They prevent the mapping of a state-encoding bit in the circumstances described above (see Figure 4b). Constraint (20) is obtained from constraint gw,v,v,r=1=⇒∑ w0,v0,r0 gw0,w,v0,r0+gw0,v0,w,r0+∑ u,v0,r0 fu,w,v0,r0+fu,v0,w,r0=0∀w,v,r(33) which prevents an output directly mapped to another being used to generate a third signal (either an output or a state-encoding bit). Figure 4c,d show the cases of outputs and stateencoding bits, respectively. The aim of these constraints is to prevent that a direct mapping leads to the situations shown in Figure 4e, despite constraints from (16) to (19). It might be thought that (20) prevents some valid solutions. For example, supposing that Ov is not a mapped output, the implementation shown on the left of Figure 4c could be valid if it is not prevented by (20), allowing that Ow and Ow0 are mapped outputs. However, the solver Electronics 2023,12, 502 8 of 15 will find the following equivalent solution (which do is allowed): Ov and O0 v generate O0 w via the multiplexer, and Ovalso generates Ow. (a) (b) (c) (d) Figure 3. Solutions that ILP constraints from (11) to (15) prevent: ( a ) constraint (11), ( b ) constraint (12), (c) constraint (13) and (d) constraints (14) and (15). Electronics 2023,12, 502 9 of 15 Finally, (21)–(23) guarantee the code assigned to each state is different from the other ones. Constraints (21) and (22) ensure that the i -th bit of the encoding of Sj is different from the i-th bit of the encoding of Skif di,j,k=1; that is, di,j,k=1=⇒cj,i6=ck,i∀i,j,k(34) Constraint (23) guaranties that any pair of states, Sjand Sk, differ at least in one bit. Constraint (24) assigns the values of the outputs that are not don’t care values, and thus they cannot be determined by the solver. (a) (b) (c) (d) (e) Figure 4. Solutions that ILP constraints from (16) to (20) prevent: ( a ) constraints (16) and (17), ( b ) constraints (18) and (19), ( c ) constraint (20) for outputs, ( d ) constraint (20) for state encoding bits and (e) an example of the situation that must be prevented. 5. Experimental Results OMOSEBO has been evaluated using FSMs of the MCNC benchmark set [ 27 ]. The number of states of these FSMs were previously minimized by STAMINA [ 28 ]. All designs were synthesized and implemented using Xilinx Vivado Design Suite 2022.1 in a Spartan-7 FPGA (xc7s6cpga196-2). Therefore, the results include the delay of the placement-and- routing stage. In order to evaluate the effectiveness of OMOSEBO, the implementations obtained using this technique were compared to the corresponding conventional FSM implementations (which will be called CONV). CONV implementations were generated