Boretskyy T. Development and implementation of methods for elementary functions calculation on the basis of software and hardware

Українська версія

Thesis for the degree of Candidate of Sciences (CSc)

State registration number

0419U002104

Applicant for

Specialization

  • 05.13.05 - Комп'ютерні системи та компоненти

29-03-2019

Specialized Academic Board

Д 35.052.08

Lviv Polytechnic National University

Essay

The dissertation is devoted to the improvement of methods for calculating elementary functions, which today are used mainly in semiconductor equipment. The main tasks in the study were to increase the speed of algorithms by optimizing the structures used to achieve lower latency (and, consequently, the number of cycles), as well as improving the resource-intensity indices when implementing algorithms using hardware. The proposed methods were implemented at the software level for processor architectures of different complexity levels, and with the help of programmable logic integrated circuits, which allows the porting of the developed methods to the system on a chip. The advantages and weaknesses of the methods that appear or may arise in one or another configuration of the final equipment or in the final product are shown. The ways in which it is possible to accelerate or simplify existing computational methods, increase their speed, or reduce latency and resource intensity is represented. The process of deducing dependencies and formulas is described. The block diagrams of algorithms, results distribution gistographs are presented. New approaches and ways of calculation of functions are offered, their logic diagrams are represented and the comparison of the accuracy of calculations is carried out depending on the complexity of the implementation of the chosen method. Considerable attention is paid to the CORDIC method by which one it is possible to compute functions such as sinus, cosine, tangent, exponent, square root, hyperbolic and inverse trigonometric functions. Taking into account that the great interest in the presented functions is the calculation of sinus and cosine in the practical implementation of methods depending on the context of the problem, the functions used to demonstrate the work are done. When we using classical methods, the accuracy of calculations depends on the number of operands and the number of iterations performed. In small quantities of iterations, all input and output values can be set in the form of a table placed in memory. Given that, for the vast majority of devices, some memory, though insignificant, is available, can be used to accelerate the CORDIC method. Moreover, the effect will be noticeable if the volume of allocated memory is hundreds or even dozens of bytes (operating or flash memory in the case of microcontroller). The author proposes a new method for the conversion of the input argument into an alternate, which allows flexible change of the memory for the look-up table and the number of iterations. The hardware implementation of the considered methods on the FPGA platforms is carried out. Analyzed the available hardware base for their implementation from Intel (Altera) and Xilinx manufacturers. The features of selected FPGAs, the specifics of the hardware implementation of algorithms, in particular, the influence of architecture and integrated FPGA blocks on the functionality of the implemented methods are considered. The schemes of the offered algorithms on the level of register gears and the low level at the stage of their placement (fitting) in the crystal are given. The methods of optimization of algorithms in terms of use a specific platform and depending on the version and settings of the development environment are considered. The results of impetence of methods directly in the FPGA with the estimation of their initial characteristics, such as the maximum clock frequency, resource intensity and energy consumption are given. The verification of correctness of algorithms functioning is carried out both by means of simulation modeling, and after measurement of physical indicators and data obtained during the testing of the programmed FPGA. Considerable attention is paid to the modified method of alternating transcoding - unsigned transcoding, in which all arguments take only positive values, allow simplification of the implementation of the algorithm, and necessary hardware resources for this, while preserving the advantages of the transcoding approach. The main parameter demonstrating the advantages of the proposed algorithm is the latency, which is inversely proportional to the clock frequency, and depends on the number of steps required to calculate the function. The number of cycles, in turn, may change due to the change in the size of the allocated memory. Comparison of the results of the undocumented conversion method for the Xilinx platform was carried out with the proposed implementation by the CORIDC IP library. For the Intel prototype, a comparison was made with the built-in megafunction.

Files

Similar theses