Спосіб розробки ізоефективної гетерогенної системи на основі машинного навчання для задачі дискретного перетворення Фур’є

СПОСІБ РОЗРОБКИ ІЗОЕФЕКТИВНОЇ ГЕТЕРОГЕННОЇ СИСТЕМИ НА ОСНОВІ МАШИННОГО НАВЧАННЯ ДЛЯ ЗАДАЧІ ДИСКРЕТНОГО ПЕРЕТВОРЕННЯ ФУР’Є

METHOD OF DEVELOPMENT OF ISOEFFICIENT HETEROGENEOUS SYSTEM USING MACHINE LEARNING FOR THE PROBLEM OF DISCRETE TRANSFORMATION OF FOURIER

Сторінки: 19-24. Номер: №3, 2021 (297)
Автори:
В.В. РУСІНОВ, О.В. ЧЕРЕВАТЕНКО, Л.М. ПУСТОВІТ, О.М. ПУСТОВІТ
Національний технічний університет України “Київський політехнічний інститут імені Ігоря Сікорського”
V.V. Rusinov, O.V. Cherevatenko, L.M. Pustovit, O.M. Pustovit
National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”
DOI: https://www.doi.org/10.31891/2307-5732-2021-297-3-19-24
Надійшла / Paper received :  13.05.2021 р
Надрукована / Paper Printed : 30.06.2021 р

Анотація мовою оригіналу

В даній роботі розглянуто питання ізоефективності систем MPP та гетерогенних систем CPU-GPU на задачі дискретного перетворення Фур’є. Розробка паралельних додатків у якості своєї цілі може мати не лише скорочення часу виконання, але і забезпечення можливостей вирішення проблем більшої розмірності. Особливість паралелізації алгоритму включає ефективне використання апаратних засобів при збільшенні розмірності задачі є важливою характеристикою паралельних обчислень.
Ключові слова:  ізоефективність, гетерогенні обчислення, перетворення Фур’є.

Розширена анотація англійською мовою

Abstract — In this paper, the isoefficiency of MPP systems and heterogeneous CPU-GPU systems on the problem of discrete Fourier transform is considered.  The development of parallel applications as its goal can not only reduce execution time, but also provide opportunities to solve problems of a larger dimension. The peculiarity of algorithm parallelization includes the efficient use of hardware while increasing the dimension of the problem is an important characteristic of parallel computing. However, currently heterogeneous systems have not been researched extensively to determine isoefficiency characteristics and build application-specific systems around said method, although there are articles that show potential using isoefficiency to design the system and using heterogeneous approach to accelerate performance of different tasks. Discrete Fourier Transform algorithm lets build systems that discretize analogue and digital signals and it can serve as a benchmark to test different systems. Algorithms suited for MPP systems can use analytical approach to find out issoefficiency function and to determine how scaling the system or changing the size of the task will change its performance metrics. One of the most popular approaches to linking up processing units in MPP systems is using hypercube topology. MPP system that is connected using this topology will be analyzed. CPU-GPU heterogeneous system will be analyzed using an approach based on polynomial regression. Due to the nature of heterogeneous systems, analytic approach used in MPP system is impossible. Predictive model based on polynomial regression will use modelling results from using CPU and GPU separately to estimate how much time it will take for heterogeneous system to finish the task. To ensure accuracy of the experiment, several systems will be used to model the task. Using this approach, resulting issoefficient heterogeneous system will be analyzed using performance metrics such as time. From the resulting graphs, we can see the isoefficient properties across all of the heterogeneous systems.
Keywords: isoefficiency, heterogeneous calculations, Fourier transformation

References

1. Hwang K. Scalability and programmability of massively parallel processor. Parallel Processing: CONPAR 94—VAPP VI. Springer, Berlin, Heidelberg, 1994. P. 1–4.
2. Grama A. Y., Gupta A., Kumar V. Isoefficiency: Measuring the scalability of parallel algorithms and architectures. IEEE Parallel & Distributed Technology: Systems & Applications. 1993. Vol. 1. Issue 3. P. 12–21.
3. Drozdowski M., Singh G., Marszalkowski J. M. Isoefficiency Maps for Divisible Computations in Hierarchical Memory Systems. PPAM (1). 2019. P. 224–234.
4. Ostertagová E. Modelling using polynomial regression. Procedia Engineering. 2012. Vol. 48. P. 500–506.
5. Bracewell R. N., Bracewell R. N. The Fourier transform and its applications. New York: McGraw-Hill, 1986. Vol. 31999. P. 267–272.
6. Harish P., Narayanan P. J. Accelerating large graph algorithms on the GPU using CUDA. International conference on high-performance computing. Springer, Berlin, Heidelberg, 2007. P. 197–208.
7. Hey T., Scott C., Surridge M. Simulation and modelling applications on mpp systems. Massively Parallel Processing Applications and Development. Elsevier, 1994. P. 15–21.
8. Yongchang J. et al. A scalability metric for algorithm-machine on NOW and MPP. Proceedings Fourth International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region. IEEE, 2000. Vol. 1. P. 405–407.