«Автоматизация и информатизация ТЭК»

Реализация дискретного преобразования Хартли на многоядерных ускорителях

УДК: 681.3.05
DOI: 10.33285/2782-604X-2023-7(600)-35-42

Авторы:

¹ РГУ нефти и газа (НИУ) имени И.М. Губкина, Москва, Россия

Ключевые слова: многомерное дискретное преобразование Хартли, быстрое преобразование Хартли, высокопроизводительные вычисления, OpenMP, CUDA, обработка изображений, GPGPU

Аннотация:

В статье представлены два подхода к параллельной реализации многомерного дискретного преобразования Хартли (ND-DHT). В первом случае рассматривается использование быстрого преобразования Хартли (FDHT), во втором – его матричное представление. Описан широкий спектр задач, для которого имеет смысл использовать предложенные методы. Рассмотрены преимущества и недостатки FDHT относительно алгоритма быстрого преобразования Фурье (Real-FFT). Приведены результаты тестирования параллельных алгоритмов (с использованием Fortran/C+OpenMP для CPU и Fortran/С+CUDA для GPGPU) на наборах данных разных размерностей: для изображений с разрешением от 128×128 до 4096×4096.

Список литературы:

1. Tahmasebi P., Sahimi M., Caers J. MS-CCSIM: Accelerating pattern-based geostatistical simulation of categorical variables using a multi-scale search in Fourier space // Computers & Geosciences. – 2014. – Vol. 67. – P. 75–88. – DOI: 10.1016/j.cageo.2014.03.009
2. Fast two-dimensional Hartley transform / R.N. Bracewell, O. Buneman, Hong Hao, J. Villasenor // Proc. of the IEEE. – 1986. – Vol. 74, Issue 9. – P. 1282–1283. – DOI: 10.1109/PROC.1986.13619
3. Real-valued fast Fourier transform algorithms / H.V. Sorensen, D.L. Jones, M. Heideman, C. Burrus // IEEE Transactions on acoustics, speech, and signal processing. – 1987. – Vol. 35, Issue 6. – P. 849–863. – DOI: 10.1109/TASSP.1987.1165220
4. Duhamel P., Vetterli M. Improved Fourier and Hartley transform algorithms: Application to cyclic convolution of real data // IEEE Transactions on Acoustics, Speech, and Signal Processing. – 1987. – Vol. 35, Issue 6. – P. 818–824. – DOI: 10.1109/TASSP.1987.1165218
5. Popovic M.V., Sevic D.M. A New Look at the Comparison of the Fast Hartley and Fourier Transforms // IEEE Transactions on Signal Processing. – 1994. – Vol. 42, Issue 8. – P. 2178–2182. – DOI: 10.1109/78.301854
6. The EuRoC micro aerial vehicle datasets / M. Burri, J. Nikolic, P. Gohl [et al.] // The Int. J. of Robotics Research. – 2016. – Vol. 35, Issue 10. – P. 1157–1163. – DOI: 10.1177/0278364915620033
7. Hong Hao, Bracewell R.N. A three-dimensional DFT algorithm using the fast Hartley transform // Proc. of the IEEE. – 1987. – Vol. 75, Issue 2. – P. 264–266. – DOI: 10.1109/PROC.1987.13729
8. Rader C.M. Discrete Fourier transforms when the number of data samples is prime // Proc. of the IEEE. – 1968. – Vol. 56, Issue 6. – P. 1107–1108. – DOI: 10.1109/PROC.1968.6477
9. Foster I.T., Worley P.H. Parallel Algorithms for the Spectral Transform Method // SIAM J. on Scientific Computing. – 1997. – Vol. 18, Issue 3. – P. 806–837. – DOI: 10.1137/S1064827594266891
10. Arsenyev-Obraztsov S.S., Volkov E.A., Plusch G.O. Proposals on 3D parallel edge-preserving filtration for x-ray tomographic digital images of porous medium core plugs // IOP Conf. Series: Materials Science and Engineering. – 2019. – Vol. 700, Issue 1. – P. 012053. – DOI: 10.1088/1757-899X/700/1/012053
11. Takahashi D. Fast Fourier Transform Algorithms for Parallel Computers. – Springer Singapore, 2019. – IX, 114 p. – (High-Performance Computing Series. – Vol. 2). – DOI: 10.1007/978-981-13-9965-7
12. Технология программирования CUDA: учеб. пособие / Д.Н. Тумаков, Д.Е. Чикрин, А.А. Егорчев, С.В. Голоусов. – Казань: Казанский гос. ун-т, 2017. – 112 с.