Проект аппаратной реализации русского языка программирования | ПДМ. Приложение. 2013. № 6.

Проект аппаратной реализации русского языка программирования

Представлен проект процессора, реализующего ЛЯПАС-Т аппаратно, и предпроцессора, конвертирующего программы на ЛЯПАСе-Т в исполняемый код процессора. Сообщается о процессоре для подмножества ЛЯПАСа-Т без подпрограмм, операций над комплексами и длинных операндов, описанном на VHDL, протестированном средствами компьютерного моделирования и реализованном на ПЛИС с помощью системы автоматизированного проектирования.

Project of hardware implementation of Russian programming language.pdf In [1] a cryptographic extension LYaPAS-T of Russian programming language and a compiler for its implementation in software were presented. The objective of this paper is to present an information about the project of a processor implementing LYaPAS-T programs in hardware, and a preprocessor translating LYaPAS-T programs to executive code for the processor. 1. Parameters In LYaPAS-T implemented in hardware, the operand length, the largest number of a complex and the maximal quantity of subprograms in the hierarchical structure of a program are assumed to be bounded by natural n, m and k respectively. Hence, the quantities of different complexes (logical and symbol) and variables in a LYaPAS-T program executed by a processor do not exceed, respectively, mk and 27k. Nowadays the values like m = 64, k =128 are quite sufficient for the majority of practical algorithms. 2. Executive code For being executed by LYaPAS-T processor, a LYaPAS-T program should be preliminary represented by a sequence of instructions in the executive code (called LE-code) for the processor. Each instruction in it has fields containing information about operation code, operand type (constant or not, complex type — logical, symbol, static or dynamic if the operand is a complex or its element) and complex and variable addresses in the data memory. The field for complex address is used if the operation deals with the data of the form xv or L. In the first case the address of static complex к being, by definition, the address of the first element in к is explicitly written in this field, and the address of the variable v is written in the field for variable address. In the second case the field of the complex address contains the address of the complex L, and the field of the variable address remains empty (equals 0). In all other cases the field of the complex address is empty. The same is true for dynamic complex with the following exception: the field of its address contains not the complex address itself but the address where it is kept. 3. Architecture The architecture of the processor implementing LYaPAS-T in hardware consists of three units: Memory, Arithmetic Logical Unit (ALU) and Control Device (CD). 3.1. Memory The Memory is divided into two segments — IM (Instruction Memory) and DM (Data Memory) used to store, respectively, a sequence of instructions in LE-code representing a LYaPAS-T program P and data for it — unit constants Ii, complexes and variables for every subprogram in the hierarchical structure of the program P. Accordingly, for P with k subprograms, DM is conditionally divided into four sections: section I — for keeping vectors Ii, i = 0,1,... ,n — 1; sections C and G divided into k subsections Cj and Gj — for keeping respectively static and dynamic complexes in jth subprogram; and section W also divided into k subsections Wj — for keeping local variables a, b, ..., z, Z belonging to j th subprogram, and parameters and addresses of all complexes in jth subprogram. Sections I, C, W form so called static memory and section G — the dynamic memory of the processor. The data allocation in the first is made by the L-preprocessor (before the execution of the program P), in the second — by the processor itself (during the execution of P). Instructions in IM and data in DM are disposed compactly, with no gaps and in the order of section enumeration: I, C, W, G. The quantity of engaged elements in the subsection Gj is fixed as a value of an element in Wj. The address of this element is denoted aj. Its value is the least address of free element in Gj. Particularly, before the beginning of the processor work addresses aj for all j equal the number of elements in the static memory. Static complexes being created in jth subprogram are placed in Cj by L-preprocessor pointing for them parameters and addresses in Wj. The cardinality and the address in Wj of a dynamic complex are remained by L-preprocessor undetermined. A dynamic complex being created in j th subprogram with the cardinality equaled the value of a variable £ is placed in Gj as an array of a certain size with the address of the initial (first) element written in the element of Wj whose address is aj. It is done in the same way by the processor at the moment when it executes the given operation: parameters and the address of the complex are stored in Wj, the value of the element having address aj is increased by £. 3.2. ALU The unit ALU consists of three registers т, Z and O of the maximal possible length n called the Registers of Common Use (CURs) and destined for keeping, respectively, variables т, Z and operand being read from DM, and also of Operational Devices (OD) and a circuit CEA (Complex Element Address) for determining the address in DM of a complex element. Operational devices are used for executing arithmetic and logical operations in LYaPAS-T over operands and with the operation results represented in registers т, Z and O. For a complex element ки, its address in DM is computed by the circuit CEA as 9 = + 4u for logical к or as 9 = ^ + и for symbol к where ^ is the address in DM of the first element in к (also called the address of the complex к itself). 3.3. C o n t r o l d e v i c e The main functions of CD are the following: to receive and analyse information signals of other units, to select the next instruction from IM, to identify the operation code in it, to determine the operand address in DM and the next instruction address in IM, and to form and send control signals to other executive units. For carrying out these functions, CD contains Instruction Counter (IC), Instruction Register (IR) and two decoders — Address Decoder (ADec) and Operation Decoder (ODec). 4. Functioning algorithm 1. CD selects from IM an instruction at the address pointed in IC and writes it to IR. 2. ODec decodes the contents of the operation code field, ADec decodes the contents of type and operand (complex and/or variable) address fields in IR. 3. CD takes the information from ODec and ADec, generates the signals either for selecting from DM (possibly by means of the circuit CEA) an operand (constant, variable, logical complex or complex element) at the corresponding address and writing it into one of the CURs, or, if the operand is a constant given explicitly in the instruction, for writing it to the register O or to IC. 4. If the operation in the instruction is related to the functional type being a logical or arithmetic one, CD generates a signal initiating the corresponding OD. 5. Initiated OD fulfils the operation of the instruction in IR, and CD writes results into CURs according to the operation. 6. If the operation code is of the transition type, the value of the variable address field in the instruction in IR is written to IC; otherwise the state of IC is increased for selecting the next instruction from IM. 7. If the instruction in IR implies creation of a dynamic complex with a variable capacity £ in a jth subprogram, the cardinality 0 and capacity £ of this complex are written at addresses of its parameters in Wj, and the value at address aj is stored to Wj as the address of this complex in Gj and then it is increased by £. In this algorithm, the work of the control device CD is formally described by the finite automata model. 5. L-preprocessor For translating LYaPAS-T program into LE-code, a special compiler (called L-prepro-cessor) is used. It can be written in any programming language (for example in LYaPAS-T) and run on any computer provided with a proper compiler. The following is the sequence of main actions which L-preprocessor should make over a LYaPAS program P: 1) for every subprogram in the hierarchical structure of the program P, to prescribe to it a unique number from the series 1, 2, . . . , k; 2) for every j = 1, 2,... ,k, to give a unique address in Wj to every local variable and to every static local complex met in the jth subprogram of P; 3) for all i,j G {1, 2,... ,k} where i = j, for every call for j th subprogram from ith subprogram in P, the real parameters, pointed in the call, to substitute for the corresponding abstract (external) parameters in the text of j th subprogram; for every dynamic complex in j th subprogram, the address in Wj, where the address of this complex in Gj is written, to substitute for the name of this complex in the text of jth subprogram; and the sequence of instructions ai, ^ aj and the text of jth subprogram to substitute for the call itself in P; 4) every other operation in P to replace with the equivalent sequence of instructions in LE-code — either directly or through the intermediate replacement by the series of unary operations each having not more than one operand being different from т. 6. Alternative variant In the alternative variant of the processor, the segment IM saves the executive codes both of a head program and of all subprograms in its hierarchical structure. In this case, if the program P contains the call for a subprogram S, the L-preprocessor substitutes for this call in P an instruction A with the operation code of the transition to the address of the subprogram S executive code in IM, and, at the end of this code, it writes an instruction with the operation code of return back, that is, of transition to the address of an instruction in IM next to A. Besides, when executing the program P, the processor, before the execution of the instruction A, transfers the values of the input operands of the subprogram S, pointed in its call, at the corresponding addresses in DM, written in its executive code, and, before returning back to the instruction next to A, transfers the results of the subprogram code work at the addresses of the corresponding output operands, pointed in its call. The transferring the values of the program operands decreases the rate of the processor work in comparison with its basic variant, but essentially reduces the necessary size of the segment IM. At the same time, the absence of transferring between operands in the basic variant does not guarantee the value integrity for the input operands of a subprogram if it is not provided by the programmer. 7. Applications There are, at least, two possible applications of LYaPAS-T processor: as a cryptopro-cessor and as a control processor. In the first case the segment IM is filled in LE-code of a program in LYaPAS-T representing a cryptographic algorithm, and data for it (a plaintext, a ciphertext, a key and others) are written in the segment DM. In the second case IM and DM are used for storing, respectively, LE-code of a LYaPAS-T program destined for the secure control of a critically important object (cosmic, energetic, transport, etc.) and data for this program. 8. vLYaPAS subset processor Let L1 be the vLYaPAS subset that includes all operations at the first level of vLYaPAS and does not contain (calls for) subprograms and operations over complexes. For the first time, a processor architecture for L1 (also called L1-processor) was elaborated and implemented in VHDL in 2012 by S. E. Soldatov, a student of the Information Security and Cryptography Department of Tomsk State University. For preliminary verification, all individual units in L1-processor and its architecture on the whole were simulated by means of the program product ModelSim PE Student Edition 10.1d. Besides, the programmable logical integrated circuit of L1-processor was synthesized with the help of the computer-aided design system ISE WebPACK 9.2i by Xilinx. The maximal operating frequency of the circuit equals 50 MHz which is equivalent to the circuit delay of 20 ns. The size of the circuit is the third of the size of Nexys2 FPGA debugging board by Digilent Inc. This result shows that the implementation in hardware of the processor for LYaPAS-T is the quite real affair promising trustworthy means for effective performance of cryptographic and other combinatorial algorithms.

Ключевые слова

русский язык программирования, ЛЯПАС-Т, аппаратная реализация, предпроцессор, Russian programming language, LYaPAS-T, hardware implementation, LYaPAS-T preprocessor


Агибалов Геннадий ПетровичТомский государственный университетзаведующий кафедрой защиты информации и криптографии, доктор технических наук, профессорagibalov@isc.tsu.ru
Липский Валерий БорисовичТомский государственный университетдоцент кафедры защиты информации и криптографии, кандидат технических наукlipsky@mail.tsu.ru
Панкратова Ирина АнатольевнаТомский государственный университетдоцент кафедры защиты информации и криптографии, кандидат физико-математических наук, доцентpank@isc.tsu.ru
Всего: 3


 Проект аппаратной реализации русского языка программирования | ПДМ. Приложение. 2013. № 6.

Проект аппаратной реализации русского языка программирования | ПДМ. Приложение. 2013. № 6.