Valery Salauyou

Michal Ostapczuk

State assignment of finite-state machines by using the values of input variables

Keywords: finite state machine (FSM), field programmable gate array (FPGA), state assignment, area minimization, state splitting, look up table

In this paper, we propose the method of FSM synthesis on field programmable gate arrays (FPGAs) when input variables are used for state assignment. For this purpose we offer a combined structural model of class A and class E FSMs. This paper also describes in detail the algorithms for synthesis a class AE FSM which consists of splitting of internal states for performance of necessary conditions for synthesis of the class E FSM and state assignment of the class AE FSM. It is shown that the proposed method reduces the area for all families of FPGAs by a factor of 1.19-1.39 on average and by a factor of three for certain families. Practical issues concerning the method and the specific features of its use are discussed, and possible directions of the elaboration of this approach are proposed.

Introduction

In the general case, a digital system can be represented by a set of combinational circuits and finite state machines (FSMs). FSMs are also widely used as individual units as controllers and control devices. Usually, when working on a project, the designer has to develop new FSMs each time. It is clear that the parameters of FSMs used in a digital system to a large extent determine the success of the whole project. For this reason, the issue of minimization of FSMs is very important. As the FSM optimization criteria, one typically uses area, delay, and power consumption. Presently, field programmable gate arrays (FPGAs) are widely used in digital systems; for this reason, many FSM optimization methods are designed for the implementation of FSMs based in FPGAs. The idea of using the values of the input and output variables of the FSM for encoding its internal states was first proposed in [START_REF] Mccluskey | Reduction of Feedback Loops in Sequential Circuits and Carry Leads in Iterative Networks[END_REF]. Later, this approach was elaborated in [START_REF] Pomeranz | STOIC: State Assignment Based on Output/Input Functions[END_REF], where various combinations of the input and output variables that can be used for encoding the internal states are considered. The choice of the minimum number of input and output variables for encoding is an NP-hard problem. In [START_REF] Forrest | ODE : Output Direct State Machine Encoding[END_REF], it was pro-posed to use the values of the output variables of the Moor FSM as the codes of the internal states.

In [START_REF] Solovjev | Synthesis of Sequential Circuits on Programmable Logic Devices Based on New Models of Finite State Machines[END_REF], structural models of FSMs based on the architectural capabilities of FPGAs were proposed; these models make it possible to use the values of the FSM input and output variables as internal state codes. A new classification of structural models of FSMs is given. Here the class A and B FSMs are traditional of Mealy and Moore FSMs accordingly. In the class C (Mealy) and the class D (Moore) FSMs the value of an output vector completely coincides with the code of the present state of the FSM. In the class E (Mealy) and class F (Moore) FSMs the value of an input vector completely coincides with the code of the next state of the FSM.

In [START_REF] Solov | Minimization of Mealy Finite-State Machines by Using the Values of the Output Variables for State Assignment[END_REF], the synthesis method of Mealy FSMs was proposed, where the values of output variables are used as the codes of FSM states. In this paper, we present the method of FSM synthesis which allows, unlike [START_REF] Solov | Minimization of Mealy Finite-State Machines by Using the Values of the Output Variables for State Assignment[END_REF], to use the values of input variables as the codes of FSM states. For this purpose, the structural model of the class E FSM [START_REF] Solovjev | Synthesis of Sequential Circuits on Programmable Logic Devices Based on New Models of Finite State Machines[END_REF] is used.

Structural FSM models

The most general model of the Mealy FSM can be described by means of following equations:

), , ( ); , (

1 t t t t t t a z w a z a     
where Φ is the transition function, Ψ is the output function, a t is the present state of the FSM at time t (t=1,2,3,...), a t+1 is the next state of the FSM, z t is a collection of values of the input variables (the input vector) on the FSM input at time t, and w t is a collection of values of the output variables (the output vector) formed at time t.

The Mealy FSM in classification [START_REF] Solovjev | Synthesis of Sequential Circuits on Programmable Logic Devices Based on New Models of Finite State Machines[END_REF] received a title the class A FSM. The structural model of the Mealy FSM show on fig. 1,a, where CL Φ is the combinational circuit forming the values of the transition functions, CL Ψ is the combinational circuit forming the values of the output functions, and RG is the FSM's memory. In the class E FSM the value of the input vector z t determines the code of the next state a t+1 ; therefore, the equations of functioning of the class E FSM have the following view:

), , ( ;

1 t t t t t a z w z a    
In contrast to the Mealy FSM, the structure of the class E FSM does not include the combinational circuit CL Φ (fig. 1,b) that allows to build FSMs of a low cost (an area) and a high-speed performance.

However in practice, the "pure" type of the class E FSM meets very rarely. Therefore, in the present work we offer the combined model of the class AE FSM. In the class AE FSM the codes of internal states are divided on two parts: one part is defined by the value of input variables, and the second part is formed the same as in the class A FSM, by means of combinational circuit CL Φ (fig. 2 The memory of the class AE FSM is presented by two registers RG A and RG E which correspond to the class A and the class E FSMs. The internal state a t of the class AE FSM is defined by a concatenation of two states: a' t and a" t , i.e. a t = {a' t , a" t }, where a' t is the value on outputs of the register RG E , and a" t is the value on outputs of the register RG A . The code of the next state a t+1 also is defined by the concatenation of two states: a' t+1 and a" t+1 , i.e. a t+1 = {a' t+1 , a" t+1 }. Here the code of the state a' t+1 coincides with the value of the input vector z t , and the code of the state a" t+1 is formed by the combinational circuit CL Φ on the basis of the input vector z t and the code of the state a t . Functioning of the class AE FSM can be described by means of following equations:

). , ( ); , (

U(a i ) = {X(a m ,a i ) | a m  B(a i )}, (1)
where X(a m ,a i ) is a collection of values of the input variables (a transition condition or an input vector) that initiates the transition from the state a m to the state a i , B(a i ) is the set of states, transitions from which terminate in the state a i .

The state a i , a i  A, is a state of the class E FSM, i.e.

a i  A E , if next conditions are satisfied: | U(a i ) | = 1 (2) U(a i )  U(a j ) =  at i  j for all a j  A, ( 3
)
where |M| is the cardinality (the number of elements) of the set M,  is an empty set.

A performance of the condition [START_REF] Pomeranz | STOIC: State Assignment Based on Output/Input Functions[END_REF] guarantees that all transitions to the state a i are carried out by the same transition condition (i.e. the state a i has only one code), and a performance of the condition (3) provides a determinacy of a FSM behavior (i.e. the transition condition in some state a i does not initiate passages to other FSM states).

The FSM is the class E FSM if all its states are states of the class E FSM, i.e. A E = A. In other words, the finite state machine is the class E FSM if for all its states conditions (2) and (3) are satisfied.

The satisfaction of the conditions (2) is carried out by splitting of FSM states. Let, for example, for some state a i , a i  A, takes place |U(a i )| = Q  1. It is possible to split a state a i on states a i_1 ,...,a i_Q so that the transitions in each state a i_q were defined only by one transition condition, i.e. was fulfilled |U(a i_q )| =1, q= Q , 1 . Now instead of one state a i , we have Q states for which conditions (2) are satisfied.

In case of violations of the conditions (3), the synthesis of the class E FSM is impossible, since the determinacy of the FSM behavior is broken. In this case, it is offered to use the combined model of the class AE FSM (fig. 2). For this purpose, the second part of the code of the class A FSM is added to the code of each internal state of the class E FSM, which corresponds to the states a" t and a" t+1 . The last is carried out by special state assignment of the FSM.

Splitting of internal states for performance of necessary conditions for synthesis of the class E FSM

Note that splitting the internal states is an equivalent transformation of the FSM and it does not change the operation algorithm of the FSM. Let M be the number of internal states of the FSM, P(a i ) be the set of transitions of the FSM from the state a i , i= M , 1 , C(a i ) be the set of transitions of the FSM that terminate in the state a i , a i  A, and X(a i ) be some a transition condition to the state a i , X(a i )  U(a i ). Then the algorithm splitting of internal states for performance of necessary conditions for synthesis of the class E FSM has the following view.

Algorithm 1.

1. For each internal state a i , a i  A, according to (1) the set U(a i ) is defined.

In the set

condition X q (a m ,a i )  U(a i ), a m  B(a i ), q= Q , 1 .
5. The subsets P(a i_1 ),…,P(a i_Q ) of transitions from the states a i_1 ,…,a i_Q are determinated in the following way: P(a i_q ) := P(a i ) for all q= Q , 1 .

6. Put A:=A\{a i }, A:=A  { a i_1 ,…,a i_Q }, and M:=M+Q-1; go to Step 2.

7. Stop.

State assignment of the class AE FSM

The main purpose of encoding the internal states when designing the class AE FSMs is to ensure the mutual orthogonality of these codes. To encode the internal states of a class AE FSM, a ternary matrix W is constructed in which the rows correspond to the internal states and the columns correspond to the variables of the set G. A unit is put on intersection of the row i and the column j of the matrix W, if the input variable x j has the value 1 in the condition X(a i ), a zero, if the input variable x j has the value 0 in the condition X(a i ), and an undetermined value (the dash), if the variable x j does not influence on the transition condition X(a i ). Later, the rows of the matrix W will determine the codes of the internal states of the class AE FSM.

To make the codes of internal states of the class AE FSM orthogonal it is necessary to solve the following task.

Task 1. To add in matrix W the minimum number of the columns, which corresponding to the variables e 1 ,...,e R , and to encode the rows of the matrix W by binary values of the variables e 1 ,...,e R so that all the rows of the matrix W were mutually orthogonal.

In order to solve the Task 1 and to encode the internal state of the class AE FSM the following algorithm is offered.

Algorithm Example. Let us apply the proposed method for designing the FSM described by the state diagram shown in Fig. 4. The vertices correspond to the internal states a 1 ,…,a 5 of this FSM, and the arcs correspond to the FSM transitions. Beside each arc, the value of the input vector that initiates the transition and, separated by a slash, the value of the output vector that formed on this transition are indicated. In this example, the FSM has five states, three input variables, and two output variables. The encoding of the internal states begins with constructing the matrix W (Table 1). Figure 5 shows the orthogonality graph H of the rows of W. The graph H is decomposed into two complete subgraphs H 1 and H 2 . As the number of subgraphs T is equal 2, then one variable e 1 has enough for coding of two subgraphs. According to Step 4 of algorithm 5, the subgraph H 1 is encoded by binary code "1", and the subgraph H 2 is encoded by the code "0". The matrix W with an additional column e 1 for orthogonalization of rows is resulted in Table 2.

Table 1. The matrix W for state assignment of a class AE FSM 2. The matrix W after orthogonalization of rows

g 1 g 2 g 3 a 1 - - 0 a 2_1 0 1 - a 2_2 - - 1 a 3 0 0 - a 4 1 0 - a 5 1 1 -
g 1 g 2 g 3 e 1 a 1 - - 0 1 a 2_1 0 1 -0 a 2_2 - - 1 1 a 3 0 0 -0 a 4 1 0 -0 a 5
1 1 -0 The logical equations implemented by combinative circuit CL (fig. 3) for our example have the following view: . ; ;

3 1 2 1 2 1 1 3 2 1 1 2 1 2 1 1 3 2 2 1 1 3 2 1 1 2 1 2 1 1 3 1 1 2 1 1 x e g g x
       
As it is possible to see from the resulted equations, the transition functions for the class AE FSM are very simple. The implementation cost of the given system of Boolean functions (it is traditionally defined as the number of inputs of the necessary for implementation gates) is equal 40, while at traditional implementation of the class A FSM, the implementation cost is equal 74. Thus, for the considered example usage of structural model of the class AE FSM, in comparison with the traditional approach, allowed to reduce the implementation cost by a factor of 1.85 or by 54 %.

The efficiency of the proposed method for designing the class AE FSMs was tested by implementing the FSM described in the example above in the FPGAs manufactured by Altera using the CAD tools Quartus Prime version 16.0. It is the synthesis parameters by default of CAD Quartus were used. The initial FSM of class A and the synthesized FSM of class AE have been described in language Verilog. 3 show the results of experiments for various FPGA families manufactured by the companies Altera, where LE A and LE AE are the numbers of the logical elements (functional generators LUTlook-up table) used in the implementation of the class A FSM and the class AE FSM, F maxA and F maxAE are the maximum operation frequencies (in MHz) of these FSMs, LE A /LE AE and F maxAE /F maxA are the ratio of the corresponding parameters, and mid is the mean value of the parameter. The data in Tables 3 show that the proposed method for designing the class AE FSM reduced the implementation area of the FSM from the example on the Altera FPGAs by a factor of 1.35 on average and by a factor of 3.00 for the Arria II family. Thus the maximum operation frequency of the class AE FSM concedes to the maximum operation frequency of the class A FSM a little.

6

Experimental study

The synthesis method of the class AE FSM was researched at implementation on FPGA for the FSM benchmarks MCNC [START_REF] Yang | Logic synthesis and optimization benchmarks user guide. Version 3.0[END_REF]. For this purpose to each benchmark of the FSM the considered synthesis method was applied. Both finite state machines, the initial class A FSM and synthesized the class AE FSM, were described in language Verilog. Then standard implementation on FPGA of FSMs by means of CAD Quartus II version 13.1 was fulfilled. It is the synthesis parameters by default of CAD Quartus were used. As criteria of optimization the implementation cost (C), defined by the number of used logical elements LUT, and the maximum operation frequency (F) was considered.

In Table 4 and 5, the parameter relations are presented for eleven FSM benchmarks for which usage of the synthesis method of the class AE FSM is the most effective. Here relation C A /C AE shows in how many time the synthesis method of the class AE FSM, in comparison with the class A FSM, improves the implementation cost; F AE /F A the frequency.

The analysis of Table 4 and 5 shows that the synthesis method of the class AE FSM allows to reduce a implementation cost by a factor of 3.00 for the benchmark shiftreg for all FPGA families, a time delay by a factor of 1.60 for the benchmark lion for family Cyclone, and an operation frequency by a factor of 2.93 for the benchmark train4 for family Stratix.

An average improving is of a cost by a factor from 1.19 (Cyclone, Stratix) to 1.39 (Arria, Stratix II, (III), of a time delayfrom 0.97 (Cyclone II) to 1.05 (Cyclone), of a frequencyfrom 1.92 (Cyclone II) to 1.10 (Stratix).

Conclusions

The considered method of synthesis of the class AE FSM showed the high efficiency at minimization of implementation cost of FSMs for various FPGA families, by a factor of 1.19-1.39 on average and by a factor of 3.00 for certain families. Besides, in certain cases the method allows to increase the FSM performance (by a factor of 2.93 for benchmark train4 for family Sratix). An application of the given method is the most effective for FSMs with the many of input variables, especially when the transitions in the various states are initiated by different transition conditions.

The proposed method for the minimization of FSMs based on the use of the structural model of the class AE FSM is universal because it is applicable to Mealy FSMs (i.e., to arbitrary FSMs), does not change the operational algorithm of the FSM, and is efficient for all FPGA families. Therefore, this method can be recommended for inclusion in industrial CAD tools in order to minimize the area of implementation. The given method can be used not only at implementation of FSMs on FPGA, but also on other an element basis, for example on ASIC (Application Specific Integrated Circuit). We see perspective a direction of the further researches when values of input and output variables of the FSM are shared for states assignment.

Fig. 1 .

 1 Fig. 1. The structural models of FSMs: athe class A FSM; bthe class E FSM

;

Fig. 3 .

 3 Fig. 3. The structural diagram of the class AE FSM

Fig. 4 .Fig. 5 .

 45 Fig. 4. The state diagram of the initial FSM

2 Fig. 6 .

 26 Fig. 6. The graph H for orthogonality of rows of the matrix W

  ).

	z t	CL 	a' t+1 a" t+1	RG E RG A CLK	a' t a" t	CL 	w t
				CLK
		Fig. 2. The structural model of the class AE FSM

  2. 1. The graph H for the orthogonalization of the rows of the matrix W is constructed. The vertices of H correspond to the rows of W (internal states of the FSM). Two vertices of H are connected by an edge if the corresponding rows of W are orthogonal. 2. The vertices connected to all other vertices (the rows of W corresponding to these vertices are orthogonal to all other rows) are removed from H. 3. The graph H is decomposed into the minimum number of complete subgraphs H 1 ,…,H T using Algorithm 3. 4. The subgraphs H 1 ,…,H T are encoded by binary codes of the minimum length R = intlog 2 T using Algorithm 5. 5. R columns that correspond to the variables e 1 ,...,e R of the codes of the subgraphs H T + 1. In the graph H, find a complete graph H T with the maximum number of vertices. 3. Remove the vertices of H T from the graph H. 4. If the set of vertices of H is not empty, the go to Step 2; otherwise, go to Step Find a vertex a i in H with the greatest local degree. 2. Include a i into the graph Ht. 3. Among all the vertices of H not included in H t , find a node a i connected to all the nodes of the subgraph H t . If several such nodes are found, choose a node with the greatest local degree among them. 4. If a vertex connected to all the vertices of the subgraph H t was found at Step 3, then go to Step 2; otherwise, go to Step 5. 5. Stop. To encode the subgraphs H 1 ,…,H T (Step 4 of Algorithm 2) the following algorithm is used to minimize the area of implementing the transition functions. Algorithm 5. 1. Calculate the length R of the codes of the subgraphs H 1 ,…,H T : R = intlog 2 T. 2. Form the set K of binary codes of length R. 3. The subgraph containing the initial state a 1 is encoded by the zero code from K. 4. If all the subgraphs H 1 ,…,H T are encoded, then go to Step 5; otherwise, find among the not yet encoded subgraphs H 1 ,…,H T a subgraph H t for which ∑|C(a i )|=max for all a i  H t . To encode the subgraph H t , the code with the minimum number of unities is chosen in the set K. Go to Step 4. 5. Stop.

	, 1 , contain-
	ing the vertex a i , i= M , 1 . The other positions of the additional columns in W
	are filled by zeros.
	6. The contents of the row i of W is used as the code of the internal state a i ,
	i= M , 1 .
	7. Stop.
	The decomposition of the graph H into the minimum number of complete graphs
	H 1 ,…,H T (at Step 3 of Algorithm 2) is made by the following algorithm.
	Algorithm 3.
	1. Set T : = 0.
	2. Set T : = 5.
	5. Stop.
	The maximal complete subgraph H t , t= T , 1 , at Step 2 of Algorithm 3 can be found
	using the following algorithm.
	Algorithm 4.
	1.

[START_REF] Mccluskey | Reduction of Feedback Loops in Sequential Circuits and Carry Leads in Iterative Networks[END_REF]

,…,H T are added to the matrix W. In row i of W, the positions of the additional columns are filled by the code of the subgraph H t , t= T

Table 3 .

 3 Results of experimental researches at implementation on FPGA of the FSMs from the considered example

FPGA LE A F maxA LE AE F maxAE LE A /LE AE F maxAE /F maxA

	MAX II	12	517.06	10	417.19	1.20	0.807
	MAX V	12	261.57	10	260.15	1.20	0.996
	MAX 10	13	592.42	11	581.40	1.18	0.981
	Arria II	8 1025.64	4 1022.49	2.00	0.997
	Cyclone IV E	12	738.01	10	801.92	1.20	1.085
	Cyclone IV GX	12	726.74	10	727.27	1.20	1.001
	Cyclone V	6	640.20	4	640.20	1.50	1.000
	mid					1.35	0.981
	Tables

Table 4 .

 4 Results of experimental researches of the synthesis method of the class AE FSM for families Arria GX and Cyclone

	FSM	Arria GX	Cyclone	Cyclone II Cyclone III
		C A /	F AE /	C A /	F AE /	C A /	F AE /	C A /	F AE /
		C AE	F A	C AE	F	C AE	F A	C AE	F A
					A
	dk15	0.86 1.55 0.71 1.45 0.71 1.18 0.71 1.06
	dk16	1.31 0.85 0.63 0.80 0.55 0.74 0.55 0.69
	dk17	1.67 1.06 0.96 0.70 0.96 0.91 0.96 1.12
	dk27	1.33 1.05 1.25 0.97 1.25 0.99 1.25 1.04
	dk512	1.42 0.82 0.68 0.91 0.78 0.82 0.78 0.77
	ex5	0.79 0.61 0.64 0.67 0.64 0.68 0.64 0.69
	lion	1.00 0.65 0.71 0.54 0.77 0.63 0.77 0.64
	lion9	1.43 0.81 1.82 1.16 1.82 1.08 1.82 0.91
	shiftreg 3.00 0.62 3.00 0.55 3.00 0.75 3.00 0.64
	train4	0.75 1.77 1.00 1.60 1.00 1.45 1.00 1.56
	train11 1.71 1.49 1.71 1.56 1.92 0.94 1.92 0.84
	mid	1.39 1.03 1.19 0.99 1.22 0.92 1.22 0.91
	max	3.00 1.77 3.00 1.60 3.00 1.45 3.00 1.56

Table 5 .

 5 Results of experimental researches of the synthesis method of the class AE FSM for families MAX II and Stratix

	FSM	MAX II	Stratix	Stratix II	Stratix III
		C A /	F AE /	C A /	F AE /	C A /	F AE /	C A /	F AE /
		C AE	F A	C AE	F A	C AE	F A	C AE	F A
	dk15	0.70 1.18 0.71 1.07 0.86 1.02 0.86 0.66
	dk16	0.63 0.83 0.63 0.73 1.31 0.77 1.31 0.82
	dk17	1.39 0.98 0.96 0.75 1.67 1.21 1.67 1.02
	dk27	1.25 1.20 1.25 0.95 1.33 0.89 1.33 1.00
	dk512	0.70 0.89 0.68 0.98 1.42 1.03 1.42 0.78
	ex5	0.62 0.77 0.64 0.63 0.79 0.48 0.79 0.68
	lion	0.71 0.77 0.71 0.84 1.00 0.66 1.00 0.54
	lion9	1.82 0.82 1.82 0.75 1.43 0.95 1.43 0.87
	shiftreg 3.00 1.14 3.00 0.31 3.00 0.66 3.00 0.71
	train4	1.00 0.95 1.00 2.93 0.75 1.77 0.75 1.91
	train11 1.77 0.97 1.71 2.15 1.71 1.74 1.71 1.65
	mid	1.24 0.95 1.19 1.10 1.39 1.02 1.39 0.97
	max	3.00 1.20 3.00 2.93 3.00 1.77 3.00 1.91

Acknowledgements. The present study was supported by a grant S/WI/1/2013 from Bialystok University of Technology and founded from the resources for research by Ministry of Science and Higher Education.


Maciej Szymkowski
email: szymkowskimack@gmail.com

Khalid Saeed
email: k.saeed@pb.edu.pl

A Multimodal Face and Fingerprint Recognition Biometrics System

Keywords: face, fingerprint, biometrics, physiological biometrics, identification, security systems, multimodal systems, fusion

Biometrics helps protect users' data against hackers. There are two groups of biometrics features, the first contains physiological features and the second consists of behavioral traits. In the case of biometrics safety procedure the user does not need to remember his/her password because they always have them. It is proved that physiological biometrics can grant higher accuracy than systems that base on behavioral traits. One of the most popular physiological features are fingerprints and face. In the work presented in this paper, these two features are taken into consideration at the same time in a multimodal system. The accuracy of user identification is calculated for each of the two features individually and also for them when combined together.

Introduction

Recent research is showing that most of security systems are at the risk of breaking their hedges. To protect users' data, biometrics safety procedures introduce the possibility of increasing the system protection level. The main reason of using this kind of safety procedure is that the user does not need to carry the tokens or remember the password. People are simply recognized by the features showing 'what they are'they are authenticated by their physiological or behavioral characteristics. In biometrics safety systems, simply, the user himself is the key. Fingerprints, retina, face or other measurable traits could play the role of the password, a key that is not as easy to break as the traditional one because human traits are not easy to imitate. There are two groups of biometrics features. The first is a group that contains representatives of physiological traits. For instance, face, fingerprint, retina or hand geometry are classified as participants of this group. It means that these features are connected with how human organism is built. In the case of behavioral biometrics features, keystroke dynamics, voice or signature are connected with this group.

In the system described in this work, only physiological features are taken into consideration. It is connected with the fact that they are not easy to imitate and that each man have these features unique. On the other hand one can claim that behavioral traits are easier to implement because they, in the most of the cases, do not need any specialized hardware and could be collected without notifying the user. This statement is true but samples of behavioral traits differ from each other even within the same user and hence the repeatability is very low because it is hard to repeat proper activity each time in exactly the same manner. Moreover, physiological traits grant higher level of identification accuracy because of their uniqueness.

The system presented in this paper is multimodal. It means that at least two features are combined in order to check whether this combination gives higher accuracy than the data obtained from each of the selected traits separately. Another goal of the presented approach is to check whether more data to analyze can lead to more accurate classification. In the authors' approach fingerprint and face were chosen. Each of them can easily be collected because most of personal computers contain cameras whilst the fingerprint scanners are available and built-in scanners in the laptops and mobile phones are becoming more popular.

Known approaches

Lately more interest in the case of face and fingerprint recognition has been observed.

To present the current state of the knowledge, the authors of this work selected a few different approaches that can be compared with the idea presented in this paper.

In [1] an idea that uses eigenvectors to identify user by his face is described. In 1987 the originators of this approach were Sirovich and Kirby although eigenvectors as a significant part of human recognition algorithm were firstly used by Matthew Turk and Alex Paul Pentland. Their algorithm mainly bases on principal component analysis (PCA), in which one of the most essential steps is the image conversion to vertical vector to be a part of the analyzed matrix. Then the mean value of each horizontal vector is calculated and finally the mean vertical vector is obtained to subtract from each of the matrix vertical vectors. The matrix values normalization is done to change all matrix values into 0 -255 interval. Then main principal values of matrix and each of vertical vectors are calculated. Authors of this algorithm, have only described the processing method, they do not present or compare results.

Authors of [2] mostly based on the idea that was presented by Turk and Pentland in [1]. In the case of Eigenface technique one can easily observe that variation was maximized, while in Fisherface method, the main aim is to maximize mean distance between classes and to minimize variance within each class. Authors of this approach prepared an algorithm in which the Modified Fisher Linear Discriminant Model (MFLD) is used. This model consist of decomposition of Fisher Linear Discriminant into simultaneous diagonalization of the two within-and between-class scatter matrices. As the second part of the work Fuzzy Fisher Linear Discriminant (FFLD) was mentioned. One of the main goals of authors approach was dimensionality reduction of analyzed matrix by which algorithm could be more efficient. To measure distance between two samples, Euclidean metric was used. Authors claimed that by usage of MFLD, accuracy of user identification was 91.4% and for FFLD it equals 94.8%.

Completely different approach, one could observe in the method called Local binary pattern histograms (LBPH). In [1-2] whole image was taken into consideration in contrary to Eigenface and Fisherface techniques, in method that is presented in [3], image local features are taken into account. For each pixel, binary string is determined. It is created by comparison between analyzed pixel value and values of all his neighbors. Therefore each pixel is described by p-value binary string, where p is a number of neighbors that were taken into consideration in the comparison process. This string is called local binary pattern (LBP). The main idea of this algorithm is connected with dividing an input image into m different parts and calculating function LBP for each, previously separated part. Then for each region histogram that is created on the basis of calculated LBP and specific vector basing on histograms are prepared. For new sample that was not stored in the database, histogram vector is calculated and it is compared with all vectors that are in the database. Authors of this approach have only described the processing method, they do not present or compare results.

In the solution that was originally published in [4], one can observe that authors mainly focused on interesting processing algorithm for fingerprint feature extraction. In the case of this algorithm ridge bifurcations, ridge endings, core and deltas, as a kind of minutiae, are detected. Moreover authors presented their own idea by which all minutiae could be easily described. Feature vector of the whole fingerprint is prepared with usage of minutiae-type, their location and orientation. Authors of [4] claim that there is no such a need to begin fingerprint analysis with image preprocessing (for instance improving contrast or histogram alignment). The authors' algorithm starts with image analysis methods such as initial segmentation, orientation computation and ridge frequency computation. As the main purpose of this stage, localization of a fingerprint area on the image, orientation of each pixel and calculation frequency of ridges are mentioned. On the basis of [4] one could get into know that these steps are enough to prepare fingerprint image to filtration process. Moreover, in this paper authors presented an interesting idea by which spurious minutiae could be easily removed. As it was in the case of [1,3] in this paper only processing method is described, authors do not present or compare obtained results.

Another solution that was originally published in [5], presents the processing algorithm that could be used to prepare two fingerprints to comparison procedure. One can easily observe that unlike algorithm presented in [4], this one is taking into account only two types of minutiae that are ridge ending and ridge bifurcation. This approach is using CN algorithm to detect different types of minutiae and different image analysis operations that have to prepare an image to minutiae classification. Feature vector consists of minutiae type and localization. Authors of this approach also described comparison method between two different fingerprints. They take into account number of minutiae in two compared images and by its usage determine matching score of analyzed fingerprints. Despite the fact that the whole comparison procedure was described, no information about accuracy of proposed approach were attached in this work.

The algorithm that is presented in [6], as the one described in [5], deals with two types of minutiaeridge ending and ridge bifurcation but it also takes into consideration Core in fingerprint. Moreover in this solution is not described any specific identification algorithm. On the other hand on the basis of this algorithm, one can easily prepare feature vector by which comparison between two fingerprint images will be done. In the case of this approach, additional image analysis operations are done on an image. These steps are used to obtain image from which minutiae could be extract.

Due to the fact that in this work authors deal with the problem of multimodal biometrics system, a few works about this kind of systems were also analyzed.

In [7] authors presented a system that bases on two behavioral features that are keystroke dynamics and mouse movement. The dynamics of moving and mouse button dwell times were taken into consideration. Authors prepared simple comparison method by which interesting results were obtained. As a classifier k-Nearest Neighbor was used. Authors measured the accuracy for different number of nearest neighbors and for each of the analyzed features separately and also for combination of keystroke dynamics and mouse movement. The best results were obtained in the case of combination of two features and accuracy was 68.8%. All accuracies for other traits were lower than in the case of fusion system.

In the literature there are several examples of multimodal biometrics systems. There are a few different ideas of how these solutions should work [8][9][10]. In the papers [8-9], no specific solution was presented. Only the main aim and the idea of multimodal biometrics systems were described.

Multimodal biometrics systems that combine face and fingerprint were presented in [11][12]. In [11] authors used face and fingerprint as the primary characteristics and gender, ethnicity, height as soft characteristics. Experiments were done on a database that consists of 263 users. Results show that the recognition accuracy of the primary characteristics can be improved by additional step that basis on soft characteristics.

Authors of [12] also presented the work about multimodal face and fingerprint biometrics system. Face verification module incorporates Gabor Wavelet texture features and face edges. For the fingerprint classification, authors prepared an algorithm that basis on minutiae detection and builds feature vector for each fingerprint from the database and for a new sample. Authors claimed that their system could be effectively used for people identification at airports.

Proposed approach

In order to measure accuracy of each of the proposed ways of user identification, an algorithm with its computer implementation in Java are presented. Two algorithms were implementedone for face recognition and one for fingerprint classification. In the case of face recognition problem, Eigenface method [1] was used. This idea was selected due to the high accuracy level, effectiveness of processing process and simplicity of implementation. It was implemented with the usage of Java CV, which also provides methods by which programmer could easily grab current image from the camera connected to the computer. Each of users in our database is described by three images of his fingerprint and by three images of his face. In the case of fingerprint classification, authors prepared their own approach that provides a procedure for fingerprint image processing. After image processing, feature vector is generated. Manhattan distance is then followed with classic k-Nearest Neighbor algorithm. All steps of this approach are presented in the form of block diagram in Fig. 1.

At the beginning of fingerprint image processing the image is binarized. Different strategies of binarization were described in [13]. Authors decided to implement manual binarization with threshold set at 215. Pixel value is set to black if condition presented in (1) is satisfied, where x and y are the position of the X and Y axis respectively and R is red channel pixel value at the given location. Accordingly G is for green channel value and B is for blue. The results of this procedure and the original image are presented respectively in Fig. 2a and in Fig 2b .   𝑅 𝑥,𝑦 + 𝐺 𝑥,𝑦 + 𝐵 𝑥,𝑦 3 > 𝑡ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑 (1)

As the second step of image preprocessing morphological closing is proposed. This step is connected with the quality of captured images. Due to the fact that these images are not in the best quality, small spaces in fingerprint are visible. Authors implemented this kind of morphological operation because it consists of image erosion preceded by image dilation. It causes that small spacing are filled with black pixels that represents elements belonging to fingerprint and then additional, redundant black pixels are removed. By this operation the fingerprint image quality is a little bit raised.

In Fig. 2c. fingerprint image after thinning procedure is presented. By this step all fingerprint lines are reduced to 1-pixel width. It was done due to the fact that redundant pixels could make significant impact on minutiae detection method. Additional pixels could be classified as pixels that belongs to minutiae but in fact they are not connected with the real one. As the third step of image processing minutiae detection was done. All minutiae were extracted with usage of CN algorithm. This solution is a widely-used algorithm for minutiae detection. In this approach authors take into consideration 8 closest neighbors of analyzed pixels. Crossing number was calculated as in (2).

𝐶𝑁 = 1 2 • ∑|𝑃 𝑖 -𝑃 𝑖-1 | 8 𝑖=1 (2)
By calculation of this number analyzed pixel could be properly classified. When CN = 0 it means that this pixel belongs to background, CN = 1means that analyzed pixel is ridge terminal, CN = 2points at ridge continuation and CN = 3return information that pixel is ridge bifurcation.

Due to the low quality of processed image, as another step spurious minutiae removing was presented. This step was done in the same way as it was described in [4]. It means that distance between minutiae and all of its neighbors is calculated. If this distance is too low, minutiae is classified as spurious and is removed. After removing all redundant minutiae, feature vector is generated. In the case of this approach it consists only of two simple informationnumber of ridge endings and number of ridge bifurcations. All steps of the processing algorithm are presented in Table 1.

In the case of classification, distances between new samples feature vector and all feature vectors of all samples that are stored in the database are measured. Then classification is done with classic k-NN algorithm. Classification procedure is presented in Table 2. In Table 3 description of multimodal system is provided.

Table 1. Fingerprint processing algorithm

Input: Image that is provided by the user. Output: Feature vector that describes fingerprint.

1. Binarize input image with manual thresholding binarization method. Set binarization_threshold = 215. 2. Do morphological closing with 3x3 mask on the image obtained after step 1. 3. Do thinning with usage of KMM algorithm. 4. Detect all minutiae likely structures on the fingerprint image with usage of CN algorithm. 5. Remove spurious minutiae a. Set minutiae_threshold = 60. b. For each detected minutiae: i. Measure distance to all other minutiae ii. If at least one distance is lower than minutiae_threshold remove minutiae that is too close to analyzed one. 6. Count number of ridge bifurcations and ridge endings. 7. Create feature vector that consists of numbers established in step number 6.

Results of the experiment

Authors' database consists of 50 users that are described by 3 fingerprint samples and 3 face samples each. Experiments were based on dividing the database into two 75samples sets that were: test and learning set. Also different number of input samples modifications were taken into consideration. Accuracy was also measured for 5, 10, 20, 30, 40 and 45 users. Fingerprint images were obtained with Futronic® FS80 fingerprint scanner, face photos were done with Tracer® PC Prospecto Cam.

Effectiveness of each of implemented algorithms separately

Face Fingerprint

In Fig. 3 results of two implemented algorithms were presented. As one can observe better results were obtained with usage of face identification algorithm. Results of this way of identification was nearby 100% mostly for each of number of users. In the case of proposed fingerprint classification algorithm with increasing number of users, classification accuracy decreases. Probably it was connected with the fact that simple feature vector was used to describe each of sample. One can observe that by usage of more complex descriptor accuracy level could be higher.

In Fig. 4. the accuracy results of each of identification methods are presented in comparison with the approach when those two features are analyzed simultaneously. One can easily observe that combination of these two algorithms gives quite good results.

Fig. 4. Comparison of different identification ways

On the basis of the results that are presented in Fig. 4, one can observe that the best implemented algorithm was Eigenface that was used to recognize user by his face. On the other hand, the worst was fingerprint algorithm. As it was mentioned before, this results is caused by simple feature vector. It is observable that two fingerprints that have similar numbers of ridge bifurcations and ridge endings could be classified as fingerprints that belongs to one man. Results that were obtained with combination of these two features are quite good. These results present that user could be recognized on the basis of his face and fingerprint with the accuracy ratio that is nearby 81%.

Conclusions and future work

Biometrics security procedures provide new high standard of security methods that can be used in different programs or devices. One can observe that even if user knows how fingerprint or the face of other user looks like, it is really hard for him to imitate these features. What is more, recent cameras or fingerprint scanners take into consideration not only the form of analyzed feature but also its life span. For instance in the case of cameras, user have to move his head in the left and in the right side. By this step false faces, prepared by photos could be detected. Other solution is connected with fingerprints. Fingerprint scanners could also detect temperature of finger and its structure. By these ideas, false fingerprints created with the usage of different materials can also be tracked down.

As expected, combining of two human, physiological features allowed to obtain quite good recognition ratio in the case of user identification. It is easily observable that the accuracy of user identification for both of analyzed features was 81%. This result provides that proposed solution could be implemented in real circumstances. What is more combination of two features can assure better recognition ratio than relying on only one human trait. Proposed fingerprint algorithm accuracy ratio was 62.5%. It is easily observable that combination of face and fingerprint provided better recognition ratio than the approach based only on fingerprint.

The approach presented in this work, can be used in the case of user verification problem. Moreover, one can easily observe that biometrics safety procedure that were implemented in this program, assure satisfying verification accuracy level.

As future work the authors would work under more detailed fingerprint processing algorithm and more effective face identification model. These steps aim to increase accuracy of the presented idea. For instance, more complex feature vector could be used. Moreover different face identification algorithms will be tested. Authors' database is continuously expanding. In the near feature authors would work under detection of more minutiae types.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Block diagram of fingerprint algorithm that was implemented in the application

Fig. 3 .

 3 Fig. 3. Effectiveness of implemented algorithms

Table 2 .

 2 Fingerprint classification procedureInput: Fingerprint image sample that is not stored in the database.

	Output: Classification decision.
	1. Create feature vector for the new sample with usage of fingerprint
	processing algorithm described in Table 1.
	2. For each image in the database:
	a. Create feature vector for currently analyzed image.
	b. Measure distance between feature vectors of currently analyzed
	image and the new samples one.
	c. Add calculated value to the list with the information about image
	class.
	3. Calculate with k-Nearest Neighbor algorithm the most probable class for the
	new sample.

Table 3 .

 3 Multimodal system descriptionInput: Face and fingerprint images that are not stored in the database.

	Output: Classification decision
	1. Create feature vector for fingerprint image and classify it with usage of
	classification procedure described in Table 2.
	2. Classify face image with usage of Eigenface algorithm.
	3. Compare classification decisions:
	a. If both algorithms return the same user class then user is
	recognized as the one pointed by both procedures.
	b. If classes returned by both algorithms are different then user is not
	recognized.
	4. Return classification decision.

Acknowledgment

This work was supported by grant S/WI/1/2013 from Białystok University of Technology and funded with resources for research by the Ministry of Science and Higher Education in Poland.


Artur Malinowski
email: artur.malinowski@pg.gda.pl

Pawe L Czarnul
email: pczarnul@eti.pg.gda.pl

Distributed NVRAM cache -optimization and evaluation with power of adjacency matrix

Keywords: NVRAM, distributed cache, graph processing, performance optimization

In this paper we build on our previously proposed MPI I/O NVRAM distributed cache for high performance computing. In each cluster node it incorporates NVRAMs which are used as an intermediate cache layer between an application and a file for fast read/write operations supported through wrappers of MPI I/O functions. In this paper we propose optimizations of the solution including handling of write requests with a synchronous mode, additional modes preventing data preloading from a file and synchronization on file close if the solution is used as temporary cache only. Furthermore, we have evaluated the solution for a real application that computes powers of an adjacency matrix of a graph in parallel. We demonstrated superiority of our solution compared to a regular MPI I/O implementation for various powers and numbers of graph nodes. Finally, we presented good scalability of the solution for more than 600 processes running on a large HPC cluster.

Introduction

High performance computing (HPC) was always related to aiming at better and better hardware. At the beginning, it mainly involved building larger clusters with better CPUs. A breakthrough emerged with manycore processors, such as graphics processing unit (GPU) used for general purpose processing (e.g. NVIDIA CUDA, OpenCL), coprocessors designed especially for computations (e.g. Intel R Xeon Phi TM , Epiphany architecture) or even specially designed CPUs (e.g. Sunway processors used in Sunway TaihuLight, the most powerful supercomputer in TOP500 list, June 2016 edition).

Apart from a processing unit, another essential component of computer architecture is memory. With memory the situation is much different. Typical improvement of RAM is based on a higher capacity and better parameters (e.g. higher frequency, lower latency) of next generation Double Data Rate (DDR) RAM devices, while modern storage is always connected with superior SSDs. So far, no hardware device that would extend memory properties has acquired significant popularity.

Universal memory, that is only hypothetical for now, is one of possible candidates for breakthrough in memory technologies. Combining advantages of RAM (byte-level access, high speed and bandwidth, low latency) with advantages of SSD (large capacity and persistence) should definitely increase performance of many computer systems. Although not available on the market yet, many technologies are being researched to create a practical device and several of these seem to be promising [START_REF] Wong | Memory leads the way to better computing[END_REF]. Moreover, recent press reports suggest, that we can expect devices with parameters between NAND based memory (used in SSD) and DRAM soon [START_REF]Intel Corporation: Intel and Micron Produce Breakthrough Memory Technology[END_REF] [START_REF]Introducing Breakthrough Memory Technology[END_REF]. In order to describe such memory in this paper, we would use the NVRAM term (non-volatile, random access memory) keeping in mind, that this memory is expected to have a byte-level access.

Full replacement of main memory and storage by a single, universal memory would probably trigger the need for redesigning the architecture of computing systems at multiple levels, but such a huge change cannot be expected to be introduced at once. Instead of this, we assume that first NVRAM devices would be used as complementary memory together with RAM and storage. For that reason, we decided to focus on possibilities coming from incorporating supplementary NVRAM devices into HPC platforms.

In 2016 we proposed the idea of NVRAM distributed cache located as an additional layer between a file system and a parallel distributed application [START_REF] Malinowski | A Parallel MPI I/O Solution Supported by Byte-addressable Non-volatile RAM Distributed Cache[END_REF]. The extension was transparent to the developer, because of its compatibility with the well-known Message Passing Interface (MPI) I/O API [START_REF]Message Passing Interface Forum: MPI: A Message-Passing Interface Standard Version 3[END_REF]. The motivation for this solution was improving performance and making the development process easier. Initial testing with a set of benchmarks gave promising results. Within this paper, we present further research on our MPI I/O NVRAM distributed cache. The research includes performance optimizations, as well as evaluation of the solution with a real life application -computing power of graph adjacency matrix. In fact, the application could be used e.g. for social network analysis or calculating shortest path lengths between multiple nodes simultaneously.

Related work

In 2009, Kryder and Kim presented a set of thirteen emerging non-volatile memory technologies, that had a potential to replace NAND Flash by 2020 [START_REF] Kryder | After Hard Drives -What Comes Next? Magnetics[END_REF]. A report, published by Wong and Salahuddin in 2015, agrees on the candidates to the universal memory technology, but did not try to predict when real devices would appear on the market [START_REF] Wong | Memory leads the way to better computing[END_REF]. Scientist, that conduct research on magnetoresistive RAM (MRAM) [START_REF] Åkerman | Toward a Universal Memory[END_REF][4], spin-transfer-torque MRAM (STT-MRAM) [START_REF] Makarov | Magnetic Tunnel Junctions with a Composite Free Layer: A New Concept for Future Universal Memory[END_REF][19], or phase change memory (PCM) [START_REF] Alpert | Analytical model of graphene-enabled ultra-low power phase change memory[END_REF] [START_REF] Zilberberg | Phase-change memory: An architectural perspective[END_REF], suggest, that we can expect it soon.

3D XPoint TM technology, announced by Intel R and Micron R in 2015 [START_REF]Intel Corporation: Intel and Micron Produce Breakthrough Memory Technology[END_REF][10], is probably the closest to be used in production environment -first 3D XPoint TM Intel R Optane TM devices are expected in 2016 [START_REF]Intel Corporation: Introducing Intel Optane Technology Bringing 3D XPoint Memory to Storage and Memory Products[END_REF]. Comparison between NVMe NAND SSD (nowadays the fastest SSDs) and a prototype of 3D XPoint TM technology powered device gave promising results -the time to access a 4kB block from an application was reduced almost 7 times [START_REF] Foong | Storage As Fast As Rest of the System[END_REF]. Unfortunately, at the mo-ment of writing this paper, we do not have any more Intel R Optane TM performance results.

Emerging memory technologies triggered research on architectures, algorithms, and applications that would benefit from properties of the new hardware. NVMcached, key-value cache for byte-addressable NVRAM, is an example -designing the system taking into consideration the new memory type allowed to improve performance up to 2.85 times [START_REF] Wu | NVMcached: An NVM-based Key-Value Cache[END_REF]. Another exemplary research on this topic could be a log-structured file system NOVA [START_REF] Xu | NOVA: A Log-structured File System for Hybrid Volatile/Nonvolatile Main Memories[END_REF], or our idea for checkpointing in NVRAM using the MPI One-sided API [START_REF] Dorożynski | Checkpointing of Parallel MPI Applications Using MPI One-sided API with Support for Byte-addressable Non-volatile RAM[END_REF].

There are also solutions based on NVRAM related with speeding up I/O operations in HPC. Two papers concern Active NVRAM -a device that, apart from memory component, includes low power CPU [START_REF] Kannan | PUsing Active NVRAM for I/O Staging[END_REF] [START_REF] Kannan | Using Active NVRAM for Cloud I/O[END_REF]. Although the proposed architecture has potential benefits, computing units are not expected in first production devices. Another set of solutions use SSD devices. Systems like S4D-Cache [START_REF] He | S4D-Cache: Smart Selective SSD Cache for Parallel I/O Systems[END_REF] or SLA-Cache [START_REF] He | Improving Performance of Parallel I/O Systems through Selective and Layout-Aware SSD Cache[END_REF] significantly improve parameters of PFS, however, we believe that differences between typical SSD and byte-addressable NVRAM require more dedicated solutions.

3 Proposed solution

NVRAM distributed cache architecture

This section is a short summary of our previous research on NVRAM distributed cache. In a typical MPI application, MPI I/O is used in order to communicate with parallel file system (PFS). Figure 1 shows a difference between the classical approach and our solution. Instead of calling an MPI I/O implementation directly, an application uses NVRAM cache routines. This process is transparent to the programmer as the cache API is the same as MPI I/O API. NVRAM cache communicates with PFS through MPI I/O, which gives an instant support for many file systems.

We assume that each node is equipped with its own NVRAM device and it participates in a distributed cache. On each node a single thread, called a cache manager, is spawned -it is responsible for creation and management of its part of the cache. When a file is opened, it is split into equally sized parts, one for each cache manager. Then, the cache manager is responsible for prefetching its whole part of file (in the file opening phase), serving read, write and sync requests from the application, flushing all of the data into PFS (in the file closing phase). The main advantages of the extension, in comparison to typical solutions, are:

low latency, caused by serving requests as fast as possible by omitting complicated data rearrangement algorithms, fully decentralized management with no communication between cache managers -cache parts are assigned at the beginning, so each application process knows exactly where data is, minimal meta-data -no cache blocks, no fetched flags (all data prefetched), no dirty flags (all data treated as dirty). It is clear, that a significant overhead is introduced with prefetching the whole file and flushing it back in the end. Moreover, the solution is aimed at applications that access small chunks of data (gain from byte addressing of NVRAM) from spread file locations (no drawback from omitting staging algorithms). As it was shown in previous papers [START_REF] Malinowski | A Parallel MPI I/O Solution Supported by Byte-addressable Non-volatile RAM Distributed Cache[END_REF][START_REF] Malinowski | A Fail-Safe NVRAM Based Mechanism for Efficient Creation and Recovery of Data Copies in Parallel MPI Applications[END_REF], for long running and data intensive HPC applications that operate on small data parts, our solution performs better than unmodified MPI I/O. In this paper, we want to evaluate it with an application that does not meet those criteria strictly. Another important issue is connected with persistence of NVRAM. We have shown, that our solution could be used to prevent data from being damageda consistent state of the file could be recreated from the cache [START_REF] Malinowski | A Fail-Safe NVRAM Based Mechanism for Efficient Creation and Recovery of Data Copies in Parallel MPI Applications[END_REF]. Although it allows to recover only from several failure types, its low overhead and ease of programming could be a solution complementary or even in some cases competitive to checkpointing.

Extension optimizations

The most significant performance optimization applies to serving write requests. In the first version of the extension, a cache manager responded to the process in an asynchronous way, before the exact data was written into a device. Data consistency was provided by sequential processing of the cache manager thread. Although such a strategy reduced the latency slightly when the number of requests was kept at a low level, it caused performance drop with more data-intensive applications. In most popular MPI implementations write requests started queuing in a cache manager, that caused unpredictable and huge growth of latency for successive requests. The solution based on changing communication into a synchronous version and sending a response after all the processing was done, fixed the performance drop.

Another optimization is connected with omitting unnecessary overhead in opening and closing a file. Introduced improvements rely on better support for three MPI File open access modes:

-MPI MODE CREATE: if the file does not exist, prevent from prefetching data, -MPI MODE RDONLY: prevent from synchronization at file closing, -MPI DELETE ON CLOSE: prevent from synchronization at file closing.

In special cases like treating the file as a huge distributed shared memory, most of the cache overhead related to file opening and closing is avoided.

Graph processing application

The graph theory has many real world applications like obtaining social network properties (e.g. Facebook, Twitter), processing maps and locations (e.g. Google Maps, GPS based navigation systems), optimizing layout of connections (e.g. designing cellular network layout) or preparing some recommendations (e.g. Netflix, Google PageRank). A great deal of algorithms hidden behind those applications are computational demanding and without further optimization they will not be able to handle increasing volume of data. In this paper we propose how to extend a selected algorithm with our MPI I/O NVRAM distribute cache. As an exemplary algorithm we have chosen the transformation, that could provide multiple graph properties, among others:

number of paths of length n that connect two vertices, shortest path lengths, number of triangles in the graph.

Many different data structures could be used for representation of graphs. The selected problem requires checking often whether two vertices are adjacent, so a representation that minimizes complexity of this operation would be beneficial. Complexity of such query in adjacency matrix is O(1). Disadvantages of an adjacency matrix are irrelevant in the context of the selected algorithm. Slow adding or removing vertices is negligible because of constant size of a graph. Large memory consumption is unimportant since NVRAM distributed cache provides storage of size limited to the sum of all NVRAM capacities in a cluster. In our implementation, an adjacency matrix graph representation is used.

With an adjacency matrix, in order to search for walks of particular length between vertices, matrix multiplication could be used. Assuming A is the adjacency matrix, in the matrix A n each element a n(i,j) represents the number of walks of length n connecting vertex i with vertex j. The idea is illustrated with the exemplary A, A 2 and A 3 :

A =     0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0     , A 2 = A • A =     0 0 1 1 0 0 0 1 1 1 0 0 0 1 2 0     , A 3 = A • A • A =     1 1 0 1 1 1 0 0 0 1 2 0 0 0 1 2     .
From the above matrices one can read for instance:

there are 2 paths of length 2 that connect vertex 4 with vertex 3 (a 2(4,3) = 2), the shortest path from vertex 3 to vertex 1 is 2 (smallest n where a n(3,1) > 0 is 2), the number of triangles in the graph is 2 (

1 3 v i=1 a 3(i,i) = 2).
To calculate power of a matrix efficiently, in this application, communicationavoiding Cannon's algorithm is used [START_REF] Cannon | A cellular computer to implement the Kalman Filter Algorithm[END_REF].

Experiments

The MPI I/O NVRAM extension is designed for applications of specific properties. To benefit most from the extension, a data-intensive application should access small data chunks from spread locations and run long enough to compensate for the overhead for initialization and deinitialization. Implementation of an algorithm for graph adjacency matrix is an attempt of validating the extension with an application that does not strictly possess these properties. The application accesses larger data chunks at once from neighboring locations, what is especially convenient for parallel file systems we want to compete with. Within this section we want to prove, that proposed MPI I/O NVRAM distributed cache is beneficial for a wide range of applications by showing a case study of an application that does not meet our cache requirements.

Testbed environment

The extension was tested on two clusters: Lap06 and K2 described in detail in Tables 1 and2. Each node in Lap06 is equipped with an NVRAM hardware simulation platform, set to pessimistic values. Lower times would result in even better results for the NVRAM version. In contrast, K2 simulates NVRAM using tmpfs but its size allows to measure scalability.

Performance tests

Calculating power of a matrix can have different real-world applications, including graph processing. For some of them, storing a final matrix is crucial (e.g. searching for the number of walks of a particular length), but other use it only as intermediate values (e.g. searching for the number of triangles). From the perspective of MPI I/O, if the application does not need the final matrix stored on disk, MPI MODE DELETE ON CLOSE could be used in order to trigger additional optimizations. For that reason, most test cases are split into groups according to delete on close mode (on and off). As the execution time does not depend on graph properties other than its size, for each test case we generated n nodes and connected each two nodes with the probability of 2%. All scenarios apply to low graph powers, so each value of the adjacency matrix is stored in a 1 byte cell, that results in the size of the final file equal to n 2 bytes.

Performance optimizations As stated in section 3, handling of write requests with a synchronous mode was the most noticeable improvement over the previously proposed extension. Comparison of synchronous and asynchronous mode for graph processing application is presented in Figure 2. Results show 30% reduction of application's execution time for small computed graph powers. Moreover, while increasing the power of a graph, the performance gain is greater.

Results with delete on close mode off According to Figure 3, execution time of the application grows linearly with the power. The greater the power of a matrix, the greater execution time and greater performance gain from the NVRAM distributed cache. For example, with power of 2 the proposed extension is less than 20% faster than unmodified MPI I/O, while for larger powers it is more than 40% faster. Increasing performance gain is caused by overhead for initialization and deinitialization that is independent from the power.

Figure 4, and 5 present an exponential growth of execution time for different sizes of input graphs. Plots prepared for power of 2 show that for small powers with delete on close mode off the proposed extension is beneficial only for small input data. The chart with results of power of 8 is an example that for higher powers the NVRAM distributed cache is superior for each input size. Results with delete on close mode on The delete on close mode allows to omit the phase of synchronization between the NVRAM distributed cache and the parallel file system. For that reason, execution time of an application is reduced, what is especially important for smaller powers. Figure 6 shows that the proposed solution performs significantly better than the regular MPI I/O for powers starting with 2, while Figure 7 proves, that the extension gives performance gain both for small and large size of input.

Scalability Figure 8 illustrates a respectable scalability of the algorithm, as well as the proposed NVRAM cache. With an increasing size of a cluster environment, average load of a single node related to I/O operations is constant, because a higher number of I/O requests from computing nodes is handled by a higher number of cache managers. A typical PFS environment usually is not so flexible and in case of an unexpected heavy load requires hardware reconfiguration.

Summary and future work

Motivation of this research was related to expected incorporation of emerging memory technologies in production devices soon, which was justified in the intro- duction and related work. Within this paper we described an optimized version of MPI I/O distributed cache supported by byte-addressable NVRAM. Then we focused on its evaluation with an application that computes powers of adjacency matrix using Cannon's algorithm. Presented results of experiments prove, that with the tested application our solution performed better than regular MPI I/O. Our future plans include further optimization of the extension and its evaluation with a wider range of applications. Moreover, we also want to focus on the mechanism, that would allow to predict the benefit from our extension without actual running of an application.

Fig. 1 .

 1 Fig. 1. Exemplary architecture of the solution for cluster nodes, components within a single node are inside dashed bracket. NVRAM cache layer marked with gray illustrates the difference between classical architecture and the one extended with NVRAM cache. Number of nodes in the solution is not limited.

Fig. 2 .

 2 Fig.2. Power of adjacency matrix, comparison between synchronous and asynchronous write. Values for fixed graph size (10 000 nodes) and different powers. Lap06 cluster.

Fig. 3 .

 3 Fig. 3. Power of adjacency matrix, comparison between unmodified MPI I/O and proposed extension. Values for fixed graph size (20 000 nodes) and different powers. Lap06 cluster. Delete on close mode off.

Fig. 4 .

 4 Fig. 4. Power of adjacency matrix, comparison between unmodified MPI I/O and proposed extension. Values for fixed power (2) and different graph sizes. Lap06 cluster. Delete on close mode off.

Fig. 5 .

 5 Fig. 5. Power of adjacency matrix, comparison between unmodified MPI I/O and proposed extension. Values for fixed power (8) and different graph sizes. Lap06 cluster. Delete on close mode off.

Fig. 6 .

 6 Fig. 6. Power of adjacency matrix, comparison between unmodified MPI I/O and proposed extension. Values for fixed graph size (20 000 nodes) and different powers. Lap06 cluster. Delete on close mode on.

Fig. 7 .

 7 Fig. 7. Power of adjacency matrix, comparison between unmodified MPI I/O and proposed extension. Values for fixed power (2) and different graph sizes. Lap06 cluster. Delete on close mode on.

Fig. 8 .

 8 Fig. 8. Power of adjacency matrix, scalability. Values for fixed power (2) and fixed graph size (20 000 nodes). K2 cluster. Delete on close mode off.

Table 1 .

 1 Lap06 and K2 clusters -hardware and software configuration

		Lap06	K2
	Number of computing nodes 6	96
	Number of PFS nodes	2	3
	CPU	2 x Intel R Xeon R E5-4620, 2 x Intel R Xeon R E5345,
		2.20 GHz (2.60 GHz turbo) 2.33 GHz
	RAM	15GB	8GB
	Network	40Gb/s Infiniband	10Gb/s Ethernet
	Storage	SSD	HDD
	NVRAM simulation	17GB, hardware simulation 4GB, tmpfs
	MPI implementation		MPICH 3.2
	PFS		Orange-FS 2.8.7

Table 2 .

 2 NVRAM simulation platform parameters in Lap06 cluster

	Additional latency to access the data	2000ns
	Time required to flush data on device	600ns
	Memory bandwidth	9.5GB/s

Acknowledgments. The research in the paper was supported by a Grant from Intel Technology Poland.


Adam Klimowicz
email: a.klimowicz@pb.edu.pl

Synthesis Method of Finite State Machines Based on State Minimization for Low Power Design

Keywords: finite state machine (FSM), state minimization, logic synthesis, low power design

A new method for the synthesis of finite state machines (FSMs) is proposed. In this method, such optimization criterion as the power consumption is taken into account already at the stage of minimizing internal states. In addition, the proposed method allows one to minimize the number of transitions and input variables of the FSM. The method is based on sequential merging of two internal states. For this purpose, the set of all pairs of states that can be merged is found, and the pair that best satisfies the optimization criteria is chosen for merging. The sequential algorithm is used for low power state encoding. Experimental results show, that the dissipated power is less by 7% comparing to traditional methods.

Introduction

In recent years digital systems appears in all spheres of human activities. Reducing the power consumption of digital devices has become more important due to especially for battery powered mobile devices. Depending on specific conditions, this parameter can be the major factor to be optimized. There are several approaches to the solution of this problem: technological, logical, system level etc. A some way of solving this problem is to reduce the power consumption of finite state machines (FSMs). The finite state machine (FSM) provides a mathematical model that is widely used for designing digital systems, which are often designed as sequential circuits. For that reason, the optimization of FSMs with respect to the power consumption parameter is an important task.

The conventional approach to the synthesis of FSMs includes the following stages, which are executed sequentially: minimization of the number of internal states, state assignment and synthesis of the combinational part of the FSM. Under the conventional approach, a developer has only two methods of optimizing the FSM: minimization of the number of internal states and state assignment.

Often, even the exact minimization of the number of internal states does not make it possible to solve the optimization problems at the stage of logic synthesis.

In work [START_REF] Hallbauer | Procedures of state reduction and assignment in one step in synthesis of asynchronous sequential circuits[END_REF], the problem of minimization and state assignment was considered for asynchronous FSMs. The method proposed in [START_REF] Lee | Concurrent Minimization and State Assignment of Finite State Machines[END_REF] is applicable only to FSMs with the number of states not exceeding 10. In [START_REF] Avedillo | SMAS: A program for concurrent state reduction and state assignment of finite state machines[END_REF], a program for concurrent state reduction and state encoding was presented, which made it possible to build incompletely specified state codes.

The power consumption of an FSM can be directly reduced by special encoding of internal states [START_REF] Benini | State assignment for low power dissipation[END_REF][START_REF] Chattopadhyay | Low power state assignment and flipflop selection for finite state machine synthesis -a genetic algorithmic approach[END_REF][START_REF] Koegst | State Assignment for FSM Low Power Design[END_REF]. In [START_REF] Gören | On state reduction of incompletely specified finite state machines[END_REF][START_REF] Xia | Genetic algorithm based state assignment for power and area optimization[END_REF][START_REF] Aiman | Finite state machine state assignment for area and power minimization[END_REF], the implementation cost is minimized simultaneously with the minimization of the power consumption at the stage of state assignment. In the majority of these works, genetic algorithms are used. In [START_REF] Lindholm | High frequency and low power semi-synchronous PFM state machine[END_REF], the minimization of power consumption and delay is considered for asynchronous FSMs. The concept of a low power semi-synchronous FSM operating on a high frequency is proposed that can be implemented and tested as an ordinary synchronous FSM. In [START_REF] Shiue | Novel state minimization and state assignment in finite state machine design for low-power portable devices[END_REF], the conventional approach to the synthesis of FSMs is considered, under which the number of internal states is first minimized, then the internal states are encoded; next, the program ESPRESSO is used to build disjunctive normal forms (DNFs) of the functions to be realized and, finally, the cost, power consumption, and speed of operation are estimated. A set of algorithms is proposed to select the best state assignment so as to minimize the parameters mentioned above.

The analysis of available studies showed that the number of internal states and power consumption are not simultaneously minimized. The methods that claim to simultaneously take into account several optimization criteria actually reduce to the conventional approach in which several different algorithms are proposed for each stage. In the present paper, we propose a heuristic method for the minimization of incompletely specified FSMs that makes it possible to optimize a power consumption already at the stage of minimization of the number of internal states. In addition the method of synthesis also applies a special state assignment method called sequential encoding algorithm [START_REF] Grzes | Sequential algorithm for low-power encoding internal states of finite state machines[END_REF] designed for low power optimization. The proposed approach suits well for the implementation of FSMs on programmable logic devices (PLDs).

Idea of the proposed approach

A FSM behavior can be described by the transition list. The transition list is a table with four columns: a m , a s , X(a m ,a s ), and Y(a m ,a s ). Each row of the transition list corresponds to one FSM transition. The column a m contains the present, the column a s contains the next state, the column X(a m ,a s ) contains the set of values of the input variables that initiates this transition (a transition condition or an input vector), and the column Y(a m ,a s ) contains the set of values of the output variables that is generated by FSM at this transition (an output vector).

The proposed approach is based on the method for the minimization of the number of internal states of incompletely specified FSMs (ISFSM) proposed in [START_REF] Klimowicz | Minimization of incompletely specified Mealy finite-state machines by merging two internal states[END_REF]. An ISFSM output vector is represented by ternary vector. For example, Y(a m ,a s )="01-0", where 0 denotes zero value, 1 denotes unity value, and dash ("-") denotes a don't care value of the corresponding output variable.

The idea of the method [START_REF] Klimowicz | Minimization of incompletely specified Mealy finite-state machines by merging two internal states[END_REF] is to sequentially merge two states. For this purpose, the set G of all pairs of internal states of the FSM satisfying the merging condition is found at each step. Then, for each pair in G, a trial merging is done. Next, the pair (a i , a j ) that leaves the maximum possibilities for merging other pairs in G is chosen for real merging.

In distinction from [START_REF] Klimowicz | Minimization of incompletely specified Mealy finite-state machines by merging two internal states[END_REF], in the present paper we chose for merging at each step the pair (a i , a j ) that best satisfies the optimization criteria in terms of power consumption, and leaves the maximum possibilities for merging other pairs in G. This procedure is repeated while at least one pair of states can be merged.

After procedure of state minimization, the sequential algorithm of state assignment [START_REF] Grzes | Sequential algorithm for low-power encoding internal states of finite state machines[END_REF] is performed to provide encoding which minimizes the power consumption.

Let (a s , a t ) be a pair of states in G, where P st is the estimate of power consumption, and M st is the estimate of the possibility to merge other states. Then, with regard to the above considerations, the FSM synthesis algorithm can be described as follows.

Algorithm 1 (general algorithm for FSM synthesis)

1. Using the method described in [START_REF] Klimowicz | Minimization of incompletely specified Mealy finite-state machines by merging two internal states[END_REF], form the set G of pairs of states that can be merged. If G =  (no pairs can be merged), go to step 5 2. For each pair of states (a s , a t ) in set G, calculate the estimates P st , and M st of the optimization criteria. 3. According to the specified order of optimization criteria, choose a pair of states (a i , a j ) for merging. Among all the pairs in G, choose a pair (a i , a j ) for which P ij = min; if there are several such pairs, then choose among them the one for which M ij = max. 4. Merge the pair of states (a i , a j ). Store the results of minimization (transition list and corresponding P st value ). Go to step 1. 5. Among all saved results of minimization select one with minimal P st value. 6. Minimize the number of transitions in the FSM. 7. Minimize the number of input variables in the FSM. 8. Perform state assignment using sequential algorithm [START_REF] Grzes | Sequential algorithm for low-power encoding internal states of finite state machines[END_REF]. 9. Stop.

Algorithms of minimization of the number of transition an input variables are based on some observations. Suppose, for instance, that one transition from a state a 1 under condition x 1 leads to a state a 2 and the second transition from a 1 under condition 1 x leads to another state a 3 and on each of these transitions not orthogonal output vectors are formed ( 1x is an inversed form of the variable x 1 ). Suppose that the states a 2 and a 3 can be merged. After merging a 2 and a 3 , a new state a 23 is formed. Now two transitions lead from a 1 to a 2_3 , one under condition x 1 and the second under condition 1

x . The latter means that the transition from a 1 to a 23 is unconditional and two transi- tions can be replaced by one unconditional transition. Notice that in general transition conditions from a state a 1 can be much more complicated.

At minimization of the number of FSM transitions one can arrive at a situation when certain input variables have no impact on the transition conditions. Suppose, for instance, that one transition from a state a 1 under condition x 1 leads to a state a 2 and another transition from a 1 under condition 1

x leads to a state a 3 and the variable x 1 does not meet anywhere else in transition conditions of the FSM. Suppose that after the states a 2 and a 3 have been merged, the transition from the state a 1 to the state a 23 becomes unconditional, i.e. it does not depend on values of input variables. The latter means that the variable x 1 has no impact on any FSM transition and therefore it is redundant.

Estimation of optimization criteria

To estimate the optimization criteria, all pairs of states in G are considered one after another. For each pair of states (a s , a t ) in G, a trial merging is performed. Next the internal states are encoded using sequential algorithm and the system of Boolean functions corresponding to the combinational part of the FSM is built. Next, for the pair (a s , a t ), power consumption P st , and the possibility of minimizing other states M st are estimated. The optimization criteria for each pair of states (a s , a t ) in G are estimated at step 2 of Algorithm 1 using the following algorithm.

Algorithm 2 (estimation of optimization criteria).

1. Sequentially consider the elements of the set G.

2. For each pair of states (a s , a t )  G, make a trial merging.

3. Encode the internal states using sequential algorithm. 4. Estimate the power consumption P st . 5. Estimate the possibility of other states minimization M st . 6. Return to the original FSM (before merging at step 2). 7. Execute steps 2-9 for all pairs of states in G.

Stop.

The estimate M st is determined by the number of pairs of the FSM that can be merged after merging the pair (a s , a t ). To provide the best possibilities for merging other states, M st should be maximized. Using the method described in [START_REF] Klimowicz | Minimization of incompletely specified Mealy finite-state machines by merging two internal states[END_REF], the set G st of pairs of states that can be merged upon merging the pair (a s , a t ) must me find. After that, the parameter M st can be calculated as the cardinality of the set

G st (M st = | G st |).
To estimate the power consumption of an FSM, we use the method given in [START_REF] Tsui | Power estimation methods for sequential logic circuits[END_REF] because it is the quite universal and suitable for any hardware components built using the CMOS technology. The procedure described in [START_REF] Tsui | Power estimation methods for sequential logic circuits[END_REF] makes it possible to calculate the dynamic power consumption of an FSM taking into account the encoding of its internal states and the probability of occurrence of ones at FSM inputs.

According to [START_REF] Tsui | Power estimation methods for sequential logic circuits[END_REF], the power consumption of the FSM is determined by the rule:

      R r R r r DD r N fC V P P 1 1 2 2 1 ( 1
)
where P r is the power consumed by the trigger r, V DD is the supply voltage, f is the frequency at which the FSM operates, C is the capacity of trigger output, and N r is the activity of the trigger r.

Let k i be a binary code of a state a i . Denote by i r k the value of the bit r in the code k i of the state a i . Then, the activity N r of switching the memory element r of the FSM satisfies the following equation

         M m M s r s r m s m r k k a a P N 1 1 (2)
where P(a m  a s ) is the probability of transition from the state a m to the state a s and  is the XOR operation. The FSM has to be encoded first to determine the activity of each trigger.

The probability P(a m  a s ) of transition from the state a m to the state a s is given by the following equation:

        s m m s m a a X P a P a a P ,   (3)
where P (a m ) is the probability of the FSM to be in the state a m and P(X(a m , a s ) is the probability of appearing the vector X(a m , a s ) initiating the transition from a m to a s at the input of the FSM.

The probability m , a s ) of the vector X(a m , a s ) to appear at the input of the FSM is given by the rule:

          L b b s m d x P a a X P 1 , (4)
where d  {0, 1, '-'} and P(x b = d) is the probability that the input variable x b in the input vector X(a m , a s ) takes the value d. We make an assumption that 0 and 1 appear at each input of the FSM with the same probability; therefore, P (x b = 0) = P (x b = 1) = 0.5 and P (x b = '-') = 1 (the probability that 0 or 1 appear at each input of the FSM is equal one because symbol '-' means logic zero or logic one and any other values cannot appear at input). For a specific FSM, P (x b = 0) and P (x b = 1) may be different; however, it must hold that P (x b = 0) + P (x b = 1) = 1. The probability P(a i ) to find the FSM in each state a i can be determined by solving the system of equations

           M m i m m i a a X P a P a P 1 , ,   M i , 1  (5)
If there are no transitions between the states a m and a i , then we set P (X (a m , a i )) = 0. If there are several transitions, then P(X (a m , a i )) is the sum of the probabilities of appearing each input vector initiating the transition from a m to a i . System (5) is a system of M linear equations with M unknowns P(a 1 ),…, P(a M ), which can be solved by any available method, for example, by the Gauss method. Since the FSM is always in one of its internal states, it holds that

     M m m a P 1 1 (6)
To simplify the solution of system ( 5), one equation in ( 5) can be replaced with [START_REF] Koegst | State Assignment for FSM Low Power Design[END_REF].

With regard to the above considerations, the algorithm for estimating the FSM power consumption is as follows.

Algorithm 3 (estimation of the power consumption).

1. According to (4), for each input vector X(a m , a s ) (a m , a s  A), calculate the probability P(X(a m , a s )) of its appearance at the input of the FSM. 2. Solve system of equations ( 5) to find the probabilities P(a i ) of the FSM to be in each state a i  A. 3. Using (3), calculate the probabilities of transitions P(a m  a s ) of the FSM for a m , a s  A. 4. Based on the encoding of internal states, find the activity N r (

  R r , 1

) of each trigger using (3). 5. Using (1), calculate the power consumption P of the FSM for the following values of the parameters: V DD = 5 V, f = 10 MHz, and C = 3 pF (these are typical values for most chips manufactured using the CMOS technology). Set P st := P. 6. Stop.

State assignment procedure

The encoding of internal states is proposed to be made with the sequential algorithm more precisely described in [START_REF] Grzes | Sequential algorithm for low-power encoding internal states of finite state machines[END_REF]. In this method assigning the code to the state depends on states assigned earlier. It needs to define the set K R of the all state codes that can be assigned, where R = [int log 2 M, M]. An FSM can be described by a state transition graph (STG), where the states are defined by the vertices and the transitions are defined by the edges. STG is a directed graph but for the power computations purpose we can convert it to an undirected graph because the transition from a i to a j causes that the same number of the flip-flops changes the output value as the transition from a j to a i . Weights of the edges can be expressed by:

w i,j = P(a i → a j ) + P(a j → a i ) (7)
Every state a i must be assigned a code c i . Thus internal states set A is connected with states codes set C = {c 1 , c 2 , ..., c M }. Every code must be orthogonal with the all other states codes. The code width R can be any value from the range [int log 2 M, M].

Let l i c denote l-th bit of the code of the state a i . Hamming distance H(c i , c j ) is de- fined as the number of bits in the same position with the opposite phase:

      R i l j l i j i c c c c H 1 , (8)
Then, with regard to the above considerations, the sequential encoding algorithm can be described as follows.

Algorithm 4 (sequential low power encoding).

1. Select two states a i and a j , for which w i,j is highest. 2. Assign two codes from the K R , such that Hamming distance H(c i , c j ) = 1. Remove the assigned state codes from K R . 3. Repeat steps 4-5 until all states are assigned. 4. Select the unassigned state a i , such that sum of the weights of the edges connected with the already assigned states is highest. 5. Assign the state a i unassigned code from K R with the lowest value of the function γ.

        M j j i j i i c c H w c 1 , ,  (9)
6. Remove the code from the K R . 7. Stop.

Experimental results

The method for synthesis of finite state machines was implemented in a program called ZUBR. To estimate the efficiency of the offered method we used MCNC FSM benchmarks [START_REF] Yang | Logic synthesis and optimization benchmarks user guide[END_REF] and well-known STAMINA minimization program [START_REF] Rho | Exact and heuristic algorithms for the minimization of incompletely specified state machines[END_REF] for comparison. The experiments were performed using Altera Quartus Prime version 16.0 EDA tool. All benchmarks in all three cases (without minimization, minimized with STAMINA and synthesized with proposed method) were implemented using identical design flow optimization parameters. Three parameters were taken from report files for further analysis: Core Dynamic Power (P), Total Logic Elements (C) and Maximum Clock Frequency -Fmax (F). For an implementation author has chosen the EP4CE115F29I8L devicea popular low cost FPGA from the Cyclone IV E family. The experimental results for Core Dynamic Power are presented in Table 1, where M 0 and P 0 are, respectively, the number of internal states and dissipated power (in mW) of the initial FSM (without minimization); M 1 and P 1 are, respectively, the number of internal states and dissipated power (in mW) after minimization using STAMINA and M 2 , and P 2 are, respectively, the number of internal states and dissipated power (in mW) after synthesis using proposed method. P 0 /P 2 and P 1 /P 2 are ratios of the corresponding parameters. Average row contains the mean values. The analysis of Table 1 shows that application of the proposed method allows to reduce the number of internal states of the initial FSM. Similarly, the average reduction of the power consumption of the FSM makes 1.07 times, and on occasion (example S832) 1.19 times. In comparison to STAMINA the number of states is higher in 4 cases but the average reduction of the power consumption of the FSM makes 1.06 times, and on occasion (example S208) 1.13 times.

The experimental results for cost (Total Logic Elements) and speed (Fmax) are presented in Table 2, where C 0 and F 0 are, respectively, the number used logic element and maximum frequency of the initial FSM (without minimization); C 1 and F 1 are, respectively, the same parameters after minimization using STAMINA [START_REF] Rho | Exact and heuristic algorithms for the minimization of incompletely specified state machines[END_REF] and C 2 , and F 2 are, respectively, the same parameters after synthesis using proposed method. Average row contains the mean values.

The analysis of Table 2 shows that application of the proposed method also allows to reduce the number of used logic elements in 9 of 10 cases in relation to FSMs without any minimization and in 8 of 10 cases in relation to FSMs minimized by STAMINA. In addition the maximum clock frequency in benchmarks realized with proposed method was higher than in base FSMs in 8 of 10 cases and higher than in STAMINA minimized benchmarks in 6 of 10 cases. Of course, there are examples where the cost and the speed were worse in relation to initial machines or FSMs minimized with STAMINA. It is related to fact, that in minimization method with power consumption criterion, the full minimization of states is not performed. There is al-ways selected a result with lower power dissipation, which is not always the same as one with minimal number of states.

Conclusion

In this paper we presented an efficient method for FSM synthesis. In contrast to traditional approaches, the proposed method allows to minimize not only the number of FSM states and consumed power, but also the number of FSM transitions and input variables what has an influence the cost and the speed of synthesized circuits. Using the proposed method there are always obtained machines with less or the same power consumption as the initial machines or STAMINA minimized FSMs.

Presented method is the part of future work on the complex minimization method, where not only power consumption, but also speed and area parameters are taken in consideration. In the general case, the problem of choosing the group of states for merging is a multicriteria discrete optimization problem, which can be solved by various algorithms.

In future, the complex synthesis method will serve to minimize power and cost and increase speed for FSM realization on programmable logic devices.

Table 1 .

 1 The experimental results for power and number of states

	Name	M0	P0	M1	P1	M2	P2 P0/P2 P1/P2
	LION9	9 0.21	4 0.2	5 0.20 1.05 1.00
	PLANET	48 0.29	48 0.29	48 0.26 1.12 1.12
	S208	18 0.27	18 0.27	18 0.24 1.13 1.13
	S27	6 0.21	5 0.2	5 0.20 1.05 1.00
	S386	13 0.22	13 0.22	13 0.21 1.05 1.05
	S420	18 0.26	18 0.26	18 0.25 1.04 1.04
	S820	25 0.35	24 0.38	25 0.34 1.03 1.12
	S832	25 0.37	24 0.32	25 0.31 1.19 1.03
	SAND	32 0.34	32 0.34	32 0.32 1.06 1.06
	TMA	20 0.23	18 0.24	19 0.23 1.00 1.04
	Average 21.4 0.28 20.4 0.27 20.8 0.26 1.07 1.06

Table 2 .

 2 The experimental results for cost and speed Average 128.6 280.02 127.2 281.36 112.7 297.09

	Name	C0	F0	C1	F1	C2	F2
	LION9	20 490.20		6 587.2	11 504.80
	PLANET	134 369.96	134 369.96	126 457.25
	S208	150 171.94	150 171.94	115 193.12
	S27	22 388.50	18 450.65	18 420.34
	S386	46 358.29	46 358.29	44 289.44
	S420	135 177.43	135 177.43	127 175.62
	S820	227 141.38	238 152.74	209 157.88
	S832	247 148.92	228 143.55	204 159.92
	SAND	221 164.12	221 164.12	189 194.10
	TMA	84 389.41	96 237.76	84 418.41

Acknowledgements. The research has been done in the framework of the grant S/WI/1/2013 and financed from the funds for science by MNiSW.