Lukasz Gadomer
email: l.gadomer@pb.edu.pl

Zenon A Sosnowski
email: z.sosnowski@pb.edu.pl

Fuzzy Random Forest with C-Fuzzy Decision Trees

Keywords: Fuzzy Tree, C-Fuzzy Decision Tree, Fuzzy Random Forest

In this paper a new classification solution which joins C-Fuzzy Decision Trees and Fuzzy Random Forest is proposed. Its assumptions are similar to the Fuzzy Random Forest, but instead of fuzzy trees it consists of C-Fuzzy Decision Trees. To test the proposed classifier there was performed a set of experiments. These experiments were performed using four datasets: Ionosphere, Dermatology, Pima-Diabetes and Hepatitis. Created forest was compared to C4.5 rev. 8 Decision Tree and single C-Fuzzy Decision Tree. The influence of randomness on the classification accuracy was also tested.

Introduction

Authors propose a new kind of classifier which joins C-Fuzzy Decision Trees and Fuzzy Random Forest. In this paper the construction of this ensemble classifier is presented. It is built similar to the Fuzzy Random Forest but instead of Janikow Fuzzy Trees [START_REF] Janikow | Fuzzy decision trees: issues and methods[END_REF] it uses C-Fuzzy Decision Trees [START_REF] Pedrycz | C-fuzzy decision trees[END_REF]. The first part of this paper consists of all of the techniques connected with the proposed ensemble classifier: Fuzzy Decision trees, C-Fuzzy Decision Trees and Ramdom Forests. In the next part the details of Fuzzy Random Forest with C-Fuzzy Decision Trees classifier are described. After that, the experiments are described their results are presented. The quality of classification acquired using Fuzzy Random Forest with C-Fuzzy Decision Trees is compared with C-Fuzzy Decision Trees working singly. Also, the strength of randomness is tested by comparing results obtained using random node selection with the results achieved without it.

Related work

The idea of Fuzzy Random Forest with C-Fuzzy Decision trees is based on the Fuzzy Random Forest. Before presenting this issue it is worth to take a look at two classifiers which are the fundaments of the mentioned forest. The first one is the Fuzzy Tree, the second one is the Random Forest. Both of these issues are described in following paragraphs.

Fuzzy decision trees

Fuzzy trees are modification of traditional decision trees. The characteristic feature of this kind of trees is the fact of using fuzzy logic in their construction, learning and decision making process. There are a lot of works which concern this issue, for example [START_REF] Yuan | Induction of fuzzy decision trees[END_REF] or [START_REF] Robin | Fuzzy decision tree algorithms[END_REF]. One of the most popular articles about fuzzy trees is C. Z. Janikow's paper [START_REF] Janikow | Fuzzy decision trees: issues and methods[END_REF]. This article is described in following paragraphs.

C. Z. Janikow created fuzzy trees [START_REF] Janikow | Fuzzy decision trees: issues and methods[END_REF] in order to join advantages of fuzzy logic and decision trees. This kind of trees have simple, clear and intelligible knowledge structure, which is characteristic for decision trees and they can deal with noises, imprecise information etc., which is possible thanks to the fuzzy logic. It allows for using fuzzy decision trees at areas where decision trees didn't work well.

Fuzzy decision trees [START_REF] Janikow | Fuzzy decision trees: issues and methods[END_REF] are based on two popular decision tree creation algorithms: CART [START_REF] Breiman | Classification and Regression Trees[END_REF] and ID3 [START_REF] Quinlan | Induction of decision trees[END_REF]. C. Z. Janikow decided to build his version of tree following assumptions of ID3, but modifying them in the way that allows for successful working with both discrete and continuous values. Proposed tree differs from the traditional one in two ways. First of them is the fact it uses the different inference procedures. The second one is about using node division criterions based on the fuzzy relations.

Random Forests

Random forest was created by L. Brieman and presented in [START_REF] Breiman | Random forests[END_REF]. A forest is classifier which consists of many trees. Each of these trees makes its own decision about assigning the object to the given class. After that, forest decides about the class where the object belongs, using to all of the decisions made by single trees. The thing which differs random forest from the standard one is the fact of using randomness during the tree construction process. It reduces correlation between trees with keeping the accuracy of classification. L. Briemann proposed two methods of using randomness to create random forest.

First method is based on random set of attributes selection before the node split. The nubmer of elements in this set is constant and equal for the each tree. When attributes are selected, the best candidate to divide the node is chosen. The choice is performed from the mentioned set. Brieman tested two sizes of attributes sets used to random selection. The first set's size is one, which means that from available attributes there is randomly chosen one in order to divide the node. The second set's size is the biggest number lower than log 2 M + 1 where M is a total number of attributes in the dataset. Tree growth is performed according to the assumptions of CART method [START_REF] Breiman | Classification and Regression Trees[END_REF], trees are not pruned. L. Brieman called the structure created the described way Forest-RI.

The second proposed method can be used when the dataset has relatively small number of features. In such situation the random choice is being made from linear combinations of attributes instead of the attributes. The structure created that way was called by its author Forest-RC.

Fuzzy random forests

The classifier with joins two solutions described in previous paragraphs was first presented in [START_REF] Bonissone | A fuzzy random forest: Fundamental for design and construction[END_REF] and then widely described in [START_REF] Bonissone | Combination methods in a fuzzy random forest[END_REF] and [START_REF] Bonissone | A fuzzy random forest[END_REF]. The mentioned classifier was based on two papers cited before: [START_REF] Janikow | Fuzzy decision trees: issues and methods[END_REF] and [START_REF] Breiman | Random forests[END_REF]. Fuzzy random forest, according to its assumptions, combines the robustness of ensemble classifiers, the power of the randomness to decrease the correlation betweeen the trees and increase the diversity of them and the flexibility of fuzzy logic for dealing with imperfect data [START_REF] Bonissone | A fuzzy random forest[END_REF].

Fuzzy random forest construction process is similar to Forest-RI, described in [START_REF] Breiman | Random forests[END_REF]. After the forest is constructed, the algorithm begins its working from the root of each tree. First, a random set of attributes is chosen (it has the same size for each node). For each of these attributes information gain is computed, using all of the objects from training set. Attribute with the highest information gain is chosen to node split. When the node is splitted, selected attribute is removed from the set of attributes possible to select in order to divide the following nodes. Then, for all of the following tree nodes, this operation is repeated using a new set of randomly selected attributes (attributes which were used before are excluded from the selection) and the same training set.

During the tree construction process, when the node is dividing, the given object's membership degree to the given node is computed. Before the division, for each node the membership degree is 1. When the division is completed, each object can belong to any number of created leaves (at least one). If the object belongs to one leaf, its membership degree to this leaf achieves 1 (for the other leaves it is equal to 0). If it belongs to more than one leaf, the membership degree to each leaf can take values between 0 and 1 and it sums to 1 in the set of all children of the given node. If the division is performed using attribute with missing value, the object is assigned to each split node with the same membership degree.

According to described algorithm trees are constructed. Each tree is created using randomly selected set of attributes, different for each tree, which ensures diversity of trees in the forest.

Bonissone et al. proposed two fuzzy random forest decision making strategies. First of them assumpts making decisions by each tree separately -then, using achieved results, forest is making its final decision about the class where the object belongs. The second strategy is about making one common decision by the forest using all of the information collected by all of the trees. For each of these strategies authors proposed several decision making methods.

C-Fuzzy Decision Trees

In [START_REF] Pedrycz | C-fuzzy decision trees[END_REF] W. Pedrycz and Z. A. Sosnowski proposed the new kind of decision trees, called C-Fuzzy Decision Trees. This class of trees was created in order to deal with the main problems of traditional trees. There are some fundamentals of decision trees. They usually operate on a relatively small set of discrete attributes. To split the node in the tree construction process, the single attribute which brings the most information gain is chosen. In their traditional form decision trees are designed to operate on discrete class problems -the continuous problems are handled by regression trees. These fundamentals bring some problems.

To handle continuous values it is necessary to perform the discretization. It can impact on the overall performance of the tree negatively. What is more, information bringed by the nodes which were not selected to split the node is kind of lost.

C-Fuzzy Decision Trees were developed to deal with these problems of traditional trees. The idea of this kind of trees assumed treating data as collection of information granules. These granules analogous to fuzzy clusters. Authors decided to span the proposed tree over them. The data is grouped in such multivariable granules characterized by high homogenity (low variablity) which are treated as generic building blocks of the tree.

The construction of C-Fuzzy Decision Tree starts from grouping the data set into c clusters. It is performed in the way that the similar objects should be placed in the same cluster. Each cluster is characterized by its prototype (centroid), which is randomly selected first and then improved iteratively during the tree counstruction process. When objects are grouped into clusters, the diversity of the each of these clusters is computed using the given heterogenity criterion. The computed diversity value decides if the node is selected to split or not. From all of the nodes the most heterogenous is chosen to split. The selected node is divided into c clusters using fuzzy clustering. Then, for the newly created nodes, the diversity is computed and the selection to split is performed. This algorithm works until it achieves the given stop criterion. The growth of the tree can be deep or breadth intensive. Each node of such tree has 0 or c children.

To make the paper self contained we describe the tree construction process in a formal way. Let's do the following assumptions:

c is a number of clusters, i = 1, 2, ..., c, -N is a number of training instances, k = 1, 2, ..., N , d ik is a distance function between the ith prototype and the kth instance, m is a fuzzification factor (usually m = 2),

-U = [u ik ] is a partition matrix, -Z = {x(k), y(k)} is an input-output pair of data instances, -z k = [x 1 (k)x 2 k...x n (k)y(k)] T , -f i is the prototype of the cluster.
Constructing clusters and grouping objects into them is based on Fuzzy C-Means technique (FCM), which is is an example of a fuzzy clustering. Clusters are built through a minimization of objective function Q, which assumes the format:

Q = c ∑ i=1 N ∑ k=1 u m ik d 2 ik (1)
During the iterations of Fuzzy C-Means process partitions u ik and prototypes f i are updated. For partitions it is performed according to the following equation:

u ik = 1 c ∑ j=1 ( d ik d jk ) 2/(m-1) (2)
Prototypes are updated using the following expression:

f i = N ∑ k=1 u m ik z k N ∑ k=1 u m ik (3)
In order to describe the node splitting criterion let's do the following assumptions:

-V i is the variability of the data in the output space existing at the given node, m i is the representative of this node positioned in the output space,

-X i = {x(k)|u i (x(k)) > u j (x(k)
) for all j ̸ = i}, where j pertains to the nodes originating from the same parent, denotes all elements of the data set which belong to the given node in virtue of the highest membership grade, -Y i = {y(k)|x(k) ∈ X i } collects the output coordinates of the elements that have already been assigned to X i ,

-U i = [u i (x(1))u i (x(2))...u i (x(Y i ))] is a vector of the grades of membership of the elements in X i , -N i =< X i , Y i , U i >,
According to these notation, m i is the following weighted sum:

m i = ∑ (x(k),y(k))∈Xi×Y i u i (x(k))y(k) ∑ (x(k),y(k))∈Xi×Y i u i (x(k)) (4)
The variability is computed as follows:

V i = ∑ (x(k),y(k))∈Xi×Y i u i (x(k))(y(k) -m i ) 2 (5)
The tree growth stop criterion could be, for example, defined in the following way: [START_REF] Pedrycz | C-fuzzy decision trees[END_REF] -There aren't enough elements in any node to perform the split. The minimal number of elements in the node which allows for the split is c. Normally the boundary number of the elements in each node would be the multiplicity of c, for example 2 × c or 3 × c, -All nodes achieve lower diversity than assumed boundary value, -The structurability index achieves the lower value than assumed boundary value, -The number of iterations (splits) achieved the assumed boundary value.

When the tree is constructed it can be used for classification. Each object which has to be classified starts from the root node. The membership degrees of this object to the children of the given node are computed. These membership degrees are the numbers between 0 and 1 and they sum to 1. The node where the object belongs with the highest membership is chosen and the object is getting there. The same operation is repeated as long as the object achieves to the node which has no children. The classification result is the class assigned to achieved node.

Fuzzy Random Forest with C-Fuzzy Decision Trees

To describe created classifier we used the following notations (based on [START_REF] Bonissone | A fuzzy random forest[END_REF] and [START_REF] Pedrycz | C-fuzzy decision trees[END_REF]):

-T is the number of trees in the C-FRF ensemble, t is the particular tree, -N t is the number of nodes in the tree t, n is a particular leaf reached in a tree, -I is the number of classes, i is a particular class, -C F RF is a matrix with size (T ×M AX Nt ) with

M AX Nt = max {N 1 , N 2 , ..., N t },
where each element of the matrix is a vector of size I containing the support for every class provided by every activated leaf n on each tree t; this matrix represents C-Fuzzy Forest or Fuzzy Random Forest with C-Fuzzy Decision Trees, c is the number of clusters, -E is a training dataset, e is a data instance, We propose creating the new kind of classifiers: Fuzzy Random Forest with C-Fuzzy Decision Trees. It is the forest, based on the idea of Fuzzy Random Forest, which consists of C-Fuzzy Decision Trees. The Fuzzy Random Forest uses randomness to improve the classification quality while C-Fuzzy Decision Tree is constructed randomly by definition -centroids of its clusters (the partition matrix) are selected randomly first. Combination these two structures is expected to give promising results.

-V = [V 1 , V 2 , ..., V b ] is the variability vector. -U = [U 1 , U 2 , ..., U |E| ]
The randomness in Fuzzy Random Forest with C-Fuzzy Decision Trees is ensured by two main aspects. The first of them refers to the Random Forest.

During the tree's construction process, node to split is selected randomly. This randomness can be full, which means selecting the random node to split instead of the most heterogenous, or limited, which assumpts selecting the set of nodes with the highest diversity, then randomly selecting one of them to perform the division (the size of the set is given and the same for the each split). The second aspect refers to the C-Fuzzy Decision Trees and it concerns the creation of partition matrix. At first, the centroid (prototype) of the each cluster selection is fully random. Objects which belong to the parent node are divided into clusters grouped around these centroids using the shortest distance criterion. Then the prototypes and the partition matrix are being corrected as long as they achieve the stop criterion. Each tree in the forest, created the described way, can be selected from the set of created trees. To create the single tree which will be chosen to the forest there can be build the set of trees. Each tree from such set is tested and the best of these trees (the one which achieved the best classification accuracy for the training set) is being chosen as the part of forest. The size of the set is given and the same for the each tree in the forest.

The split selection idea is similar to the one used in Fuzzy Random Forest. The difference is about the nature of tree used in the classifier. In Fuzzy Random Forest, the random attribute was being chosen to split. The node which was chosen to split was specified by tree growth strategy. In Fuzzy Random Forest with C-Fuzzy Decision Trees there isn't any attribute chosen -for each of the splits all of the attributes are considered. The choice concerns the node to split selection which means some nodes does not have to be splitted (when the stop criterion is achieved). The same idea is expressed in two completely different ways of building trees. Each C-Fuzzy Decision Tree in the forest can be completely different or very similar -it depends on the stop criterion and the number of clusters. The influence of randomness can be set using algorithm parameters which allows classifier to fit the given problem in a flexible way.

Prototypes of each cluster are selected randomly and then corrected iteratively, which means some of created trees can work better than others. Diversity of trees created that way depends on the number of the correction process' iterations. It is possible to build many trees and choose only the best of them to the forest in order to achieve better results. The diversity of the trees in the forest can be modified by changing the size of the set from which the best tree is chosen and the number of iterations. These parameters specifiy the strength of randomness in the classifier. Operating on these values also allow to fit to the given problem to improve the classification quality.

Fuzzy Random Forest with C-Fuzzy Decision Trees learning

The process of Fuzzy Random Forest with C-Fuzzy Decision Trees learning is analogous to the learning of Fuzzy Random Forest, proposed in [START_REF] Bonissone | A fuzzy random forest[END_REF]. The differences concern two aspects. First is about the kind of trees used in the forest. In the proposed classifier there are used C-Fuzzy Decision Trees instead of Janikow's Fuzzy Trees. The second aspect refers to the way of random selection of the node to split, which was described before.

The Fuzzy Random Forest with C-Fuzzy Decision Trees is created using Algorithm 1.

Algorithm 1 Fuzzy Random Forest with C-Fuzzy Decision Trees learning 1: procedure FRFwC-FDTlearning 2:

for 1 to T do 3:

1. Take a random sample of |E| examples with replacement from the dataset E 4:

2. Apply Algorithm 2 to the subset of examples obtained in the previous step to construct C-Fuzzy Decision Tree 5:

end for 6: end procedure Each tree in Fuzzy Random Forest with C-Fuzzy Decision Trees is created using Algorithm 2.

Algorithm 2 C-Fuzzy Decision Tree learning

1: procedure C-FDTlearning 2:
1. Start with the examples in E 3:

2. Create the partition matrix U randomly 4:

3. Perform FCM 5:

while Stop criterion is not satisfied do 6:

4. Divide the samples belonging to the splitted node into its children 7:

5. Make a random selection of nodes from the set of unsplitted nodes B 8:

6. Compute the variability matrix V 9:

7. Choose the node with maximum variability to split nodes 10:

8. Perform FCM 11:

end while 12: end procedure

Fuzzy Random Forest with C-Fuzzy Decision Trees classification

After the Fuzzy Random Forest with C-Fuzzy Decision Trees is constructed it can be used for new object's classification. The decision-making strategy used in the proposed sollution assumpts making decision by forest after each tree's decisions are made. 1 . It is performed according to the algorithm 3. It can be described by equation, similar to the one presented in [START_REF] Bonissone | A fuzzy random forest[END_REF]: Assign to class according to the simple majority vote of trees decisions 13: end procedure

D F RF (t, i, C F RF ) =      1 if i = arg max j,

Experimental studies

To test a quality of created classifier there were performed several experiments. These experiments were performed on four popular datasets from UCI Machine Learning Repository [START_REF] Lichman | UCI machine learning repository[END_REF]:

-Ionosphere, -Dermatology, -Pima-Diabetes, -Hepatitis.

Each dataset was divided into five parts with equal size (or as close to the equal as it's possible) randomly. Each of these parts had the same proportions of objects representing each decision class as it is in the whole dataset (or as close to the same as it's possible). There were no situations when in some of parts there weren't any objects representing some of decision classes. This random and proportional division was saved and used for each experiment.

Each experiment was performed using 5-fold crossvalidation. Four of five parts were used to train the classifier, one to test the learned forest. This operation was repeated five times, each time the other part was excluded from training and used for testing the classifier. After that, classification accuracy of all five out of bag parts were averaged.

For each dataset there were performed researches for both Fuzzy Forest with C-Fuzzy Decision Trees and Fuzzy Random Forest with C-Fuzzy Decision Trees. For each of these configurations there were performed expermients with 2, 3, 5, 8, 13 and 20 clusters. Each forest were consisting of 50 trees.

The objective of the research is to test how randomness influences the classification accuracy of the forest. There is also checked how the classification accuracy changes with the different number of clusters.

All of the results are presented in paragraph 5. They are all compared with themselves and also with single C-Fuzzy Decision Tree and C4.5 rev. 8 tree.

Results and discussion

Classification accuracies part consists of the following information:

-Classification accuracy achieved using C4.5 rev. 8 Decision Tree, -Classification accuracy achieved using a single C-Fuzzy Decision Tree, -Classification accuracies achieved using Fuzzy Forest with C-Fuzzy Decision Trees, -Classification accuracies achieved using Fuzzy Random Forest with C-Fuzzy Decision Trees.

The results for tested datasets are presented in the following tables:

-Ionosphere -Table 1, -Dermatology -Table 2, -Pima-Diabetes -Table 3, -Hepatitis -Table 4. The general tendention that can be observed in all of those results is decreasing the classification accuracy with increasing the number of clusters. In most cases results were the best for around 5 clusters, a bit worse for 2 -3 clusters and significally worse for 13 -20 clusters. This dependence is a bit different for each dataset, which means the number of clusters should be chosen according to the given problem.

In most cases Fuzzy Random Forests with Fuzzy Decision Trees achieved better results than Fuzzy Forests with Fuzzy Decision Trees. The exception was Pima-Diabetes dataset, where at the same number of cases the results were better or worse, depending on the number of clusters. It means that randomness generally increased the classification accuracy.

For each dataset there was at least one number of clusters which in almost all cases allowed to achieve better result that C4.5 rev. 8 Decision Tree. For Hepatitis dataset the better result was achieved independently from the number of clusters (exception was 20 clusters), but for the rest of datasets there were only one or two number of clusters, where these results were better. It shows how important is the choice of the proper number of clusters for C-Fuzzy Decision Trees used in Fuzzy Forests with Fuzzy Decision Trees and Fuzzy Random Forests with Fuzzy Decision Trees.

In almost all of the cases (unusual exceptions) results achieved using Fuzzy Forest with Fuzzy Decision Trees and Fuzzy Random Forest with Fuzzy Decision Trees were better than using single C-Fuzzy Decision Tree. It clearly shows the strength ensemble classifier build of this kind of trees. They achieve much better results when working together that when working as a single classifier.

Conclusion

In the previous paragraphs of this article there was proposed Fuzzy Random Forest with Fuzzy Decision Trees classifier. The created solution was checked on four datasets. Ionosphere, Dermatology, Pima-Diabetes andHepatitis. There were tested how successfully the classifier works in comparison to the C4.5 rev. 8 Decision Tree and a single C-Fuzzy Decision Tree. There were also tested how randomness affects achieved classification quality.

Performed experiments proved than in most cases Fuzzy Random Forest with C-Fuzzy Decision Trees classifier gives better results than C4.5 rev. 8 Decision Tree and single C-Fuzzy Decision Tree classifiers. They also demonstrated that using randomness in the forest can increase the classification quality.

  is the tree's partition matrix of the training objects, -U i = [u 1 , u 2 , ..., u c ] are memberships of the ith object to the c cluster, -B = {B 1 , B 2 , ..., B b } are the unsplitted nodes,

Fuzzy Random Forest with C-Fuzzy Decision Trees 14

  ,25 14,82 12,24 13,96 26,2 25,92

	Number of clusters	2	3	5	8	13	20
	C4.5 rev. 8			13,54
	Single C-Fuzzy Tree	15,1 15,68 14,82 17,11 38,71 36,17
	Fuzzy Forest with C-Fuzzy Decision Trees	15,1 15,39 13,39 15,67 29,93 30,19

Table 1 .

 1 Results -Ionosphere

	Number of clusters	2 3 5	8	13	20
	C4.5 rev. 8		5,98
	Single C-Fuzzy Tree	6,02 6,3 5,47 17,46 39,36 48,42
	Fuzzy Forest with C-Fuzzy Decision Trees	6,02 6,3 2,99 6,01 34,64 38,82
	Fuzzy Random Forest with C-Fuzzy Decision Trees 6,02 6,3 2,18 5,17 31,86 34,65

Table 2 .

 2 Results -Dermatology

	Number of clusters	2	3	5	8	13	20
	C4.5 rev. 8			27,95
	Single C-Fuzzy Tree	30,08 30,21 27,08 27,74 32,23 31,78
	Fuzzy Forest with C-Fuzzy Decision Trees	28,52 29,68 26,31 27,47 29,03 29,43
	Fuzzy Random Forest with C-Fuzzy Decision Trees 28,65 29,16 26,96 26,56 28,52 30,07

Table 3 .

 3 Results -Pima-Diabetes

	Number of clusters	2	3	5	8	13	20
	C4.5 rev. 8			43,86
	Single C-Fuzzy Tree	34,84 41,93 37,42 41,29 44,51 51,61
	Fuzzy Forest with C-Fuzzy Decision Trees	34,19 38,06 37,42 36,77 34,19 43,87
	Fuzzy Random Forest with C-Fuzzy Decision Trees 34,19 37,42 36,13 38,06 41,29 40

Table 4 .

 4 Results -Hepatitis

There is also another decision-making strategy which assumpts making the single decision by the whole forest. It is described in[START_REF] Bonissone | A fuzzy random forest[END_REF]

Acknowledgment

This work was supported by the grant S/WI/1/2013 from Bialystok University of Technology founded by Ministry of Science and Higher Education.


Walenty Oniszczuk
email: w.oniszczuk@pb.edu.pl

Blocking and Deadlocking Phenomena in Two-Server Tandem

Keywords: tandem queues, feedback, deadlock, blocking probability 1

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The behavior of various systems, including communication and computer systems, as well as production and manufacturing procedures, can be represented and analyzed through queuing network models to evaluate their performance [START_REF] Malekian | Novel Packet Queuing Algorithm on Packet delivery in Mobile Internet protocol Version 6 Networks[END_REF], [START_REF] Sunitha | A pre-emptive multiple queue congestion control for different traffic classes in WSN[END_REF][START_REF] Tikhonenko | On the queue-size distribution in the multi-server system with bounded capacity and packet dropping[END_REF]. System performance analysis consists of the derivation of a set of particular features [START_REF] Atencia | A discrete-time system with service control and repairs[END_REF], [START_REF] Gemikonakli | Exploring Service and Buffer Management Issues to Provide Integrated Voice and Data Services in Single and Multi-channel Wireless Networks[END_REF][START_REF] Itoh | Bottom-up learning of hierarchical models in a class of deterministic POMDP environments[END_REF], [START_REF] Kwiecień | Firefly algorithm in optimization of queueing systems[END_REF]. This usually includes the queue length distribution and various performance indicators such as response time, throughput and utilization.

Tandem queues are widely used in design, capacity planning and performance evaluation of computer and communication systems, call centers, flexible manufacturing systems, etc. Some examples of their application in real systems (two transmitter communication networks with DBA (Dynamic Bandwidth Allocation), service facility with front and back room operations) can be found in [START_REF] Raghavendran | Tandem communication network model with DBA having Non Homogeneous Poisson arrivals and feedback for first node[END_REF], [START_REF] Arivudainambi | Analysis of a service facility with cross trained servers and optional feedback[END_REF] respectively.

The theory behind tandem queues is well developed, see, e.g. [START_REF] Balsamo | Analysis of Queueing Networks with Blocking[END_REF][START_REF] Clo | MVA for product-form cyclic queueing networks with blocking[END_REF][START_REF] Economou | Product form stationary distributions for queueing networks with blocking and rerouting[END_REF], [START_REF] Martin | Large Tandem Queueing Networks with Blocking Queueing Syst[END_REF], [START_REF] Onvural | Survey of closed queuing networks with blocking[END_REF][START_REF] Perros | Queuing Networks with Blocking. Exact and Approximate Solution[END_REF]. However, there is still a great interest around more complicated setups involving blocking and deadlocking phenomena as well as different mechanisms for offering services. In particular, the two-node tandem queuing model with the BMAP (Batch Markovian Arrival Process) input flow and non-exponential service time distribution described in the paper [START_REF] Kim | The BMAP/G/1-> •/PH/1/M tandem queue with feedback and losses[END_REF]. Additionally, systems with finite capacity queues under various blocking mechanisms and scheduling constraints are analyzed by the author in [START_REF] Oniszczuk | Quality of Service Requirements in Computer Networks with Blocking[END_REF][START_REF] Oniszczuk | Modeling of dynamical flow control procedures in closed type queuing models of a computer network with blocking[END_REF][START_REF] Oniszczuk | Tandem Models with Blocking in the Computer Subnetworks Performance Analysis[END_REF][START_REF] Oniszczuk | Blocking and Deadlock Factors in Series Linked Servers with HOL Priority Feedback Service[END_REF][START_REF] Oniszczuk | Analysis of an Open Linked Series Three-Station Network with Blocking[END_REF][START_REF] Oniszczuk | An Intelligent Service Strategy in Linked Networks with Blocking and Feedback[END_REF][START_REF] Oniszczuk | Semi-Markov-based approach for analysis of open tandem networks with blocking and truncation[END_REF][START_REF] Oniszczuk | Analysis of linked in series servers with blocking, priority feedback service and threshold policy[END_REF][START_REF] Oniszczuk | Loss Tandem Networks with Blocking Analysis -A Semi-Markov Approach[END_REF][START_REF] Oniszczuk | Open tandem networks with blocking analysis -two approaches[END_REF].

In [START_REF] Oniszczuk | Quality of Service Requirements in Computer Networks with Blocking[END_REF][START_REF] Oniszczuk | Modeling of dynamical flow control procedures in closed type queuing models of a computer network with blocking[END_REF], the closed type, multi-center computer networks with different blocking strategies are investigated and measures of effectiveness based on Quality of Service (QoS) are studied. Markovian and semi-Markovian approaches for analysis of open tandem networks with blocking are presented in [START_REF] Oniszczuk | Tandem Models with Blocking in the Computer Subnetworks Performance Analysis[END_REF], [START_REF] Oniszczuk | Analysis of an Open Linked Series Three-Station Network with Blocking[END_REF], [START_REF] Oniszczuk | Semi-Markov-based approach for analysis of open tandem networks with blocking and truncation[END_REF], [START_REF] Oniszczuk | Loss Tandem Networks with Blocking Analysis -A Semi-Markov Approach[END_REF] and [START_REF] Oniszczuk | Open tandem networks with blocking analysis -two approaches[END_REF]. Some two-stage tandem queues with blocking and an optional feedback are presented in [START_REF] Oniszczuk | An Intelligent Service Strategy in Linked Networks with Blocking and Feedback[END_REF] and [START_REF] Oniszczuk | Analysis of linked in series servers with blocking, priority feedback service and threshold policy[END_REF]. In such systems, feedback is the likelihood of a task return, with fixed probability to the first node of the tandem immediately after the service at the second one. Tandems with feedback are usually more complex than the ones without and they are mostly investigated given stationary Poisson arrival process and exponential service time distribution. Blocking and deadlocking phenomena in an open series, linked network model with HOL (head-of-line) priority feedback service was investigated and presented by the author in [START_REF] Oniszczuk | Blocking and Deadlock Factors in Series Linked Servers with HOL Priority Feedback Service[END_REF].

The rest of this paper is organized as follows: Section 2 presents and explains the analytical model. Section 3, analyzes a tandem network with blocking, feedback service and deadlock phenomena. Procedures for calculating performance measures and Quality of Service (QoS) parameters are presented in Section 4. Numerical results obtained using our solution technique is given in Section 5. Finally, Section 6 concludes the paper.

Model specification and description

The general model outline:

• The arrival process from source station is Poisson.

• Each station consists of a single server and buffer.

• Two stations provide service that is exponentially distributed.

• The deadlock resolving rate µ d is also exponentially distributed.

• Scheduling disciplines are FCFS.

• All buffers have finite capacity m1 and m2. Figure one presents a simplified two-server tandem setup of the proposed model. Tasks arrive from the source at station A according to the Poisson process with rate λ and they are processed in a FIFO manner. The service received by station A is as follows: the task first accepts an exponentially distributed service with rate µ A , after service completion at station A, the task proceeds to station B (exponentially distributed service with rate µ B ), once it finishes at station B, it gets sent back to station A for reprocessing with probability 1-σ. We are also assuming that tasks, after being processed in the station B, may leave the network with probability σ.

The successive service times at both servers are mutually independent and are not conditioned on the state of the network. A finite capacity buffers (with capacity m1 and m2) are allowed at the front of each server. A task, upon service completion at server A, attempts with probability 1 -σ to join server B. If server B at the given time is full, then the first server must hold the completed task and consequently becomes blocked (i.e., not available for service on incoming tasks) until the second server completes service. The nature of the service process in this case depends only of the service rate at station B. It allows one to treat this task as located in additional places in the buffer B. Similarly, if the first buffer (with capacity m1) ahead of the first station is full, then the source station or the server B becomes blocked. In this case, the nature of the service process depends only of the service rates in station A and we can treat these tasks as located in additional places in the buffer A. There can be a maximum of m1+3 tasks assigned to the first servicing station including the tasks at the source and server B that can become blocked. Likewise, there can be a maximum of m2+2 tasks assigned to station B with a task blocked at server A (see Figure 2).

In this special type of multi-stage network with blocking a deadlock may occur. For example, let us suppose that server A is full and server B blocks it. A deadlock will occur if the task in service at server B is sent to server A upon completion of its service. We assume that a deadlock is detected instantaneously and resolved with some delay time by simultaneously exchanging both blocked tasks at the mean rate equal to µ d .

Generally, blocking and deadlocking phenomena is a very important mechanism for controlling and regulating intensity of arriving tasks from the source to the tandem stations. The arrival rate to the first server depends on the state of the network and blocking factor that reduces the rate at which source is sending traffic to this server.

B µ

Fig. 1. Two-server tandem configuration with feedback.

Exact analysis

Markov processes constitute the fundamental theory underlying the concept of queuing systems and provide very powerful and descriptive means for analysis of dynamic computer networks. Each queuing system can, in principle, be mapped onto an instance of a Markov process and then mathematically evaluated in terms of this process. According to general assumptions, a continuous-time homogeneous Markov chain can represent a tandem network. The queuing network model reaches a steadystate condition and the underlying Markov chain has a stationary state distribution. Also, such queuing network with finite capacity queues has finite state space. The solution of the Markov chain representation may then be computed and the desired performance characteristics, as queue length distribution, utilizations, and throughputs, obtained directly from the stationary probability vector. In addition, features such as deadlocks, blocking, feedback service, may be incorporated into a Markov chain representation -although the effect of doing so will increase the size of the state space.

In theory, any Markov model can be solved numerically. In particular, solution algorithm for Markov queuing networks with blocking, feedback service and deadlocks is a five-step procedure:

1. Definition of the series network state space (choosing a state space representation). 2. Enumerating all the transitions that can possible occur among the states. 3. Definition of the transition rate matrix Q that describes the network evaluation (generating the transition rate). 4. Solution of linear system of the global balance equations to derive the stationary state distribution vector (computing appropriate probability vector). 5. Computation from the probability vector of the average performance indices. In this type of a network we may denote its state by the pair (i,j), where i represents the number of tasks in server A and j denotes the number in server B (including the tasks in service, in blocking, or in deadlock). For any non-negative integer values of i and j, (i,j) represent a feasible state of this queuing network, and p i,j denotes the probability for that state in equilibrium. These states and the possible transitions among them are shown in Figure 2. The flux into a state of the model is given by all arrows into the corresponding state, and the flux out of the state is determined from the set of all outgoing arrows from the state. The arrows indicate the only transitions that are possible for this model. Transitions from top to bottom represent a change of state due to an arrival from the source station. Diagonal transitions from left to right or from right to left represent a change of state due to a task completing service at server A or at server B. Finally, transitions indicated by bottom to top arrows represent a change of state due to departures from the network, which occurs at rate µ A σ. The state diagram of the blocking network (see Fig. 2) contains all possible non-blocked states (marked by ovals) as well as the blocking states (marked by rectangles). Additionally, one special state, which represents deadlock state -is marked by a bold rectangle. The number of states in the blocking network is the sum of all possible non-blocking states plus all the blocking states: (m2+2)(m1+3)+m1+2+m2+2. Based on an analysis the state space diagram, the process of constructing the steady-state equations in the Markov model, can be divided into several independent steps, which describe some similar, repeatable patterns. For the server A, the steady-state blocking equations are:

(λ + µ B ) • p 0,m2+2 = µ A (1-σ) • p 1,m2+1 (λ + µ B ) • p i,m2+2 = λ • p i-1,m2+2 + µ A (1-σ) • p i+1,m2+1 for i = 1, ... , m1 (1) µ B • p m1+1,m2+2 = λ • p m1,m2+2 + µ A (1-σ) • p m1+2,m2+1
For the source, the blocking equations are:

(µ A σ + µ A (1-σ)) • p m1+2,j = λ • p m1+1,j for j = 0, ... , m2 (2) (µ A σ + µ A (1-σ)) • p m1+2,m2+1 = λ • p m1+1,m2+1 + µ d • p m1+3,m2+2
For the server B, the blocking equations are:

(µ A σ + µ A (1-σ)) • p m1+3,j = µ B • p m1+1,j+1
for j = 0, ... , m2

(3) For the deadlock, the steady-state blocking equation is:

0, 0 0, 1 0, m2+1 1, 0 1, 1 1, m2+1 i, m2+1 m1+1, 0 m1+1, 1 m1+1, m2+1 0, m2+2 1, m2+2 i-1, m2+2 i, m2+2 m1+1, m2+2 m1+2, 0 m1+2, 1 m1+2, m2+1 µ A σ µ A σ µ A (1-σ) µ A (1-σ) µ A σ µ A (1-σ) µ A σ µ A (1-σ) µ A (1-σ) µ A σ µ A σ µ A (1-σ) µ A σ µ A (1-σ) µ A (1-σ) µ A σ µ A (1-σ) µ A (1-σ) µ A σ µ A (1-σ) µ A σ µ A (1-σ) µ A σ µ A (1-σ) µ A σ µ A (1-σ) µ A (1-σ) µ A σ µ A σ µ A (1-σ) µ A (1-σ) µ A σ µ A (1-σ) i-1, m2+1 µ A (1-σ) m1+3, 0 m1+3, 1 µ A σ µ A (1-σ) µ A (1-σ) µ A (1-σ)
µ d • p m1+3,m2+2 = µ B • p m1+1,m2+2 (4)
The steady-state equations for all states without blocking are:

λ • p 0,0 = µ A σ • p 1,0 (λ + µ B ) • p 0,j = µ A (1-σ) • p 1,j-1 + µ A σ • p 1,j for j = 1, ... , m2+1 (λ + µ A σ + µ A (1-σ)) • p i,0 = λ • p i-1,0 + µ B • p i-1,1 + µ A σ • p i+1,0 for i = 1, ... , m1 (λ + µ A σ + µ A (1-σ) + µ B ) • p i,j = λ • p i-1,j + µ B • p i-1,j+1 + µ A σ • p i+1,j + µ A (1-σ) • p i+1,j-1 for i = 1, ... , m1, j = 1, ... , m2+1 (λ + µ A σ + µ A (1-σ)) • p m1+1,0 = λ • p m1,0 + µ B • p m1,1 + µ A σ • p m1+2,0 + µ A σ • p m1+3,0 (5) (λ + µ A σ + µ A (1-σ) + µ B ) • p m1+1,j = λ • p m1,j + µ B • p m1,j+1 + µ A σ • p m1+2,j + µ A σ • p m1+3,j + µ A (1-σ) • p m1+3,j-1 for j = 1, ... , m2 (λ + µ A σ + µ A (1-σ) + µ B ) • p m1+1,m2+1 = λ • p m1,m2+1 + µ B • p m1,m2+2 + + µ A σ • p m1+2,m2+1 + µ A (1-σ) • p m1+3,m2
A queuing network with feedback, blocking and deadlock, under appropriate assumptions, is formulated here as a Markov process. The stationary probability vector can be obtained from ( 1) -( 5) equations, by using numerical methods for linear systems of equations. The generation of the rate matrix Q can now be accomplished by going through the list of states and generating all the feasible transitions out of each state and the associated rates of each transition. For Markov processes in steady state, we have: xQ = 0 (6) where x is the stationary probability vector whose l-th element x l is the steady-state probability of a system in state l. Vector x can be obtained from ( 6) and a normalization condition for all network states 1 x l = ∑ , using equation-solving techniques.

Selected performance measures

When steady-state probabilities are known, one can easily obtain various performance measures. For example, the procedures for calculating the Quality of Service (QoS) parameters use the steady-state probabilities in the following manner:

1. Deadlock probability p dead :

ρ A = ∑ ∑ ∑ = + + = + = ⋅ + ⋅ m2 0 j 3,j m1 1 m2 0 j i,j 2 m1 1 i p 1 p 1 + ∑ + = + ⋅ 1 m1 0 i 2 i,m2 p 1 ( 14
)
9. Server B utilization ρ B :

ρ B = ∑ ∑ ∑ + = + + = + = ⋅ + ⋅ 1 m1 0 i 2 i,m2 1 m2 1 j i,j 2 m1 0 i p 1 p 1 + ∑ = + ⋅ m2 0 j 3,j m1 p 1 ( 15
)
10. The mean deadlocking time: 13. The mean blocking time in source node:

d 2 3,m2 m1 dead µ 1 p 2 t ⋅ ⋅ = + + (16
A 2 1,m2 m1 1 m2 0 j 2,j m1 blS µ 1 ) p 1 p 1 ( t ⋅ ⋅ + ⋅ = + + + = + ∑ (19)
14. The network blocking time:

blS blB blA bl t t t t + + = (20)

Numerical Results

In this section, we present some numerical examples to study the effect of the parameters on the selected performance characteristics. We will concentrate on the several important performance descriptors, such as the probability that the tandem network is deadlocked or blocked, blocking probabilities for A and B servers and various time measures. Different values of the parameters are taken for task inter-arrival rates, service intensities or feedback probabilities. To demonstrate this, the following configuration was chosen: the inter-arrival rate λ from the source station to server A is changed within a range from 0.5 to 5.0. The service rates in server A and server B are equal to: µ A = 10.0, µ B = 5.0. The deadlock resolving rate µ d is 1.5, the depart probability σ is chosen as 0.3 and the buffer capacities are equal to: m1 = 10, m2 = 5.

For this model with deadlock and blocking, the following results were obtained; the majority of them are presented in Figure 3 and Table 1. Fig. 3 and Table 1 illustrate dependencies of blocking and deadlock probabilities and their time measures given certain parameters. In this example, the utilization of the tandem network is determined only by one parameter, e.g. by increasing the interarrival rates for the fixed values of other parameters. Also, results in Fig. 3 and Table 1 evidently show that the deadlock and blocking phenomena must be taken into account because variation of inter-arrival rate drastically changes QoS and time measures of the tandem network with feedback.

Sensitivity analysis of the proposed tandem model is performed with respect to the effect of changes in the parameters µ A , µ B , µ d , σ, m1 and m2 (without changes λ -see investigation in the previous example) on the deadlock and blocking probabilities, the time measures and the nodes utilization. The data parameters for the sensitivity analysis are: λ = 1.0, µ A = 0.5, µ B = 0.5, µ d = 0.25, σ = 0.5, m1 = 10, m2= 5. The deadlock probabilities and other measures are computed with variation of -40%, -20%, 0%, +20%, +40% on the tandem model and are presented in Table 2. From the Table 3 it is clear that the probability and time measures are highly effected by small changes in the parameters µ A , µ d , and σ. On the average effect was observed, when the µ B parameter changes from -40% to +40% and minimal effect was observed, when parameters m1 and m2 varies from -40% to +40%.

Conclusions

In this paper, the problem of analytical (mathematical) modelling and calculation of the stationary state probabilities for a two-server tandem network with recycling, task blocking and deadlocking is investigated. Deadlock and task blocking probabilities and some other fundamental performance characteristics of such network are derived and followed by numerical examples. The results confirm importance of a special treatment for the models with blocking, deadlock and with feedback service, that justifies my research. The results can be used for capacity planning and performance evaluation of real-time computer networks where deadlock, blocking and feedback are present.

Fig. 2 .

 2 Fig. 2. State transmission diagram for tandem with blocking and deadlock

2 .

 2 Source node blocking probability p blS :

) 11 .

 11 The mean blocking time in server A:

Fig 3 .

 3 Fig 3. Graphs of QoS parameters, where, pbloc-A -the server A blocking probability, pblocBthe server B blocking probability, pdead is the deadlock probability, pbl is the common network blocking probability, utility-A and utility-B are the servers utilization coefficients.

  5. Simultaneously source and node A blocking probability p blSA :

		p	blSA	=	p	m1 +	1,m2	+	2	(11)
	6. Network blocking probability p bl : blB blA bl p p p + =	+	p	blS	+	p	m1 +	1,m2	+	2	(12)
	7. Idle probability p idle :	idle p =	p	0,0					(13)
	8. Server A utilization ρ

A :

Table 1 .

 1 The time measures versus mean inter arrival rates

	λ	t blA	t blS	t blB	t dead	t bl	ρ A	ρ B
	0.5	0.000 0,000	0.000	0.000	0.000	0.167	0.233
	1.0	0.001 0.000	0.000	0.000	0.001	0.337	0.467
	1.5	0.008 0.000	0.000	0.004	0.008	0.534	0.694
	2.0	0.024 0.001	0.001	0.069	0.028	0.746	0.869
	2.5	0.031 0.004	0.002	0.277	0.045	0.859	0.959
	3.0	0.025 0.008	0.003	0.523	0.051	0.868	0.991
	3.5	0.017 0.009	0.003	0.660	0.049	0.851	0.998
	4.0	0.013 0.010	0.003	0.719	0.046	0.839	0.999
	4.5	0.011 0.011	0.002	0.752	0.045	0.832	1.000
	5.0 0.009 0.011 0.002	0.773	0.045	0.828 1.000

Table 2 .

 2 Sensitive analysis of the proposed tandem model

	Para-	Performance		% change in Parameter
	meter	Measure	-40	-20	0	+20	+40
		p dead	0.242 0.285 0.319 0.345 0.366
		p bl	0.679 0.622 0.578 0.542 0.514
	µ A	p blS ρ A	0.441 0.378 0.328 0.288 0.254 0.883 0.862 0.845 0.832 0.882
		t dead	1.939 2.282 2.548 2.758 2.925
		t bl	2.159 1.512 1.155 0.935 0.789
		p dead	0.314 0.321 0.319 0.309 0.295
		p bl	0.603 0.584 0.578 0.579 0.585
	µ B	p blS ρ A	0.291 0.314 0.328 0.338 0.344 0.743 0.804 0.845 0.876 0.899
		t dead	2.513 2.573 2.548 2.472 2.261
		t bl	1.353 1.218 1.155 1.131 1.131
		p dead	0.438 0.369 0.319 0.280 0.250
		p bl	0.476 0.535 0.578 0.610 0.635
	µ d	p blS ρ A	0.271 0.304 0.328 0.349 0.361 0.872 0.857 0.845 0.837 0.830
		t dead	5.839 3.688 2.548 1.869 1.430
		t bl	0.953 1.070 1.155 1.220 1.271

Table 2 .

 2 Sensitive analysis of the proposed tandem model (cont.)

	Para-	Performance		% change in Parameter
	meter	Measure	-40	-20	0	+20	+40
		p dead	0.420 0.378 0.319 0.228 0.069
		p bl	0.539 0.556 0.578 0.604 0.603
	σ	p blS ρ A	0.285 0.304 0.328 0.365 0.438 0.792 0.815 0.845 0.891 0.894
		t dead	3.358 3.020 2.548 1.827 0.551
		t bl	1.077 1.112 1.155 1.208 1.207
		p dead	0.319 0.319 0.319 0.319 0.318
		p bl	0.578 0.578 0.578 0.578 0.578
	m1	p blS ρ A	0.328 0.328 0.328 0.328 0.328 0.845 0.845 0.845 0.845 0.845
		t dead	2.548 2.548 2.548 2.548 2.548
		t bl	1.155 1.155 1.155 1.155 1.155
		p dead	0.319 0.319 0.319 0.318 0.318
		p bl	0.577 0.577 0.578 0.578 0.578
	m2	p blS ρ A	0.329 0.329 0.328 0.328 0.328 0.845 0.845 0.845 0.845 0.845
		t dead	2.553 2.550 2.548 2.548 2.547
		t bl	1.153 1.154 1.155 1.155 1.155


Valery Salauyou
email: valsol@mail.ru

Synthesis of High-Speed Finite State Machines in FPGAs by State Splitting

Keywords: synthesis, finite state machine, high-speed, high performance, state splitting, field programmable gate array, look up table

A synthesis method of high-speed finite state machines (FSMs) in field programmable gate arrays (FPGAs) based on LUT (Look Up Table) by internal state splitting is offered. The method can be easily included in designing the flow of digital systems in FPGA. Estimations of the number of LUT levels are presented for an implementation of FSM transition functions in the case of sequential and parallel decomposition. Split algorithms of FSM internal states for the synthesis of high-speed FSMs are described. The experimental results showed a high efficiency of the offered method. FSM performance increases by 1.52 times on occasion. In conclusion, the experimental results were considered, and prospective directions for designing high-speed FSMs are specified.

Introduction

Large-size functional blocks and nodes of a digital system and also the digital system itself, as a rule, include a control device or a controller. The speed of a digital system and functional blocks depends directly on the speed of their control devices. The mathematical model for the majority of control devices and controllers is a finite state machine (FSM). Because of this, the synthesis methods of high-speed FSMs are necessary for designing high-performance digital systems. Note that an implementation cost can be ignored in the synthesis of high-speed FSMs, because an FSM area takes a small part compared with other system components (for example, memory or transceivers). Now, programmable logic devices (PLDs) are widely used for designing digital systems. Two types of PLD architectures are widely used: on the basis of two programmed matrixes (AND and OR), and on the basis of functional generators, an LUT (Look Up Table ). The first PLD type is called Complex Programmable Logic Devices (CPLDs), and the second PLD type is called Field Programmable Gate Arrays (FPGAs). It is possible to represent an FPGA structure as a great quantity of LUTs united by interconnections. Every LUT allows realizing any Boolean function from a small number of arguments (as a rule, from 4 to 6). The methods of FSM synthesis on CPLD have been considered in [START_REF] Salauyou | Logic Design of Digital Systems on Programmable Logic Devices[END_REF].

Many authors considered the synthesis problem of high-speed FSMs on PLD. Their methods were characterized by a large variety of approaches to deciding on a given task. In [START_REF] Miyazaki | Performance Improvement Technique for Synchronous Circuits Realized as LUT-Based FPGA's[END_REF], a technique for improving the performance of a synchronous circuit configured as an FPGA-based look-up table without changing the initial circuit configuration is presented. Only the register location is altered. This improves clock speed and data throughput at the expense of latency. In [START_REF] Jozwiak | Fast and compact sequential circuits through the information-driven circuit synthesis[END_REF], the methods and tools for state encoding and combinational synthesis of sequential circuits based on new criteria of information flow optimization are considered. In [START_REF] Huang | On speeding up extended finite state machines using catalyst circuitry[END_REF], the timing optimization technique for a complex FSM that consists of not only random logic but also data operators is proposed. The technique, based on the concept of a catalyst, adds a functionally redundant block (which includes a piece of combinational logic and several other registers) to the circuits under consideration so that the timing critical paths are divided into stages. In [START_REF] Kuusilinna | Finite State Machine Encoding for VHDL Synthesis[END_REF][START_REF] Rafla | A Study of finite state machine coding styles for implementation in FPGAs[END_REF], the styles of FSMs description in VHDL language and known methods of state assignment for the implementation of FSMs are researched. In [START_REF] Nedjah | Evolutionary synthesis of synchronous finite state machines[END_REF], evolutionary methods are applied to the synthesis of FSMs. At the first stage, the task of state assignment by means of genetic algorithms is resolved. Then evolutionary algorithms are applied to the minimization of chip area and time delay of FSM output signals. In [START_REF] Czerwiński | Synthesis Method of High Speed Finite State Machines[END_REF], the task of state assignment and optimization of the combinational circuit at implementation of highspeed FSMs in CPLD is considered. In [START_REF] Glaser | TR-FSM: Transition-based Reconfigurable Finite State Machine[END_REF], a novel architecture that is specifically optimized for implementing reconfigurable FSMs, Transition-based Reconfigurable FSM (TR-FSM), is presented. The architecture shows a considerable reduction in area, delay, and power consumption compared to FPGA architectures. In [START_REF] Senhadji-Navarro | Finite Virtual State Machines[END_REF], a new model of the automatic machine named the virtual finite state machine (Finite Virtual State Machine -FVSM) is offered. For implementation of the FVSM, architecture based on storage and a technique of FVSM generation from traditional FSMs is offered. FVSM implemented on new architecture have an advantage on high-speed performance compared with traditional implementation of FSMs on storage RAM. In [START_REF] Garcia-Vargas | Finite State Machines With Input Multiplexing: a Performance Study[END_REF], an implementation of FSMs in FPGA with the use of integral units of storage ROM is considered. Two pieces of FSMs architecture with multiplexers on inputs of ROM blocks which allow reducing the area and increasing high-speed FSM performance are offered. In [START_REF] Solov'ev | Splitting the Internal States in Order to Reduce the Number of Arguments in Functions of Finite Automata[END_REF], the reduction task of arguments of transition functions by state splitting is considered; this allows reducing an area and time delay in the implementation of FSMs on FPGA.

This paper also uses splitting of FSM states, but the purpose of splitting is an increase of FSMs performance in LUT-based FPGA. Splitting of FSM states belongs to operations of equivalent conversions of an FSM and does not change the algorithm of its functioning. During splitting of FSM states, the machine type (Mealy or Moore) is saved, the general structure of the FSM does not change, and embedded memory blocks of FPGAs are not used. In the course of state splitting, the hierarchy of state names is saved, which simplifies the analysis and debugging of the project. Because of this, the offered synthesis method of high-speed FSMs in FPGA is aimed at practical usage and can be easily included in the general flow of digital system design.

This paper is organized as follows. Section 2 describes estimations of the number of LUT levels in the implementation of FSM transition functions in the case of se-quential and parallel decomposition. Section 3 considers the synthesis method of high-speed FSMs, which includes two algorithms: a general algorithm and an algorithm for the decomposition of the concrete state. A detailed example shows the method. The experimental results are reported in Section 4. The paper concludes with a summary in Section 5.

Estimations for the number of LUT levels for transition functions

Let A = {a 1 , …, a M } be the set of internal states, X = {x 1 , …, x L } be the set of input variables, Y = {y 1 , …, y N } the set of output variables, and D = {d 1 , …, d R } the set of transition functions of an FSM.

A one-hot state assignment is traditionally used for the synthesis of high-speed FSMs in FPGAs. Thus, each internal state a i (a i  A) corresponds to a separate flipflop of FSM's memory. A setting of this flip-flop in 1 signifies that the FSM is in the given state. The data input of each flip-flop is controlled by the transition function d i ,

d i  D, i.e. any internal state a i (a i  A) of the FSM corresponds with its own transi- tion function d i , i= M , 1 .
Let X(a m ,a i ) be the set of FSM input variables, whose values initiate the transition from state a m to state a i (a m , a i  A). To implement some transition from state a m to state a i , it is necessary to check the value of the flip-flop output for the active state a m (one bit) and the input variable values of the X(a m ,a i ) set, which initiates the given transition. To implement the transition function d i , it is necessary to check the values of the flip-flop outputs for all states, such that transitions from which lead to state a i , i.e. |B(a i )| values, where B(a i ) is the set of states from which transitions terminate in state a i , where |A| is the cardinality of set A. Besides, it is necessary to check the values of all input variables, which initiate transitions to state a i , i.e. |X(a i )| values, where X(a i ) is the set of input variables, whose values initiate transitions to state a i ,

 ) ( ) , ( ) ( i m a B a i m i a a X a X   .
Let r i be a rank of the transition function d i , where

) ( ) ( i i i a X a B r   . ( 1
)
Let n be the number of inputs of LUTs. If the rank r i for transition function d i (i = M , 1 ) exceeds n, there is a necessity to decompose the transition function d i and its implementation on several LUTs.

Note that by splitting internal states it is impossible to lower the rank of the transition functions below the value

M s m a a X r s m , 1 , , 1 |) ) , ( max(| *    . ( 2
)
In this method, the value r* is used as an upper boundary of the ranks of the transition functions in splitting the FSM states.

It is well-known that there are two basic approaches to the decomposition of Boolean functions: sequential and parallel. In the case of sequential decomposition, all the LUTs are sequentially connected in a chain (fig. 1). The n arguments of function d i arrive on inputs of the first LUT, and the (n-1) arguments arrive on inputs of all remaining LUTs. So the number s i l of the LUT's levels (in the case a sequential decomposition of the transition function d i having the rank r i ) is defined by the expression:

LUT

1 1 int           n n r l i s i , (3)
where int(A) is the least integer number more or equal to A.

In the case of parallel decomposition, the LUTs incorporate in the form of a hierarchical tree structure (fig. 2).

  i n p i r l log int  . ( 4
)
It is difficult to predict what type of decomposition (sequential or parallel) is used by a concrete synthesizer. The preliminary research showed that, for example, the Quartus II design tool from Altera simultaneously uses both sequential and parallel decomposition. The number l i levels of LUTs in the implementation on FPGA transition function d i with the rank r i can be between values s i l and p i l , i= M , 1 .

Let k be an integer coefficient (k  [0,10]) that allows adapting the offered algorithm in defining the number of LUT's levels for the specific synthesizer. In this case the number l i of LUT's levels for the implementation of the transition function d i having the rank r i will be defined by following expression:

         s i p i i l k l k l 10 10 10 int . (5)
The specific value of coefficient k depends on the architecture of the FPGA and the used synthesizer.

The following problem is the answer to the question: when is it necessary to stop splitting the FSM states? The matter is that in splitting state a i (i= M , 1

), except for the increase of the number M of the FSM states, the number of transitions in the states of set A(a i ) is also increased, where A(a i ) is the set of states in which the transitions from state a i terminate. When splitting state a i , the cardinalities of sets B(a m ) (a m  A(a i )) are increased for the states of set A(a i ). Therefore, according to (1) for the states of set A(a i ) the ranks of the transition functions grow, which can lead to an increase of the values and s i l , p i l , and l i . In this algorithm, the process of state splitting is finished, when the following condition is met:

  mid l l int max  , (6)
where l max is the number of LUT levels, which is necessary for the implementation of the most "bad" function having the maximum rank; l mid is the arithmetic mean value of the number of LUT levels for all transition functions. Note that in the process of splitting the FSM internal states, the value l mid will increase and the value l max will decrease, therefore the algorithm execution always comes to an end.

Method for high-speed FSM synthesis

According to the above discussion, the algorithm of state splitting for high-speed FSM synthesis is described as follows.

Algorithm 1.

1. The coefficient k (k  [0,10]) is determined, which reflects the method used by the synthesis tool for the decomposition of Boolean functions. 2. According to (1) ranks r i (i= M , 1 ) for all FSM transition functions are defined. 3. On the basis of ( 3), (4), and ( 5), for each transition function d i the number l i of LUT levels is defined. 4. The values l max and l mid are determined. If condition ( 6) is met, then go to step 7, otherwise go to step 5. 5. The state a i , for which r i = max, is selected. If there are several such states, from them the state for which |A(a i )| = min is selected. 6. The state a i (which was selected in step 5) is split by means of algorithm 2 on the minimum number H of states a i_1 ,…,a i_H so that for each state a i_h (h= H , 1 ) was fulfilled r i_h ≤ r*, where r* is defined according to (2); go to step 2.

End.

Further synthesis of the FSM is performed using traditional techniques, for example, automatically by means of using a design tool synthesizer. For this purpose, it is enough to describe the FSM received after splitting internal states in one of the design languages (Verilog or VHDL). The value of coefficient k (step 1 of algorithm 1) is defined empirically by means of synthesis of the test examples in the used design tool.

For splitting some a i state, i= M , 1

, which is executed in step 6 of algorithm

* | } { | r w W t h  
, where

| } { | t h w W 
is the total number of ones in the columns of minor W h and the row w t after their joining on OR. If such rows can be selected from several among them, row w t is selected, which has the maximum number of common ones with minor W h , i.e.

max | } { |   t h w W
. The row w t is included in minor W h and row w t is eliminated from further reviewing, put

W h := W h  {w t }, W := W\{w t }.
Step 3 repeats until at least a single row can be included in minor W h . 4. If in matrix W all the rows are distributed between the minors, then go to step 5, otherwise go to step 2. 5. End.

We show the operation of the offered synthesis method in the example. It is necessary to synthesize the high-speed FSM whose state diagram is shown in fig. 3. This FSM represents the machine Moore, which has 6 states a 1 ,…,a 6 , 10 input variables x 1 ,…,x 10 , and one output variable y. The transitions from states a 3 , a 4 , and a 5 are unconditional, therefore the logical value 1 is written on these transitions as a transition condition. The values of sets B(a i ) and X(a i ), and also ranks r i of the transition functions for the initial FSM are presented in Table 1, where Ø is an empty set. Since for this example we have max(|X(a m ,a s )|)=5, then (according to (2)) the value r* = 6.

It is necessary to construct the FSM on FPGA with 6-input LUT, i.e. we have n = 6. 1). We do not know how the compiler performs a decomposition of Boolean functions, therefore we assume the sequential decomposition (a worst variant) and the value of coefficient k in expression ( 5) is equal to 10, i.e. we have k = 10. As a result, the number of LUT levels (which are necessary for the implementation of each transition function) is defined by the value l i = s i l . Thus, for our example we have int(l mid ) = int(8/6) = 2. In other words, splitting FSM internal states stops as soon as each transition function can be implemented in two levels of LUTs.

For this example, we have l max = s l 2 = 3, i.e. the condition [START_REF] Glaser | TR-FSM: Transition-based Reconfigurable Finite State Machine[END_REF] does not meet for state a 2 , since l max = s l 2 = 3 > int(l mid ) = 2. For this reason, state a 2 is split by means of algorithm 2. Matrix W is constructed for splitting state a 2 (fig. 4). a 1 a 6 x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 w 1 1 0 1 1 1 1 1 0 0 0 0 0 w 2 0 1 0 0 0 0 0 1 1 1 1 1 Fig. 4. Matrix W for splitting state a 2 Matrix W has two rows. Row w 1 corresponds to the transition from state a 1 to state a 2 , and row w 2 corresponds to the transition from state a 6 to state a 2 . The execution of algorithm 2 leads to a partition of rows of matrix W into two subsets: W 1 = {w 1 } and W 2 = {w 2 }. So, state a 2 is split into two states a 2_1 and a 2_2 , as shown in fig. 5. The new values of B(a i ), X(a i ), r i , s i l , and p i l are presented in Table 2. Now we have l max = l mid = 1 and (according to ( 6)) running of algorithm 1 is completed. Thus, for the given FSM by splitting state a 2 we reduced the number of LUT levels from 3 to 1, in the case of sequential decomposition, and from 2 to 1, in the case of parallel decomposition.

Experimental Results

The efficiency of the offered synthesis method was checked in the implementation of the initial FSM (fig. 1) and the FSM after splitting state a 2 (fig. 2) on FPGAs from Altera by means of the design tool Quartus II version 15.0. The main optimization criterion had been selected as the parameter «speed». The «one-hot» method of state assignment was selected for the initial FSM, and the «user» method of state assignment was selected for the FSM after synthesis (the state codes are defined from the FSM description). Table 3 presents the results of the experimental research of the offered method for various FPGA families, where nLUT 1 and nLUT 2 are the number of LUTs used in the implementation of the initial and the synthesized FSM, respectively; F1 and F2 are the clock frequency (in MHz) for the initial and the synthesized FSM, respectively; F1/F2 is the relation of the appropriate parameters. Analysis of Table 3 shows that the application of the offered method increased the performance of the FSM for 5 FPGA families from 7. Thus, for the family MAX II performance was increased by 1.52 times, and for the family Cyclone V performance increased by 1.35 times. In addition, the number of used LUTs decreased for the following families: Arria II GX, MAX V, and MAX II.

Conclusions

The presented results of the experimental research showed the following. Despite the fact that in the considered example the rank of transition function was reduced from 12 to 6, which allowed to reduce the number of LUT levels from 3 to 1 in the case of sequential decomposition, and from 2 to 1 in the case of parallel decomposition; however, the performance of the FSM did not increase for all FPGA families. This is a sign of the complexity of the synthesis task of high-speed FSMs. FSM performance depends not only on the results of logical synthesis, but also on the results of placing and routing. The reduction of the number of used LUTs for some FPGA families (as a result of the application of the offered method) can be accounted simply: with the reduction of the number of LUT levels, the LUT amount also decreases.

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.

Fig. 1 .

 1 Fig. 1. Sequential decomposition of Boolean function

Fig. 2 .

 2 Fig. 2. Parallel decomposition of Boolean function

Fig. 3 .

 3 Fig. 3. State diagram of the initial FSM

Fig. 5 .

 5 Fig. 5. State diagram of the FSM after splitting state a 2

  is put at the intersection of row t and column j of the second part of matrix W if input variable x Put h := h + 1. A formation of minor W h begins. The row w t , which has the maximum number of ones, is selected in minor W h as a reference row. The row w t is included in minor W H and the row w t is eliminated from further reviewing, put W h := {w t }, W := W\{w t }. 3. The rows are added in minor W h . For this purpose, among rows of matrix W, the row w t is selected, for which the next inequality is satisfied

	1. Put h := 0.
	2.
	Now the task is reduced to a partition of matrix W on a minimum number H of row
	minors W 1 ,…,W H so that the number of columns, which contain ones in each minor
	W h (h= H , 1 ), do not exceed value r* defined according to (2). The rows of each minor
	h will define transitions in state a	i_h (h= H , 1 ).
	Let w t be some row of matrix W. For finding the row partition of matrix W on a
	minimum number H of row minors W 1 ,…,W H , the following algorithm can be used.
	Algorithm 2.

1, Boolean matrix W constructed as follows. Let C(a i ) be the set of transitions to state a i . Rows of matrix W correspond to the elements of set C(a i ). Columns of matrix W are divided on two parts according to types of arguments of transition function d i . The first part of matrix W columns correspond to set B(a i ) of FSM states, the transitions from which terminate in state a i , and the second part of matrix W columns correspond to set X(a i ) of input variables, whose values initiate the transitions in state a i . A one is put at the intersection of row t (t= T , 1 , T = |C(a i )|) and column j of the first part of matrix W if the transition c t (c t  C(a i )) is executed from state a j (a j  B(a i )). A one j (x j  X(a i )) accepts a significant value (0 or 1) on transition c t (c t  C(a i )).

Table 1 .

 1 Values of B(a i ), X(a i ), r i , s

			i l , and p i l for the initial FSM
	State B(a i )	X(a i )	r i	l	s i	l	p i
	a 1	{a 6 }	{x 6 ,x 7 ,x 8 ,x 9 ,x 10 }	6	1	1
	a 2	{a 1 ,a 6 } {x 1 ,x 2 ,x 3 ,x 4 ,x 5 ,x 6 ,x 7 ,x 8 ,x 9 ,x 10 } 12 3	2
	a 3	{a 1 }	{x 1 ,x 2 ,x 3 ,x 4 ,x 5 }	6	1	1
	a 4	{a 2 ,a 3 } {x 1 }	3	1	1
	a 5	{a 2 ,a 4 } {x 1 }	3	1	1
	a 6	{a 5 }	Ø	1	1	1
	According to (3) and (4), the values s i l and p i l are defined for each state (they are
	presented in the appropriate columns of Table

Table 2 .

 2 Values of B(a i ), X(a i ), r i , s

				i l , and p i l after splitting state a 2
	State B(a i )	X(a i )	r i	s i l	i l	p
	a 1	{a 6 }	{x 6 ,x 7 ,x 8 ,x 9 ,x 10 } 6 1	1
	a 2_1	{a 1 }	{x 1 ,x 2 ,x 3 ,x 4 ,x 5 } 6 1	1
	a 2_2	{a 6 }	{x 6 ,x 7 ,x 8 ,x 9 ,x 10 } 6 1	1
	a 3	{a 1 }	{x 1 ,x 2 ,x 3 ,x 4 ,x 5 } 6 1	1
	a 4	{a 2_1 ,a 3 } {x 1 }	3 1	1
	a 5	{a 2_2 ,a 4 } {x 1 }	3 1	1
	a 6	{a 5 }	Ø 1	1 1	1

Table 3 .

 3 Results of the experimental researches

	Family	nLUT 1 F 1	nLUT 2 F 2	F 2 /F 1
	Arria II GX	8	1307 7	1269 0.97
	Cyclone IV E	9	778	10	793	1.02
	Cyclone IV GX 9	729	10	802	1.10
	Cyclone V	6	686	6	925	1.35
	MAX 10	10	800	11	816	1.02
	MAX V	10	343	9	314	0.92
	MAX II	10	389	9	593	1.52