Компиляция исходного кода на языке высокого уровня в машинный код является NP сложной задачей. Одной из проблем, возникающих в процессе компиляции и имеющих огромное пространство решений, является наличие в коде несвязанных по данным последовательностей операций. В данной работе рассматривается алгоритм поиска оптимального равномерного смешивания произвольных последовательностей инструкций, которые можно представить в виде ациклического связного графа. Целью подобного смешивания является увеличение параллелизма уровня инструкций. Для этого последовательность описывается как вектор случайных величин, каждая из которых характеризует его потребность в определенном ресурсе. Подобное представление позволяет приблизительно оценить математическое ожидание задержек, возникающих при исполнении их смеси, вследствие конкуренции нескольких последовательностей за ресурсы, без выполнения собственно компиляции. Алгоритм оперирует скалярными данными, описывающими последовательности и их комбинации, вместо длинных векторов инструкций. Поиск оптимального разбиения последовательностей на группы выполняется за время O(nk), где n – число последовательностей, а k – некоторое предельное значение числа последовательностей в смеси, зависящее от кода, латентности инструкций и числа регистров. Для вычислительных ядер современных процессоров в большинстве практических задач k не превышает 4.
1. Ахо А.В., Лам М.С., Сети Р. и др. Компиляторы: принципы, технологии и инструментарий. 2-е изд. Москва: ООО «И.Д. Вильямс»; 2017. 1184 с.
2. Логунов Б.А., Харин И.А. Методика разработки скоростного компилятора на основе модифицированного метода оптимизации loop fusion: модели и инструменты его реализации. Computational Nanotechnology. 2023;10(1):103–111. 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. Буевич Е.А. Влияние размера образа ключа на производительность хеш-таблиц в современных архитектурах. Моделирование, оптимизация и информационные технологии. 2025;13(3). 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. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. Москва: Техносфера; 2003. 512 с.
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
Буевич Евгений Андреевич
Московский государственный технологический университет “СТАНКИН”
Москва, Российская Федерация
