Article

Article title ABOUT THE POSSIBILITY OF USING THE FIRST ORDER DELTA-TRANSFORMATIONS FOR CONSTRUCTION SPECIAL-PURPOSE COMPUTER
Authors L.V. Pirskaya
Section SECTION II. COMPUTER ENGINEERING AND COMPUTER SCIENCE
Month, Year 02, 2015 @en
Index UDC 621.376.57
DOI
Abstract The aim of this paper is explored the possibility of using the algorithm of parallel solving a linear algebraic equations system based on the first order delta-transformations with variable quantum adapted for the effective implementation of special-purpose computer and represent the prerequisites for achieving high-level (in performance and hardware resources) characteristic. In this paper it is considered a block diagram of the device that implements engineered algorithm. It is obtained FPGA-oriented estimates from the quantity of hardware and performance. These estimates show that the quantity of hardware may be reduced in ~2 times using the algorithm based on the first order delta-transformations with variable quantum, and increase the performance, when operating with a 32-bit data, in ~2,5 times versus using a simple iteration method. With an increase in the order of n linear algebraic equation increases the comparative effectiveness of the use of hardware resources and the performance of the proposed algorithm. In this paper it is obtained the integrated comparative estimate, including the hardware and performance estimates. It shows the possibility of increasing efficiency using the engineered algorithm, when operating with a 32-bit data, in ~5times as compared to use of the simple iteration method and this estimate with the order of n increases rapidly.

Download PDF

Keywords Iterative methods; systems of linear algebraic equations; delta transformation of the first order; special-purpose computer; FPGA.
References 1. Maksfild K. Proektirovanie na PLIS [FPGA design]. Moscow: Dodeka-XXI, 2007, 408 p.
2. Korchinskiy A.P., Burtseva N.V. Primenenie programmiruemykh logicheskikh integral'nykh skhem v elektronnoy apparature [The use of a programmable logic integrated circuits in electronic equipment], Elektronika і sistemy upravlіnnya [Electronics and control systems], 2009, No. 4 (22), pp. 5-13.
3. Yang Н., Ziavras S.G. FPGA-based vector processor for algebraic equation solvers, IEEE International SOC Conference, 2005, pp. 115-116.
4. Zhang W., Betz V., Rose J. Portable and Scalable FPGA-Based Acceleration of a Direct Linear System Solver, ACM Transactions on Reconfigurable Technology and Systems (TRETS), 2012, Vol. 5, No. 1, Article 6.
5. Tarasov I. PLIS Xilinx i tsifrovaya obrabotka signalov. Osobennosti, preimushchestva, perspektivy [The Xilinx FPGA and digital signal processing. Features, benefits, prospects], Elektronika NTB [Electronika: Science, Technology, Business], 2011, No. 3, pp. 70-74.
6. Malinovskiy B.N., Boyun V.P., Kozlov L.G. Algoritmy resheniya sistem lineynykh algebraicheskikh uravneniy, orientirovannye na strukturnuyu realizatsiyu [Algorithms for solving systems of linear algebraic equations-oriented structural implementation], Upravlyayushchie sistemy i mashiny [Control systems and machines], 1977, No. 5, pp. 79-84.
7. Tret'yakov S.I. Algoritmy raboty spetsializirovannykh protsessorov dlya resheniya sistem uravneniy [Algorithms specialized processors for solving systems of equations], Kibernetika [Cybernetics], 1978, No. 5, pp. 34-36.
8. Baykov V.D., Sergeev M.B. Strukturno-orientirovannyy algoritm resheniya sistem lineynykh algebraicheskikh uravneniy [Structurally-oriented algorithm for solving systems of linear algebraic equations], Upravlyayushchie sistemy i mashiny [Control systems and machines],
1986, No. 2, pp. 81-84.
9. Gomozov O.V. Ladyzhenskiy Yu.V. Inkrementnye algoritmy resheniya sistem lineynykh algebraicheskikh uravneniy i arkhitektura mul'tiprotsessorov na programmiruemoy logike [Incremental algorithms for solving systems of linear algebraic equations and the architecture of multiprocessors on programmable logic], Nauchnye trudy DonNTU. Seriya «Informatika, kibernetika i vychislitel'naya tekhnika» [Scientific works of Donetsk national technical University. Series "Informatics, Cybernetics and computer engineering"], 2010, No. 12 (165), pp. 34-40.
10. Kravchenko P.P. Inkrementnye metody resheniya sistem lineynykh algebraicheskikh uravneniy [Incremental methods for solving systems of linear algebraic equations] Mnogoprotsessornye vychislitel'nye struktury [Multiprocessor computing patterns], 1983, No. 5 (XIV), pp. 30-32.
11. Kravchenko P.P. Solving systems of algebraic and differential equations by second-order difference modulation, Cybernetics, 1989, Vol. 25 (2), pp. 218-229.
12. Pirskaya L.V. The iterative algorithm for solving systems of linear algebraic equations without the multibit multiplication operation // International Conference «Engineering & Telecommunication En&T 2014». Book of Abstracts. – Dolgoprudny: MIPT, 2014. – P. 210-212.
13. Kravchenko P.P., Pirskaya L.V. Iteratsionnyy metod resheniya sistem lineynykh algebraicheskikh uravneniy, isklyuchayushchiy operatsiyu mnogorazryadnogo umnozheniya [The iterative method for solving systems of linear algebraic equations, exclusive the multi-bit multiplication operation], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2014, No. 7 (156), pp. 214-224.
14. Kravchenko P.P., Pirskaya L.V. The method of organizing the iterative process of the system of the linear algebraic equations solution excluding the multidigit multiplication operation, Biosciences Biotechnology Research Asia, 2014, Vol. 11, No. 3, pp. 1831-1839.
15. Kravchenko P.P. Osnovy teorii optimizirovannykh del'ta-preobrazovaniy vtorogo poryadka. Tsifrovoe upravlenie, szhatie, parallel'naya obrabotka informatsii: Monografiya [Fundamentals of the theory of optimized Delta-transformations of the second order. Digital control, compression, parallel information processing: Monograph]. Taganrog: Izd-vo TTI YuFU, 2008, 192 p.
16. Bakhvalov N.S., Zhidkov N.P., Kobel'kov G.M. Chislennye metody [Numerical methods], Moscow: BINOM. Laboratoriya znaniy, 2006, 632 p.
17. Greenbaum A. Iterative Methods for Solving Linear Systems. SIAM, 1997, 220 p.
18. V С. Iterative solution methods. The Netherlands: Delft Institute of Applied Mathematics, Delft, 2012, 118 p.
19. Steshenko V. Zanyatie 6. Realizatsiya vychislitel'nykh ustroystv na PLIS [Implementation of computing devices on the FPGA], Komponenty i tekhnologii [Components & Technologies], 2000, No. 8, pp. 88-91.
20. Maksimov N.V., Partyka T.L., Popov I.I. Arkhitektura EVM i vychislitel'nykh sistem: uchebnik [Computer architecture and computer systems: a Tutorial], 3 rd ed. Moscow: Forum, 2010, 512 p.
21. Tanenbaum E., Ostin T. Arkhitektura komp'yutera [The architecture of the computer], 6th ed. St. Petersburg: Piter, 2013, 816 p.

Comments are closed.