I.I. Levin1, A.A. Gulenok2, E.A. Semernikov3

1 Southern Federal University (Rostov-on-Don, Russia)

2,3 Supercomputers and Neurocomputers Research Center (Taganrog, Russia)

1 levin@sfedu.ru; 2 gulenok@superevm.ru; 3 semernikov@superevm.ru

А new method of parallelization of computations with recursive equations, more efficient in terms of equipment costs, the method of nested auto-substitutions, is proposed in this paper. The new method was considered using an example of parallelization of computations in digital recursive filters, which are described by difference equations, where the result depends on both the input and output data.

The speed of feeding input data to the input of a digital filter depends on the execution time of all computational operations specified by the difference equation, i.e. the next input sample can be fed and processed only after the processing of the previous sample has been completed. The reason is that the result of processing the next sample directly depends on the results of processing several previous samples. To feed data at a high rate, it is necessary to either use more powerful computing devices or provide parallelization of computations. Until now, the well-known method of sequential auto-substitutions has been used to parallelize computations described by recursive equations. This method allows correct introducing of pipeline registers into the feedback loops of a recursive filter and ensuring the use of high-performance computing nodes built on the pipeline principle. The method of sequential auto-substitutions has a linear function of growth of the number of operations depending on the level of parallelization of computations.

A new method, the method of nested auto-substitutions, which can be used to parallelize calculations described by recursive equations, is proposed by authors. The proposed method also allows correct introducing of pipeline registers into feedback loops, but has a logarithmic function of growth of the number of operations depending on the level of parallelization. The new method is more efficient than the well-known method of sequential auto-substitutions.

Its efficiency is proven in comparison with the well-known method of sequential auto-substitutions by example of parallelization in recursive filters of the first and second orders using the new method of nested auto-substitutions.

Numerical simulation of processing random digital sequences by pipelined filter using the method of nested auto-substitutions confirmed matching with the results of processing the same digital sequences by a non-pipelined second-order prototype filter. During the simulation, all calculations were performed in single-precision floating-point data format according to the IEEE-754 standard.

Levin I.I., Gulenok A.A., Semernikov E.A. The method of nested auto-substitutions for pipelining computations in recursive filters.
Radiotekhnika. 2025. V. 89. № 10. P. 17−28. DOI: https://doi.org/10.18127/j00338486-202510-02 (In Russian)

1. Rabiner L., Gould B. Teorija i primenenie cifrovoj obrabotki signalov. M.: Mir. 1987. 848 s. (in Russian).
2. Kougi P.M. Arhitektura konvejernyh JeVM: Per. s angl. M.: Radio i svjaz'. 1985 (in Russian).
3. Levin I.I., Semernikov E.A. Ustojchivost' konvejernyh rekursivnyh fil'trov. Vestnik Juzhnogo nauchnogo centra Rossijskoj akademii nauk. 2005. T. 1. Vyp. 2. S. 28-40 (in Russian).
4. Parhi K.K. Metody preobrazovanija algoritmov dlja parallel'nyh processorov. TIIJeR. 1987. T. 77. № 12. S. 96–114 (in Russian).
5. Levin I.I., Mihajlov D.V. Metod opredelenija ustojchivosti rekursivnogo adaptivnogo konvejerizovannogo fil'tra. Radiotehnika. 2020. T. 84. № 3(6) S. 5–11. DOI: 10.18127/j00338486-202003(06)-01 (in Russian).
6. Semernikov E.A, Semernikova E.E., Trunov I.L. Raspredelenie kornej cifrovyh konvejernyh fil'trov vtorogo porjadka. Izvestija JuFU. Tehnicheskie nauki. Tematicheskij vypusk «Bezopasnost' telekommunikacionnyh sistem». 2008. № 3(80). S. 28–33 (in Russian).
7. Dordopulo A.I., Levin I.I., Gudkov V.A., Gulenok A.A. Programmnyj kompleks vysokourovnevogo sinteza konfigura-cionnyh fajlov dlja mnogokristal'nyh rekonfiguriruemyh vychislitel'nyh system. Trudy mezhdunar. konf. «Parallel'nye vychislitel'nye tehnologii» (PAVT’2023). 2023. S. 133-142 (in Russian).