В работе рассматривается один из аспектов совместного выполнения в одном потоке нескольких независимых друг от друга по данным программных последовательностей, что достигается чередованием их инструкций в исходном коде. Эта задача является NP-сложной. В работе рассматривается метод поиска оптимального сдвига старта последовательностей через быстрое преобразование Фурье для различных вариантов постановки задачи (числа последовательностей). Цепочки инструкций представляются в виде временных рядов использования ресурсов (исполнительных портов) и регистров вычислительного ядра. При работе с регистрами ряды взаимной корреляции строятся через преобразование Фурье размерностью K, где K – число рядов. При работе с портами каждый ряд разделяется на несколько каналов, соответствующих различной нагрузке порта, для каждого канала выполняется преобразование Фурье размерностью K-1, далее результаты суммируются с заданными весами. Показано, что при K=3 в обоих случаях частотное представление имеет меньшую вычислительную сложность, чем прямой перебор. Метод также подходит для поиска оптимальной точки разреза последовательности с целью конвейерного исполнения в рамках одного потока. Алгоритм успешно находит точки оптимального совмещения для набора тестовых последовательностей с высокой дисперсией локальных средних интенсивностей использования индивидуального ресурса и сочетаний ресурсов.
1. Ferrante J., Ottenstein K.J., Warren J.D. The Program Dependence Graph and Its Use in Optimization. ACM Transactions on Programming Languages and Systems (TOPLAS). 1987;9(3):319–349.
2. Llosa J., González A., Ayguadé E., et al. Swing Modulo Scheduling: A Lifetime-Sensitive Approach. In: Proceedings of the 1996 Conference on Parallel Architectures and Compilation Technique, 20-23 October 1996, Boston, MA, USA. IEEE; 1996. P. 80–91. https://doi.org/10.1109/PACT.1996.554030
3. Zhang Z., Liu B. SDC-based modulo scheduling for pipeline synthesis. In: Proceedings of the 2013 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 18–21 November 2013, San Jose, CA, USA. IEEE; 2013. P. 211–218. https://doi.org/10.1109/ICCAD.2013.6691121
4. Lattner C., Amini M., Bondhugula U., et al. MLIR: Scaling Compiler Infrastructure for Domain Specific Computation. In: Proceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization (CGO), 27 February – 3 March 2021, Seoul, Korea (South). IEEE; 2021. P. 2–14. https://doi.org/10.1109/CGO51591.2021.9370308
5. Gupta R., Bodík R. Register Pressure Sensitive Redundancy Elimination. In: Proceedings of the 8th International Conference, CC'99, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS'99, March 22–28 1999, Amsterdam, Netherlands. Berlin, Heidelberg: Springer; 1999. P. 107–121. https://doi.org/10.1007/978-3-540-49051-7_8
6. Yang Y., Xiang P., Kong J., et al. A GPGPU compiler for memory optimization and parallelism management. In: Proceedings of the 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 5–10 June 2010, Toronto, Ontario, Canada. New York: Association for Computing Machinery; 2010. P. 86–97. https://doi.org/10.1145/1806596.1806606
7. Cui Q., Rong V., Chen D., et al. Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects. ACM Transactions on Graphics. 2023;42(4):1–14. https://doi.org/10.1145/3592126
8. Sorensen H.V., Burrus C.S. Efficient computation of the DFT with only a subset of input or output points. IEEE Transactions on Signal Processing. 1993;41(3):1184–1200. https://doi.org/10.1109/78.205723
9. Perreault-Lafleur C., Carvalho M., Desaulniers G. A stochastic integer programming approach to reserve staff scheduling with preferences. International Transactions in Operational Research. 2025;32(1):289–313. https://doi.org/10.1111/itor.13298
10. Cooley J.W., Tukey J.W. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation. 1965;19(90):297–301. https://doi.org/10.2307/2003354
Буевич Евгений Андреевич
Московский государственный технологический университет “СТАНКИН”
Москва, Российская Федерация
