RU UA EN

Preface

At this moment one of the most frequently used bases is PLD which belong to the class of FPGA [3]. Using this basis it was actual before [3], as indicated by the corresponding sections in [1] and [2]. Now, however, importance PLD FPGA has increased and confirmed particular more detailed review them in [4].

From this, we can formulate the problem, which is adapt the previously developed and tested methods of optimization circuits control machines to the basis of modern PLD FPGA. The problem of adaptation is rather complicated, considering that in each particular case it has a specific solution. However, preparing the solution of this problem, you can select a process that must be performed regardless of which method is adapted to the particular case. It is about the research results of a specific optimization method for the basis of PLD FPGA. According this article provides a methodology for conduct this kind of research.

Aims and tasks

1. Decomposition of the research process in set of separate steps (or kinds of activities) with the definition for each input and output data.

2. Determination a set of technical tools required to perform all kinds of activities and development of method their organization in a single complex.

An important aspect is the assessment possibilities of applying the proposed method in real conditions. Consequently, the third sub-task - testing opportunities for practical application of research methods.

Algorithm of research

Proposed method of this research is algorithm (Fig. 1), which includes a six-different kinds of activities.

At first run executed generation of the original model. The method of constructing the model may differ depending on what kind of optimization method is investigated, but the basic structure of it may remain the same. The generator model should allow for fine-tuning of the generation of several parameters. In particular, it should be the amount of states, the amount of characters input and output alphabets.

Next optimizes the original model. It should be borne in mind that the optimization model can be expanded by elements which are peculiar to rather digital technology than the theory of finite machines. The optimized model will be a modified model of the CD, which is connected to a set of models describing the necessary digital devices.

Figure 1 – Research algorithm method of optimization control machines
(UML activity diagram)

Next, performed generate a formal description of the models. A formal description can be done using a hardware description languages such as, VHDL or Verilog. This description must conform to generally accepted recommendations for a specific language [6, 7]. As a minimum mark of quality the formal description of CD can consider it a valid means of identification of synthesis.

The next kind of activity is the verification of the equivalence of of the initial model of its formal description, and the equivalence of models. The proof of the equivalence of machines models can be performed as follows. We assume that both control have different states of machines and the input alphabet of symbols. In this case, for each state there is no more than the outgoing transitions. Further, assume that you can install without having to change the state description, which eliminates the possibility of introducing additional errors. Hence, to prove the equivalence of two formal definitions require no more than iterations. In this case, the relevant issue is the use of parallel systems [5], since we are talking about a large number of repetitive actions.

Along with the verification necessary to perform the synthesis of formal descriptions of both models. At this stage the important aspect is the choice of basis, ie particular family or particular PLD, and a set of job specific parameters, in particular, the method of encoding the states, a global optimization strategy, etc.

The latter activity is the analysis of reports verification and synthesis. The algorithm in Fig. 1 can process only single model of the control machines. At the same time, to collect appropriate statistical data needed to perform the processing of several models that have similar characteristics. At this stage, performed analyzes all the data.

The structure of complex software

To perform the proposed algorithm requires a complex set of technical means, which consists of heterogeneous components (Fig. 2).

The generator of the initial and optimized models and the formal description of the generator can be implemented using one of the modern programming languages.

The main criterion for selecting the means of synthesis can be considered a specific model or a specific PLD family FPGA, which is performed in the basis of the study. In particular, if the family of PLD Altera Stratix III, it is necessary CAD Altera Quartus II, and for a family of Xilinx Spartan 6 CAD is required Xilinx ISE.

Verification tools can be selected based on market preference. Moreover, any connection between the means of verification and synthesis tool may be missing. In particular, one of the most common now CAD simulation, which can be used for verification, a Mentor Graphics ModelSim.

These tools are not linked by default. Therefore, in developing the complex software required to control the means of different CAD systems, as well as the implementation of data collection and processing, which suggests the possibility of creating a shell around research of the algorithm needed to collect statistically significant data, as noted in the previous section.

Figure 2 – The structure of complex software

At this time as such tools can be a language Tcl \ Tk, which, for some CAD (eg, Altera Quartus II and Mentor Graphics ModelSim), is the primary means of machines.

All of these components are required. and shown in Fig 2. However, the complex may also include additional components. In particular, in Fig. 1 we showed that certain activities can be executed in parallel. In addition, certain activities, such as verification, by themselves have the properties of parallel algorithms. Therefore, it is possible to use components that provide some degree of parallelism [5].

The structure shown in Fig. 2, is scalable. That is, it allows you to research a number of different optimization methods. In this algorithm, shown in Fig. 1, is applied to the set of pairs of models, each of which the first is the original model, and the second - one of the optimized models.

Research of the method of substitution characters input alphabet

Optimization method based on replacing the input alphabet of symbols is described in [1] and [2]. The idea is to substitute the original input alphabet a new one that includes a smaller number of characters (that is), the maximum number of characters needed to manage any transition inside the machine.

The generator model CD was designed to provide the ability to change the following parameters: - number of characters input alphabet - the maximum number of characters in the input alphabet the transition - the number of characters output alphabet - the maximum number of characters output alphabet and the transition - the number of states of the control machines.

The optimization process leads to the need for an additional model of commutation. It can be described as an associative array where the key is the state of CD, and values ??- other associative arrays, for which the key is the symbol of input alphabet, and the value - the symbol of the replacement alphabet. This model is fairly simple and complements the model machines.

Verification of the formal description of the models was performed using CAD Mentor Graphic ModelSim. To work with the "internal" (i.m. not available directly through the external interface) signals used in scripts to Tcl \ Tk [8]. Although the current standard VHDL [9] allows to work with such signals, it is supported by modeling tools only partially. Therefore, generation of test scenarios in a language that was used to formally describe the control machines, in this case is a necessary, though undesirable.

As the basis was chosen modern high PLD FPGA Family Altera Stratix III [10]. One of the main architectural peculiarities of this PLD is that they are built on the function generator from the six arguments. This makes it possible to efficiently implement complex circuit of commutation, characteristic for the investigated optimization method.

In accordance with the basis, as a CAD fusion was used Altera Quartus II [11]. Moreover, the control of the CAD, as well as in the case of Mentor Graphics ModelSim, was used language Tcl \ Tk.

To avoid unnecessary complexity language Tcl \ Tk was also used for collecting, processing and analysis of reports of CAD simulation and synthesis.

To obtain statistically valid data for each set of characteristics was performed ten different models of the generation control machines. After doing research of all these models, the results are organized according to the received advantage or losses. After that, the best and worst results discarded and the rest averaged.

In Fig. 3 shows the results obtained for models with the following specifications: Nx=10, Kx=2, Ny=20, Ky=2, Ns={20, 22,...30}.

Figure 3 – Example results of the research method, replacing the input alphabet of symbols (parameters Nx=10, Kx=2, Ny=20, Ky=2 basis - Altera Stratix III)

According to the results in Fig. 3, we can draw a conclusion about the effectiveness of this method in the base this PLD family Stratix III.

Picture 4 – ALTERA's products 5 frames. Last frame delay time = 2 sec. Other frames delay time = 1 sec. Animation size: 535px х 252px. File size: 28.5 Kbytes. Created using Adobe ImageReady.

Сonclusion

In the article proposed a method that allows to perform a study ways to optimize control circuits of machines, which includes two components: an algorithm for the study and the structure of the hardware needed for it.

Research algorithm is a sequence of steps that you can cover all the processes that are linked on the one hand, using the optimization method, and the other - to work in the basis of this PLD FPGA. The proposed algorithm is designed so that it can be implemented using parallel computing, which is an important factor.

The proposed structure of the article of the hardware includes a complete set of software tools necessary to perform the considered algorithm. In this case, the description of the structure includes a fairly detailed analysis of the actual CAD, which may be used. Also examines the processes machines of the complex with the use of specialized high-level languages??.

Besides, this article shows the approbation of the proposed method to a fairly well-known optimization methods This section covers a number of practical questions of methodology. Also proves the need for testing the proposed method in the article.

Subsequent directions of work are studies of various ways of optimizing control machines and study the feasibility of the proposed method with the use of parallel computing systems.

Literature

1. Barkalov A.A. Synthesis of control devices for programmable logic devices / Barkalov A.A. - Donetsk. : RVA DonNTU, 2002. - 262 sec. - ISBN 966-7559-62-9

2. Barkalov A.A. Syntez micro-programm avtomatov on zakaznыh prohrammyruemыh СБИС / AA Barkalov, LD Titarenko. - Donetsk. : Donetsk National Technical University, Donetsk National Technical University Technopark Unitech, 2009 - 336 sec. - ISBN 966-8248-21-X

3. Maxfield C. FPGAs: Instant Access / Clive Maxfield. – Oxford : Newnes, 2008. – 216 pp. – ISBN 978-0-7506-8974-8

4. Adamski M. Design of Digital Systems and Devices / Adamski M., Barkalov A., Wegrzyn M. – Berlin. : Springer-Verlag, 2011. – 366 pp. – ISBN 978-3-642-17544-2

5. Barkalov A.A. Synthesis of control machines using distributed and parallel systems / A. Barkalov I.J. Zeleneva, A.A. Hrytsenko// Radioelectronics, administration, informatics.. – 2010. – № 22. – С. 128-134. – ISSN 1607-3274

6. Smith D.J. HDL Chip Design: A Practical Guide for Designs, Synthesizing and Simulating ASICs and FPGAs Using VHDL or Verilog / Smith D.J. – Austin, USA : Doone Pubns, 1998. – 448 pp. – ISBN 978-0965193436

7. Chu P.P. RTL Hardware Design Using VHDL: Coding for Efficiency, Portability, and Scalability / Chu P.P. – New Jersey, USA : John Wiley and Sons, 2006. – 694 pp. – ISBN 978-0471720928

8. Mentor Graphics ModelSim User’s Manual [Electronic resource]. – Mode of access http://www.actel.com/documents/modelsim_ug.pdf. – Title from screen

9. Ashenden P.J. VHDL 2008: Just the New Stuff (Systems on Silicon) / P.J. Ashenden, J. Lewis – Burlington, USA : Morgan Kaufmann, 2008. – 256 pp. – ISBN 978-0123742490

10. Stratix III Device Handbook, Volume 1 [Electronic resource]. – Mode of access: http://www.altera.com/literature/hb/stx3/stx3_siii5v1.pdf. – Title from screen

11. Quartus II Handbook Version 10.1 Volume 1: Design and Synthesis [Electronic resource]. – Mode of access: http://www.altera.com/literature/hb/qts/quartusii_handbook.pdf. – Title from screen