Compiling high-level language source code into machine code is an NP-hard problem. One of the problems arising during compilation, which has a huge solution space, is the presence of data-independent sequences of operations in the code. This paper considers an algorithm for finding an optimal uniform mixing of arbitrary instruction sequences, which can be represented as an acyclic connected graph. The purpose of such mixing is to increase the instruction-level parallelism. To this end, a sequence is described as a vector of random variables, each of which characterizes its demand for a specific resource. This representation allows for an approximate estimation of the expected value of delays arising during the execution of their mixture due to competition among several sequences for resources, without actually compiling the code. The algorithm operates on scalar data describing sequences and their combinations, instead of long instruction vectors. The search for the optimal partitioning of sequences into groups is performed in O(nk) time, where n is the number of sequences, and k is some limiting value of the number of sequences in the mixture, depending on the code, instruction latency, and the number of registers. For computing cores of modern processors, in most practical problems k does not exceed 4.
1. Aho A.V., Lam M.S., Sethi R., et al. Compilers: principles, techniques, and tools. 2nd ed. Moscow: OOO «I.D. Williams»; 2017. 1184 p. (In Russ.)
2. Logunov B.A., Kharin I.A. Methodology for Developing a High-speed Compiler Based on the Modified Loop Fusion Optimization Method: Computational Nanotechnology. 2023;10(1):103–111. (In Russ.) https://doi.org/10.33693/2313-223X-2023-10-1-103-111
3. Ziraksima M., Lotfi S., Izadkhah H. Loop Fusion Methods: A Critical Review. International Journal of Advanced Research in Computer and Communication Engineering. 2017;6(7):1–8.
4. Xu R.G., Van Zee F.G., van de Geijn R.A. GEMMFIP: Unifying GEMM in BLIS. arXiv. URL: https://doi.org/10.48550/arXiv.2302.08417 [Accessed 16th May 2026].
5. Buevich E.A. Impact of key representation size on hash tables performance in modern CPUs. Modeling, Optimization and Information Technology. 2025;13(3). (In Russ.). https://doi.org/10.26102/2310-6018/2025.50.3.014
6. Carroll S., Ling W.M. A Queuing Model for CPU Functional Unit and Issue Queue Configuration. arXiv. URL: https://doi.org/10.48550/arXiv.1807.08586 [Accessed 16th May 2026].
7. Vishnevsky V.M. Theoretical Foundations of Computer Network Design. Moscow: Tekhnosfera; 2003. 512 p.
8. Reiser M., Lavenberg S.S. Mean-Value Analysis of Closed Multichain Queuing Networks. Journal of the ACM. 1980;27(2):313–322. https://doi.org/10.1145/322186.322195
9. Reiser M. A Queueing Network Analysis of Computer Communication Networks with Window Flow Control. IEEE Transactions on Communications. 1979;27(8):1199–1209. https://doi.org/10.1109/TCOM.1979.1094531
10. Suri R. A Concept of Monotonicity and Its Characterization for Closed Queueing Networks. Operations Research. 1985;33(3):469–703. https://doi.org/10.1287/opre.33.3.606
Buevich Evgeniy Andreevich
Moscow State Technological University "STANKIN"
Moscow, Russian Federation
