# FPGA Implementation of Reconfigurable Finite State Machine with Input Multiplexing Architecture Using Hungarian Method

Authors: Nitish Das; P. Aruna Priya
Journal: International Journal of Reconfigurable Computing
 (2018)

---

## Abstract

The mathematical model for designing a complex digital system is a finite state machine (FSM). Applications such as digital signal processing (DSP) and built-in self-test (BIST) require specific operations to be performed only in the particular instances. Hence, the optimal synthesis of such systems requires a reconfigurable FSM. The objective of this paper is to create a framework for a reconfigurable FSM with input multiplexing and state-based input selection (Reconfigurable FSMIM-S) architecture. The Reconfigurable FSMIM-S architecture is constructed by combining the conventional FSMIM-S architecture and an optimized multiplexer bank (which defines the mode of operation). For this, the descriptions of a set of FSMs are taken for a particular application. The problem of obtaining the required optimized multiplexer bank is transformed into a weighted bipartite graph matching problem where the objective is to iteratively match the description of FSMs in the set with minimal cost. As a solution, an iterative greedy heuristic based Hungarian algorithm is proposed. The experimental results from MCNC FSM benchmarks demonstrate a significant speed improvement by 30.43% as compared with variation-based reconfigurable multiplexer bank (VRMUX) and by 9.14% in comparison with combination-based reconfigurable multiplexer bank (CRMUX) during field programmable gate array (FPGA) implementation.


---

## Body

## 1. Introduction

Designing a complex digital system requires an efficient method that includes modeling a control unit (i.e., a controller). The operational speed of such systems depends on the speed of their controllers. The mathematical model for designing a controller for applications such as microprocessor control units, circuit testing, and digital signal processing (DSP) is a finite state machine (FSM). Consequently, designing such systems requires an efficient synthesis technique for high-speed FSM [1, 2]. Applications such as DSP [3, 4] and built-in self-test (BIST) [5] require specific operations to be performed only in the particular instances. Different control units are required to complete each operation. Hence, to optimally perform these operations, a single control unit is defined which can configure itself depending upon the applied mode of operation; it is also known as reconfigurable FSM [1]. The mode of operation for such FSM is controlled by a counter, timer, or any user-defined control signals based on the application requirements. An example of a reconfigurable FSM is given in [1] as a test chip for wireless sensor network. In this example, Transition-Based Reconfigurable FSM (TR-FSM) [1] is configured into one of the MCNC FSM benchmark circuits (i.e., dk15, s386, or cse) at different instances. Moreover, any application which requires sequential processing can be broken down into a series of instances (i.e., multistage reconfigurable signal processing) where at each instance only a particular operation is performed [3]. Hence, for such applications, efficient architectures can be created using reconfigurable FSM. These emerging trends in the research necessitate a framework for optimal synthesis of high-speed reconfigurable FSM.Conventional LUT-based architectures have been used for FSM implementation on a FPGA platform [6]. Similarly, ROM-based architectures are investigated for FSM implementations. Due to the area and speed advantages, they act as an excellent alternative to their conventional LUT-based counterparts [7]. In such implementations, a considerable reduction in power consumption is obtained by disabling embedded memory blocks (EMBs) during the idle states [8, 9]. The fundamental framework for FSM with input multiplexing (FSMIM) is made in [7] whose prime objective is to shorten the depth of ROM memory. In their approach, an input selector (which consists of a multiplexer bank) is used. The basic idea that has been implemented is to select only a specific set of inputs for a particular state. FSMIM with state-based input selection (FSMIM-S) is proposed in [10], which further reduces the ROM memory size.Another approach for implementation of reconfigurable FSM is RAM-based architectures. In literature, there are two underlying RAM-based architectures, that is, variation-based reconfigurable multiplexer bank (VRMUX) and combination-based reconfigurable multiplexer bank (CRMUX) [11]. The RAM-based architectures do not serve as a novel tool for implementation of complicated FSM structures such as parallel hierarchical finite state machines (PHFSM) [12] or reversible FSM [13]. Due to significant advantages of FSMIM-S architecture over other architectures, it is used to create a framework for the high-speed Reconfigurable FSMIM-S architecture.The Reconfigurable FSMIM-S architecture is constructed by combining the conventional FSMIM-S architecture [10] and an optimized multiplexer bank (which defines the mode of operation). For this, the descriptions of a set of FSMs are taken for a particular application. Hence, the problem is to obtain the optimized multiplexer bank for the given set of FSMs. It can be solved by mapping all the FSMs into one large FSM (called base_ckt) in that set. The objective of this process is to perform optimal matching between base_ckt and the other FSMs in the set so that a minimum number of bits are changed by changing the mode of operation. This situation (i.e., performing one-to-one mapping) transforms the problem into a weighted bipartite graph matching problem where the objective is to match the description of FSMs in the set to base_ckt with minimal cost [14]. As a solution, an iterative greedy heuristic based Hungarian algorithm is proposed. In this algorithm, the weights are assigned based on the input combinations, state code, and the output combinations to form a cost matrix. A cost matrix reduction based technique, that is, Hungarian algorithm [15, 16], is used for matching. A greedy based heuristic (GBH) search technique [17] is combined with the Hungarian algorithm to optimize the augmenting path search. At every iteration, descriptions of two FSMs (i.e., base_ckt and one of the FSMs in the set) are taken as inputs. It produces the modified descriptions of the FSMs of the same dimension as outputs. At the end of the algorithm, a mutual XOR operation is performed among the modified descriptions, which provides the required optimized multiplexer bank.The experimental results from MCNC FSM benchmarks illustrate the advantages of the proposed architecture as compared with VRMUX [11], as operating speed is enhanced at an average of 30.43% and LUT consumption is reduced by an average of 5.16% in FPGA implementation. It also shows that the operating speed is improved at an average of 9.14% in comparison with CRMUX [11] during FPGA implementation. The limitation of the proposed technique is the requirement of higher LUTs, as it requires an average of 88.65% more LUTs in comparison with CRMUX [11] during FPGA implementation.The rest of the paper is outlined as follows. Section2 consists of the Reconfigurable FSMIM-S architecture and the proposed iterative greedy heuristic based Hungarian algorithm. The experimental evaluation of the proposed algorithm, implementation of the Reconfigurable FSMIM-S architecture, and comparison with other proposals from the literature are presented in Section 3. The concluding remarks are devised in Section 4.


## 2. Proposed Method

As most of the FPGA platforms use synchronous EMBs, Mealy machines with synchronous outputs are used in this paper. Let a Mealy FSM be described by the following columns:am is a code of current state (am∈A, where A={a1,…,aM} is a set of states); K(am) is a code of state am∈A; h is the number of transitions per state (h∈H, where H={t1,…,tM} is a set of number of transitions per state corresponding to A); as is a state of transition (the next state); K(as) is a code of state as∈A; X={x1,…,xL} is the set of input variables, Y={y1,…,yN} is the set of output variables; and D={d1,…,dR} is defined as excitation functions for the flip-flops, where R is the number of flip-flops (i.e., the number of bits in internal state codes), R∈{log2M,M}.The descriptions of a set of FSMs are taken for a particular application. The fundamental idea is to obtain the description of a single FSM by mapping all the FSMs into one large FSM (called base_ckt) in that set. The inputs, states, and outputs of an FSM in the set are mapped into base_ckt in their respective order. The mode bits are applied through a 2 × 1 multiplexer in those positions where the polarity of bit differs (i.e., 1 in place 0 and vice versa) to perform such mapping. Hence, the resultant FSM operates in two modes, where base_ckt mode is the default mode of operation. Similarly, all other FSMs in the set are mapped into base_ckt. In this way, a single FSM (i.e., base_ckt) combined with a multiplexer bank (which defines the mode of operation) acts as reconfigurable FSM. It can be configured into a particular FSM in the set by applying the specific mode bits. Due to numerous advantages mentioned in the literature, FSMIM-S architecture [10] is chosen to implement the FSM (i.e., base_ckt) part. Therefore, the Reconfigurable FSMIM-S architecture is constructed by combining the conventional FSMIM-S architecture [10] and multiplexer bank for mode based reconfiguration as shown in Figure 1.Figure 1
Reconfigurable FSMIM-S architecture.It encounters the following two major difficulties:(i)
The complexity of the resultant multiplexer bank is very high.(ii)
It becomes difficult to define the dummy states and dummy transitions. Dummy states and dummy transitions are such states and transitions which are not present in base_ckt but exist in the other FSMs in the set and vice versa. These states and transitions lead the system to failure.As a solution, an iterative greedy heuristic based Hungarian algorithm is proposed. In this algorithm, the descriptions of a set of FSMs (i.e., [h,X,am,as,Y]) are taken as inputs. It provides the optimized multiplexer bank for mode based reconfiguration as output. It also provides the updated description (i.e., description without dummy states and dummy transitions) of base_ckt, which is used to construct the conventional FSMIM-S part of the proposed architecture. Let (B+1) be the set of FSMs for a particular application. Based on the complexity of the description of FSM, the largest FSM is selected from the set. It is called base_ckt. The rest of the FSMs are called recon_ckt_1,recon_ckt_2,…,recon_ckt_B, respectively.Each input, state, or output of arecon_ckt_b∈{recon_ckt_1,recon_ckt_2,…,recon_ckt_B} can be mapped into any one of the inputs, states, or outputs, respectively, of base_ckt; that is, there exists a one-to-one mapping. These mappings cannot be performed independently because inputs, states, and outputs of an FSM are interdependent. Consequently, mapping an input or state of recon_ckt_b into base_ckt is transformed into a weighted bipartite graph matching problem or linear assignment problem (LAP) [14] as shown in Figure 2. In this LAP, the weights are assigned based on the input combinations, state code, and the output combinations to form a cost matrix. The objective of this process is to perform matching with a minimal cost so that a minimum number of bits are changed by changing the mode of operation. Therefore, the complexity of the multiplexer bank is reduced.Figure 2
Flow chart for iterative greedy heuristic based Hungarian algorithm.In the literature, the following approaches are proposed to solve a LAP:(i)
Modified Hungarian algorithm [16](ii)
Simple greedy heuristic based algorithm [17](iii)
Evolutionary heuristic algorithm [18].The maximum number of inputs or states does not exceed 100 in MCNC FSM benchmarks or FSMs used in real-world applications. So, the number of vertices used in the resultant weighted bipartite graph is always low which results in small LAP. But, the number of LAPs formed in this process is enormous because input matching and state matching are performed together as shown in Figure2. Hence, the primary requirement of the algorithm to solve LAP becomes the fast convergence. Therefore, a cost matrix reduction based technique, that is, Hungarian algorithm [15, 16], is used for matching. A greedy based heuristic (GBH) search technique [17] is combined with the Hungarian algorithm to optimize the augmenting path search. The pseudocode of this technique is summarized in Algorithm 1. (Note: subscripts “base” and “recon” denote the parameters of base_ckt and recon_ckt, respectively, throughout the paper.)Algorithm 1:Iterative greedy heuristic based Hungarian algorithm.
Input. The descriptions of the FSMs (i.e. [h,X,am,as,Y])
Output. The optimized multiplexer bank for mode based reconfiguration
begin
select the largest FSM from the set based on the description;
base_ckt← largest FSM;
r
e
c
o
n
_
c
k
t
_
1
,
r
e
c
o
n
_
c
k
t
_
2
,
…
,
r
e
c
o
n
_
c
k
t
_
B
← rest of the FSMs in the set;
for each recon_ckt_b∈{recon_ckt_1,recon_ckt_2,…,recon_ckt_B} do
if (L_base ≥ L_recon) then /∗ performing the input matching ∗/
generate, E←PL_reconL_base combinations_of_input_lines for base_ckt to match with
input lines of recon_ckt_b;
go to state_matching; /∗ calling the function- “state_matching” ∗/
else if (L_base<L_recon) then
generate, E←PL_baseL_recon combinations_of_input_lines for recon_ckt_b to match
with input lines of base_ckt;
go to state_matching; /∗ calling the function- “state_matching” ∗/
end
select combinations_of_input_lines with min⁡{assignment_cost1,…,assignment_costE}
& min⁡{total_cost1,total_cost2,…,total_costE};
perform binary state assignment in base_ckt & recon_ckt_b i.e. apply K(am)  &  K(as);
weight_assignment( ); /∗creating arrays by [selected_input_combination, K(as), K(am)]∗/
go to dummy_replacement; /∗ calling the function- “dummy_replacement” ∗/
if (N_base ≥ N_recon) then /∗ performing the output matching ∗/
generate, G←PN_reconN_base combinations_of_output_lines for base_ckt to match
with output lines of recon_ckt_b;
go to output_matching; /∗ calling the function- “output_matching” ∗/
else if (N_base<N_recon) then
generate, G←PN_baseN_recon combinations_of_output_lines for recon_ckt_b to match
with output lines of base_ckt;
go to output_matching; /∗ calling the function- “output_matching” ∗/
end
select combinations_of_output_lines with min⁡{XOR_count1,…,XOR_countG};
update the description of base_ckt;
end
for each recon_ckt_b∈{recon_ckt_1,recon_ckt_2,…,recon_ckt_(B-1)} do
go to dummy_replacement; /∗ calling the function- “dummy_replacement” ∗/
update the description of recon_ckt_b;
end
perform a mutual (i.e.C2B) Bitwise-XOR operations between the updated descriptions of FSMs;
obtain the optimized multiplexer bank for mode based reconfiguration;
endAt every iteration∈{1,…,B}, descriptions of two FSMs, that is, base_ckt and recon_ckt_b, are taken as inputs. The major contributing factors for power consumption and LUT requirement in FSM are the number of inputs and the internal states [8, 19]. In any FSM, input variable and states are interdependent. Thus, input and state matching are performed together between base_ckt and recon_ckt.IfL_base ≥ L_recon, then E=PL_reconL_base combinations of input lines for base_ckt are generated to match with input lines of recon_ckt_b. (L_base-L_recon) input lines act as don’t cares while the system operates in recon_ckt_b mode. Otherwise, E=PL_baseL_recon combinations of input lines for recon_ckt_b are generated to match with input lines of base_ckt. In this case, (L_recon-L_base) input lines act as don’t cares while the system operates in base_ckt mode.Now, for each combination of input lines, state matching is performed (Algorithm2). This situation can be seen as a LAP where the objective is to match the states of recon_ckt_b to the states of base_ckt with minimal cost [14, 17]. For this, the number of states in both the FSMs is equalized. Thus, if M_base ≥ M_recon, then (α-M_recon, where α=M_base) dummy states are added in recon_ckt_b. Otherwise (α-M_base, where α=M_recon) dummy states are added in base_ckt.Algorithm 2:State_matching.
Input. Combinations_of_input_lines, the descriptions of base_ckt & recon_ckt_b (i.e. [h,X,am,as,Y])
Output. Assignment_coste, total_coste, modified description of recon_ckt_b
begin
for all (combinations_of_input_lines) do
if (M_base ≥ M_recon) then /∗ equating the number of states in both the FSMs ∗/
add (M_base −  M_recon) dummy states in recon_ckt_b;
α
←
M_base;
else if (M_base < M_recon) then
add (M_recon −  M_base) dummy states in base_ckt;
α
←
M_recon;
end
weight_assignment( ); /∗ calling the procedure- “weight_assignment” ∗/
GBH_hungarian_algorithm( ); /∗ performing present state matching ∗/
assignment_coste←∑i=1α∑j=1αCij⋅λij; where e∈{1,2,…,E};
total_coste←∑i=1α∑j=1αCij; where e∈{1,2,…,E};
replace all states of recon_ckt_b by their corresponding states of base_ckt obtained
from GBH_hungarian_algorithm;
corresponding to am_base order, arrange all the complete arrays of recon_ckt_b;
end
endAll LAP solving algorithms require a cost matrix as an input to perform an optimal assignment. So, to form a cost matrix for this problem, a procedure named weight_assignment is proposed.In this procedure, the combinations of input lines,am and h, for base_ckt and recon_ckt_b are taken as inputs. It provides the cost matrix to map recon_ckt_b states into base_ckt states. An array is created at each transition in both base_ckt and recon_ckt_b by combining [input_combination ∈{x1,x2,…,xL}, am].The basic idea that has been implemented is as follows: (i) replace the recon_ckt_b state with the base_ckt state sequentially in the recon_ckt_array; (ii) evaluate the weight by performing Bitwise-XOR operation (i.e., transition matching) for that particular replacement; (iii) then, construct the cost matrix.For each transition in recon_ckt_array (i.e.,hrecon∈{1,2,…,tm_recon}), transition matching is performed. This situation can be seen as a LAP where the objective is to match the transition of recon_ckt_b to the transition of base_ckt with minimal cost [14, 17]. For this, the number of transitions for the particular state is equalized in both the FSMs. Therefore, if tm_base ≥ tm_recon, then (β-tm_recon, where β=tm_base) dummy transitions are added in the recon_ckt_array. Otherwise (β-tm_base, where β=tm_base) dummy transitions are added in the base_ckt_array. Thus, for each transition in base_ckt_array (i.e., hbase∈{1,2,…,tm_base}), a Bitwise-XOR operation is performed between the arrays for that particular transition. The total number of 1’s in the Bitwise-XOR operations is counted to create a cost matrix for transition matching. Then, optimal assignment of transitions is performed by greedy based heuristic Hungarian algorithm (GBH_hungarian_algorithm) between base_ckt_array and recon_ckt_array. Let match_count be a variable defined as (1)match_count=∑i=1β∑j=1βCijλij,where,Cij⟵costmatrix,λij⟵decisionvariable.In this way, by using match_count (from (1)), the cost matrix formation to map recon_ckt_b states into base_ckt states is completed. The pseudocode of the procedure, weight_assignment, is summarized in Algorithm 5.LetV and U represent the set of vertices (i.e., transitions or states) for recon_ckt and base_ckt, respectively. μ=(V∪U,ξ) is defined as a balanced weighted bipartite graph, where V=U=η. C is the cost matrix. A number Cij≥0 for each edge [i,j]∈ξ is called the cost (or weight) of the edge [i,j].In GBH_hungarian_algorithm, the cost matrixC is taken as input. It provides an optimal assignment between V and U as output. GBH in [17] is an iterative cost matrix reduction based approach to solve the LAP. At each iteration, a single vertex is eliminated from either V or U until the advent of some stopping conditions. Let k be the last iteration (whereas k is a positive integer). Therefore, either k or (k-1) vertices are eliminated from μ at the last iteration.Letvk⊆V and uk⊆U be the subsets of the remaining vertices in V and U, respectively, at iteration k. At the first iteration, that is, k=1, v1=V, and u1=U, respectively, the objective of the LAP is to assign η resources to η tasks in such a way that optimal total cost should be obtained for the assignment. The LAP can be mathematically formulated as follows:(2)fk≡φvk,uk=min∑i=1η∑j=1ηCijλij;(3)s.t.∑j=1ηλij=1,where∀i=1,…,η;(4)∑i=1ηλij=1,where∀j=1,…,η;(5)λij∈0,1,where∀i,j=1,…,η.Equation (2) represents the objective function for LAP. If resource i is allocated to task j then the decision variable λij=1 and 0 otherwise as depicted in (5). One-to-one mapping should be practiced between resources and tasks. Equations (3) and (4) ensure these criteria.At each iteration, there are two options to eliminate a vertex, that is, from eitherV or U. For each i∈vk and j∈uk, the following parameters are defined to select one of the above options:(6)CkV=1uk·∑i∈vk∑j∈ukCij,CkU=1vk·∑i∈vk∑j∈ukCij;(7)fkV=mini∈vk⁡φvk,uk;(8)fkU=minj∈uk⁡φvk,uk.In (6), CkV and CkU can act as “potential cost contribution” [17] of vertices i∈vk and j∈uk to fk in (2). Thus, the potential cost contribution is evaluated for the vertices, and if it exceeds the corresponding removal cost, then such vertices are eliminated.IfCkV≤CkU, then an attempt is made to remove one of the vertices from vk⊆V. From (7), if fkV≤fk-1, that is, the objective function value is improved by eliminating ik, then vk+1 is set to vk and the next iteration is executed.Otherwise, one of the vertices fromuk⊆U is eliminated. From (8), if fkU≤fk-1, that is, the objective function value is improved by eliminating jk, then uk+1 is set to uk and the next iteration is executed.In this case, when the objective function value is not improved by eliminating eitherik or jk, then algorithm halts and the obtained solution is fk-1. Furthermore, if CkV>CkU, then the above steps are repeated in the opposite order. The pseudocode of this approach is devised in Algorithm 6.Therefore, after obtaining the cost matrix from weight_assignment for state matching, GBH_hungarian_algorithm is applied to obtain the following parameters:(9)assignment_coste⟵∑i=1α∑j=1αCij·λij,wheree∈1,2,…,E;total_coste⟵∑i=1α∑j=1αCij,wheree∈1,2,…,E.Thus, all the recon_ckt_b states are replaced by their assigned base_ckt states, and all the complete arrays of recon_ckt_b are arranged corresponding to am_base order. Hence, from (9), the combinations of input lines are selected with min⁡{assignment_cost1,…,assignment_costE}  &  min⁡{total_cost1,total_cost2,…,total_costE}.Now, binary state codesK(am)  and  K(as) are applied in base_ckt and recon_ckt_b. As it changes the weights of cost matrix, weight_assignment is again applied to construct a modified cost matrix. In this case, arrays are created by combining [selected_input_combination, K(as), K(am)]. Dummy states are replaced in matched states of base_ckt and recon_ckt_b by using Propositions 1 and 2. Then, dummy transitions are replaced by using Proposition 1. The dummy replacement algorithm is shown in Algorithm 3.Algorithm 3:Dummy_replacement.
Input. The descriptions of base_ckt & recon_ckt_b (i.e. [h,X,am,as,Y])
Output. The descriptions base_ckt & recon_ckt_b without dummy states and dummy transitions.
begin
if (M_base ≥ M_recon) then /∗ replacing the dummy states ∗/
replace dummy states in recon_ckt_b by Proposition 1; /∗ by considering states in place of
transitions in the modified cost matrix ∗/
else if (M_base < M_recon) then
replace dummy states in base_ckt by by Proposition 2;
end
for each (matched state,am_recon∈ recon_ckt_b) do /∗ replacing the dummy transitions ∗/
for each (transition in recon_ckt_b, hrecon∈{1,2,…,tm_recon}) do
if (tm_base ≥ tm_recon) then
replace dummy transitions in recon_ckt_b by Proposition 1;
else if (tm_base<tm_recon) then
replace dummy transitions in base_ckt by Proposition 1;
end
end
end
endProposition 1.
Dummy transitions in a matched state of base_ckt or recon_ckt_b should be replaced with one of the existing transitions in that particular state with a minimum cost.Proof.
For each matched state (or assigned state after matching)∈ recon_ckt_b, if (tm_base≥tm_recon) then (tm_base-tm_recon) dummy transitions are present in recon_ckt_b state. Hence, there are (tm_base-tm_recon) transitions, present in the corresponding state of base_ckt which are unassigned. These unassigned transitions in base_ckt will lead the system to failure while operating in recon_ckt_b mode. As a solution, these unassigned transitions of base_ckt are assigned to the existing transitions of recon_ckt_b with the least cost by looking at the particular column of the modified cost matrix.Similarly, for each matched state (or assigned state after matching)∈ recon_ckt_b, if (tm_base<tm_recon) then (tm_recon-tm_base) dummy transitions are present in base_ckt state. Hence, there are (tm_recon-tm_base) transitions, present in the corresponding state of recon_ckt_b which are unassigned. These unassigned transitions in recon_ckt_b will lead the system to failure while operating in base_ckt mode. As a solution, these unassigned transitions of recon_ckt_b are assigned to the existing transitions of base_ckt with the least cost by looking at the particular row of the modified cost matrix.LetM_Ci×j represent the modified cost matrix for a matched state, where rows (Ui) and columns (Vj) denote the base_ckt and recon_ckt_b transitions, respectively. Thus, the unassigned transitions in base_ckt state can be assigned by (10) as follows:(10)unassigned_Ui⟶Vj:min⁡M_C1j,M_C2j,M_C3j,…,M_Cij.Similarly, the unassigned transitions in recon_ckt_b state can be assigned by (11) as follows:(11)unassigned_Vj⟶Ui:min⁡M_Ci1,M_Ci2,M_Ci3,…,M_Cij.Proposition 2.
IfM_base < M_recon, then dummy states are replaced by splitting the matched state in base_ckt.Proof.
In FSM, splitting a state with high transitions results in low power consumption [8, 19]. It also improves the operating speed [2, 20]. If M_base > M_recon, then there are (M_base-M_recon) states, present in base_ckt which are unassigned. These unassigned states in base_ckt will lead to failure in the system while operating in recon_ckt_b mode. As base_ckt is the largest FSM in the collection and its transitions per state are greater than recon_ckt_b, splitting recon_ckt_b states are insignificant for the system performance. So, these unassigned states of base_ckt are assigned using Proposition 1.IfM_base < M_recon, then (M_recon-M_base) dummy states are replaced by splitting the matched state in base_ckt. Let Ψ(am_base) = Q(tm_base-tm_recon), where Q is a positive integer. Only the states for which Ψ(am_base)>1 can be split [19]. Each state can be split into nonoverlapping subsets of (tm_base-tm_recon) transitions. Algorithm 7 is proposed to split a base_ckt state.At this stage, the states and the input lines of both the FSMs are completely matched and fixed. Hence, the output matching is performed by performing a Bitwise-XOR operation and selecting the combination with the least count of 1’s. IfN_base ≥ N_recon, then G=PN_baseN_recon combinations of output lines for base_ckt are generated to match with output lines of recon_ckt_b. Otherwise, G=PN_baseN_recon combinations of output lines for recon_ckt_bare generated to match with output lines of base_ckt. Then, for each combination of output lines, Bitwise-XOR operation is performed between corresponding output lines of base_ckt and recon_ckt_b. Let XOR_countg, where g∈{1,2,…,G} represents the total number of 1’s in the Bitwise-XOR operation for a particular combination of output lines. Therefore, the combinations of output lines with min⁡{XOR_count1,…,XOR_countG} are selected.At the end of every iteration, the description of base_ckt is updated to operate on the next iteration. At the end ofBth iteration, for each recon_ckt_b∈{recon_ckt_1,recon_ckt_2,…,recon_ckt_(B-1)}, replacement of dummy transitions and states is performed and updated descriptions of recon_ckt_1, recon_ckt_2,…, recon_ckt_(B-1) are obtained. In this way, descriptions of all FSMs are optimally matched, having the same dimension. Therefore, a mutual (i.e., C2B) Bitwise-XOR operation between the updated descriptions of FSMs is conducted which provides the optimized multiplexer bank for mode based reconfiguration.


## 3. Experimental Evaluation

Experiments have been conducted to illustrate the advantages of the proposed architecture using the FSM benchmark circuits from MCNC/LGSynth [21] as shown in Table 1.Table 1
Benchmark circuits from MCNC/LGSynth [21].
Benchmark circuits
Number of states
Number of inputs
Number of outputs
s1494
48
8
19
sand
32
11
9
styr
30
9
10
planet
48
7
19
s832
25
18
19
cse
16
7
7
s386
13
7
7
ex6
8
5
8
mc
4
3
5
planet1
48
7
19
s1488
48
8
19
s208
18
11
2The proposed iterative greedy heuristic based Hungarian algorithm has been implemented in MATLAB (2016b) environment. MATLAB HDL Coder tool is used to generate the Verilog HDL code for multiplexer bank for mode based reconfiguration. The Reconfigurable FSMIM-S architecture is described in Verilog HDL and implemented on a Xilinx xc6vlx75t Speed Grade-3 device (Virtex-6) by using Xilinx ISE 14.6 [15]. All computations are performed using a computer with an Intel(R) Core(TM) i5, 8 GB RAM, and 2.67 GHz CPU.Letx1,x2,x3,… be the input lines, y1,y2,y3,… be the output lines, and S1,S2,S3,… be the states of an FSM. In the proposed algorithm, at the first stage, input matching is performed along with the state matching; after that, dummy states and transitions are replaced. Then, output matching is performed (Algorithm 4).Algorithm 4:Output_matching.
Input. Combinations_of_output_lines
Output. XOR_countg
begin
for all (combinations_of_output_lines) do
perform Bitwise-XOR operation between corresponding output lines of base_ckt &
recon_ckt_b;
XOR_countg← the total number of 1’s in the Bitwise-XOR operation;
where, g∈{1,2,…,G};
end
endAlgorithm 5:Weight_assignment.
Input. Combination_of_input_lines for base_ckt, am_base, hbase,
combination_of_input_lines for recon_ckt_b, am_recon, hrecon;
Output. Cost matrix C/∗ cost matrix formation to map recon_ckt_b states into base_ckt states ∗/
begin
base_ckt_array← create an array at each transition in base_ckt by combining
[input_combination ∈{x1_base,…,xL_base}, am_base];
recon_ckt_array← create an array at each transition in recon_ckt_b by combining
[input_combination ∈{x1_recon,…,xL_recon}, am_recon];
for each (state,am_recon∈ recon_ckt_array) do
end
endAlgorithm 6:GBH_hungarian_algorithm.
Input. Cost matrix C
Output. Optimal assignment between V and U
begin
v
1
←
V, u1←U, f0←φ(v1,u1) and k←1  /∗ Initialization ∗/
while ((fkV > fk-1) && (fkU > fk-1 )) do
C
k
V
=
1
/
u
k
⋅
∑
i
∈
v
k
∑
j
∈
u
k
C
i
j;
C
k
U
=
1
/
v
k
⋅
∑
i
∈
v
k
∑
j
∈
u
k
C
i
j;
f
k
V
=
min
i
∈
v
k
⁡
φ
v
k
,
u
k;
f
k
U
=
min
j
∈
u
k
⁡
φ
v
k
,
u
k;
if CkV ≤ CkU then /∗  performing vertex elimination from set V ∗/
if fkV ≤ fk-1 then /∗ identify whether vertex elimination from V is “profitable” ∗/
f
k
←
f
k
V, vk+1←vk, uk+1←uk;
else if fkU ≤ fk-1 then /∗ identify whether vertex elimination from U is “profitable” ∗/
f
k
←
f
k
U, vk+1←vk, uk+1←uk;
end
else if CkV > CkU then /∗ performing vertex elimination from set U ∗/
if fkU ≤ fk-1 then /∗ identify whether vertex elimination from U is “profitable” ∗/
f
k
←
f
k
U, vk+1←vk, uk+1←uk;
else if fkV ≤ fk-1 then /∗ identify whether vertex elimination from V is “profitable” ∗/
f
k
←
f
k
V, vk+1←vk, uk+1←uk;
end
end
k
←
k
+
1;
end
endAlgorithm 7:Base_ckt state splitting.
Input. am_base, M_base, M_recon, h
Output. Resultant states to replace dummy states in base_ckt
begin
while ((matched state,am_base∈ base_ckt) && (M_base ≥ M_recon)) do
for each (transition in base_ckt, hbase∈{1,2,…,tm_base}) do
if (tm_base-tm_recon)≥1 then
split the state, Ψam_base=Q>1;
end
end
m_base ←m_base + 1;
end
if (M_base > M_recon) then
replace dummy states in recon_ckt_b by Proposition 1;
end
endAs the number of inputs or outputs exceeds 8, it requires the generation of more thanP88=40320 combinations for matching, which exhausts the simulation resources. Hence, the excess input lines are discarded from input matching, which contains the maximum number of don’t cares out of the total number of transitions. Similarly, the excess output lines are discarded from output matching, which contains the minimum number of 1’s out of the total number of transitions. Therefore, the complexities of input selector bank and group encoder are reduced because the information content of these lines is minimum.The FSM “s1494” has been considered as base_ckt, because it consists of 48 states, 8 inputs, 19 outputs, and 250 transitions which are of higher values as compared with any of the FSMs in the collection. Hence, “s1494” is considered as an FSM included in the design at the 0th iteration. In this case, state splitting is never used for dummy state replacement, because base_ckt contains the highest number of states. All dummy states and transitions are replaced by using Proposition1. For output matching, y1,y2,y3,y4,y5,y6,y7,y9,y10,y16, and y18 are discarded because they contain 62,12,13,8,6,6,38,4,16,46, and 78 instances of 1’s, respectively, out of a total of 250 transitions.In the 1st iteration, an FSM, “sand,” is included in the design. For input matching,x6, x7, and x9 are discarded because they contain 178, 150, and 182 don’t cares, respectively, out of a total of 184 transitions. All states are matched with the states of base_ckt in respective order. For output matching, y8 is discarded because it contains 3 instances of 1’s, out of a total of 253 transitions.In the 2nd iteration, an FSM, “styr,” is included in the design. For input matching,x9 is discarded because it contains 160 don’t cares, out of a total of 166 transitions. States S3,S4,S15, and S16 are matched with S4,S3,S16, and S15, respectively, of base_ckt. The rest of the states are matched with the states of base_ckt in respective order. For output matching, y4 and y9 are discarded because they contain 5 and 6 instances of 1’s, respectively, out of a total of 254 transitions.In the 3rd iteration, an FSM, “planet,” is included in the design. All states are matched with the states of base_ckt in respective order. For output matching,y4,y10,y11,y12,y13,y14,y15,y16,y17,y18, and y19 are discarded because they contain 19,5,2,26,13,3,4,2,4,4, and 23 instances of 1’s, respectively, out of a total of 255 transitions.In the 4th iteration, an FSM, “s832,” is included in the design. For input matching,x1,x2,x3,x4,x6, x6,x11,x12,x13,x14, and x15 are discarded because they contain 240,228,239,234,241,224,230,235,241, and 241 don’t cares, respectively, out of a total of 245 transitions. All states are matched with the states of base_ckt in respective order. For output matching, y3,y4,y6,y9,y10,y12,y13,y14,y16,y17, and y18 are discarded because they contain 3,5,2,2,2,6,2,4,2,4, and 6 instances of 1’s, respectively, out of a total of 259 transitions.In the 5th iteration, an FSM, “cse,” is included in the design. All states of “cse” are matched with the states of base_ckt in respective order. In the 6th iteration, an FSM, “s386,” is included in the design. All states of “s386” are matched with the states of base_ckt in respective order. In the 7th iteration, an FSM, “ex6,” is included in the design. All states of “ex6” are matched with the states of base_ckt in respective order. In the 8th iteration, an FSM, “mc,” is included in the design. All states of “mc” are matched with the states of base_ckt in respective order.In the 9th iteration, an FSM, “planet1,” is included in the design. All states are matched with the states of base_ckt in respective order. For output matching,y4,y10,y11,y12,y13,y14,y15,y16,y17,y18, and y19 are discarded because they contain 19,5,2,26,13,3,4,2,4,4, and 23 instances of 1’s, respectively, out of a total of 279 transitions.In the 10th iteration, an FSM, “s1488,” is included in the design. All states are matched with the states of base_ckt in respective order. For output matching,y1,y2,y3,y4,y5,y6,y8,y10,y11,y14, and y17 are discarded because they contain 6,7,4,13,6,38,10,16,42,61, and 64 instances of 1’s, respectively, out of a total of 281 transitions.In the 11th iteration, an FSM, “s208,” is included in the design. For input matching,x3,x4, and x5 are discarded because they contain 153, 153, and 153 don’t cares, respectively, out of a total of 153 transitions. All states are matched with the states of base_ckt in respective order. The input matching and output matching among FSMs are shown in Tables 2 and 3, respectively, along with the minimum assignment_cost, total_cost, and XOR_count (as defined in Algorithm 1).Table 2
Input matching among FSMs.
Circuits
s1494base_ckt
sandrecon_ckt_1
styrrecon_ckt_2
planetrecon_ckt_3
s832recon_ckt_4
cserecon_ckt_5
s386recon_ckt_6
ex6recon_ckt_7
mcrecon_ckt_8
planet1recon_ckt_9
s1488recon_ckt_10
s208recon_ckt_11
x
1
x
4
x
7
x
6
x
9
x
5
x
4
x
3
-
x
5
x
1
x
1
x
2
x
2
x
4
x
3
x
16
x
2
-
x
4
x
3
x
1
x
5
x
8
x
3
x
1
x
5
x
4
x
18
-
x
2
-
x
1
x
6
x
3
x
6
x
4
x
10
x
3
x
2
x
17
x
3
x
7
x
1
-
x
3
x
4
x
9
x
5
x
5
x
8
x
5
x
8
x
4
x
1
x
2
x
2
x
4
x
8
x
11
x
6
x
3
x
6
x
7
x
7
x
1
x
5
-
-
x
2
x
7
x
2
x
7
x
8
x
1
x
1
x
5
x
6
x
6
x
5
-
x
7
x
2
x
10
x
8
x
11
x
2
-
x
10
x
7
x
3
-
-
-
x
6
x
7
Minimumassignment_cost
0
0
0
0
0
0
0
0
0
2
0
Minimumtotal_cost
11
50
14
22
19
31
6
1
17
42
33Table 3
Output matching among FSMs.
Circuits
s1494base_ckt
sandrecon_ckt_1
styrrecon_ckt_2
planetrecon_ckt_3
s832recon_ckt_4
cserecon_ckt_5
s386recon_ckt_6
ex6recon_ckt_7
mcrecon_ckt_8
planet1recon_ckt_9
s1488recon_ckt_10
s208recon_ckt_11
y
8
y
4
y
5
y
2
y
19
-
y
6
y
5
y
4
y
6
y
18
-
y
11
y
6
y
6
y
6
y
15
y
7
y
1
y
8
y
2
y
7
y
7
y
1
y
12
y
2
y
7
y
8
y
2
y
3
y
3
y
4
y
5
y
1
y
13
-
y
13
y
9
y
8
y
9
y
8
y
5
y
4
y
1
y
1
y
8
y
19
-
y
14
y
7
y
3
y
5
y
7
y
1
-
y
6
y
3
y
2
y
9
y
2
y
15
y
3
y
2
y
3
y
1
y
4
y
7
y
7
-
y
5
y
15
-
y
17
y
5
y
1
y
1
y
11
y
6
y
5
y
2
-
y
3
y
12
-
y
19
y
1
y
10
y
7
y
5
y
2
y
2
y
3
-
y
9
y
16
-
XOR_count
95
163
106
76
134
154
86
72
142
103
136At the end of the proposed algorithm, optimized multiplexer bank for mode based reconfiguration is formed by performing a mutual Bitwise-XOR operation between the updated descriptions of FSMs. Hence, to evaluate the individual hardware contribution of FSMs in the Reconfigurable FSMIM-S, architecture is evaluated as follows: (i) the Bitwise-XOR operation is performed iteratively between the updated description of base_ckt and the FSM included in that particular iteration. (ii) The Verilog HDL code for the required multiplexer bank is generated at every iteration to implement in Xilinx xc6vlx75t-3 device. (iii) Thus, the number of LUTs occupied by the particular FSM is measured by the difference between the numbers of LUTs in the current iteration and previous iteration of the system. The iterative implementation of the Reconfigurable FSMIM-S architecture on Virtex-6 is shown in Table4. Therefore, at the last iteration, the total number of LUTs required and the average speed of operation are obtained for the proposed architecture.Table 4
Iterative implementation of the Reconfigurable FSMIM-S architecture on Virtex-6.
Iteration
FSM included in theparticular iteration
#LUTs occupied in theparticular iteration
Maximum operatingfrequency
Maximum pathdelay
#LUTs occupied by the FSM(#LUTs in the current iteration − #LUTs in the previous iteration)
0th
s1494
42
810.17 MHz
4.571 ns
42
1st
sand
79
779.271 MHz
4.778 ns
37
2nd
styr
105
775.164 MHz
4.455 ns
26
3rd
planet
137
728.704 MHz
4.609 ns
32
4th
s832
199
725.005 MHz
5.381 ns
62
5th
cse
230
722.335 MHz
5.140 ns
31
6th
s386
249
720.643 MHz
5.662 ns
19
7th
ex6
255
715.231 MHz
4.967 ns
6
8th
mc
269
706.889 MHz
4.526 ns
14
9th
planet1
303
676.338 MHz
5.098 ns
34
10th
s1488
330
671.760 MHz
4.486 ns
27
11th
s208
349
665.181 MHz
3.014 ns
19
Note. #LUTs denotes the number of LUTs in ISE.The experimental results from MCNC FSM benchmarks illustrate the advantages of the proposed architecture as compared with VRMUX [11]. As a result, operating speed is enhanced at an average of 30.43%, and LUT consumption is reduced by an average of 5.16% in FPGA implementation. It also shows that the operating speed is improved at an average of 9.14% in comparison with CRMUX [11] during FPGA implementation. The limitation of the proposed technique is the requirement of higher LUTs, as it requires an average of 88.65% more LUTs in comparison with CRMUX [11] during FPGA implementation. The comparisons of hardware requirement and operating speed are presented in Figures 3 and 4, respectively.Figure 3
Comparison of hardware requirements during FPGA implementation.Figure 4
Comparison of operating speeds during FPGA implementation.The operating speed of the proposed system is maximum (i.e., 810.17 MHz) and its LUT requirement is minimum (i.e., 42 LUTs) in the 0th iteration. The operating speed is reduced, and the LUT requirement is increased successively by adding an FSM at each iteration as shown in Table4. Therefore, the proposed architecture acts as an ideal candidate for such applications where the similarity between the sets of FSMs is high (i.e., fewer differences in their descriptions). Many FPGA families such as Altera stratix-IV, stratix-V, or MAX-II do not contain RAM blocks, and hence CRMUX cannot be used. The proposed architecture is preferred in such cases.Moreover, in the proposed algorithm, the next state function is partially included in matching, and binary state encoding is used. The experimental results from [22–24] show that the evolutionary state encoding algorithms such as [23] or [24] outperform the binary or random state encoding techniques by an average of 59.72% and 64.06%, respectively. Therefore, the LUT requirement for the proposed architecture can be further reduced by 20 to 30% by using the evolutionary state encoding techniques.


## 4. Concluding Remarks

This paper presents a high-speed reconfigurable FSM with input multiplexing and state-based input selection (Reconfigurable FSMIM-S) architecture. The creation of such architecture leads to a problem of defining the optimized multiplexer bank for mode based reconfiguration for the set of FSMs in a particular application. This situation transforms the problem into a weighted bipartite graph matching problem where the objective is to match the description of FSMs in the set with minimal cost. As a solution, an iterative greedy heuristic based Hungarian algorithm is proposed, which provides the required optimized multiplexer bank. By using the proposed architecture, operating speed is enhanced at an average of 30.43% and LUT consumption is reduced by an average of 5.16% in FPGA implementation in comparison with VRMUX [11]. It has also been shown that the operating speed is improved at an average of 9.14% as compared with CRMUX [11]. The only trade-off of the proposed technique is that it requires 88.65% more LUTs compared with CRMUX [11] during FPGA implementation.Further, the improvement on this work is focused on reducing the LUT requirement to implement the proposed architecture. In this study, a binary state encoding is used, and next state function is partially included in matching. However, evolutionary state encoding algorithms such as [23] or [24] can be used to reduce the increased LUT requirement.



---

*Source: 6831901-2018-01-10.xml*