Phase optimization of single-threaded execution of independent program sequences

This paper considers one aspect of the joint execution of several data-independent program sequences in a single thread, achieved by interleaving their instructions in the source code. This problem is NP-hard. The paper considers a method for finding the optimal sequence start shift using the fast Fourier transform for various problem formulations (number of sequences). Instruction chains are represented as time series of resource (execution ports) and core register utilization. When working with registers, cross-correlation series are constructed using the Fourier transform of dimension K, where K is the number of series. When working with ports, each series is divided into several channels corresponding to different port loads. A Fourier transform of dimension K-1 is performed for each channel, and the results are then summed with the specified weights. It is shown that for K=3, in both cases, the frequency representation has lower computational complexity than brute force. The method is also suitable for finding the optimal sequence cut point for pipelined execution within a single thread. The algorithm successfully finds optimal matching points for a set of test sequences with high variance of local average usage intensities of individual resources and combinations of resources.

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