# FPGA Implementation of an Improved Reconfigurable FSMIM Architecture Using Logarithmic Barrier Function Based Gradient Descent Approach

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

---

## Abstract

Recently, the Reconfigurable FSM has drawn the attention of the researchers for multistage signal processing applications. The optimal synthesis of Reconfigurable finite state machine with input multiplexing (Reconfigurable FSMIM) architecture is done by the iterative greedy heuristic based Hungarian algorithm (IGHA). The major problem concerning IGHA is the disintegration of a state encoding technique. This paper proposes the integration of IGHA with the state assignment using logarithmic barrier function based gradient descent approach to reduce the hardware consumption of Reconfigurable FSMIM. Experiments have been performed using MCNC FSM benchmarks which illustrate a significant area and speed improvement over other architectures during field programmable gate array (FPGA) implementation.


---

## Body

## 1. Introduction

Digital signal processing (DSP) [1–3], pattern matching [4], and circuit testing [5] are the primary applications for most of the digital systems. These applications require a hardware-oriented as well as high-speed control unit. A finite state machine (FSM) is an integral part of any complex digital system. Its inputs are multiplexed to make it hardware oriented, which is known as the finite state machine with input multiplexing (FSMIM). It serves as a control unit, and its operating speed determines the processing speed of the system. The applications as mentioned earlier can be observed as cascaded stages (i.e., multistage) of operations [2], where each stage requires a specific FSM. Hence, a Reconfigurable FSM is investigated in the literature for optimal performance in such applications [6, 7]. A Reconfigurable FSM is defined as a single FSM, which acts as one of the FSMs from the set (i.e., set of FSMs for a specific application) by applying particular mode bits. Its implementation is performed on field programmable gate array (FPGA) platforms [6].The Reconfigurable FSMIM architecture is created by joining (A) Conventional FSMIM architecture [8] and (B) multiplexer bank (which defines the mode based reconfiguration). The optimal synthesis of both the constituting elements is done by Iterative greedy heuristic based Hungarian algorithm (IGHA) [6]. An efficient state encoding technique for an FSM serves as a vital tool to optimize the hardware utilization while implementing on an FPGA platform [9, 10]. In the case of Reconfigurable FSMIM, the state encoding of the constituent FSMs altogether affects the look-up table (LUT) requirement of the Reconfigurable FSMIM [6].The major problem concerning IGHA is the disintegration of a state encoding technique. It uses binary state encoding as a default state assignment technique for operation. The state assignment method for the Reconfigurable FSMIM architecture leads to an optimization problem [6]. To the best of the authors’ knowledge, all the state assignment techniques proposed in the literature provide state codes only for a single FSM. Therefore, the objective of this work is the integration of IGHA with an optimal state encoding technique to reduce the hardware consumption of Reconfigurable FSMIM on an FPGA platform.In the literature, another direction in the implementation of an FSM is RAM-based architectures. The following three types of RAM-based FSM architectures are studied [11]: (a) basic RAM-based FSM architecture, (b) RAM-based FSM architecture with transition-controlled multiplexers, and (c) RAM-based FSM architecture with state-controlled multiplexers. In the basic RAM-based FSM architecture, bits are stored in the form of words. For each transition (i.e., present state combined with the external inputs), the outputs and the state assignment bits for next state are stored in the RAM-word memory [12, 13]. The RAM size required for basic RAM-based FSM implementation is enormous. Hence, to reduce the RAM depth, RAM-based FSM architecture with transition-controlled multiplexers is used. It consists of an input selector bank, which provides active inputs from the external inputs for selecting a particular state [11]. RAM-based FSM architecture with state-controlled multiplexers is used to reduce the RAM size further. It consists of two separate RAM blocks, out of which the smaller RAM block is assigned to operate the input selector bank [11]. Thus, designing such architecture is very complicated.In this paper, the Improved Reconfigurable FSMIM architecture is proposed, which surmounts the issue of high LUT consumption during FPGA implementation. The proposed architecture is formed using the improved iterative greedy heuristic based Hungarian algorithm (Improved-IGHA). The Improved-IGHA is the integration of IGHA with the state assignment using logarithmic barrier function based gradient descent approach.To validate the proposed approach, experiments have been performed using MCNC FSM benchmarks [14]. Experimental results for the proposed architecture illustrate a significant area reduction by an average of 20.38% and speed improvement by an average of 32.73% over VRMUX [11] during FPGA implementation. It also demonstrates an adequate area reduction by an average of 16.05% and speed improvement by an average of 1.77% over Reconfigurable FSMIM-S architecture [6] during FPGA implementation. When these results are compared with CRMUX [11], a speed improvement by an average of 11.06% is obtained. The proposed architecture requires an average of 58.38% more LUTs as compared with CRMUX [11] during FPGA implementation. It is the only trade-off for the proposed design.The remainder of this article is formed as follows. The research problem formulation is made in Section2. Section 3 consists of state assignment using logarithmic barrier function based gradient descent approach and an illustrative example. Experimental setup and comparative analysis of this work with the literature are devised in Section 4. In the end, concluding remarks are drawn in Section 5.


## 2. Problem Formulation

Recently, the Reconfigurable FSM has drawn the attention of the researchers for multistage signal processing applications. A novel framework for the creation of Reconfigurable FSMIM is given in [6].A Mealy FSM is represented in a vector form, such as(
S
,
X
,
Y
,
δ
,
π
,
S
0
) whereS
=
(
S
0
,
…
,
S
(
M
)
)
⟵ set of states;
X
=
(
x
1
,
…
,
x
L
)
⟵ set of input variables;
Y
=
(
y
1
,
…
,
y
N
)
⟵ set of output variables;
δ
⇒
S
∗
X
→
S
⟵ transition function;
π
⇒
S
∗
X
→
Y
⟵ output function;
S
0
⟵ initial state.Moreover, the following variables are defined to illustrate the complete functionality of an FSM:S
(
m
)
⟵ any instantaneous stateS
(
m
)
∈
S wherem
∈
(
0,1
,
…
,
M
);
K
(
S
(
m
)
)
⟵ binary state code for the, state S
(
m
)
∈
S;
H
=
(
t
1
,
…
,
t
M
)
⟵ set of number of transitions per state corresponding to S;
h
⟵ number of transitions per state where h
∈
(
1,2
,
…
,
H
);
R
⟵ the minimum length of a binary-state code, R
=
⌈
log
2
⁡
M
⌉
.The Reconfigurable FSMIM is defined as a single FSM, which acts as any one of the FSM from the set (i.e., set of FSMs for a specific application) by applying particular mode bits. A set of FSM for a specific application is chosen, whereb
a
s
e
_
c
k
t
⟵ the largest FSM (i.e., the FSM with the highest total number of transitions, states, and inputs) in the set and  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. b
a
s
e
_
c
k
t-mode is the default mode of operation for the Reconfigurable FSMIM [6].The Reconfigurable FSMIM architecture is created by joining the following two parts: (A) Conventional FSMIM architecture [8], & (B) Multiplexer bank (which defines the mode based reconfiguration). The optimal synthesis of the Multiplexer bank is done by iterative greedy heuristic based Hungarian algorithm (IGHA) [6]. At the last phase of IGHA, state transitions of each constituent FSM of the Reconfigurable FSMIM architecture are presented in Figure 1. Therefore, the state encoding of the constituent FSMs altogether affects the LUT requirement of the Reconfigurable FSMIM architecture. At the end of IGHA, a modified description of a single FSM (i.e., b
a
s
e
_
c
k
t) is obtained which is used to create the Conventional FSMIM part [6].Figure 1
State transitions of each constituent FSM of the Reconfigurable FSMIM architecture at the last phase of iterative greedy heuristic based Hungarian algorithm (IGHA).In FSM implementation on an FPGA platform, state encoding technique acts as a tool for minimizing the hardware consumption [9, 10]. For example, an MCNC FSM benchmark t
b
k requires 82 LUTs when implemented on a Xilinx xc6vlx75t-3 device (Virtex-6) using the Grey encoding technique. But it needs only 41 LUTs on the same platform using the binary encoding technique.The major problem concerning IGHA is the disintegration of a state encoding technique. It uses binary state encoding as a default state assignment technique for operation [6]. The state assignment method for the Reconfigurable FSMIM architecture leads to an optimization problem as evident from Figure 1. To the best of the authors’ knowledge, all the state assignment techniques proposed in the literature provide state codes only for a single FSM.Therefore, the objective of this work is the integration of IGHA with an optimal state encoding technique to reduce the hardware consumption of Reconfigurable FSMIM on an FPGA platform.


## 3. Methodology

This work is an extension of work presented in [6]. Hence, all the variables from [6] are used in the same context throughout the article. An improved version of IGHA (Improved-IGHA) is proposed. It addresses the issue of optimal state encoding.A recent body of literature has investigated the performance of three fundamental types of state encoding techniques on an FPGA platform [9]. The studied methods are as follows: (a) structural approaches, (b) heuristic approaches, and (c) pragmatic approaches. Out of these three approaches, structural state encoding technique outperforms on an FPGA platform [9, 10]. It uses the knowledge of internal structure (i.e., state transition) of the FSM to generate optimal state codes. Therefore, structural information of FSMs is considered to develop the proposed state encoding technique for the Reconfigurable FSMIM.The structural information of the Reconfigurable FSMIM (i.e., state transition) is obtained from Figure1. Hence, a unified weight matrix is defined by adding the weight of all component FSMs for the same corresponding states. It is given in (1).The mathematical formulation of the cost function for an FSM is given in [15]. It uses the structural information (i.e., state transitions) of the particular FSM. Let ω
i
j
⟵ element of weight matrix and  D
i
s
t
_
M
a
t
r
i
x
i
j be the hamming distance between two particular state codes. D
i
s
t
_
M
a
t
r
i
x
i
j is obtained by counting the number of 1’s after an exclusive-OR operation between the binary state codes as shown in Figure 2. Therefore, from the literature [15], the cost associated with a particular set of state codes (i.e., μ) is defined by (2).(1)
ω
11
=
ω
11
∣
b
a
s
e
_
c
k
t
+
ω
11
∣
r
e
c
o
n
_
c
k
t
_
1
+
ω
11
∣
r
e
c
o
n
_
c
k
t
_
2
+
⋯
+
ω
11
∣
r
e
c
o
n
_
c
k
t
_
B
⋯
⋯
ω
1
M
-
1
=
ω
1
M
-
1
∣
b
a
s
e
_
c
k
t
+
ω
1
M
-
1
∣
r
e
c
o
n
_
c
k
t
_
1
+
ω
1
M
-
1
∣
r
e
c
o
n
_
c
k
t
_
2
+
⋯
+
ω
1
M
-
1
∣
r
e
c
o
n
_
c
k
t
_
B
ω
1
M
=
ω
1
M
∣
b
a
s
e
_
c
k
t
+
ω
1
M
∣
r
e
c
o
n
_
c
k
t
_
1
+
ω
1
M
∣
r
e
c
o
n
_
c
k
t
_
2
+
⋯
+
ω
1
M
∣
r
e
c
o
n
_
c
k
t
_
B
⋯
⋯
ω
M
-
1
1
=
ω
M
-
1
1
∣
b
a
s
e
_
c
k
t
+
ω
M
-
1
1
∣
r
e
c
o
n
_
c
k
t
_
1
+
ω
M
-
1
1
∣
r
e
c
o
n
_
c
k
t
_
2
+
⋯
+
ω
M
-
1
1
∣
r
e
c
o
n
_
c
k
t
_
B
ω
M
1
=
ω
M
1
∣
b
a
s
e
_
c
k
t
+
ω
M
1
∣
r
e
c
o
n
_
c
k
t
_
1
+
ω
M
1
∣
r
e
c
o
n
_
c
k
t
_
2
+
⋯
+
ω
M
1
∣
r
e
c
o
n
_
c
k
t
_
B
⋯
⋯
ω
M
M
=
ω
M
M
∣
b
a
s
e
_
c
k
t
+
ω
M
M
∣
r
e
c
o
n
_
c
k
t
_
1
+
ω
M
M
∣
r
e
c
o
n
_
c
k
t
_
2
+
⋯
+
ω
M
M
∣
r
e
c
o
n
_
c
k
t
_
B
(2)
c
o
s
t
μ
=
∑
i
=
0
M
-
1
∑
j
=
0
M
-
1
ω
i
j
×
D
i
s
t
_
M
a
t
r
i
x
i
jFigure 2
Formation ofD
i
s
t
_
M
a
t
r
i
x by calculating the Hamming distance between particular nodes (i.e., states).


### 3.1. State Assignment Using Logarithmic Barrier Function Based Gradient Descent Approach for the Reconfigurable FSM

Let the graph described by (2) be G
m
a
p
=
(
V
m
a
p
,
E
m
a
p
), where E
m
a
p ( i.e., ω
i
j) indicates the edge weights between the nodes &  V
m
a
p ( i.e., columns of μ) represents the set of nodes. Hence, each node corresponds to a particular binary state code because μ
i
j opts only the binary labels. M symbolizes the total number of nodes in the graph G
m
a
p.Let a hypercube be characterized asχ
η
=
(
V
χ
,
E
χ
), where η is the dimension, E
χ is the set of edges, and V
χ is the set of vertices of the hypercube [16]. The cardinality of E
χ and V
χ is given in (3) and (4), respectively.(3)
E
χ
=
V
χ
×
η
2
=
2
η
-
1
×
η
(4)
V
χ
=
2
ηNow, the concept of hypercube embedding is used to reduce (2). An embedding is performed from graph G
m
a
p onto a hypercube χ
η as described earlier [16, 17]. It is defined as μ
:
V
m
a
p
→
V
χ which is a one-to-one mapping function. Consequently, M-binary η-vectors are defined as in (5). Thus, if a node of graph G
m
a
p (i.e., i) is expressed by a binary state code, the corresponding vertex of the hypercube (i.e., k
i) is represented by the same binary state code.(5)
k
i
∈
k
:
k
∈
0,1
η
w
h
e
r
e
i
∈
V
m
a
p
i
.
e
.
,
c
o
l
u
m
n
s
o
f
μIn a hypercube,D
i
s
t
_
M
a
t
r
i
x
i
j
(
i
,
j
∈
V
m
a
p
) represents the hamming distance between k
i and k
j. It is shown in (6), where τ
i
j is the instantaneous value of k
i
j. The value of τ
i
j varies between -
1 and 1. Therefore, the cost function is reduced to (7) using hypercube embedding.(6)
D
i
s
t
_
M
a
t
r
i
x
i
j
=
∑
κ
=
1
η
τ
i
κ
-
τ
j
κ
2
w
h
e
r
e
,
k
i
j
=
1
i
f
τ
i
j
≥
0
0
i
f
τ
i
j
<
0
(7)
c
o
s
t
μ
=
∑
i
=
0
M
-
1
∑
j
=
0
M
-
1
∑
κ
=
1
η
ω
i
j
×
τ
i
κ
-
τ
j
κ
2The objective is thus confined to minimize the cost function given in (7). Evidently, it is a discrete optimization problem, where each state can opt only a particular binary state code.The convergence of Improved-IGHA depends on the convergence of its constituent algorithms, i.e., IGHA and the applied state assignment technique. Therefore, an algorithm with a high convergence speed is preferred to construct the state assignment technique for Improved-IGHA.The evolutionary technique, such as genetic algorithm (GA), presents a significant shortcoming as its convergence speed slows down near the global optimum [18, 19]. Similarly, particle swarm optimization (PSO) and differential evolution (DE) operate with a high convergence rate but offer premature convergence which is a critical drawback [20, 21]. In the literature, penalty-based approaches, such as Lagrangian technique and logarithmic-barrier function (LBF) method, have proven their potentials to obtain the optimum solution with a high convergence speed [22, 23]. These methods are advantageous in solving a discrete or combinatorial optimization problem [24, 25].Therefore, the LBF-based Gradient descent approach is adopted to construct the state assignment technique for Improved-IGHA. It is an interior point method that assures the feasible solution. The mathematical formulation of the cost minimization function is performed by LBF. Then, it is reduced iteratively by the gradient-projection approach. The flow chart for the Improved-IGHA is presented in Figure3.Figure 3
Flow chart for the improved iterative greedy heuristic based Hungarian algorithm (Improved-IGHA).In LBF technique, the search operation is performed in a continuous space domain to deduce the optimal points. Then, these points are discretized to obtain the optimal solution [26, 27].In LBF method, an objective function subject to inequality constraints is given in(8)
m
i
n
f
τ
s
.
t
.
c
o
n
s
t
r
a
i
n
t
i
τ
≥
0
,
i
=
1
,
…
,
uThe logarithmic barrier function to minimize the cost function (as in (7)) is given in (9). In LBF search, for any move which omits the constraints, the second term serves as a barrier [28] as shown in (9)
min
⁡
ψ
τ
,
ϕ
=
f
τ
+
ϕ
∑
i
=
1
u
log
e
⁡
c
o
n
s
t
r
a
i
n
t
i
τAt the iterationi
t
e
r
_
t, (9) is defined as shown in (10)
min
⁡
ψ
τ
,
ϕ
i
t
e
r
_
t
i
t
e
r
_
t
=
f
τ
+
ϕ
i
t
e
r
_
t
∑
i
=
1
u
log
e
⁡
c
o
n
s
t
r
a
i
n
t
i
τInitially, LBF selects a feasibleτ
0 and ϕ
0
>
0. Then, it chooses ϕ
i
t
e
r
_
t
+
1
=
σ
·
ϕ
i
t
e
r
_
t, where σ
<
1. This iterative process goes on until ϕ
i
t
e
r
_
t reaches an adequately small value.A full-fledged method is required to solve (10) with respect to τ. A first-order gradient-projection approach [29] is well-suited for iteratively minimizing (10). In this approach, the model parameters (a.k.a. weight vectors) are evaluated to minimize the objective function when an analytical calculation is not possible [30, 31]. In this approach, the underlying representation of the objective function of the problem is given in (11)
m
i
n
ψ
τ
,
ϕ
s
.
t
.
ϑ
τ
=
0An iteration of this projection method is defined by (12). In (12), ρ denotes the step size. ρ is chosen to be a small positive real number [29].(12)
τ
←
τ
-
ρ
∇
ψ
τ
,
ϕThus, small steps (i.e.,ρ) are taken in the negative gradient direction of the objective function as illustrated in (12). Then, (13) is used to outline the value of τ on the constraint surface at the next iteration (i.e., τ
(
i
t
e
r
_
t
+
1
)).(13)
τ
←
τ
ϑ
τ
=
0The convergence criterion for this iterative process is defined by (14), where θ
∈
[
0,1
].(14)
τ
i
t
e
r
_
t
+
1
-
τ
i
t
e
r
_
t
<
θIn this way, embedding problem is reduced to the determination ofM-binary η-vectors (as shown in (15)) which optimizes the cost function (i.e., (7)).(15)
τ
i
∈
τ
:
τ
∈
R
η
&
τ
2
=
1
;
i
∈
V
m
a
p
w
h
e
r
e
τ
2
d
e
n
o
t
e
s
t
h
e
n
o
r
m
o
f
τHence, the cost function (from (7)) is defined in terms of Hamming distance as shown in (16)
c
o
s
t
μ
=
∑
i
=
0
M
-
1
∑
j
=
0
M
-
1
ω
i
j
×
τ
i
-
τ
j
2
w
h
e
r
e
,
τ
i
=
τ
i
1
,
τ
i
2
,
…
,
τ
i
η
T
τ
i
-
τ
j
2
=
∑
κ
=
1
η
τ
i
κ
-
τ
j
κ
2The constraint (i.e., boundary condition) for this problem is formed, such as any two vertices on hypercube should not contain the same binary state code (i.e.,τ
i
-
τ
j
≠
0). Hence, the mathematical representation of the constraint is presented in (17)
c
o
n
s
t
r
a
i
n
t
τ
=
τ
i
-
τ
j
2
>
0By applying (16) and (17) on (9), the objective function for LBF is reduced to (18)
min
⁡
ψ
τ
,
ϕ
=
∑
i
=
0
M
-
1
∑
j
=
0
M
-
1
ω
i
j
×
τ
i
-
τ
j
2
+
ϕ
∑
i
=
0
M
-
1
∑
j
=
0
M
-
1
log
e
⁡
τ
i
-
τ
j
2Therefore, the entityϑ
(
τ
) (from (13)) is defined by (19)
ϑ
τ
=
τ
1
2
-
1
,
τ
2
2
-
1
,
…
,
τ
M
2
-
1
T
s
.
t
.
τ
=
τ
1
,
τ
2
,
…
,
τ
M
T
τ
i
=
τ
i
1
,
τ
i
2
,
…
,
τ
i
η
T
;
w
h
e
r
e
e
a
c
h
τ
i
1
≤
i
≤
MThe evaluation of the derivative term (i.e.,∇
ψ
(
τ
,
ϕ
)) is required to move in the gradient descent direction as shown in (12). The needed derivative term is obtained by putting (20), (21), (22), and (23) into (18). Hence, ∇
ψ
(
τ
,
ϕ
) is defined by (24).(20)
∂
∂
τ
i
τ
i
-
τ
j
2
=
2
τ
i
-
τ
j
(21)
∂
∂
τ
j
τ
i
-
τ
j
2
=
2
τ
j
-
τ
i
(22)
∂
∂
τ
i
log
e
⁡
τ
i
-
τ
j
2
=
2
τ
i
-
τ
j
τ
i
-
τ
j
2
(23)
∂
∂
τ
j
log
e
⁡
τ
i
-
τ
j
2
=
2
τ
j
-
τ
i
τ
i
-
τ
j
2
(24)
∇
ψ
τ
,
ϕ
=
2
∑
j
=
1
M
ω
1
j
×
τ
1
-
τ
j
+
ϕ
∑
j
=
1
M
τ
1
-
τ
j
τ
1
-
τ
j
2
∑
j
=
1
M
ω
2
j
×
τ
2
-
τ
j
+
ϕ
∑
j
=
1
M
τ
2
-
τ
j
τ
2
-
τ
j
2
⋯
⋯
⋯
∑
j
=
1
M
ω
M
j
×
τ
M
-
τ
j
+
ϕ
∑
j
=
1
M
τ
M
-
τ
j
τ
M
-
τ
j
2By applying (19) into (13), the normalized vector τ is defined as shown in (25)
τ
ϑ
τ
=
0
=
τ
1
τ
1
τ
2
τ
2
⋯
⋯
τ
M
τ
MIf (14) is satisfied, a solution vector which is defined as τ
^
i
j is obtained at the end of the iteration. Therefore, the required set of state codes (i.e., k
^
i
j) is deduced by discretizing τ
^
i
j using (26)
k
^
i
j
=
1
i
f
τ
^
i
j
≥
0
0
i
f
τ
^
i
j
<
0The pseudocode for the proposed state assignment approach is presented in Algorithm1.Algorithm 1:State assignment using logarithmic barrier-function based gradient descent approach for the Reconfigurable FSM.
Input:
the objective function defined by Equation (7)
Output:
μ
∗ (i.e., the final state code vector)
begin
Initialization:
μ
←
B
i
n
a
r
y
s
t
a
t
e
c
o
d
e
s;
ϕ
←
i
n
i
t
i
a
l
_
ϕ
(
s
.
t
.
ϕ
0
>
0
);
while (ϕ
>
f
i
n
a
l
_
ϕ)do
repeat
for
i
t
e
r
_
t
←
1
t
o
θ
τ
i
t
e
r
_
t
←
τ
(
i
t
e
r
_
t
-
1
)
-
ρ
{
∇
ψ
(
τ
,
ϕ
)
};
/
∗
b
y
E
q
u
a
t
i
o
n (12)
&
E
q
u
a
t
i
o
n (24)∗
/
end
return
τ
^
i
j
(
i
.
e
.
t
h
e
v
a
l
u
e
o
f
τ
a
t
t
h
e
i
t
e
r
a
t
i
o
n
θ
);
evaluate
k
^
i
j
=
1
,
i
f
τ
^
i
j
≥
0
;
0
,
i
f
τ
^
i
j
<
0
;
/
∗
b
y
E
q
u
a
t
i
o
n (26)∗
/
C
o
m
p
u
t
e
c
o
s
t
f
o
r
t
h
e
n
e
w
v
a
l
u
e
o
f
μ
u
s
i
n
g
E
q
u
a
t
i
o
n (7);
if (c
o
s
t
(
o
l
d
_
μ
)
≥
c
o
s
t
(
n
e
w
_
μ
))then
u
p
d
a
t
e
,
μ
∗
←
n
e
w
_
μ;
else if (c
o
s
t
(
o
l
d
_
μ
)
<
c
o
s
t
(
n
e
w
_
μ
))then
u
p
d
a
t
e
,
μ
∗
←
o
l
d
_
μ;
end
until
t
h
e
a
l
g
o
r
i
t
h
m
c
o
n
v
e
r
g
e
s
ϕ
←
σ
⋅
ϕ;
end
return
μ
∗;
end


### 3.2. An Illustrative Example for the Improved Reconfigurable FSMIM Architecture

The following MCNC FSM benchmarks [14] are considered to demonstrate the steps involved in the creation of the Improved Reconfigurable FSMIM architecture:(1)
t
r
a
i
n
11 (description is provided in Table 1)
(2)
l
i
o
n
9 (description is provided in Table 2)Table 1
Description oft
r
a
i
n
11 from MCNC FSM Benchmarks [14].
Input
PS
NS
O/P
x
1
x
2
y
1
0
0
S
0
S
0
0
1
0
S
0
S
1
-
0
1
S
0
S
2
-
1
0
S
1
S
1
1
0
0
S
1
S
3
1
1
1
S
1
S
5
1
0
1
S
2
S
2
1
0
0
S
2
S
7
1
1
1
S
2
S
9
1
0
0
S
3
S
3
1
0
1
S
3
S
4
1
0
1
S
4
S
4
1
0
0
S
4
S
0
-
1
1
S
5
S
5
1
0
1
S
5
S
6
1
0
1
S
6
S
6
1
0
0
S
6
S
0
-
0
0
S
7
S
7
1
1
0
S
7
S
8
1
1
0
S
8
S
8
1
0
0
S
8
S
0
-
1
1
S
9
S
9
1
1
0
S
9
S
10
1
1
0
S
10
S
10
1
0
0
S
10
S
0
-Table 2
Description ofl
i
o
n
9 from MCNC FSM Benchmarks [14].
Input
PS
NS
O/P
x
1
x
2
y
1
1
0
S
0
S
1
0
0
0
S
0
S
0
0
0
0
S
1
S
0
0
1
0
S
1
S
1
0
1
1
S
1
S
2
0
1
0
S
2
S
1
0
1
1
S
2
S
2
0
0
1
S
2
S
3
0
1
1
S
3
S
2
1
0
1
S
3
S
3
1
0
0
S
3
S
4
1
0
1
S
4
S
3
1
0
0
S
4
S
4
1
1
0
S
4
S
5
1
0
0
S
5
S
4
1
1
0
S
5
S
5
1
1
1
S
5
S
6
1
1
0
S
6
S
5
1
1
1
S
6
S
6
1
0
1
S
6
S
7
1
1
1
S
7
S
6
1
0
1
S
7
S
7
1
0
0
S
7
S
8
1
0
1
S
8
S
7
1
0
0
S
8
S
8
1The improved Reconfigurable FSMIM architecture is created by joining (A) Conventional FSMIM architecture and (B) Multiplexer bank (which defines the mode based reconfiguration). The optimal synthesis of the Multiplexer bank is done by the proposed Improved-IGHA. At the end of the proposed algorithm, a modified description of a single FSM (i.e.,b
a
s
e
_
c
k
t) is obtained which is used to create the Conventional FSMIM part [6]. The Improved-IGHA consists of the following steps:(i)
Initialization (Define b
a
s
e
_
c
k
t  and  r
e
c
o
n
_
c
k
t): t
r
a
i
n
1
1 is selected as b
a
s
e
_
c
k
t because its complexity is greater than l
i
o
n
9 as observed from their descriptions. Consequently, l
i
o
n
9 acts as r
e
c
o
n
_
c
k
t.
(ii)
Input and State Matching using Hungarian Algorithm: Input and state matchings are performed together using Algorithms 1, 2, 5, and 6 from [6]. Combinations of input lines of b
a
s
e
_
c
k
t (i.e., 2
P
2
=
2) are generated. For the first combination (
x
1
∣
t
r
a
i
n
11
,
x
2
∣
t
r
a
i
n
11
), states are matched as S
0
l
i
o
n
9
→
S
0
t
r
a
i
n
11, S
1
l
i
o
n
9
→
S
1
t
r
a
i
n
11, S
3
l
i
o
n
9
→
S
2
t
r
a
i
n
11, S
4
l
i
o
n
9
→
S
3
t
r
a
i
n
11, S
7
l
i
o
n
9
→
S
4
t
r
a
i
n
11, S
2
l
i
o
n
9
→
S
5
t
r
a
i
n
11, S
8
l
i
o
n
9
→
S
6
t
r
a
i
n
11, S
5
l
i
o
n
9
→
S
7
t
r
a
i
n
11, D
u
m
m
y
s
t
a
t
e
→
S
8
t
r
a
i
n
11, S
6
l
i
o
n
9
→
S
9
t
r
a
i
n
11, and D
u
m
m
y
s
t
a
t
e
→
S
1
0
t
r
a
i
n
11. It offers zero a
s
s
i
g
n
m
e
n
t
_
c
o
s
t  and  t
o
t
a
l
_
c
o
s
t. For the second combination (
x
2
∣
t
r
a
i
n
11
,
x
1
∣
t
r
a
i
n
11
), states are matched as S
0
l
i
o
n
9
→
S
0
t
r
a
i
n
11, S
3
l
i
o
n
9
→
S
1
t
r
a
i
n
11, S
1
l
i
o
n
9
→
S
2
t
r
a
i
n
11, S
4
l
i
o
n
9
→
S
3
t
r
a
i
n
11, S
5
l
i
o
n
9
→
S
4
t
r
a
i
n
11, S
2
l
i
o
n
9
→
S
5
t
r
a
i
n
11, D
u
m
m
y
s
t
a
t
e
→
S
6
t
r
a
i
n
11, S
7
l
i
o
n
9
→
S
7
t
r
a
i
n
11, S
8
l
i
o
n
9
→
S
8
t
r
a
i
n
11, S
6
l
i
o
n
9
→
S
9
t
r
a
i
n
11, and D
u
m
m
y
s
t
a
t
e
→
S
1
0
t
r
a
i
n
11. It also offers zero a
s
s
i
g
n
m
e
n
t
_
c
o
s
t  and  t
o
t
a
l
_
c
o
s
t. Therefore, the first combination (
x
1
∣
t
r
a
i
n
11
,
x
2
∣
t
r
a
i
n
11
) is finalized to match with (
x
1
∣
l
i
o
n
9
,
x
2
∣
l
i
o
n
9
).
(iii)
Dummy State and Position Replacement: The replacements of the dummy states and positions in b
a
s
e
_
c
k
t  and  r
e
c
o
n
_
c
k
t are performed using Algorithm 3 from [6]. The replaced dummy states (highlighted in “bold italic font”)  and dummy positions (highlighted in “bold font”) are presented in Tables 3 and 4.
(iv)
Output Matching using Bitwise-XOR Operations: Output Matching is not required in this case, as there is a single output line in b
a
s
e
_
c
k
t as well as in r
e
c
o
n
_
c
k
t.
(v)
Update the descriptions of FSMs: The updated descriptions of b
a
s
e
_
c
k
t  and  r
e
c
o
n
_
c
k
t are presented in Tables 3 and 4, respectively.
(vi)
State assignment using logarithmic barrier function based gradient descent approach for the Reconfigurable FSM: The pictorial representation of state transitions for b
a
s
e
_
c
k
t  and  r
e
c
o
n
_
c
k
t (from Tables 3 and 4) is given in Figure 4. Therefore, the weight matrix ω is formed using (1). It is given in (27)
ω
=
2
2
1
0
0
0
0
0
0
0
0
1
2
0
1
0
2
0
0
0
0
0
0
0
2
1
0
1
0
1
0
1
0
0
0
1
2
1
0
0
1
0
0
0
1
0
0
0
2
0
1
0
0
1
0
0
1
1
0
0
2
1
0
0
0
0
1
0
0
0
1
0
2
0
0
0
0
0
0
0
1
0
0
0
2
1
1
0
2
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
1
0
2
1
2
1
0
0
0
0
0
0
0
0
1
The proposed state assignment algorithm starts by considering the binary state codes as an initial solution. It offers the cost as 62 (from (2)).
At the10
0
t
h iteration, the instantaneous value τ (from previous iteration, τ
(
i
t
e
r
_
99
)) is obtained as defined by (28)
τ
i
t
e
r
_
99
=
0.51
0.85
-
0.85
0.84
-
0.52
-
0.85
-
0.51
0.85
0.85
-
0.52
-
0.51
-
0.85
0.84
-
0.51
0.51
-
0.52
-
0.51
0.51
0.85
-
0.52
-
0.85
-
0.52
-
0.85
-
0.51
-
0.52
0.84
-
0.51
-
0.85
0.84
0.51
-
0.52
-
0.85
0.51
-
0.85
-
0.85
0.51
0.85
0.84
0.51
-
0.52
-
0.51
0.51
-
0.52
0.85
T
The derivative (from (24)) is evaluated as defined by (29)
∇
ψ
τ
,
ϕ
=
-
1517
-
1224
-
2118
2126
-
1739
1258
-
2622
2960
2135
701
1558
402
-
1223
1598
1793
736
722
-
739
2886
760
1262
723
-
2888
1550
1506
-
1209
-
1775
401
-
398
1754
763
-
2889
-
1549
-
2118
418
-
1579
2945
2953
1761
-
1736
-
2583
-
1504
1506
207
9
T
So, the current value ofτ (i.e., τ
(
i
t
e
r
_
100
)) is obtained from (12). It is given in (30) by choosing ρ
=
1
0
-
3 (a very small value). (30)
τ
i
t
e
r
_
100
=
2.027
2.074
1.268
-
1.286
1.219
-
2.108
2.112
-
2.11
-
1.285
-
1.221
-
2.068
-
1.252
2.063
-
2.108
-
1.283
-
1.256
-
1.232
1.249
-
2.036
-
1.28
-
2.112
-
1.243
2.038
-
2.06
-
2.026
2.049
1.265
-
1.251
1.238
-
1.244
-
1.283
2.039
2.059
1.268
-
1.268
2.089
-
2.095
-
2.113
-
1.251
1.216
2.073
2.014
-
2.026
-
1.229
T
Then,τ is directed towards the unity radius hypersphere. It is given in (31)
τ
^
=
0.85
0.84
0.51
-
0.52
0.51
-
0.85
0.85
-
0.85
-
0.52
-
0.51
-
0.85
-
0.51
0.84
-
0.85
-
0.52
-
0.51
-
0.51
0.51
-
0.85
-
0.52
-
0.85
-
0.52
0.84
-
0.85
-
0.85
0.85
0.51
-
0.51
0.51
-
0.51
-
0.52
0.85
0.85
0.51
-
0.51
0.85
-
0.85
-
0.85
-
0.51
0.51
0.84
0.84
-
0.85
-
0.51
T
←
S
0
←
S
1
←
S
2
←
S
3
←
S
4
←
S
5
←
S
6
←
S
7
←
S
8
←
S
9
←
S
10
The required set of state codes is deduced asS
0
→
1110, S
1
→
1010, S
2
→
0000, S
3
→
1000, S
4
→
0100, S
5
→
0010, S
6
→
0110, S
7
→
1001, S
8
→
1101, S
9
→
0001, and S
10
→
110
0 by discretizing the current value of τ using (26). Hence, the cost is reduced to 48 (from (2)).Table 3
Updated description oft
r
a
i
n
11.
Input
PS
NS
O/P
x
1
x
2
y
1
0
0
S
0
S
0
0
1
0
S
0
S
1
-
0
1
S
0
S
2
-
1
0
S
1
S
1
1
0
0
S
1
S
3
1
1
1
S
1
S
5
1
0
1
S
2
S
2
1
0
0
S
2
S
7
1
1
1
S
2
S
9
1
0
0
S
3
S
3
1
0
1
S
3
S
4
1
0
0
S
3
S
3
1
0
1
S
4
S
4
1
0
0
S
4
S
0
-
0
1
S
4
S
4
1
1
1
S
5
S
5
1
0
1
S
5
S
6
1
1
1
S
5
S
5
1
0
1
S
6
S
6
1
0
0
S
6
S
0
-
0
0
S
7
S
7
1
1
0
S
7
S
8
1
1
0
S
7
S
8
1
1
0
S
8
S
8
1
0
0
S
8
S
0
-
0
0
S
8
S
0
-
1
1
S
9
S
9
1
1
0
S
9
S
10
1
1
1
S
9
S
9
1
1
0
S
10
S
10
1
0
0
S
10
S
0
-
0
0
S
10
S
0
-Table 4
Updated description ofl
i
o
n
9.
Input
PS
NS
O/P
x
1
x
2
y
1
0
0
S
0
S
0
0
1
0
S
0
S
1
0
0
0
S
0
S
0
0
1
0
S
1
S
1
0
0
0
S
1
S
0
0
1
1
S
1
S
5
0
0
1
S
2
S
2
1
0
0
S
2
S
3
1
1
1
S
2
S
5
1
0
0
S
3
S
3
1
0
1
S
3
S
2
1
1
0
S
3
S
7
1
0
1
S
4
S
4
1
0
0
S
4
S
6
1
1
1
S
4
S
9
1
1
1
S
5
S
5
0
0
1
S
5
S
2
0
1
0
S
5
S
1
0
0
1
S
6
S
4
1
0
0
S
6
S
6
1
0
0
S
7
S
3
1
1
0
S
7
S
7
1
1
1
S
7
S
9
1
1
0
S8
S1
0
0
0
S8
S0
0
0
0
S8
S0
0
1
1
S
9
S
9
1
1
0
S
9
S
7
1
0
1
S
9
S
4
1
1
0
S10
S1
0
0
0
S10
S0
0
0
0
S10
S0
0Figure 4
The pictorial representation of state transitions forb
a
s
e
_
c
k
t  and  r
e
c
o
n
_
c
k
t.In the end, a Bitwise-XOR operation is performed between the updated descriptions oft
r
a
i
n
11  and  l
i
o
n
9. It provides the Multiplexer bank (i.e., part-B). The updated descriptions of t
r
a
i
n
1
1 are used to construct the Conventional FSMIM part (i.e., part-A).


## 3.1. State Assignment Using Logarithmic Barrier Function Based Gradient Descent Approach for the Reconfigurable FSM

Let the graph described by (2) be G
m
a
p
=
(
V
m
a
p
,
E
m
a
p
), where E
m
a
p ( i.e., ω
i
j) indicates the edge weights between the nodes &  V
m
a
p ( i.e., columns of μ) represents the set of nodes. Hence, each node corresponds to a particular binary state code because μ
i
j opts only the binary labels. M symbolizes the total number of nodes in the graph G
m
a
p.Let a hypercube be characterized asχ
η
=
(
V
χ
,
E
χ
), where η is the dimension, E
χ is the set of edges, and V
χ is the set of vertices of the hypercube [16]. The cardinality of E
χ and V
χ is given in (3) and (4), respectively.(3)
E
χ
=
V
χ
×
η
2
=
2
η
-
1
×
η
(4)
V
χ
=
2
ηNow, the concept of hypercube embedding is used to reduce (2). An embedding is performed from graph G
m
a
p onto a hypercube χ
η as described earlier [16, 17]. It is defined as μ
:
V
m
a
p
→
V
χ which is a one-to-one mapping function. Consequently, M-binary η-vectors are defined as in (5). Thus, if a node of graph G
m
a
p (i.e., i) is expressed by a binary state code, the corresponding vertex of the hypercube (i.e., k
i) is represented by the same binary state code.(5)
k
i
∈
k
:
k
∈
0,1
η
w
h
e
r
e
i
∈
V
m
a
p
i
.
e
.
,
c
o
l
u
m
n
s
o
f
μIn a hypercube,D
i
s
t
_
M
a
t
r
i
x
i
j
(
i
,
j
∈
V
m
a
p
) represents the hamming distance between k
i and k
j. It is shown in (6), where τ
i
j is the instantaneous value of k
i
j. The value of τ
i
j varies between -
1 and 1. Therefore, the cost function is reduced to (7) using hypercube embedding.(6)
D
i
s
t
_
M
a
t
r
i
x
i
j
=
∑
κ
=
1
η
τ
i
κ
-
τ
j
κ
2
w
h
e
r
e
,
k
i
j
=
1
i
f
τ
i
j
≥
0
0
i
f
τ
i
j
<
0
(7)
c
o
s
t
μ
=
∑
i
=
0
M
-
1
∑
j
=
0
M
-
1
∑
κ
=
1
η
ω
i
j
×
τ
i
κ
-
τ
j
κ
2The objective is thus confined to minimize the cost function given in (7). Evidently, it is a discrete optimization problem, where each state can opt only a particular binary state code.The convergence of Improved-IGHA depends on the convergence of its constituent algorithms, i.e., IGHA and the applied state assignment technique. Therefore, an algorithm with a high convergence speed is preferred to construct the state assignment technique for Improved-IGHA.The evolutionary technique, such as genetic algorithm (GA), presents a significant shortcoming as its convergence speed slows down near the global optimum [18, 19]. Similarly, particle swarm optimization (PSO) and differential evolution (DE) operate with a high convergence rate but offer premature convergence which is a critical drawback [20, 21]. In the literature, penalty-based approaches, such as Lagrangian technique and logarithmic-barrier function (LBF) method, have proven their potentials to obtain the optimum solution with a high convergence speed [22, 23]. These methods are advantageous in solving a discrete or combinatorial optimization problem [24, 25].Therefore, the LBF-based Gradient descent approach is adopted to construct the state assignment technique for Improved-IGHA. It is an interior point method that assures the feasible solution. The mathematical formulation of the cost minimization function is performed by LBF. Then, it is reduced iteratively by the gradient-projection approach. The flow chart for the Improved-IGHA is presented in Figure3.Figure 3
Flow chart for the improved iterative greedy heuristic based Hungarian algorithm (Improved-IGHA).In LBF technique, the search operation is performed in a continuous space domain to deduce the optimal points. Then, these points are discretized to obtain the optimal solution [26, 27].In LBF method, an objective function subject to inequality constraints is given in(8)
m
i
n
f
τ
s
.
t
.
c
o
n
s
t
r
a
i
n
t
i
τ
≥
0
,
i
=
1
,
…
,
uThe logarithmic barrier function to minimize the cost function (as in (7)) is given in (9). In LBF search, for any move which omits the constraints, the second term serves as a barrier [28] as shown in (9)
min
⁡
ψ
τ
,
ϕ
=
f
τ
+
ϕ
∑
i
=
1
u
log
e
⁡
c
o
n
s
t
r
a
i
n
t
i
τAt the iterationi
t
e
r
_
t, (9) is defined as shown in (10)
min
⁡
ψ
τ
,
ϕ
i
t
e
r
_
t
i
t
e
r
_
t
=
f
τ
+
ϕ
i
t
e
r
_
t
∑
i
=
1
u
log
e
⁡
c
o
n
s
t
r
a
i
n
t
i
τInitially, LBF selects a feasibleτ
0 and ϕ
0
>
0. Then, it chooses ϕ
i
t
e
r
_
t
+
1
=
σ
·
ϕ
i
t
e
r
_
t, where σ
<
1. This iterative process goes on until ϕ
i
t
e
r
_
t reaches an adequately small value.A full-fledged method is required to solve (10) with respect to τ. A first-order gradient-projection approach [29] is well-suited for iteratively minimizing (10). In this approach, the model parameters (a.k.a. weight vectors) are evaluated to minimize the objective function when an analytical calculation is not possible [30, 31]. In this approach, the underlying representation of the objective function of the problem is given in (11)
m
i
n
ψ
τ
,
ϕ
s
.
t
.
ϑ
τ
=
0An iteration of this projection method is defined by (12). In (12), ρ denotes the step size. ρ is chosen to be a small positive real number [29].(12)
τ
←
τ
-
ρ
∇
ψ
τ
,
ϕThus, small steps (i.e.,ρ) are taken in the negative gradient direction of the objective function as illustrated in (12). Then, (13) is used to outline the value of τ on the constraint surface at the next iteration (i.e., τ
(
i
t
e
r
_
t
+
1
)).(13)
τ
←
τ
ϑ
τ
=
0The convergence criterion for this iterative process is defined by (14), where θ
∈
[
0,1
].(14)
τ
i
t
e
r
_
t
+
1
-
τ
i
t
e
r
_
t
<
θIn this way, embedding problem is reduced to the determination ofM-binary η-vectors (as shown in (15)) which optimizes the cost function (i.e., (7)).(15)
τ
i
∈
τ
:
τ
∈
R
η
&
τ
2
=
1
;
i
∈
V
m
a
p
w
h
e
r
e
τ
2
d
e
n
o
t
e
s
t
h
e
n
o
r
m
o
f
τHence, the cost function (from (7)) is defined in terms of Hamming distance as shown in (16)
c
o
s
t
μ
=
∑
i
=
0
M
-
1
∑
j
=
0
M
-
1
ω
i
j
×
τ
i
-
τ
j
2
w
h
e
r
e
,
τ
i
=
τ
i
1
,
τ
i
2
,
…
,
τ
i
η
T
τ
i
-
τ
j
2
=
∑
κ
=
1
η
τ
i
κ
-
τ
j
κ
2The constraint (i.e., boundary condition) for this problem is formed, such as any two vertices on hypercube should not contain the same binary state code (i.e.,τ
i
-
τ
j
≠
0). Hence, the mathematical representation of the constraint is presented in (17)
c
o
n
s
t
r
a
i
n
t
τ
=
τ
i
-
τ
j
2
>
0By applying (16) and (17) on (9), the objective function for LBF is reduced to (18)
min
⁡
ψ
τ
,
ϕ
=
∑
i
=
0
M
-
1
∑
j
=
0
M
-
1
ω
i
j
×
τ
i
-
τ
j
2
+
ϕ
∑
i
=
0
M
-
1
∑
j
=
0
M
-
1
log
e
⁡
τ
i
-
τ
j
2Therefore, the entityϑ
(
τ
) (from (13)) is defined by (19)
ϑ
τ
=
τ
1
2
-
1
,
τ
2
2
-
1
,
…
,
τ
M
2
-
1
T
s
.
t
.
τ
=
τ
1
,
τ
2
,
…
,
τ
M
T
τ
i
=
τ
i
1
,
τ
i
2
,
…
,
τ
i
η
T
;
w
h
e
r
e
e
a
c
h
τ
i
1
≤
i
≤
MThe evaluation of the derivative term (i.e.,∇
ψ
(
τ
,
ϕ
)) is required to move in the gradient descent direction as shown in (12). The needed derivative term is obtained by putting (20), (21), (22), and (23) into (18). Hence, ∇
ψ
(
τ
,
ϕ
) is defined by (24).(20)
∂
∂
τ
i
τ
i
-
τ
j
2
=
2
τ
i
-
τ
j
(21)
∂
∂
τ
j
τ
i
-
τ
j
2
=
2
τ
j
-
τ
i
(22)
∂
∂
τ
i
log
e
⁡
τ
i
-
τ
j
2
=
2
τ
i
-
τ
j
τ
i
-
τ
j
2
(23)
∂
∂
τ
j
log
e
⁡
τ
i
-
τ
j
2
=
2
τ
j
-
τ
i
τ
i
-
τ
j
2
(24)
∇
ψ
τ
,
ϕ
=
2
∑
j
=
1
M
ω
1
j
×
τ
1
-
τ
j
+
ϕ
∑
j
=
1
M
τ
1
-
τ
j
τ
1
-
τ
j
2
∑
j
=
1
M
ω
2
j
×
τ
2
-
τ
j
+
ϕ
∑
j
=
1
M
τ
2
-
τ
j
τ
2
-
τ
j
2
⋯
⋯
⋯
∑
j
=
1
M
ω
M
j
×
τ
M
-
τ
j
+
ϕ
∑
j
=
1
M
τ
M
-
τ
j
τ
M
-
τ
j
2By applying (19) into (13), the normalized vector τ is defined as shown in (25)
τ
ϑ
τ
=
0
=
τ
1
τ
1
τ
2
τ
2
⋯
⋯
τ
M
τ
MIf (14) is satisfied, a solution vector which is defined as τ
^
i
j is obtained at the end of the iteration. Therefore, the required set of state codes (i.e., k
^
i
j) is deduced by discretizing τ
^
i
j using (26)
k
^
i
j
=
1
i
f
τ
^
i
j
≥
0
0
i
f
τ
^
i
j
<
0The pseudocode for the proposed state assignment approach is presented in Algorithm1.Algorithm 1:State assignment using logarithmic barrier-function based gradient descent approach for the Reconfigurable FSM.
Input:
the objective function defined by Equation (7)
Output:
μ
∗ (i.e., the final state code vector)
begin
Initialization:
μ
←
B
i
n
a
r
y
s
t
a
t
e
c
o
d
e
s;
ϕ
←
i
n
i
t
i
a
l
_
ϕ
(
s
.
t
.
ϕ
0
>
0
);
while (ϕ
>
f
i
n
a
l
_
ϕ)do
repeat
for
i
t
e
r
_
t
←
1
t
o
θ
τ
i
t
e
r
_
t
←
τ
(
i
t
e
r
_
t
-
1
)
-
ρ
{
∇
ψ
(
τ
,
ϕ
)
};
/
∗
b
y
E
q
u
a
t
i
o
n (12)
&
E
q
u
a
t
i
o
n (24)∗
/
end
return
τ
^
i
j
(
i
.
e
.
t
h
e
v
a
l
u
e
o
f
τ
a
t
t
h
e
i
t
e
r
a
t
i
o
n
θ
);
evaluate
k
^
i
j
=
1
,
i
f
τ
^
i
j
≥
0
;
0
,
i
f
τ
^
i
j
<
0
;
/
∗
b
y
E
q
u
a
t
i
o
n (26)∗
/
C
o
m
p
u
t
e
c
o
s
t
f
o
r
t
h
e
n
e
w
v
a
l
u
e
o
f
μ
u
s
i
n
g
E
q
u
a
t
i
o
n (7);
if (c
o
s
t
(
o
l
d
_
μ
)
≥
c
o
s
t
(
n
e
w
_
μ
))then
u
p
d
a
t
e
,
μ
∗
←
n
e
w
_
μ;
else if (c
o
s
t
(
o
l
d
_
μ
)
<
c
o
s
t
(
n
e
w
_
μ
))then
u
p
d
a
t
e
,
μ
∗
←
o
l
d
_
μ;
end
until
t
h
e
a
l
g
o
r
i
t
h
m
c
o
n
v
e
r
g
e
s
ϕ
←
σ
⋅
ϕ;
end
return
μ
∗;
end


## 3.2. An Illustrative Example for the Improved Reconfigurable FSMIM Architecture

The following MCNC FSM benchmarks [14] are considered to demonstrate the steps involved in the creation of the Improved Reconfigurable FSMIM architecture:(1)
t
r
a
i
n
11 (description is provided in Table 1)
(2)
l
i
o
n
9 (description is provided in Table 2)Table 1
Description oft
r
a
i
n
11 from MCNC FSM Benchmarks [14].
Input
PS
NS
O/P
x
1
x
2
y
1
0
0
S
0
S
0
0
1
0
S
0
S
1
-
0
1
S
0
S
2
-
1
0
S
1
S
1
1
0
0
S
1
S
3
1
1
1
S
1
S
5
1
0
1
S
2
S
2
1
0
0
S
2
S
7
1
1
1
S
2
S
9
1
0
0
S
3
S
3
1
0
1
S
3
S
4
1
0
1
S
4
S
4
1
0
0
S
4
S
0
-
1
1
S
5
S
5
1
0
1
S
5
S
6
1
0
1
S
6
S
6
1
0
0
S
6
S
0
-
0
0
S
7
S
7
1
1
0
S
7
S
8
1
1
0
S
8
S
8
1
0
0
S
8
S
0
-
1
1
S
9
S
9
1
1
0
S
9
S
10
1
1
0
S
10
S
10
1
0
0
S
10
S
0
-Table 2
Description ofl
i
o
n
9 from MCNC FSM Benchmarks [14].
Input
PS
NS
O/P
x
1
x
2
y
1
1
0
S
0
S
1
0
0
0
S
0
S
0
0
0
0
S
1
S
0
0
1
0
S
1
S
1
0
1
1
S
1
S
2
0
1
0
S
2
S
1
0
1
1
S
2
S
2
0
0
1
S
2
S
3
0
1
1
S
3
S
2
1
0
1
S
3
S
3
1
0
0
S
3
S
4
1
0
1
S
4
S
3
1
0
0
S
4
S
4
1
1
0
S
4
S
5
1
0
0
S
5
S
4
1
1
0
S
5
S
5
1
1
1
S
5
S
6
1
1
0
S
6
S
5
1
1
1
S
6
S
6
1
0
1
S
6
S
7
1
1
1
S
7
S
6
1
0
1
S
7
S
7
1
0
0
S
7
S
8
1
0
1
S
8
S
7
1
0
0
S
8
S
8
1The improved Reconfigurable FSMIM architecture is created by joining (A) Conventional FSMIM architecture and (B) Multiplexer bank (which defines the mode based reconfiguration). The optimal synthesis of the Multiplexer bank is done by the proposed Improved-IGHA. At the end of the proposed algorithm, a modified description of a single FSM (i.e.,b
a
s
e
_
c
k
t) is obtained which is used to create the Conventional FSMIM part [6]. The Improved-IGHA consists of the following steps:(i)
Initialization (Define b
a
s
e
_
c
k
t  and  r
e
c
o
n
_
c
k
t): t
r
a
i
n
1
1 is selected as b
a
s
e
_
c
k
t because its complexity is greater than l
i
o
n
9 as observed from their descriptions. Consequently, l
i
o
n
9 acts as r
e
c
o
n
_
c
k
t.
(ii)
Input and State Matching using Hungarian Algorithm: Input and state matchings are performed together using Algorithms 1, 2, 5, and 6 from [6]. Combinations of input lines of b
a
s
e
_
c
k
t (i.e., 2
P
2
=
2) are generated. For the first combination (
x
1
∣
t
r
a
i
n
11
,
x
2
∣
t
r
a
i
n
11
), states are matched as S
0
l
i
o
n
9
→
S
0
t
r
a
i
n
11, S
1
l
i
o
n
9
→
S
1
t
r
a
i
n
11, S
3
l
i
o
n
9
→
S
2
t
r
a
i
n
11, S
4
l
i
o
n
9
→
S
3
t
r
a
i
n
11, S
7
l
i
o
n
9
→
S
4
t
r
a
i
n
11, S
2
l
i
o
n
9
→
S
5
t
r
a
i
n
11, S
8
l
i
o
n
9
→
S
6
t
r
a
i
n
11, S
5
l
i
o
n
9
→
S
7
t
r
a
i
n
11, D
u
m
m
y
s
t
a
t
e
→
S
8
t
r
a
i
n
11, S
6
l
i
o
n
9
→
S
9
t
r
a
i
n
11, and D
u
m
m
y
s
t
a
t
e
→
S
1
0
t
r
a
i
n
11. It offers zero a
s
s
i
g
n
m
e
n
t
_
c
o
s
t  and  t
o
t
a
l
_
c
o
s
t. For the second combination (
x
2
∣
t
r
a
i
n
11
,
x
1
∣
t
r
a
i
n
11
), states are matched as S
0
l
i
o
n
9
→
S
0
t
r
a
i
n
11, S
3
l
i
o
n
9
→
S
1
t
r
a
i
n
11, S
1
l
i
o
n
9
→
S
2
t
r
a
i
n
11, S
4
l
i
o
n
9
→
S
3
t
r
a
i
n
11, S
5
l
i
o
n
9
→
S
4
t
r
a
i
n
11, S
2
l
i
o
n
9
→
S
5
t
r
a
i
n
11, D
u
m
m
y
s
t
a
t
e
→
S
6
t
r
a
i
n
11, S
7
l
i
o
n
9
→
S
7
t
r
a
i
n
11, S
8
l
i
o
n
9
→
S
8
t
r
a
i
n
11, S
6
l
i
o
n
9
→
S
9
t
r
a
i
n
11, and D
u
m
m
y
s
t
a
t
e
→
S
1
0
t
r
a
i
n
11. It also offers zero a
s
s
i
g
n
m
e
n
t
_
c
o
s
t  and  t
o
t
a
l
_
c
o
s
t. Therefore, the first combination (
x
1
∣
t
r
a
i
n
11
,
x
2
∣
t
r
a
i
n
11
) is finalized to match with (
x
1
∣
l
i
o
n
9
,
x
2
∣
l
i
o
n
9
).
(iii)
Dummy State and Position Replacement: The replacements of the dummy states and positions in b
a
s
e
_
c
k
t  and  r
e
c
o
n
_
c
k
t are performed using Algorithm 3 from [6]. The replaced dummy states (highlighted in “bold italic font”)  and dummy positions (highlighted in “bold font”) are presented in Tables 3 and 4.
(iv)
Output Matching using Bitwise-XOR Operations: Output Matching is not required in this case, as there is a single output line in b
a
s
e
_
c
k
t as well as in r
e
c
o
n
_
c
k
t.
(v)
Update the descriptions of FSMs: The updated descriptions of b
a
s
e
_
c
k
t  and  r
e
c
o
n
_
c
k
t are presented in Tables 3 and 4, respectively.
(vi)
State assignment using logarithmic barrier function based gradient descent approach for the Reconfigurable FSM: The pictorial representation of state transitions for b
a
s
e
_
c
k
t  and  r
e
c
o
n
_
c
k
t (from Tables 3 and 4) is given in Figure 4. Therefore, the weight matrix ω is formed using (1). It is given in (27)
ω
=
2
2
1
0
0
0
0
0
0
0
0
1
2
0
1
0
2
0
0
0
0
0
0
0
2
1
0
1
0
1
0
1
0
0
0
1
2
1
0
0
1
0
0
0
1
0
0
0
2
0
1
0
0
1
0
0
1
1
0
0
2
1
0
0
0
0
1
0
0
0
1
0
2
0
0
0
0
0
0
0
1
0
0
0
2
1
1
0
2
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
1
0
2
1
2
1
0
0
0
0
0
0
0
0
1
The proposed state assignment algorithm starts by considering the binary state codes as an initial solution. It offers the cost as 62 (from (2)).
At the10
0
t
h iteration, the instantaneous value τ (from previous iteration, τ
(
i
t
e
r
_
99
)) is obtained as defined by (28)
τ
i
t
e
r
_
99
=
0.51
0.85
-
0.85
0.84
-
0.52
-
0.85
-
0.51
0.85
0.85
-
0.52
-
0.51
-
0.85
0.84
-
0.51
0.51
-
0.52
-
0.51
0.51
0.85
-
0.52
-
0.85
-
0.52
-
0.85
-
0.51
-
0.52
0.84
-
0.51
-
0.85
0.84
0.51
-
0.52
-
0.85
0.51
-
0.85
-
0.85
0.51
0.85
0.84
0.51
-
0.52
-
0.51
0.51
-
0.52
0.85
T
The derivative (from (24)) is evaluated as defined by (29)
∇
ψ
τ
,
ϕ
=
-
1517
-
1224
-
2118
2126
-
1739
1258
-
2622
2960
2135
701
1558
402
-
1223
1598
1793
736
722
-
739
2886
760
1262
723
-
2888
1550
1506
-
1209
-
1775
401
-
398
1754
763
-
2889
-
1549
-
2118
418
-
1579
2945
2953
1761
-
1736
-
2583
-
1504
1506
207
9
T
So, the current value ofτ (i.e., τ
(
i
t
e
r
_
100
)) is obtained from (12). It is given in (30) by choosing ρ
=
1
0
-
3 (a very small value). (30)
τ
i
t
e
r
_
100
=
2.027
2.074
1.268
-
1.286
1.219
-
2.108
2.112
-
2.11
-
1.285
-
1.221
-
2.068
-
1.252
2.063
-
2.108
-
1.283
-
1.256
-
1.232
1.249
-
2.036
-
1.28
-
2.112
-
1.243
2.038
-
2.06
-
2.026
2.049
1.265
-
1.251
1.238
-
1.244
-
1.283
2.039
2.059
1.268
-
1.268
2.089
-
2.095
-
2.113
-
1.251
1.216
2.073
2.014
-
2.026
-
1.229
T
Then,τ is directed towards the unity radius hypersphere. It is given in (31)
τ
^
=
0.85
0.84
0.51
-
0.52
0.51
-
0.85
0.85
-
0.85
-
0.52
-
0.51
-
0.85
-
0.51
0.84
-
0.85
-
0.52
-
0.51
-
0.51
0.51
-
0.85
-
0.52
-
0.85
-
0.52
0.84
-
0.85
-
0.85
0.85
0.51
-
0.51
0.51
-
0.51
-
0.52
0.85
0.85
0.51
-
0.51
0.85
-
0.85
-
0.85
-
0.51
0.51
0.84
0.84
-
0.85
-
0.51
T
←
S
0
←
S
1
←
S
2
←
S
3
←
S
4
←
S
5
←
S
6
←
S
7
←
S
8
←
S
9
←
S
10
The required set of state codes is deduced asS
0
→
1110, S
1
→
1010, S
2
→
0000, S
3
→
1000, S
4
→
0100, S
5
→
0010, S
6
→
0110, S
7
→
1001, S
8
→
1101, S
9
→
0001, and S
10
→
110
0 by discretizing the current value of τ using (26). Hence, the cost is reduced to 48 (from (2)).Table 3
Updated description oft
r
a
i
n
11.
Input
PS
NS
O/P
x
1
x
2
y
1
0
0
S
0
S
0
0
1
0
S
0
S
1
-
0
1
S
0
S
2
-
1
0
S
1
S
1
1
0
0
S
1
S
3
1
1
1
S
1
S
5
1
0
1
S
2
S
2
1
0
0
S
2
S
7
1
1
1
S
2
S
9
1
0
0
S
3
S
3
1
0
1
S
3
S
4
1
0
0
S
3
S
3
1
0
1
S
4
S
4
1
0
0
S
4
S
0
-
0
1
S
4
S
4
1
1
1
S
5
S
5
1
0
1
S
5
S
6
1
1
1
S
5
S
5
1
0
1
S
6
S
6
1
0
0
S
6
S
0
-
0
0
S
7
S
7
1
1
0
S
7
S
8
1
1
0
S
7
S
8
1
1
0
S
8
S
8
1
0
0
S
8
S
0
-
0
0
S
8
S
0
-
1
1
S
9
S
9
1
1
0
S
9
S
10
1
1
1
S
9
S
9
1
1
0
S
10
S
10
1
0
0
S
10
S
0
-
0
0
S
10
S
0
-Table 4
Updated description ofl
i
o
n
9.
Input
PS
NS
O/P
x
1
x
2
y
1
0
0
S
0
S
0
0
1
0
S
0
S
1
0
0
0
S
0
S
0
0
1
0
S
1
S
1
0
0
0
S
1
S
0
0
1
1
S
1
S
5
0
0
1
S
2
S
2
1
0
0
S
2
S
3
1
1
1
S
2
S
5
1
0
0
S
3
S
3
1
0
1
S
3
S
2
1
1
0
S
3
S
7
1
0
1
S
4
S
4
1
0
0
S
4
S
6
1
1
1
S
4
S
9
1
1
1
S
5
S
5
0
0
1
S
5
S
2
0
1
0
S
5
S
1
0
0
1
S
6
S
4
1
0
0
S
6
S
6
1
0
0
S
7
S
3
1
1
0
S
7
S
7
1
1
1
S
7
S
9
1
1
0
S8
S1
0
0
0
S8
S0
0
0
0
S8
S0
0
1
1
S
9
S
9
1
1
0
S
9
S
7
1
0
1
S
9
S
4
1
1
0
S10
S1
0
0
0
S10
S0
0
0
0
S10
S0
0Figure 4
The pictorial representation of state transitions forb
a
s
e
_
c
k
t  and  r
e
c
o
n
_
c
k
t.In the end, a Bitwise-XOR operation is performed between the updated descriptions oft
r
a
i
n
11  and  l
i
o
n
9. It provides the Multiplexer bank (i.e., part-B). The updated descriptions of t
r
a
i
n
1
1 are used to construct the Conventional FSMIM part (i.e., part-A).


## 4. Numerical Results and Discussions

To validate the proposed approach, experiments have been performed using MCNC FSM benchmarks [14]. MATLAB (2016b) environment is used to implement the proposed Improved-IGHA. It produces the optimized description for the constituting parts of the Improved Reconfigurable FSMIM architecture. The obtained description is then converted into the Verilog HDL code using MATLAB HDL Coder tool-box. The implementation of the Improved Reconfigurable FSMIM architecture is performed on the Virtex-6 speed-3 device as in [6, 11]. The configuration of the workstation to execute computations is as follows: Intel(R) Core i7 (6th Gen), 16 GB RAM, and 3.5 GHz CPU.In Improved-IGHA, combinations of input lines, states, and output lines are generated using permutation to perform input, state, and output matching, respectively. The number of input and output lines used for matching is restricted to 7 (i.e.,7
P
7
=
504
0 combinations) to utilize the resources efficiently. Hence, the information content of an input/output line becomes the criteria for selection. An input/output line with high information content is preferred.The following MCNC FSM benchmarks [14] are selected to illustrate the implementation of the Improved Reconfigurable FSMIM architecture and present its comparative analysis with the existing literature: s
1494, s
832, s
208, p
l
a
n
e
t, s
386, s
a
n
d, m
c, s
t
y
r, c
s
e, e
x
6, p
l
a
n
e
t
1, and s
1488.s
149
4 is chosen as b
a
s
e
_
c
k
t (i.e., the circuit added at the 0
t
h iteration of Improved-IGHA), as it is more complex (i.e., the total number of transitions is high) as compared with the other FSMs in the set. The other FSMs in the set are added iteratively in the design in their respective order.In an FSM, a specific state is chosen only if a particular set of input bits (i.e., 1’s or 0’s) are present. Hence, the percentage of 1’s and 0’s together in an input line acts as information content as shown in Table5 (the selected input lines to match with b
a
s
e
_
c
k
t are highlighted). Similarly, the output is always defined by “1.” Hence, the percentage of 1’s in an output line serves as information content as shown in Tables 6 and 7 (the selected output lines to match with b
a
s
e
_
c
k
t are highlighted).Table 5
The information content for input lines of MCNC FSM Benchmarks and their matching with input lines ofb
a
s
e
_
c
k
t.
FSM
No. of I/P
Input lines with their
Matched withb
a
s
e
_
c
k
t
No. of state
information content
s
1494
8
x
1
99.6
%, x
2
(
10
%
),
x
1, x
3,
48
x
3
25.6
%, x
4
(
24.8
%
)
,
x
4, x
5,
x
5
(
12.4
%
), x
6
(
66
%
)
,
x
6, x
7,
x
7
(
41.6
%
), x
8
(
20.4
%
)
x
8
s
832
18
x
1
(
2.04
%
), x
2
(
6.93
%
),
25
x
3
(
2.44
%
), x
4
(
4.48
%
),
x
5
(
70.61
%
), x
6
(
1.63
%
),
x
7
(
14.28
%
), x
8
(
9.79
%
),
x
9, x
11,
x
9
(
8.97
%
), x
10
(
8.16
%
),
x
18, x
17,
x
11
8.57
%, x
12
(
6.12
%
),
x
8, x
7, x
5
x
13
4.081
%, x
14
(
4.08
%
),
x
15
1.63
%, x
16
(
1.63
%
),
x
17
(
59.18
%
), x
18
(
81.63
%
),
s
208
11
x
1
(
96.73
%
), x
2
(
91.5
%
),
18
x
3
0
%, x
4
(
0
%
),
x
1, x
8,
x
5
0
%, x
6
(
2.61
%
)
,
x
6, x
9,
x
7
(
2.61
%
), x
8
(
5.22
%
),
x
11, x
2,
x
9
(
12.41
%
), x
10
(
49.01
%
)
,
x
10
x
11
(
77.12
%
)
p
l
a
n
e
t
7
x
1, x
2,
x
6, x
3,
48
x
3, x
4,
x
4,x
2,
x
5, x
6,
x
5, x
7,
x
7
x
1
s
386
7
x
1, x
2
,
x
4, x
3,
13
x
3, x
4
,
x
2, x
7,
x
5, x
6
,
x
1, x
5,
x
7
x
6
s
a
n
d
11
x
1
(
52.17
%
), x
2
(
52.17
%
),
32
x
3
(
52.17
%
), x
4
(
52.17
%
),
x
4, x
2,
x
5
(
24.45
%
), x
6
(
3.26
%
),
x
1, x
10,
x
7
(
18.47
%
), x
8
(
26.63
%
),
x
5, x
3,
x
9
(
1.08
%
), x
10
(
79.89
%
),
x
8
x
11
(
19.56
%
)
m
c
3
−,x
3,
4
x
1, x
2,
x
1,−,
x
3
x
2, −,
-
s
t
y
r
9
x
1
(
92.16
%
), x
2
(
4.81
%
),
30
x
3
(
48.79
%
), x
4
(
69.87
%
),
x
2, x
4,
x
5
(
68.67
%
), x
6
(
39.15
%
),
x
5, x
3,
x
7
(
4.81
%
), x
8
(
5.42
%
),
x
8, x
6, x
1
x
9
(
3.61
%
)
c
s
e
7
x
1, x
2,
x
5, x
2,
16
x
3, x
4,
x
7, x
3,
x
5, x
6,
x
4, x
1,
x
7
x
6
e
x
6
5
x
3, x
4,
8
x
1, x
2,
−,x
1,
x
3, x
4, x
5
x
2, −,
x
5
p
l
a
n
e
t
1
7
x
1, x
2,
x
5
,
x
1,
48
x
3, x
4,
x
6
,
x
3,
x
5, x
6,
x
4
,
x
2,
x
7
x
7
s
1488
8
x
1
(
98.8
%
), x
2
(
12.74
%
),
x
1, x
5,
48
x
3
(
23.5
%
), x
4
(
23.9
%
),
x
3, x
4,
x
5
(
16.33
%
), x
6
(
65.73
%
),
x
8, x
7,
x
7
(
40.23
%
), x
8
(
18.32
%
)
x
6Table 6
The information content for output lines of MCNC FSM Benchmarks & their matching with output lines ofb
a
s
e
_
c
k
t.
FSM
No. of O/P
Output lines with their
Matched withb
a
s
e
_
c
k
t
information content
s
1494
19
y
1
(
24.8
%
), y
2
(
4.8
%
), y
3
(
5.2
%
),
y
4
(
3.2
%
), y
5
2.4
%, y
6
(
2.4
%
),
y
11, y
12,
y
7
(
15.2
%
), y
8
(
25.2
%
), y
9
(
1.6
%
),
y
13, y
14,
y
10
(
6.4
%
), y
11
(
87.2
%
), y
12
(
40.4
%
)
,
y
15, y
17,
y
13
(
32.8
%
), y
14
(
70.4
%
), y
15
(
38.4
%
)
,
y
19
y
16
(
18.4
%
), y
17
70
%, y
18
(
31.2
%
),
y
19
(
49.2
%
)
s
832
19
y
1
(
5.71
%
), y
2
(
2.44
%
), y
3
(
1.22
%
),
y
4
(
1.63
%
), y
5
(
2.44
%
), y
6
(
0.81
%
),
y
19, y
15,
y
7
(
2.44
%
), y
8
73.06
%, y
9
(
0.81
%
),
y
2, y
8,
y
10
(
0.81
%
), y
11
(
5.3
%
), y
12
(
2.44
%
),
y
7, y
1,
y
13
(
0.81
%
), y
14
1.63
%, y
15
(
6.12
%
)
,
y
11
y
16
(
0.81
%
), y
17
(
1.63
%
), y
18
(
2.44
%
),
y
19
(
41.22
%
)
s
208
2
y
1, y
2
−,y
1,
−, −,
y
2, −,
−
p
l
a
n
e
t
19
y
1
(
54.78
%
), y
2
(
23.47
%
), y
3
(
69.56
%
)
,
y
4
(
16.52
%
), y
5
(
32.17
%
), y
6
(
73.91
%
)
,
y
6
,
y
8,
y
7
(
26.08
%
), y
8
(
28.69
%
), y
9
(
91.3
%
)
,
y
9
,
y
5,
y
10
(
4.34
%
), y
11
(
1.73
%
), y
12
(
22.6
%
),
y
3
,
y
1,
y
13
(
11.3
%
), y
14
(
2.6
%
), y
15
(
3.47
%
),
y
7
y
16
(
1.73
%
)
,
y
17
(
3.47
%
)
,
y
18
(
3.47
%
),
y
19
(
20
%
)
s
386
7
y
6, y
1,
y
1, y
2, y
3
,
y
3, y
4,
y
4, y
5, y
6
,
y
7
y
7, y
5,
y
2
s
a
n
d
9
y
1
(
22.28
%
), y
2
(
36.41
%
), y
3
(
16.84
%
)
,
y
4, y
6,
y
4
(
62.5
%
), y
5
(
15.76
%
), y
6
(
8.15
%
)
,
y
2
,
y
7,
y
7
(
17.39
%
), y
8
(
1.63
%
), y
9
(
3.26
%
)
y
3, y
5, y
1
m
c
5
y
4, y
2,
y
1, y
2, y
3,
y
5, y
1,
y
4, y
5
y
3, −,
-
s
t
y
r
10
y
1
(
15.66
%
), y
2
(
33.73
%
), y
3
(
25.9
%
)
,
y
5, y
6,
y
4
(
3.012
%
), y
5
(
8.43
%
), y
6
(
7.22
%
)
,
y
7, y
8,
y
7
(
5.42
%
), y
8
(
11.445
%
), y
9
(
3.614
%
),
y
3, y
2,
y
10
(
4.819
%
)
y
1
c
s
e
7
y
7
,
y
3,
y
1, y
2, y
3,
y
5
,
y
1,
y
4, y
5, y
6, y
7
y
4
,
y
6,
y
2
e
x
6
8
y
1
(
58.82
%
), y
2
(
29.41
%
), y
3
(
55.88
%
)
,
y
5, y
8,
y
4
(
29.41
%
), y
5
(
50
%
), y
6
(
26.47
%
)
,
y
4, y
1,
y
7
5.88
%, y
8
(
23.52
%
)
y
6, y
2, y
3Table 7
The information content for output lines of MCNC FSM Benchmarks and their matching with output lines ofb
a
s
e
_
c
k
t.
FSM
No. of O/P
Output lines with their
Matched withb
a
s
e
_
c
k
t
information content
p
l
a
n
e
t
1
19
y
1
(
54.78
%
), y
2
(
23.47
%
), y
3
(
69.56
%
),
y
4
(
16.52
%
), y
5
(
32.17
%
), y
6
(
73.91
%
),
y
6, y
7,
y
7
(
26.08
%
), y
8
(
28.69
%
), y
9
(
91.3
%
),
y
1, y
8,
y
10
(
4.34
%
), y
11
(
1.73
%
), y
12
(
22.6
%
),
y
5, y
3,
y
13
(
11.3
%
), y
14
(
2.6
%
), y
15
(
3.47
%
),
y
9
y
16
(
1.73
%
), y
17
(
3.47
%
), y
18
(
3.47
%
),
y
19
(
20
%
)
s
1488
19
y
1
(
2.39
%
), y
2
(
2.78
%
), y
3
(
1.59
%
),
y
4
(
5.17
%
), y
5
(
2.39
%
), y
6
(
15.13
%
),
y
18, y
7,
y
7
(
71.31
%
), y
8
(
3.98
%
), y
9
(
51.39
%
),
y
13, y
19,
y
10
(
6.3
%
), y
11
(
16.7
%
), y
12
(
37.1
%
)
,
y
9, y
15,
y
13
(
70.5
%
), y
14
(
24.3
%
), y
15
(
87.6
%
),
y
12
y
16
(
31.1
%
), y
17
(
25.4
%
), y
18
(
31.4
%
)
,
y
19
(
39.84
%
)At the first phase of Improved-IGHA, input and state matching are performed together, and optimal assignments (with respect tob
a
s
e
_
c
k
t) are made. It is presented in Table 5. All the r
e
c
o
n
_
c
k
t states are mapped onto b
a
s
e
_
c
k
t states in their respective order. Output matching (with respect to b
a
s
e
_
c
k
t) is performed iteratively by Bitwise-XOR operations. It is presented in Tables 6 and 7. Then, after updating the descriptions of constituting FSMs, the state assignment using logarithmic barrier function based gradient descent approach is performed.To present a comparative analysis of the total computation time required by IGHA [6] and Improved-IGHA, an inbuilt feature in MATLAB named “stopwatch timer” is used. It evaluates the elapsed time (i.e., the execution time between the starting and stopping of a function). As evident from the literature [6], linear assignment problems (LAPs) are solved several times by IGHA to perform matchings among all generated combinations to add r
e
c
o
n
_
c
k
t
_
b
∈
{
r
e
c
o
n
_
c
k
t
_
1
,
…
,
r
e
c
o
n
_
c
k
t
_
B
} iteratively. The convergence period of IGHA to solve a single LAP ranges from 0.0
3 ms to 0.6 ms. Hence, the total elapsed time taken by IGHA (i.e., t
I
G) is given in (32). The convergence time for the state assignment using LBF-based gradient descent approach (i.e., t
S
E) to add r
e
c
o
n
_
c
k
t
_
b
∈
{
r
e
c
o
n
_
c
k
t
_
1
,
…
,
r
e
c
o
n
_
c
k
t
_
B
} iteratively is given in Table 8. Therefore, the total elapsed time taken by Improved-IGHA (i.e., t
P
r
o
p
o
s
e
d) is an addition of t
I
G  and  t
S
E (from Figure 3). It is presented in Table 8.(32)
T
o
t
a
l
e
l
a
p
s
e
d
t
i
m
e
f
o
r
I
G
H
A
=
∑
r
e
c
o
n
_
c
k
t
_
b
1
+
E
M
_
b
a
s
e
×
M
_
r
e
c
o
n
×
E
l
a
p
s
e
d
t
i
m
e
f
o
r
I
G
H
A
t
o
s
o
l
v
e
a
s
i
n
g
l
e
L
A
P
s
.
t
.
E
=
P
L
_
b
a
s
e
L
_
r
e
c
o
n
i
f
L
_
b
a
s
e
≥
L
_
r
e
c
o
n
;
P
L
_
r
e
c
o
n
L
_
b
a
s
e
i
f
L
_
b
a
s
e
<
L
_
r
e
c
o
n
;
r
e
c
o
n
_
c
k
t
_
b
∈
r
e
c
o
n
_
c
k
t
_
1
,
…
,
r
e
c
o
n
_
c
k
t
_
B
.Table 8
Comparative analysis of the total computation time required by IGHA [6] and Improved-IGHA.
Iteration No.
FSM included
Total elapsed time
Total elapsed time
Total elapsed time for Improved-IGHA
in the specific
for IGHA [6]
for state encoding
(Hrs)t
P
r
o
p
o
s
e
d
=
t
I
G
+
t
S
E
iteration
(Hrs)t
I
G
tech. (ms)t
S
E
∵
t
I
G
≫
t
S
E
,
∴
t
P
r
o
p
o
s
e
d
≅
t
I
G
0
t
h
s
1494
0
296.529
0
1
s
t
s
832
25.34
214.468
25.34
2
n
d
s
208
18.57
156.062
18.57
3
r
d
p
l
a
n
e
t
48.65
338.560
48.65
4
t
h
s
386
13.17
182.808
13.17
5
t
h
s
a
n
d
32.43
293.894
32.43
6
t
h
m
c
0.182
148.784
0.182
7
t
h
s
t
y
r
30.409
249.509
30.409
8
t
h
c
s
e
16.21
387.923
16.21
9
t
h
e
x
6
4.38
167.144
4.38
1
0
t
h
p
l
a
n
e
t
1
48.544
312.809
48.544
1
1
t
h
s
1488
48.654
326.406
48.654The experimental results presented in Table8 illustrate that the total computation time required by IGHA is far higher than the convergence time for the proposed state assignment technique (i.e., t
I
G
≫
t
S
E). Therefore, the total computation time required by Improved-IGHA is equivalent to the total computation time needed by IGHA (i.e., t
P
r
o
p
o
s
e
d
≅
t
I
G).Convergence plot for the state assignment using logarithmic barrier function based gradient descent approach after adding the last constituting FSM in the proposed architecture is presented in Figure5. It starts by taking binary state codes as an initial code. The cost offered to the proposed architecture is calculated by (2). It converges to 200 iterations. The cost is reduced from 1028 to 923 as shown in Figure 5. Consequently, at 20
0
t
h iteration, the following state codes are obtained: S
0
→
010111, S
1
→
000000, S
2
→
000111, S
3
→
110000, S
4
→
010100, S
5
→
110101, S
6
→
000110, S
7
→
011101, S
8
→
001100, S
9
→
011010, S
10
→
011110, S
11
→
001110, S
12
→
010110, S
13
→
111011, S
14
→
000011, S
15
→
100110, S
16
→
110111, S
17
→
001010, S
18
→
011100, S
19
→
100001, S
20
→
101001, S
21
→
110010, S
22
→
100000, S
23
→
001000, S
24
→
001111, S
25
→
101101, S
26
→
010011, S
27
→
101010, S
28
→
110001, S
29
→
001011, S
30
→
111010, S
31
→
011111, S
32
→
000101, S
33
→
000100, S
34
→
111101, S
35
→
000001, S
36
→
001101, S
37
→
101000, S
38
→
000010, S
39
→
100111, S
40
→
110110, S
41
→
011001, S
42
→
100010, S
43
→
001001, S
44
→
010001, S
45
→
100101, S
46
→
101111, and S
47
→
010010.Figure 5
Convergence plot for the state assignment using logarithmic barrier function based gradient descent approach after adding the last constituting FSM in the proposed architecture.At the last phase of Improved-IGHA, a mutual Bitwise-XOR operation is conducted between the updated descriptions of FSMs. Therefore, the constituting parts of the proposed architecture are created. The individual share of constituent FSMs in the Improved-Reconfigurable FSMIM architecture is determined by the difference between the occupied LUTs in the recent and its previous iteration. After adding all the constituting FSMs in the proposed design (i.e., at the last iteration), the total LUT consumption and operating frequency are obtained. It is presented in Table9.Table 9
Implementation of the Improved Reconfigurable FSMIM architecture on the Virtex-6 speed-3 device in an iterative manner.
Iteration No.
FSM included
#LUTs occupied
Maximum
Maximum
#LUTs occupied by the FSM
in the specific
in the specific
Operating
Path
(#LUTs in the current iteration
iteration
iteration
Frequency (MHz)
Delay (ns)
- #LUTs in the previous iteration)
0
t
h
s
1494
40
831.693
3.898
40
1
s
t
s
832
97
803.44
4.288
57
2
n
d
s
208
114
793.583
5.252
17
3
r
d
p
l
a
n
e
t
142
785.326
4.219
28
4
t
h
s
386
157
776.863
4.534
15
5
t
h
s
a
n
d
187
760.88
4.117
30
6
t
h
m
c
198
757.237
3.854
11
7
t
h
s
t
y
r
217
743.431
4.204
19
8
t
h
c
s
e
240
713.929
4.401
23
9
t
h
e
x
6
249
704.892
4.649
9
1
0
t
h
p
l
a
n
e
t
1
274
690.83
4.977
25
1
1
t
h
s
1488
293
676.928
5.151
19
#LUTs→ number of LUTs occupied in ISEExperimental results for the proposed architecture illustrates a significant area reduction by an average of 20.38%  and speed improvement by an average of 32.73% over VRMUX [11] during FPGA implementation. It also demonstrates an adequate area reduction by an average of 16.05%  and speed improvement by an average of 1.77% over Reconfigurable FSMIM-S architecture [6] during FPGA implementation. When these results are compared with CRMUX [11], a speed improvement by an average of 11.06% is obtained. The proposed architecture requires an average of 58.38% more LUTs as compared with CRMUX [11] during FPGA implementation. It is the only trade-off for the proposed design. A comparative analysis of the hardware consumption and maximum operating frequency variation on FPGA implementation is presented in Figures 6 and 7, respectively.Figure 6
Comparative analysis of the number of LUT consumption on FPGA implementation.Figure 7
Comparative analysis of maximum operating frequency on FPGA implementation.


## 5. Concluding Remarks

This article furnishes the framework for the Improved-Reconfigurable FSMIM architecture. The Improved-Reconfigurable FSMIM architecture is created by joining the following two parts: (A) Conventional FSMIM architecture and (B) Multiplexer bank (which defines the mode based reconfiguration). An improved version of iterative greedy heuristic based Hungarian algorithm (Improved-IGHA) is proposed to establish the constituting parts as mentioned earlier. Improved-IGHA is an integration of IGHA [6] and a state assignment using logarithmic barrier function based gradient descent approach. It reduces the hardware consumption of the proposed architecture by performing an optimal state encoding. An illustrative example using MCNC FSM benchmarks is also given to demonstrate the steps involved in the creation of the proposed architecture.The proposed architecture illustrates a significant area reduction by an average of 20.38% and speed improvement by an average of 32.73% over VRMUX [11] during FPGA implementation. It also demonstrates an adequate area reduction by an average of 16.05% and speed improvement by an average of 1.77% over Reconfigurable FSMIM-S architecture [6] during FPGA implementation. When these results are compared with CRMUX [11], a speed improvement by an average of 11.06% is obtained. The proposed architecture requires an average of 58.38% more LUTs as compared with CRMUX [11] during FPGA implementation. It is the only trade-off for the proposed design.Further, the proposed architecture will be investigated to develop an efficient architecture for multistage signal processing [1, 2] and circuit testing [5] based applications.



---

*Source: 3727254-2019-04-01.xml*